ITS235 - Chapter 5: CPU Scheduling

CPU-I/O Burst Cycle

process execution consists of a cycle of CPU execution and I/O wait

short-term scheduler

selects from among the processes in ready queue, and allocates the CPU to one of them

nonpreemptive scheduling

once a process starts using the CPU, it runs until it finishes or moves to a waiting state

preemptive schedulingdis

OS can interrupt and pause a currently running process before it finishes, moving it back to the ready queue

dispatcher module

gives control of the CPU to the process selected by the short-term scheduler

dispatch latency

time it takes for the dispatcher to stop one process and start another running

CPU utilization

keep the CPU as busy as possible

throughput

number of processes that complete their execution per time unit

turnaround time

amount of time to execute a particular process

waiting time

amount of time a process has been waiting in the ready queue

response time

amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)

convoy effect

short process behind long process

shortest-job-first

associates with each process the length of its next CPU burst - use these lengths to schedule the process with the shortest time

priority scheduling

a priority number is associated with each process - the CPU is allocated to the process with the highest priority (smallest integer = highest priority)

starvation

problem = low priority processes may never execute

aging

solution = as time progresses increase the priority of the process

round robin

each process gets a small unit of CPU time - after this time has elapsed, the process is preempted and added to the end of the ready queue

multilevel queue

ready queue is partitioned into separate queues

foreground

(interactive)

background

(batch)

multilevel feedback queue

a process can move between the various queues; aging can be implemented this way

thread scheduling

process contention scope

scheduling competition is within the process

system contention scope

scheduling competition is among all threads in the system

asymmetric multiprocessing

only one processor accesses the system data structures, alleviating the need for data sharing

symmetric multiprocessing

each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes

processor affinity

process has affinity for processor on which it is currently running

load balancing

attempts to keep the workload evenly distributed

push migration

periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs

pull migration

idle processors pulls waiting task from busy processor

soft real-time systems

no guarantee as to when critical real-time process will be scheduled

hard real-time systems

task must be serviced by its deadline

interrupt latency

time from arrival of interrupt to start of routine that services interrupt

target latency

interval of time during which task should run at least once

deterministic modeling

takes a particular predetermined workload and defines the performance of each algorithm for that workload

queueing models

describes the arrival of processes, and CPU and I/O bursts probabilistically

deterministic evaluation

for each algorithm, calculate minimum average waiting time

Little’s law

in steady state, processes leaving queue must equal processes arriving

simulations

programmed model of computer system