OPERATING SYSTEM
CSET209
CPU SCHEDULING ALGORITHMS
OUTLINE
CPU Scheduling Algorithms
Shortest Remaining Time First (SRTF)
Priority scheduling
Round Robin scheduling
Shortest Remaining Time First (SRTF)
This algorithm is pre-emptive version of SJF algorithm.
The process will be allocated to CPU which is near to its completion.
This does not allow new, ready processes to hold the completion of older processes.
Characteristics:
This algorithm is applied where short jobs are needed to be given preference.
A process closer to completion is allocated, but it can be preempted by a newly ready
process, with less completion time.
Impossible to implement if CPU Time is not known.
Quiz
Process Arrival Time Burst Time
1. Consider four processes: P1, P2, P3, and P1 0 7
P4. Calculate the average waiting time P2 2 4
using preemptive Shortest Job First (SJF). P3 4 1
P4 5 4
2. Consider three processes P1, P2 and P3.
Calculate the average waiting time using
SRTF.
PRIORITY SCHEDULING
A priority number (integer) is associated with each process. VM1
The CPU is allocated to the process with the highest priority (smallest
integer = highest priority)
It can also be of two types:
Preemptive
Non-preemptive
In FCFS, there are equal priority processes.
Slide 13
VM1 However, there is no general agreement on whether 0 is the
highest or lowest priority. Some systems use low numbers to represent low
priority; others use low numbers for high priority
Vivek Mehta, 2/5/2023
PRIORITY SCHEDULING
Priority can be defined either internally or externally
Internally, priority can be computed on the basis of some measurable quantity like
Time limit, memory requirements, number of open files, etc.
Externally, priority can be set by criteria such as
Urgency, importance of the process,, etc.
Problem: Starvation – low priority processes may never execute
Solution: Aging – as time progresses increase the priority of the process.
For example, if priorities range from 127 (low) to 0 (high), we could increase the priority of a waiting process by 1
every 15 minutes. Eventually, even a process with an initial priority of 127 would have the highest priority in the
system and would be executed. (~32 hours for a priority-127 process).
PRIORITY SCHEDULING
PRIORITY SCHEDULING
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
PRIORITY SCHEDULING
PRIORITY SCHEDULING
Process Priority Burst time Arrival time
P1 1 4 0
P2 2 3 0
P3 1 7 6
P4 3 4 11
P5 2 2 12
Considering preemptive priority scheduling, calculate
average waiting time?
VM2
ROUND ROBIN SCHEDULING
Round Robin scheduling = FCFS + Preemption
Designed for time sharing systems
A small unit of time called time quantum/time slice is defined
Each process gets the CPU for this fixed time quantum during which it executes and after that it is
preempted and added to the end of ready queue. Timer interrupts every quantum to schedule next
process.
Lets say there are n processes in ready queue and time quantum is q time units,
Then, each process can execute for at most q time on CPU.
Each process gets 1/n x (CPU time) in chunks of at most q time units at a time.
No process has to wait for more than (n-1)q time (considering no context switch time)
Slide 19
VM2 In our next topic we see an algortihm which is expecially designed for multi-tasking operating systems. The
name is round robin
Vivek Mehta, 2/5/2023
VM5
ROUND ROBIN SCHEDULING
Implementation:
Ready queue is treated as a FIFO queue of processes.
New processes are added to the tail of the ready queue.
If the CPU burst of the currently running process is longer than 1 time quantum, a context
switch will be executed and the current process will be put at the tail of the ready queue.
The CPU scheduler will then select the next process from the ready queue.
Slide 20
VM5 In our next topic we see an algortihm which is expecially designed for multi-tasking operating systems. The
name is round robin
Vivek Mehta, 2/5/2023
ROUND ROBIN SCHEDULING
Time Quantum =20
Waiting time
Assume arrival time = 0 for all process
P1 = 57+24 = 81
Neglect context switch time for simplicity
From t=20 to t =77
Process Burst Time From t=97 to t=121
P1 53 P2 = 20
P2 17
from t=0 to t =20
P3 68
P3 = 37+40+17 = 97
P4 24
Form t=0 to t 37
From t=57 to t =97
From t =117 to t =134
P4 = 57+40 = 97
From t=0 to t = 57
From t=77 to t=117
Avg waiting time: (81 + 20 + 94 + 97)/4 = 73
ROUND ROBIN SCHEDULING
Advantages: No starvation, fair time and resource sharing, and good response time
Disadvantages: High avg turnaround time than SRTF, does not consider priority.
Performance:
If q is large, RR becomes FCFS and leads to poor waiting time
If q is small, overhead is too high and inefficient CPU utilization (q must be large than
context switch time).
Usually, q =10 to 100 milliseconds, and Context switch < 10 microseconds
Round Robin Scheduling
Time quantum and Context switch
Round Robin Scheduling
Consider the set of 5 processes whose arrival time and burst time are given below-
Process Id Arrival time Burst time
P1 0 5
P2 1 3
P3 2 1
P4 3 2
P5 4 3
If the CPU scheduling policy is Round Robin with a time quantum of 2 units, calculate
the average waiting time and average turnaround time.
Round Robin Scheduling
ROUND ROBIN SCHEDULING: SAMPLE PROBLEM
Turn Around time = Exit time – Arrival time
Waiting time = Turn Around time – Burst time
ROUND ROBIN SCHEDULING: SAMPLE PROBLEM
Process Id Exit time Turn Around time Waiting time
P1 13 13 – 0 = 13 13 – 5 = 8
P2 12 12 – 1 = 11 11 – 3 = 8
P3 5 5–2=3 3–1=2
P4 9 9–3=6 6–2=4
P5 14 14 – 4 = 10 10 – 3 = 7
Average Turn Around time = (13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6 unit
Average waiting time = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit
THANK YOU
?
