Scheduling
Scheduling management
processes are managed through the use of multiple queues (or lists) of PCB's; the word queue (in an OS context) has a loose interpretation
the job queue contains all jobs submitted to the system, but not yet in main memory
the ready queue contains all jobs in main memory ready to execute
each I/O device has a queue of jobs waiting for various I/O operations
a process is dispatched from the ready queue to the CPU; its processing may cause it to be put on a device queue
all of these events are signaled by interrupts
job scheduling versus process scheduling (or CPU scheduling)
here we are primarily discussing process scheduling
CPU and I/O Bursts
a process cycles between CPU processing and I/O activity
a process generally has many short CPU bursts or a few long CPU bursts
I/O bound processes have many short CPU bursts
CPU bound processes have few long CPU bursts
this can effect the choice of CPU scheduling algorithm used in an OS
Preemptive scheduling
CPU scheduling decisions may take place when a process
switches from the running to waiting state
switches from the running to ready state
switches from the waiting to ready state
terminates
scheduling under conditions 1 and 4 is called non-preemptive (context switch is caused by the running program)
scheduling under conditions 2 and 3 is preemptive (context switch caused by external reasons)
Scheduling Criteria
Each scheduling algorithm favors particular criteria:
CPU utilization (maximize)
throughput: number of processes which complete execution per time unit (maximize)
turnaround time (TA): total amount of time to execute a particular process (minimize)
waiting time: amount of time a process has been waiting in the ready queue (minimize)
response time: amount of time it takes from when a request is submitted to when the response is produced (minimize); does not include the time for a response to be output
Some work is being done to minimize response time variance, to promote predictability.
CPU Scheduling Algorithms
First-Come, First Serve (FCFS or FIFO) (non-preemptive)
Priority (e.g., Shortest Job First (SJF; non-preemptive)
or Shortest Remaining Time First (SRTF; preemptive))
Round Robin (preemptive)
Multi-level Queue
Multi-level Feedback Queue
First-Come, First Serve
non-preemptive scheduling management
ready queue is managed as a FIFO queue
example: 3 jobs arrive at time 0 in the following order (batch processing):
Gantt chart:
(regenerated from [OSC] p. 189)
average waiting time: (0+24+27)/3 = 17
average turnaround time: (24+27+30) = 27
consider arrival order: 2, 3, 1
Gantt chart:
(regenerated from [OSC] p. 189)
average waiting time: (0+3+6)/3 = 3
average turnaround time: (3+6+30) = 13
another example:
Gantt chart:
average waiting time: (0+11+14)/3 = 8.33
average turnaround time: (12+17+23) = 52/3 = 17.33
another example:
Gantt chart:
(regenerated from [OSC] p. 214)
average waiting time: (0+10+39+42+49)/5 = 28
average turnaround time: (10+39+42+49+61)/5 = 40.2
Priority Scheduling
associate a priority with each process, allocate the CPU to the process with the highest priority
any 2 processes with the same priority are handled FCFS
SJF is a version of priority scheduling where the priority is defined using the predicted CPU burst length
priorities are usually numeric over a range
high numbers may indicate low priority (system dependent)
internal (process-based) priorities: time limits, memory requirements, resources needed, burst ratio
external (often political) priorities: importance, source (e.g., faculty, student)
priority scheduling can be non-preemptive or preemptive
problem: starvation --- low priority processes may never execute because they are waiting indefinitely for the CPU
a solution: aging --- increase the priority of a process as time progresses
nice in UNIX executes a utility with an altered scheduling priority
renice in UNIX alters the priority of running processes
Shortest Job First (SJF)
associate with each process the length of its next CPU burst
schedule the process with the shortest time
two schemes
non-preemptive: once scheduled, a process continues until the end of its CPU burst
preemptive: preempt if a new process arrives with a CPU burst of less length than the remaining time of the currently executing process; known as theShortest Remaining Time First (SRTF) algorithm
SJF is provably optimal; it yields a minimum average waiting time for any set of processes
however, we cannot always predict the future (i.e., we do not know the next burst length)
we can only estimate its length
an estimate can be formed by using the length of its previous CPU bursts:
Tn = actual length of the nth CPU burst
ψn = predicted value of nth CPU burst
0 <= w <= 1
ψn+1 = w * Tn + (1-w) * ψn
SJF (non-preemptive) examples
Gantt chart:
(regenerated from [OSC] p. 190)
average waiting time: (3+16+9+0)/4 = 7
average turnaround time: (9+24+16+3)/4 = 13
another example:
Gantt chart:
average waiting time: (0+6+3+7)/4 = 4
average turnaround time: (7+4+10+11)/4 = 8
another example:
Gantt chart:
(regenerated from [OSC] p. 214)
average waiting time: (10+32+0+3+20)/5 = 13
average turnaround time: (10+39+42+49+61)/5 = 25.2
SRTF (preemptive) examples
Gantt chart:
(regenerated from [OSC] p. 192)
average waiting time: (9+0+15+2)/4 = 6.5
average turnaround time: (17+4+24+7)/4 = 13
another example:
Gantt chart:
average waiting time: (9+1+0+2)/4 = 3
average turnaround time: (16+5+1+6)/4 = 7
Priority Scheduling example
Gantt chart:
(regenerated from [OSC] p. 193)
average waiting time: (6+0+16+18+1)/5 = 8.2
average turnaround time: (1+6+16+18+19)/5 = 12
Round Robin
time sharing (preemptive) scheduler where each process is given access to the CPU for 1 time quantum (slice) (e.g., 20 milliseconds)
a process may block itself before its time slice expires
if it uses its entire time slice, it is then preempted and put at the end of the ready queue
the ready queue is managed as a FIFO queue and treated as a circular
if there are n processes on the ready queue and the time quantum is q, then each process gets 1/n time on the CPU in chunks of at most q time units
no process waits for more than (n-1)q time units
the choice of how big to make the time slice (q) is extremely important
if q is very large, Round Robin degenerates into FCFS
if q is very small, the context switch overhead defeats the benefits
example (q = 20):
Gantt chart:
waiting times:
p1: (77-20) + (121-97) = 81
p2: (20-0) = 20
p3: (37-0) + (97-57) + (134-117) = 94
p4: (57-0) + (117-77) = 97
average waiting time: (81+20+94+97)/4 = 73
another example (q = 4):
Gantt chart:
(regenerated from [OSC] p. 194)
average waiting time: (6+4+7)/3 = 5.67
average turnaround time: (30+7+10)/3 = 15.67
another example (q = 10):
Gantt chart:
(regenerated from [OSC] p. 214)
average waiting time: (0+32+20+23+40)/5 = 23
average turnaround time: (10+39+42+49+61)/5 = 35.2
Multilevel Queue
the ready queue is managed as multiple queues based on various characteristics. For instance,
foreground (interactive)
background (batch)
each queue uses a particular scheduling algorithm. For instance,
foreground (round robin)
background (FCFS)
scheduling must be done between queues:
fixed priority (may lead to starvation) (e.g., foreground jobs have absolute priority over background jobs)
time slice per queue
Multilevel Feedback Queue
processes move between the various queues
a multilevel feedback queue is characterized by
number of queues
scheduling algorithm for each queue
method used to determine when to upgrade a process
method used to determine when to demote a process
method used to determine on which queue a process begins (each time it returns to the ready state)
example:
3 queues
fixed priority based on length of CPU burst
RR for 1st queue, FCFS for last queue
each process begins on top queue (quantum = 8)
(regenerated from [OSC] Fig. 5.7 on p. 198)
Algorithm Evaluation
which algorithm should be used in a particular system?
how should the parameters (e.g., q, number of levels) be defined?
on which criteria do we base our decisions?
Four approaches to evaluation
deterministic modeling
queue models
simulation
implementation
Deterministic modeling
define a workload and compare it across algorithms
simple to execute and results in distinct values to compare
however, the results apply only to that case and cannot be generalized
a set of workload scenarios with varying characteristics can be defined and analyzed
must be careful about any conclusion drawn
Queuing models
n = average queue length
W = average waiting time in the queue
λ = average arrival rate
Little's Formula: n = λ * W
Little's formula can be applied to the CPU and ready queue, or the wait queue for any device
values can be obtained by measuring a real system over time and mathematically estimating
the estimates are not always accurate due to:
complicated algorithms
assumptions
therefore, the queuing model may not reflect reality to the level needed
References
[OSC]
[OSCJ]
[OSIDP]
A. Silberschatz, P.B. Galvin, and G. Gagne. Operating Systems Concepts. John Wiley and Sons, Inc., Eighth edition, 2009.
A. Silberschatz, P.B. Galvin, and G. Gagne. Operating Systems Concepts with Java. John Wiley and Sons, Inc., Seventh edition, 2007.
W. Stallings. Operating Systems: Internals and Design Principles. Prentice Hall, Upper Saddle River, NJ, Sixth edition, 2009.