Operating

Systems
CS2006
Chapter: 4
CPU Scheduling-II

1 CS-2006 Operating Systems

 What’s in today’s
lecture
Basic Concepts
Scheduling Criteria
Scheduling Algorithms

2 CS-2006 Operating Systems

 Scheduling
Algorithms
First come, First serve (FCFS)
Shortest Job First (SJF)
Priority Scheduling
Round-Robin Scheduling
Multi-level Queue Scheduling
Multi-level Feed back queue
Scheduling

3 CS-2006 Operating Systems

2. Shortest-Job-First (SJF)
Scheduling
Associate with each process the length of its next
CPU burst. Use these lengths to schedule the
process with the shortest time
Two schemes:
Nonpreemptive – once CPU is given to the process it
cannot be preempted until the process completes its
CPU burst
Preemptive – if a new process arrives with CPU burst
length less than the remaining time of current
executing process, preempt. This scheme is know as
the Shortest-Remaining- Time-First (SRTF)
SJF is optimal – gives minimum average waiting
4
timeOperating
CS-2006 for aSystems
given set of processes
 Example of Non-Preemptive
SJF Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF
(non-preemptive)
P1 P3 P2 P4

0 3 7 8 12 16

Average waiting time = (0 + 6 + 3 + 7)/4 =

5 4
CS-2006 Operating Systems
 SRTF - Shortest Remaining
Time First
Preemptive version of SJF
Ready queue ordered on length of time till
completion (shortest first)
Arriving jobs inserted at proper position
Shortest job
Runs to completion (i.e. CPU burst finishes) or
Runs until a jobwith a shorter remainingtime
arrives (i.e. placed in the ready queue)

6 CS-2006 Operating Systems

 Example of Preemptive SJF
(i.e., SRTF)
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Preemptive SJF (i.e.,
SRTF)
P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

Average waiting time = (9 + 1 + 0 +2)/4 =

7 3
CS-2006 Operating Systems
 Shortest-Job-First (SJF)
ReadyScheduling
queue treated as a priority queue based on smallest
CPU- time requirement
Arriving jobs inserted at proper position in queue
Shortest job (1st in queue) runs to completion
In general, SJF is often used in long-term scheduling
Advantages: provably optimal w.r.t. average waiting time
Disadvantages: Unimplementable at the level of short-term
CPU [Link], starvation is possible!
Can do it approximately: use exponentialaveraging to
predict length of next CPU burst
==> pick shortest predicted burst next!

8 CS-2006 Operating Systems

 Determining Length of Next
CPU Burst
Can only estimate the length
Can be done by using the length of previous CPU
bursts, using exponential averaging
th
1. tn actual lenght of n CPU burst
2. n1
predicted value for the next (i.e.,thn1) CPU burst
3. n
predicted value for the thn CPU burst

4. , 0 1 ) tn  (1
5. Define : n1
.
= 0 implies makingn no use of recent history ( n+1 n
)
= 1 implies n+1 = tn (past prediction not used)
= 1/2 implies weighted (older bursts get less and less weight)
9 CS-2006 Operating Systems
 Prediction of the Length of the
Next CPU Burst
This figure is 0.5 and 0
for 10

10 CS-2006 Operating Systems

 3. Priority
AScheduling
priority number (integer) is associated with each process
Priority can be internally computed (e.g., may involve time limits,
memory usage) or externally (e.g., user type, funds being paid)
In SJF, priority is simply the predicted next CPU burst time
The CPU is allocated to the process with the highest
priority (smallest integer might mean highest priority)
Starvation is a problem, where low priority processes may
never
execute
Solution: as time progresses, the priority of the long
waiting (starved) processes is [Link] is called
aging

11 CS-2006 Operating Systems

 Priority
scheduling
Priority scheduling can be Preemptive or
Non- Preemptive
When a process arrives and enters the Ready
Queue
Its priority is compared with the currently
Running Process
If Higher
Preemptive Scheduling
Run the New process
Non-Preemptive Scheduling
Continue running the process
12 CS-2006 Operating Systems
 Priority
Scheduling
process priority service turnaround waiting
time ts time tt time tw
A 4 10 18 8
B 3 1 8 7
C 2 3 7 4
D 1 4 4 0

AVERAGE 9.25 4.75

13 CS-2006 Operating Systems

 4. Round Robin
(RR)
RR reduces the penalty that short jobs suffer with
FCFS by preempting running jobs periodically
Each process gets a small unit of CPU time
(time quantum), usually 10-100 milliseconds
The CPU blocks the current job when its reserved
time quantum (time-slice) is exhausted
The current job is then put at the end of the ready queue
if it has not yet completed
If the current jobis completed, it will exit the
system (terminate)

14 CS-2006 Operating Systems

 Round Robin
If(RR)
there are n processes in the ready queue and the
time quantum is q, then each process gets 1/n of
the CPU time in chunks of at most q time units at
once. No process waits more than (n -1)q time
units
Performance: the critical issue with the RR policy
is the length of the quantum q
q is large: RR will behave like FIFO and hence
interactive processes will suffer
q is small: the CPU will be spending more time on
context switching
q must be large with respect to context switch, otherwise overhead
15 is too
CS-2006 highSystems
Operating
 Time Quantum and Context
Switch Time

16 CS-2006 Operating Systems

 Example of RR with Time Quantum
= 20
Process Burst
P Time
1 53
P 17
2 68
P
24
3
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
P
0 20 37 57 77 97 117 121 134 154 162
4
The Gantt chart
Typically, is:
higher average turnaround than SJF
but better
response
17 CS-2006 Operating Systems
 Round Robin’s
Disadvantage
Good for Varying sized jobs
But what about same-sized
jobs?
Assume 2 jobs of time =100
each:1 2 3 4 199 200
CPU 5
A B A B A A B A B

time
• Avg completion time?
• (200 + 200) / 2 = 200
• How does this compare with FCFS for same two jobs?
• (100 + 200) / 2 = 150

18 CS-2006 Operating Systems

 Turnaround Time Varies With The
Time Quantum
Increasing the time quantum does not
necessarily improve the average turnaround
time!

19 CS-2006 Operating Systems

 5. Multilevel Queue
Scheduling
Ready queue is partitioned into separate queues:
For example, foreground (interactive) and background
(batch)
Each queue has its own scheduling algorithm:
Foreground – RR
Background – FCFS
Scheduling must be done between the queues
Fixed priority scheduling; (i.e., serve all from
foreground then from background)
Possibility of starvation
Time slice – each queue gets a certain amount of
CPU time which it can schedule amongst its
20
processes
CS-2006 Operating Systems
i.e., 80% to foreground in RR and 20% to background in FCFS
 Multilevel Queue
Scheduling

21 CS-2006 Operating Systems

 6. Multilevel Feedback
A
Queue
process can move between the various queues;
aging can be implemented this way
Multilevel-feedback-queue scheduler defined followin
by the parameters: g
number of queues
scheduling algorithms for each queue
method used to determine when to upgrade a
process
method
method used
used to
to determine
determine which queue
when to a process
demote a will
enter
process
when that process needs service

23 CS-2006 Operating Systems

 Multilevel Feedback Queue
Scheduling
Example
If a process used too much CPU time, then move it to a
lower- priority queue
If a process waits too long in a lower priority queue,
then move it to a higher priority queue

23 CS-2006 Operating Systems

 Multilevel Feedback
Queue
Three queues:
Q0 – time quantum 8 milliseconds
Q1 – time quantum 16 milliseconds
Q2 – FCFS
Scheduling
A new job enters queue Q0 which is served FCFS. When
it gains CPU, the job receives 8 milliseconds. If it does
not finish in 8 milliseconds, the job is moved to queue
Q1
At Q1 , the job is again served FCFS and receives 16
additional milliseconds. If it still does not complete, it is
25 preempted
CS-2006 and moved to queue Q2
Operating Systems
 Multilevel Feedback
Queue

26 CS-2006 Operating Systems

 MLFQ
•
Example
At t=0 there are three CPU bound processes (no I/O) in the
system. The CPU burst lengths are: 30 units for P1, 20 units
for P2, and 10 units for [Link] system has three RR queues
with the following time slices: 1 for queue1, 2 for queue 2,
and 4 for queue3. RR- 1 Unit of time slice

• Gantt Chart
• Average Completion Time
• Average Waiting Time

27 CS-2006 Operating Systems

 Solutio
n:

28 CS-2006 Operating Systems

 Summary of CPU Scheduling
Algorithms
First-Come, First-Served (FCFS)
Scheduling
Shortest-Job-First (SJF) Scheduling
Nonpreemptive
Preemptive or Shortest Remaining Time First
(SRTF)
Priority Scheduling
Preemptive
Nonpreemptive
Round Robin (RR)
Multilevel Queue Scheduling
29 Multilevel
CS-2006 Feedback Queue
Operating Systems
 Referenc
es
Operating System Concepts (Silberschatz, 9th
edition) Chapter 5

30 CS-2006 Operating Systems