CPU Scheduling

Outline

 Scheduling Objectives
 Levels of Scheduling
 Scheduling Criteria
 Scheduling Algorithms
 FCFS, Shortest Job First, Priority, Round Robin,
Multilevel
 Multiple Processor Scheduling
 Real-time Scheduling
 Algorithm Evaluation
Introduction to Scheduling
 Multiprogramming Environment, Many
processes competing for the CPU at the same
time.
 Two or more processes are in ready state and
one CPU then choice is to be made which
process to run next.
 The part of the OS that makes the choice is
called the scheduler and algorithm it uses is
called the scheduling algorithms.
 Process Scheduling and Thread Scheduling
many things are same.
Introduction to Scheduling
 Batch Systems
 I/P in the form of card s or a magnetic tape
 Scheduling was very simple, Just run the next job on
the tape
 Time Sharing Systems
 Scheduling algorithms became more complex
because multiple users waiting for service.
 Because CPU time is a scarce resource, a good
scheduler can make a big difference in perceived
performance and satisfaction
 Great work was done into devising cleaver &
efficient scheduling algorithms
Introduction to Scheduling
 Advent of PCs situation changed in two ways
 First, most of the time there is only one process
 Second, computers became so faster that the CPU is
rarely a scarce resource any more.
 Ex. Word or Excel running at a time
 It hardly matters which goes first since the user
is waiting for both of them to finish
 Scheduling does not matter much on simple PCs
Introduction to Scheduling
 When we turn to high-end networked
workstations and servers the situation changes
 Multiple processes often compete for the
CPU so scheduling matters
 EX CPU has to choose between running a
process that updates the screen after the user
has closed the window
 Running a process that sends out queued email
 It makes huge difference in the perceived
response
Introduction to Scheduling
 Closing Window must not take time
because user can perceive that and
 If email is delayed by 2 seconds its okay,
even may not be noticed also.
 In this case scheduling matters very much
 In addition to pick a right process, scheduler
also has to worry about making efficient use
of the CPU because process switching is also
expensive.
Process Behavior

 CPU–I/O Burst Cycle – Process execution consists of a cycle of

CPU execution and I/O wait

 Bursts of CPU usage alternate with periods of I/O wait

 a CPU-bound process

 an I/O bound process

Process Behavior
When to Schedule
 CPU scheduling decisions may take place
under following circumstances, When a
process
1. Switches from running to waiting state
 For example, when the process has an IO request
 This is non-preemptive
2. Switches from running to ready state
 For example, when an interrupt occurs
 This is preemptive

9/3/2024 10
When to Schedule
 CPU scheduling decisions may take place
under following circumstances, When a
process
3. Switches from waiting to ready state
 For example, at the completion of I/O
 This is preemptive
4. Terminates
– For example, the process (running program) is done
– This is non-preemptive

9/3/2024 11
Process State
 A process changes state as it executes.
https://youtu.be/Y3mQYaQsrvg

new admitted
exit terminated
5 Scheduler picks
another process 6
2

running
ready
3
Scheduler picks
I/O or this Process
event I/O or
completion event wait
4 1

blocked
CPU Scheduler
 Selects from among the processes in memory that are ready to
execute, and allocates the CPU to one of them.
 Non-preemptive Scheduling

 Once CPU has been allocated to a process, the process

keeps the CPU until
Process exits OR


 Process switches to waiting state

 Preemptive Scheduling
 Process can be interrupted and must release the CPU.
 Need to coordinate access to shared data
 Can take the CPU back due to
 Time slice
 Higher priority process arrived
 Interrupts

9/3/2024 13
Categories Of Scheduling Algorithms
 Scheduling algorithms differs for different environment
and different systems
 Batch
 No users waiting for a quick response
 Non-preemptive or preemptive algorithm with long time periods
for each process are often acceptable
 This approach reduces process switches and thus improves
performance
 Interactive
 Preemption is essential to keep one process hogging the CPU
and denying service to the others
 Real Time
 With real time constraints

9/3/2024 14
Scheduling Algorithm Goals/ Scheduling
Criteria/ Objectives of Scheduling
 What a good algorithm should do?
 CPU Utilization
 Keep the CPU and other resources as busy as possible
 Throughput
 # of processes that complete their execution per time
unit.
 Turnaround time
 amount of time to execute a particular process from its
entry time. (Time of Completion of Job – Time of
Submission of Job)

9/3/2024 15
Scheduling Algorithm Goals/ Scheduling
Criteria/ Objectives of Scheduling
 Waiting time
 amount of time a process has been waiting in the ready
queue.
 Response Time (in a time-sharing
environment)
 amount of time it takes from when a request was
submitted until the first response is produced, called
response time
 The amount of time it takes to start responding, but not
the time it takes to output that response.
Scheduling Algorithm Goals/ Scheduling
Criteria/ Objectives of Scheduling
 Priority
 Give preferential treatment to processes with higher
priority
 Balanced Utilization
 Utilization of memory, I/O devices & other system
resources are also considered not only CPU utilization
 Fairness
 Can be reflected by treating all the processes same and
no process should suffer indefinite postponement
Scheduling

Scheduling Algorithm Goals

Optimization Criteria

 Max CPU Utilization

 Max Throughput
 Min Turnaround time
 Min Waiting time
 Min response time
Scheduling algorithms

 FCFS First Come First Serve

 SJF Shortest Job First
 Shortest Remaining Time Next
 Three level Scheduling
First Come First Serve (FCFS) Scheduling
 Simplest of all scheduling algorithms.
 Policy: Process that requests the CPU FIRST is
allocated the CPU FIRST. (Single queue of ready
processes)
 FCFS is a non-preemptive algorithm.

 Implementation - using FIFO queues

 incoming process is added to the tail of the
queue.
 Process selected for execution is taken from
head of queue.
 When the first job enters the system from the outside, it
is started immediately and allowed to run as long as it
wants to.
First Come First Serve (FCFS) Scheduling
 As another job comes in, they are put into the end of the
queue
 When the running process blocks, the first process from
the queue is run next
 When the blocked process becomes ready, like newly
arrived job, it is put on the end of the queue.
 Performance metric - Average waiting time in
queue.
 Easy to understand and Easy to program
 Gantt Charts are used to visualize schedules.
First-Come, First-Served(FCFS)
Scheduling
 Example  Suppose the arrival
order for the processes
Process Burst Time
P1 24
is
P2 3  P1, P2, P3
P3 3
 Waiting time
 P1 = 0;
Gantt Chart for Schedule
 P2 = 24;
P1 P2 P3  P3 = 27;
0 24 27 30  Average waiting time
 (0+24+27)/3 = 17
FCFS Scheduling (cont.)
 Suppose the arrival order for the
processes is
 Example
 P2, P3, P1
 Waiting time
Process Burst Time  P1 = 6; P2 = 0; P3 = 3;
P1 24  Average waiting time
P2 3
P3 3  (6+0+3)/3 = 3 , better..
 Convoy Effect:
Gantt Chart for Schedule
 short process behind long
process, e.g. 1 CPU bound
P2 P3 P1 process, many I/O bound
processes.
0 3 6 30  Simple, fair, but poor
performance. Average queuing
time may be long.
Disadvantages of FCFS Scheduling
 Average waiting time under FCFS is
generally not minimal
 There is a convoy effect
 Results in lower CPU & device Utilization
 FCFS is non-preemptive
 FCFS can not be used for time-sharing
environment
First-Come, First-Served(FCFS)
Scheduling
 Example
Process Burst Time
P1 3
P2 6
P3 4
P4 2
First-Come, First-Served(FCFS)
Scheduling
 Example
Process Burst Time
P1 3
P2 6
P3 4
P4 2

Gantt Chart for Schedule

P1 P2 P3 P4

0 3 9 13 15
First-Come, First-Served(FCFS)
Scheduling order of the processes 

 Example  P1, P2, P3,P4

Process Burst Time
P1 3  Waiting time
P2 6  P1 = 0;
P3 4
 P2 = 3;
P4 2
 P3 = 9;
Gantt Chart for Schedule
 P4 = 13;
P1 P2 P3 P4

0 3 9 13 15
 Average waiting time
 (0+3+9+13)/4 = 6.25ms
First-Come, First-Served(FCFS)
Scheduling Turn around Time: 

 Example Waiting Time + Burst Time

 P1 = 0 + 3 = 3
Process Burst Time  P2 = 3 + 6 = 9
P1 3
 P3 = 9 + 4 = 13
P2 6
P3 4
 P4 = 13 + 2 = 15
P4 2  Average Turn around Time:
Gantt Chart for Schedule  (3+9+13+15) / 4
 =10 ms
P1 P2 P3 P4

0 3 9 13 15
Example

Processes Burst time

P1 20
P2 7
P3 5

Calculate Average Waiting Time using FCFS

if the processes arrive in the order of :
(1) P1, P2, P3 (AWT = 15.6)
(2) P2, P3, P1 (AWT = 6.33 )
(3) P3, P1,P2 (AWT = 10)
(4) P3, P2, P1 (AWT= 5.6)
Example

Processes Burst time

P1 6
P2 8
P3 7
P4 3

Calculate Average Waiting Time for FCFS & SJF?

1. P1, P2, P3, P4
2. P4, P1, P3, P2
Example

Processes Burst time

P1 6
P2 8
P3 7
P4 3

FCFS average waiting time: (0+6+14+21)/4=10.25

SJF average waiting time: (3+16+9+0)/4=7
Example

Processes Burst time

P1 8
P2 4
P3 4
P4 4

Calculate Average Waiting Time for FCFS & SJF?

0123
FCFC = 7.5 ms
Non-Preemptive SJF = 7.5 ms
Preemptive SJF = 5.25 ms
Example

Processes Burst time

P1 8
P2 4
P3 4
P4 4

Average Waiting Time for FCFS is 9 ms

Average Turnaround Time for FCFS is 14ms

Average Waiting Time for SJF is 6 ms

Average Turnaround Time for SJF is 11ms
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:
 Scheme 1: Non-preemptive
 Once CPU is given to the process it cannot be preempted
until it completes its CPU burst.
 Scheme 2: Preemptive
 If a new CPU process arrives with CPU burst length less
than remaining time of current executing process, preempt.
Also called Shortest-Remaining-Time-First (SRTF).
 SJF is optimal - gives minimum average waiting time for
a given set of processes.
Non-Preemptive SJF Scheduling

 Example
Process Arrival TimeBurst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Gantt Chart for Schedule

P1 P3 P2 P4

0 7 8 12 16
Average waiting time =
(0+6+3+7)/4 = 4
Shortest-Job-First(SJF) Scheduling
 Advantages:
 SJF is provably optimal, in that it gives the minimum
average waiting time for a given set of processes.
 By moving short processes before long process
waiting time for short can be decreased by increasing
waiting time of the long process.
 The average waiting time decreases.

 Difficulty
 With SJF is knowing the length of the next CPU
request
 Can be work out by approximating the next CPU
Burst.
 Example  order of the processes
Non-Preemptive SJF  P1, P2, P3,P4

Process Arrival TimeBurst Time  Waiting time

P1 0 8  P1 = 0;
P2 1 4  P2 = (8-1)=7;
P3 2 9
P4 3 5  P3 = (17-2)=15;

 P4 = (12-3)=9;

P1 P2 P4 P3
 Average waiting time
0 P2 P3 P4 8 12 17 26
(0+7+15+9)/4 = 7.75ms
Example
Non-Preemptive SJF
 Example  Arrival Time for all
Process Burst Time processes is 0 ms
P1 3
P2 6  order of the processes
P3 4
 P1, P2, P3,P4
P4 2
 Example
Non-Preemptive SJF
 Example  Arrival Time for all processes is
0 ms
Process Burst Time
 order of the processes
P1 3
 P1, P2, P3,P4
P2 6
P3 4
 Waiting time
P4 2
 P1 = 2;
 P2 = 9;
 P3 = 5;
P4 P1 P3 P2
 P4 = 0;
0 2 5 9 6
 Average waiting time
 (2+9+5+0)/4 = 4 ms
 Example
Non-Preemptive SJF
 Example  Turn around Time
Process Burst Time  P1 = 2+3 = 5
P1 3  P2 = 9+6 = 15
P2 6  P3 = 5+4 = 9
P3 4
 P4 = 0+2 =2
P4 2
 Avg. Turnaround Time =
(5+15+9+2)/4 = 7.75 ms
P4 P1 P3 P2

0 2 5 9 6
SRTF (Shortest Remaining Time First)
 SJF is preemptive or non-preemptive
 The choice arises when a new process arrives at
the ready queue while a previous process is
executing.
 The new process may have shorter next CPU burst
than what is left of the currently executing process.
 The preemptive SJF algorithm will preempt the
currently executing process, whereas a non-
preemptive SJF algorithm will allow the currently
running process to finish the CPU burst.
 Preemptive SJF is sometimes called Shortest-
Remaining-Time-First
Preemptive SJF Scheduling(SRTF)

 Example
Process Arrival TimeBurst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Gantt Chart for Schedule

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16
Average waiting time =
(9+1+0+2)/4 = 3
Example SRTF
 Waiting Time for
Process Arrival Time Burst Time  P1 = 0 + (10-1) = 9 ms
P1 0 8
 P2 = 1-1 = 0 ms
P2 1 4
P3 2 9
 P3 = 17-2 = 15 ms
P4 3 5  P4 = 5-3 = 2 ms
 Avg. Waiting Time =
(9+0+15+2) / 4 = 6.5 ms
Example
Process Arrival Time Processing Time

A 0 3

B 1 6

C 4 4

D 6 2

•For the processes listed in the following table,

•which of the following scheduling scheme will give the lowest average turnaround time?
1.First Come First Serve
2.Non-Preemptive Shortest Job First
3.Shortest Remaining Time First/ Preemptive SJF
Example
Process Arrival Time Processing Time

A 0 3

B 1 6

C 4 4

D 6 2

•For the processes listed in the following table,

•which of the following scheduling scheme will give the lowest average turnaround time?
1.First Come First Serve (A. W. T. = 3.5, A.T.T. = 7.25)
2.Non-Preemptive Shortest Job First (A.W.T.= 3, A.T.T. =6.75)
3.Shortest Remaining Time First/ Preemptive SJF (A.W.T. = 2.5, A.T.T. = 6.25)
FCFS
Non-Preemptive SJF
Preemptive SJF (SRTF)
SRTF (Shortest Remaining Time First)
 SRTF is Preemptive counter part of SJF
 SRTF is useful in time-sharing environment
 Advantages:
 In SRTF, process with the smallest estimated burst time
completes first, including new arrivals
 In SRTF, running process may be preempted with the
arrival of new process with shortest estimated time.
 Superior turnaround time than SJF

 Disadvantages:
 SRTF has higher overload than SJF.

 SRTF must keep track of the elapsed time of the running

process and must handle preemptions.
Round-Robin Scheduling Algorithm
 Specially designed for Time-Sharing Systems
 Same as FCFS but preemption is added to switch
between processes
 A small unit of time called a time quantum (or time slice) is
defined.
 In this algorithm Ready queue is assumed to be a circular
queue
 To implement RR scheduling, Ready queue as FIFO queue
of the processes
 New processes are added to the tail of the ready queue
 The CPU scheduler picks the first process from the ready
queue, sets a timer to interrupt after 1 time quantum, and
dispatches.
Round-Robin Scheduling Algorithm
 One of the two things may happen
 The Process may have a CPU burst of less than 1
time quantum. In this case, the process itself will
release the CPU voluntarily.
 The scheduler will than processed to the next process
in the ready queue.
 If the CPU burst of the currently running process is
longer than 1 time quantum, the timer will go off and
will cause an interrupt to the OS.
 The average waiting time under RR is often, quite
long.
Example RR

Process Burst Time  Arrival Time is 0 ms and

P1 20 order is P1,P2,P3 and time
P2 3
quantum of 4 ms
P3 4
 Waiting Time for
 P1 = 0 ms + (11 - 4) ms = 7 ms
 P2 = 4 ms
 P3 = 7 ms
 Avg waiting Time
= (7 + 4+ 7)/3
= 6 ms
Example RR

Process Burst Time  Arrival Time 0 ms and

P1 3 Time quantum is 2 ms
P2 6
P3 4
 Waiting Time for
P4 2  P1 = 0 + (8-2) = 6 ms
 P2 = 2 + (9-4) +(13-11)
=9
 P3 = 4 + (11-6) = 9
 P4 = 6
 Avg waiting Time =
(6+9+9+6) /4 = 7.5 ms
Example RR

Process Burst Time  Arrival Time 0 ms and

P1 3 Time quantum is 2 ms
P2 6
P3 4
 Arrival Time 0 ms and
P4 2 Time quantum is 4 ms
Example RR
 Turn around Time
Process Burst Time  P1 = 3 + 6 = 9
P1 3
P2 6  P2 = 6+ 9 = 15
P3 4
 P3 = 4+9 = 13
P4 2
 P4 = 2+6 = 8

 Avg Turn around Time

= (9+15+13+8) /4
= 11.25 ms
Round-Robin Scheduling Algorithm
 In the RR scheduling algorithm, no process is
allocated the CPU for more than 1 time quantum in a
row (unless it is the only runnable process).
 If a process's CPU burst exceeds 1 time quantum, that
process is preempted and is put back in the ready
queue.
 The RR scheduling algorithm is thus preemptive.
Round-Robin Scheduling Algorithm
 If 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.
 Each process must wait no longer than (n - 1) x q time units
until its next time quantum.
Round-Robin Scheduling Algorithm
 If the time quantum is very high, then it becomes
FCFS
 If the time quantum is very short, then short processes
will move through the system relatively quickly.
 It increases the processing overhead involved in
handling the clock interrupt and performing the
scheduling and dispatch function.
 Thus very short time quantum should be avoided.
RR Scheduling

 Example

Process Burst Time

P1 24
P2 3
P3 3

 Suppose that processes arrive at time 0ms

 Time quantum 4ms
Example RR
Example
Process Arrival Time Processing Time

A 0 3

B 1 6

C 4 4

D 6 2

•For the processes listed in the following table,

•which of the following scheduling scheme will give the lowest average turnaround time?
1.First Come First Serve (A. W. T. = 3.5, A.T.T. = 7.25)
2.Non-Preemptive Shortest Job First (A.W.T.= 3, A.T.T. =6.75)
3.Shortest Remaining Time First/ Preemptive SJF (A.W.T. = 2.5, A.T.T. = 6.25)
4.Round Robin with Quantum value two
RR
Example
 Five processes A through E arrive with following details.
Process Arrival Time CPU Time
A 0 9
B 1 5
C 2 2
D 3 6
E 4 8

 Calculate the Turnaround Time and Waiting Time for all processes applying
A. First Come First Serve algorithm (FCFS)
B. Shortest Job First algorithm (SJF)
C. Shortest Remaining Time First (SRTF)
D. Round Robin algorithm (with Time Quanta=3, Quanta=6, Quanta=10) (RR)
FCFS
Non-Preemptive SJF
Preemptive SJF
RR (time quanta = 3)
RR (time quanta = 6)
RR (time quanta = 10)
Comparison FCFS & RR
SR. FCFS RR
No.
1 FCFS is non-preemptive RR is preemptive

2 Minimum overhead Low overhead

3 Response Time may be high Provides good response time

for short processes
4 Not used for time-sharing Designed for time-sharing
system system
5 Simply Processed in the Like FCFS but uses time-
arrival order quantum
6 No starvation in FCFS No starvation in RR
Priority Scheduling Algorithm
 A Priority is attached with each process, and CPU is
allocated to the process with the highest priority.
 Equal priority processes are scheduled in FCFS order.
 Priorities are generally some fixed range of numbers
such as 0 to 7.
 Priority Scheduling is preemptive or non-preemptive.
 Non-Preemptive will simply put the new process at the
head of the ready queue
 Preemptive will preempt the CPU if the priority of the
newly arrived process is higher than the priority of the
currently running process.
Example Priority
 Arrival Time is 0 ms
Process
P1
Burst-Time
10
Priority
3
 Order is P1,P2,…P5
P2 1 1  Low number represents
P3 2 4
higher priority
P4 1 5
P5 5 2  Waiting Time for
 P1 = 6 ms
 P2 = 0 ms
 P3 = 16 ms
 P4 = 18 ms
 P5 = 1 ms
 Avg. Waiting Time =
(6+0+16+18+1) / 5 = 8.2 ms
Example Priority
Process Burst-Time Priority Arrival time
P1 10 3 0
P2 5 2 1
P3 2 1 2
Example Priority
 Waiting Time for
Process Burst-Time Priority Arrival time
 P1 = 0 ms +(8-1) ms =
P1 10 3 0
P2 5 2 1
7 ms
P3 2 1 2  P2 = (4-2) ms = 2 ms

 P3 = (2-2) ms = 0 ms

 Avg. Waiting Time

 = (7+2+0) / 3= 3 ms
Example Priority
 Arrival Time is 0 ms
Process Burst-Time Priority
P1 3 2
 Order is P1,P2,P3,P4
P2 6 4
P3 4 1
P4 2 3
Example Priority
 Arrival Time is 0 ms
Process Burst-Time Priority
P1 3 2
 Order is P1,P2,P3,P4
P2 6 4  Waiting Time for
P3 4 1
 P1 = 4 ms
P4 2 3
 P2 = 9 ms
 P3 = 0 ms
 P4 = 7 ms
 Average waiting Time
= 4+9+0+7 / 4
= 5 ms
Example Priority
 Turnaround Time
Process Burst-Time Priority
 P1 = 3 + 4 ms = 7 ms
P1 3 2
P2 6 4
 P2 = 6 + 9 ms = 15 ms
P3 4 1  P3 = 4 + 0 ms = 4 ms
P4 2 3  P4 = 2 + 7 ms = 9 ms
 Average Turnaround Time
= 7+15+4+9 / 4
= 8.75 ms
Problem with Priority Scheduling Algorithm
 The Problem with Priority scheduling algorithm arises
when it becomes the biggest cause of starvation of a
process.
 If a process is in ready state but its execution is almost
always preempted, due to the arrival of higher priority
processes. It will starve for its execution.
 Therefore, a mechanism called “ageing” has to be built
into the system so that almost every process should
get the CPU in a fixed interval of time.
 This can be done by increasing the priority of a low-
priority process after a fixed interval of time, so that at
one moment of time it becomes a high-priority process
compared to others and thus, finally gets CPU for its
execution.