05.

Scheduling
Algorithms
9th ed: Ch. 6
10th ed: Ch. 5
Objectives
• To understand how to apply several common scheduling algorithms
• FCFS, SJF, SRTF
• Round Robin
• Priority
• Multilevel Queues
• To understand use of measurement and prediction for unknown
scheduling parameters

05. Scheduling Algorithms 2

Outline
• First-Come First-Served (FCFS)
• Shortest Job First (SJF)
• Shortest Remaining Time First (SRTF)
• Round Robin (RR)
• Priority scheduling
• Multilevel queues

05. Scheduling Algorithms 3

Outline
• First-Come First-Served (FCFS)
• Convoy effect
• Shortest Job First (SJF)
• Shortest Remaining Time First (SRTF)
• Round Robin (RR)
• Priority scheduling
• Multilevel queues

05. Scheduling Algorithms 4

First-Come First-Served (FCFS)
• Schedule depends purely on the order in which processes arrive
• Simplest possible scheduling algorithm
• Not terribly robust to different arrival processes

• E.g., suppose processes with the following burst times arrive in the
order P1, P2, P3 Process Burst Time
P1 24
P2 3
P3 3

05. Scheduling Algorithms 5

First-Come First-Served (FCFS)
• Then the Gantt chart is

Process Burst Time Waiting Time

• The waiting times are P1 24 0
P2 3 24
P3 3 27

• This gives an average per-process waiting time of 0 + 24 + 27 = 17

3

05. Scheduling Algorithms 6

The Convoy Effect
• Now suppose the same processes arrive in the order P2, P3, P1
• Then the Gantt chart and waiting times are:

• Gives an average per-process waiting time Process Burst Time Waiting Time
of 6 + 0 + 3 = 3 P1 24 6
3 P2 3 0
P3 3 3
• First case is an example of the Convoy Effect
• Short-run processes getting stuck behind long-run processes
• Consider one CPU-bound and many IO-bound processes
05. Scheduling Algorithms 7
Outline
• First-Come First-Served (FCFS)
• Shortest Job First (SJF)
• Shortest Remaining Time First (SRTF)
• Round Robin (RR)
• Priority scheduling
• Multilevel queues

05. Scheduling Algorithms 8

Shortest Job First (SJF)
• Associate length of next CPU burst with each process
• Schedule the process with the shortest next burst
• Optimality: SJF gives the least possible waiting time for a given set of
processes

05. Scheduling Algorithms 9

Shortest Job First (SJF)
• Consider the following arrivals process and resulting Gantt chart:
Process Burst Time
P1 6
P2 8
P3 7
P4 3

• Gives an average per-process waiting time of 3 + 16 4+ 9 + 0 = 7

05. Scheduling Algorithms 10

Outline
• First-Come First-Served (FCFS)
• Shortest Job First (SJF)
• Shortest Remaining Time First (SRTF)
• Predicting the future
• Exponential averaging
• Round Robin (RR)
• Priority scheduling
• Multilevel queues

05. Scheduling Algorithms 11

Shortest Remaining Time First
(SRTF)
• Simply a pre-emptive version of SJF
• Pre-empt current process if a new one arrives with a shorter burst length than
the remaining time of the current process
• Distinguish arrival time and burst length, e.g., Process Arrival Time Burst Length
P1 0 8
• Gives Gantt chart P2 1 4
P3 2 9
P4 3 5

• Average waiting time now ( 10 − 1 ) + ( 1 − 1) + ( 17 − 2) + ( 5− 3 ) = 26 = 6 1

4 4 2

05. Scheduling Algorithms 12

Optimality in the future
• If SJF is optimal given a known set of processes (demand), then surely
SRTF is optimal in the face of new runnable processes arriving?
• No! Why?
• Context switches are not free, so if short burst processes keep arriving
the OS will start thrashing the CPU, so no useful work gets done

• More fundamentally,
how can we know the length of a future burst?

(Ask the user? Ask the developer? Measure and predict?)

05. Scheduling Algorithms 13
Predicting burst lengths
• Assume the next burst will not be too different from the previous
• Then
• measure burst lengths as processes are scheduled,
• predict next burst length, and
• choose the process with the shortest predicted burst length
• E.g., exponential averaging on length of previous bursts
• Set tn to be the measured length of the nth CPU burst
• Define τn+1, predicted length of (n+1)th burst as τn+1 = αtn + (1 − α)τn

05. Scheduling Algorithms 14

Examples of exponential averaging
• Expanding this formula gives, for τ0 some constant
j n+1
τ n+1 =α t n +…+ ( 1− α ) αt n − j +…+ ( 1− α ) τ0
• As both α, 1–α ≤ 1, each term has less weight than its predecessor
• Choose value of α according to our belief about the system, e.g,
• If we believe past history irrelevant, choose α ≈ 1 and then get τn+1 ≈ tn
• If we believe recent history irrelevant, choose α ≈ 0 and then get τn+1 ≈ τn
• Exponential averaging is often a good predictor if the variance is small
• ...if the variance is not changing “too fast” with respect to the size of time slot
• Also consider system load, else (counter-intuitively) priorities increase with load
05. Scheduling Algorithms 15
Examples of exponential averaging

05. Scheduling Algorithms 16

Outline
• First-Come First-Served (FCFS)
• Shortest Job First (SJF)
• Shortest Remaining Time First (SRTF)
• Round Robin (RR)
• Priority scheduling
• Multilevel queues

05. Scheduling Algorithms 17

Round Robin
• A pre-emptive scheduling scheme for time-sharing systems
• Give each process a quantum (or time-slice) of CPU time e.g., 10—100 milliseconds
• Once quantum elapsed, process is pre-empted and appended to the ready queue
• Timer interrupts every quantum to schedule next process
• Can be tricky to choose correctly =
• q too large degenerates into a
FIFO queue (~ FCFS)
• q too small makes the context switch
overhead too great
• q usually 10ms to 100ms,
while context switch < 10 μsec
05. Scheduling Algorithms 18
Round Robin
• Consider the first example again Process Burst Time
P1 24
P2 3
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30 P3 3

• For quantum q and n processes ready,

• Fair: each process gets 1/n CPU time in chunks of at most q time units, and
• Live: no process ever waits more than (n-1)q time units
• Typically
• higher average turnaround time than SRTF, but
• better average response time
05. Scheduling Algorithms 19
Outline
• First-Come First-Served (FCFS)
• Shortest Job First (SJF)
• Shortest Remaining Time First (SRTF)
• Round Robin (RR)
• Priority scheduling
• Dynamic priorities
• Computed priorities
• Multilevel queues

05. Scheduling Algorithms 20

Priority scheduling
• Associate integer priority with process, and schedule the highest priority
(~ lowest number) process, e.g., Process Priority Burst Length
P1 3 10
P2 1 1
P3 4 2
P4 5 1
• Average waiting time now P5 2 5

( 1+5 ) + 0 + ( 1+5+10 ) + ( 1+5+10+2) + 1 41 1

5 = 5 = 85

• Consider: SJF as priority scheduling using inverse of predicted burst length

05. Scheduling Algorithms 21

Dynamic priority scheduling
• Starvation can occur if low priority processes never execute
• Urban legend?
• When the IBM 7074 at MIT was shut down in 1973, low-priority processes
were found that had been submitted in 1967 and had not yet been run...
• This is the biggest problem with static priority systems!
• A low priority process is not guaranteed to run — ever!
• Solve by making priorities dynamic
• E.g., aging increases priority starting from a static base as time passes without
process being scheduled

05. Scheduling Algorithms 22

Computed Priority
• E.g., UNIX scheduler
• Priorities 0–127; user processes ≥ Base = 50
• Round robin within priority queue, quantum = 100ms
• Priority recalculated every 4 ticks (typically, 40ms) it is found running
• Kernel mode process scheduling
• Fixed priority, non-preemptive
• Modified by reasons for process waiting
• E.g., waiting for disk I/O < waiting for terminal input
• User mode process scheduling
• Dynamically computed, pre-emptive
• Per-tick (10ms), if there is a higher-priority process, switch to it
• Per-quantum (10 ticks = 100ms), if there is a process in the same priority queue, switch to it

05. Scheduling Algorithms 23

Computing the priority
• Priority of process j at start of interval i is based on
• basej, the base priority of a user mode process (50)
• nicej, a user controllable parameter between -20 and 20 (default = 0)
• loadj, the sampled (1 minute) average length of the run queue
• CPUj, incrementing counter if process j was observed running this tick
• Every 100 ticks,
2×load j
• Age the CPUj counter: CPU j ( i ) = CPU j ( i − 1)
( 2×load j) +1
CPU j ( i )
• Compute the new priority: P j ( i ) = Base j + 4 + 2×nice j

05. Scheduling Algorithms 24

Outline
• First-Come First-Served (FCFS)
• Shortest Job First (SJF)
• Shortest Remaining Time First (SRTF)
• Round Robin (RR)
• Priority scheduling
• Multilevel queues
• Multilevel queues
• Multilevel feedback queues

05. Scheduling Algorithms 25

Multilevel Queues
• Partition Ready queue into many queues
for different types of process, e.g.,
• Foreground/interactive processes
• Background/batch processes
• Each process is permanently assigned a
given queue
• Each queue runs its own scheduling
algorithm, e.g.,
• Foreground runs Round Robin
• Background runs First-Come First-Served

05. Scheduling Algorithms 26

Multilevel Feedback Queues
• Now scheduling must be done between the queues:
• Fixed priority, e.g., serve all from foreground then from background, permits starvation
• Time slice, each queue gets a certain amount of CPU time which it can schedule amongst
its processes, e.g., 80% to foreground in RR, 20% to background in FCFS
• A process can move between the various queues
• Aging can be implemented this way
• Multilevel-feedback-queue scheduler defined by the following parameters:
• number of queues
• scheduling algorithms 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 which queue a process will enter when it needs service
05. Scheduling Algorithms 27
Multilevel Feedback Queues
• Three queues: =
• Q0 – RR with time quantum 8 milliseconds
• Q1 – RR time quantum 16 milliseconds
=
• Q2 – FCFS
• Scheduling
• A new job enters queue Q0 which is served FCFS
• When it gains CPU, job receives 8 milliseconds
• If it does not finish in 8 milliseconds, job is moved to queue Q1
• At Q1 job is again served FCFS and receives 16 additional milliseconds
• If it still does not complete, it is pre-empted and moved to queue Q2
05. Scheduling Algorithms 28
Summary
• First-Come First-Served (FCFS) • Round-Robin (RR)
• Convoy effect • Priority scheduling
• Shortest Job First (SJF) • Dynamic priorities
• Computed priorities
• Shortest Remaining Time First
• Multilevel queues
(SRTF)
• Multilevel feedback queues
• Predicting the future
• Exponential averaging

05. Scheduling Algorithms 29