Operating
Systems
Lecture 16
Syed Mansoor Sarwar
Agenda for Today
Review of previous lecture
SJF is optimal
Round-Robin scheduling
Multi-level queues scheduling
Multi-level feedback queues
scheduling
Recap of lecture
14 September 2019 © Copyright Virtual University of
Pakistan
Review of Lecture 15
Shortest-Job-First (SJF)
Shortest-Remaining-Time-First
(SRTF)
Exponential averaging
Priority scheduling
14 September 2019 © Copyright Virtual University of
Pakistan
Review of Lecture 15
Exponential Averaging
n+1 = tn + (1- ) n
for = ½
n+1 = tn/2 + tn-1/22 + tn-2/23 + tn-3/24 + …
14 September 2019 © Copyright Virtual University of
Pakistan
SJF is Optimal
Logical Argument: Decrease in
the wait times for short processes
is much more than increase in the
wait times for long processes
P1 P2 P3
5 3 2
P3 P2 P1
2 3 5
14 September 2019 © Copyright Virtual University of
Pakistan
Round Robin (RR)
Each process gets a small unit
of CPU time, called time slice or
quantum, which is usually 10-
100 milliseconds. After this
time has elapsed, the process
is preempted and added to the
end of the ready queue.
14 September 2019 © Copyright Virtual University of
Pakistan
Round Robin (RR)
If there are n processes in the
ready queue, the time quantum
is q, and context switch time is
tcs, then no process waits more
than (n-1)(q+tcs) time units
Used in time-sharing systems
where response time is an
important performance criteria
14 September 2019 © Copyright Virtual University of
Pakistan
Round Robin (RR)
Performance
q large FCFS
q small q must be large with
respect to context
switch, otherwise
overhead is too high.
14 September 2019 © Copyright Virtual University of
Pakistan
Round Robin Example
Process Burst Time
P1 53 — 33 — 13
P2 17
P3 68 — 48 — 28 — 8
P4 24 — 4
The Gantt chart with quantum 20 is:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
14 September 2019 © Copyright Virtual University of
Pakistan
Round Robin Example
Process Turnaround Time Waiting Time
P1 134 134 – 53 = 81
P2 37 37 – 17 = 20
P3 162 162 – 68 = 94
P4 121 121 – 24 = 97
Average waiting time = 73
Average waiting time for SJF = 38
Typically, higher average turnaround
than SJF, but better response.
14 September 2019 © Copyright Virtual University of
Pakistan
Quantum vs Context
Switch
Process Time = 10 Quantum Context
Switches
12 0
6 1
1 9
14 September 2019 © Copyright Virtual University of
Pakistan
Turnaround Time vs
Quantum
14 September 2019 © Copyright Virtual University of
Pakistan
Multilevel Queues
Ready queue is partitioned into
separate queues:
- foreground (interactive)
- background (batch)
Each queue has its own priority
and scheduling algorithm:
- foreground – RR
- background – FCFS
14 September 2019 © Copyright Virtual University of
Pakistan
Multilevel Queues
Scheduling must be done across
queues.
Fixed priority scheduling; i.e.,
serve all from foreground then
from background.
Time slice – each queue gets a
certain percentage of CPU time,
e.g., 80% to foreground in RR
and 20% to background in FCFS
14 September 2019 © Copyright Virtual University of
Pakistan
Multilevel Queues
14 September 2019 © Copyright Virtual University of
Pakistan
Recap of Lecture
SJF is optimal
Round-Robin scheduling
Multi-level queues scheduling
14 September 2019 © Copyright Virtual University of
Pakistan
