Process Scheduling Algorithms

What is process scheduling?

What is process scheduling?
• Process scheduling is the activity of the
process manager that handles suspension of
running process from CPU and selection of
another process on the basis of a particular
strategy.
• The part of operating system that makes the
choice is called scheduler.
• The algorithm used by this scheduler is called
scheduling algorithm.
• Process scheduling is an essential part of a
multiprogramming operating systems.
Objectives (goals) of scheduling
Objectives (goals) of scheduling
• Fairness: giving each process a fair share of the CPU.
• Balance: keeping all the parts of the system busy (Maximize).
• Throughput: no of processes that are completed per time unit (Maximize).
• Turnaround time: time to execute a process from submission to completion
(Minimize).
• Turnaround time = Process finish time – Process arrival time
• CPU utilization: percent of time that the CPU is busy in executing a process.
• keep CPU as busy as possible (Maximized).
• Response time: time between issuing a command and getting the result
(Minimized).
• Waiting time: amount of time a process has been waiting in the ready queue
(Minimize).
• Waiting time = Turnaround time – Actual execution time
Types of schedulers
Types of schedulers

Long Term Short Term

Scheduler Scheduler
Ready Queue
Admit Dispatch Exit
Processor

Medium Term Time-out

Scheduler

Event Wait
Event
Occurs Blocked Queue
Types of schedulers
Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler
It is a job scheduler. It is a CPU scheduler. It is a process swapping
scheduler.
It selects processes from pool It selects those processes It can re-introduce the process
and loads them into memory which are ready to execute. into memory and execution
for execution. can be continued.
Speed is lesser than short term Speed is fastest among other Speed is in between both short
scheduler. two schedulers. and long term scheduler.
It is almost absent or minimal It is also minimal in time It is a part of time sharing
in time sharing system. sharing system. systems.
Preemptive and Non-preemptive Scheduling

91
Scheduling algorithms
Scheduling algorithms
1. First Come First Served (FCFS)
2. Shortest Job First (SJF)
3. Shortest Remaining Time Next (SRTN)
4. Round Robin (RR)
5. Priority
I. Preemptive
II. Non-Preemptive
First Come First Served (FCFS)
First Come First Served (FCFS)
• Selection criteria:
• The process that request first is served first.
• It means that processes are served in the exact order of their arrival.
Ready queue

P0 Head P1 P2 Tail P3

• Decision Mode:
• Non preemptive: Once a process is selected, it runs until it is blocked for an I/O or some
other event or it is terminated.
• Implementation:
• This strategy can be easily implemented by using FIFO (First In First Out) queue.
• When CPU becomes free, a process from the first position in a queue is selected to run.
First Come First Served (FCFS)
Process Arrival Time Burst Time Finish Time Turnaround Time Waiting Time
(T0) (ΔT) (T1) (TAT = T1 - T0) (WT = TAT - ΔT)
P0 0 10 10 10 0

P1 1 6 16 15 9

P2 3 2 18 15 13

P3 5 4 22 17 13

• Gantt Chart P0 P1 P2 P3
0 10 16 18 22

• Average Turnaround Time: (10+15+15+17)/4 = 14.25 ms.

• Average Waiting Time: (0+9+13+13)/4 = 8.75 ms.
First Come First Served (FCFS)
• Advantages
• Simple and fair.
• Easy to understand and implement.
• Every process will get a chance to run, so starvation doesn't occur.
• Starvation is the problem that occurs when high priority processes keep executing and low priority processes
get blocked for indefinite time.
• Disadvantages
• Not efficient because average waiting time is too high.
• Convoy effect is possible. All small I/O bound processes wait for one big CPU bound process to
acquire CPU.

• CPU utilization may be less efficient especially when a CPU bound process is running with many I/O
bound processes.
Shortest Job First (SJF)
Shortest Job First (SJF)
• Selection criteria:
• The process, that requires shortest time to complete execution, is served first.
Ready queue

P0 (4) Head P1 (2) P2 (6) Tail P3 (3)

• Decision Mode:
• Non preemptive: Once a process is selected, it runs until it is blocked for an I/O or some
other event or it is terminated.
• Implementation:
• This strategy can be easily implemented by using sorted FIFO (First In First Out) queue.
• All processes in a queue are sorted in ascending order based on their required CPU bursts.
• When CPU becomes free, a process from the first position in a queue is selected to run.
Shortest Job First (SJF)
Process Arrival Time Burst Time Finish Time Turnaround Time Waiting Time
(T0) (ΔT) (T1) (TAT = T1 - T0) (WT = TAT - ΔT)
P0 0 10 10 10 0

P1 1 6 22 21 15

P2 3 2 12 9 7

P3 5 4 16 11 7

• Gantt Chart P0 P2 P3 P1
0 10 12 16 22

• Average Turnaround Time: (10+21+9+11)/4 = 12.75 ms.

• Average Waiting Time: (0+15+7+7)/4 = 7.25 ms.
Shortest Job First (SJF)
• Advantages
• Less waiting time.
• Good response for short processes.
• Disadvantages
• It is difficult to estimate time required to complete execution.
• Starvation is possible for long process. Long process may wait forever.
• Starvation is the problem that occurs when high priority processes keep executing and low priority
processes get blocked for indefinite time.
Shortest Remaining Time Next (SRTN)
Shortest Remaining Time Next (SRTN)
• Selection criteria:
• The process, whose remaining run time is shortest, is served first. This is a preemptive version of
SJF scheduling.
Ready queue

P0 (2) Head P1 (2) P2 (6) Tail P3 (1)

• Decision Mode:
• Preemptive: When a new process arrives, its total time is compared to the current process
remaining run time.
• If the new process needs less time to finish than the current process, the current process is
suspended and the new job is started.
• Implementation:
• This strategy can also be implemented by using sorted FIFO queue.
• All processes in a queue are sorted in ascending order on their remaining run time.
• When CPU becomes free, a process from the first position in a queue is selected to run.
Shortest Remaining Time Next (SRTN)
Process Arrival Time Burst Time Finish Time Turnaround Time Waiting Time
(T0) (ΔT) (T1) (TAT = T1 - T0) (WT = TAT - ΔT)
P0 0 10 22 22 12

P1 1 6 9 8 2

P2 3 2 5 2 0

P3 5 4 13 8 4

P0 P1 P2 P1 P3 P0
• Gantt Chart 0 1 3 5 9 13 22
Process Remaining
Process
Process Time
Remaining
Remaining Time
Time Remaining
Process Process Time
Remaining Time
P1 P0 6 P0 9 9P0 9P0 9
• Average Turnaround Time: 10 ms P0 P2 9 P1 2 4P3 4
• Average Waiting Time: 4.5 ms P1 P3 4 4
Shortest Remaining Time Next (SRTN)
• Advantages
• Less waiting time.
• Quite good response for short processes.
• Disadvantages
• It is difficult to estimate time required to complete execution.
• Starvation is possible for long process. Long process may wait forever.
• Starvation is the problem that occurs when high priority processes keep executing and low priority
processes get blocked for indefinite time.
• Context switch overhead is there.
Round Robin (RR)
Round Robin (RR)
• Selection criteria:
• Each selected process is assigned a time interval, called time quantum or time slice.
• Process is allowed to run only for this time interval.
• Here, two things are possible:
• First, process is either blocked or terminated before the quantum has elapsed. In this case the CPU
switching is done and another process is scheduled to run.
Ready queue & Quantum = 3
P0 (2) Head P1 (2) P2 (6) Tail P3 (1)

• Second, process needs CPU burst longer than time quantum. In this case, process is running at the
end of the time quantum.
• Now, it will be preempted and moved to the end of the queue.
• CPU will be allocated to another process.
• Here, length of time quantum is critical to determine.
Ready queue & Quantum = 3
P0 (1) P1 (2) P2 (6) Tail P3 (1)
Head
P0 (4) Ready queue & Quantum = 3
Round Robin (RR)
• Decision Mode:
• Preemptive: When a new process arrives, its total time is compared to the current process
remaining run time.
• Selection of new job is as per FCFS scheduling algorithm.
• Implementation:
• This strategy can be implemented by using circular FIFO queue.
• If any process comes, or process releases CPU, or process is preempted. It is moved to the
end of the queue.
• When CPU becomes free, a process from the first position in a queue is selected to run.
Round Robin (RR)
Process Arrival Time Burst Time Finish Time Turnaround Time Waiting Time
(T0) (ΔT) (T1) (TAT = T1 - T0) (WT = TAT - ΔT)
P0 0 10 28 28 18

P1 1 6 25 24 18

P2 3 2 12 9 7

P3 5 4 22 17 13

P0 P1 P2 P0 P3 P1 P0

• Gantt Chart
▪ Quantum time is 4 ms &
▪ Context switch overhead is 1 ms

• Avg. Turnaround Time: 19.5 ms

• Avg. Waiting Time: 14 ms
0 4 5
9
Process Remaining Time
10 12
P1 6
Process Remaining Time
P2 2 13
P2 2 17
P0 6 Process Remaining Time 18 22
P0 6
P0 6 Process Remaining Time
P3 4 23 25
P3 4 P3 4 26
P1 2
Process Remaining Time 28
P1 2 P1 2 P1 2 Process Remaining Time
P0 2 P0 2 P0 2
Round Robin (RR)
• Advantages
• Simplest, fairest and most widely used algorithms.
• Disadvantages
• Context switch overhead is there.
• Determination of time quantum is too critical.
• If it is too short, it causes frequent context switches and lowers CPU efficiency.
• If it is too long, it causes poor response for short interactive process.
Priority
(Non-Preemptive Priority)
Non-Preemptive Priority
• Selection criteria:
• The process, that has highest priority, is served first.
Ready queue

P0 (2) Head P1 (8) P2 (6) Tail P3 (7)

• Decision Mode:
• Non preemptive: Once a process is selected, it runs until it is blocked for an I/O or some
other event or it is terminated.
• Implementation:
• This strategy can also be implemented by using sorted FIFO queue.
• All processes in a queue are sorted based on their priority with highest priority process at
front end.
• When CPU becomes free, a process from the first position in a queue is selected to run.
Non-Preemptive Priority
Process Arrival Time Burst Time Priority Finish Time Turnaround Time Waiting Time
(T0) (ΔT) (T1) (TAT = T1 - T0) (WT = TAT - ΔT)
P0 0 10 5 10 10 0

P1 1 6 4 22 21 15

P2 3 2 2 16 13 11

P3 5 4 0 14 9 5

• Gantt Chart (small values for priority means higher priority of a process)
P0 P3 P2 P1
• Avg. Turnaround Time: 13.25 ms 0 10 14 16 22
• Avg. Waiting Time: 7.75 ms
Non-Preemptive Priority
• Advantages
• Priority is considered so critical processes can get even better response time.
• Disadvantages
• Starvation is possible for low priority processes. It can be overcome by using technique
called ‘Aging’.
• Aging: gradually increases the priority of processes that wait in the system for a long
time.
Priority
(Preemptive Priority)
Preemptive Priority
• Selection criteria:
• The process, that has highest priority, is served first.
Ready queue

P0 (7) Head P1 (5) P2 (4) Tail P3 (8)

• Decision Mode:
• Preemptive: When a new process arrives, its priority is compared with current process priority.
• If the new process has higher priority than the current, the current process is suspended and new
job is started.
• Implementation:
• This strategy can also be implemented by using sorted FIFO queue.
• All processes in a queue are sorted based on their priority with highest priority process at front
end.
• When CPU becomes free, a process from the first position in a queue is selected to run.
Preemptive Priority
Process Arrival Time Burst Time Priority Finish Time Turnaround Time Waiting Time
(T0) (ΔT) (T1) (TAT = T1 - T0) (WT = TAT - ΔT)
P0 0 10 5 22 22 12

P1 1 6 4 13 12 6

P2 3 2 2 5 2 0

P3 5 4 0 9 4 0

P0 P1 P2 P3 P1 P0
• Gantt Chart 0 1 3 5 9 13 22
• small values means higher priority ProcessProcess
Priority
Process
Priority Priority
Process Priority
Process Priority
P1 P0 4 P05 5P0 5P0 5
• Avg. Turnaround Time: 10 ms
P0 P2 5 P12 4P1 4
• Avg. Waiting Time: 4.5 ms P1 P34 0
Preemptive Priority
• Advantages
• Priority is considered so critical processes can get even better response time.
• Disadvantages
• Starvation is possible for low priority processes. It can be overcome by using technique
called ‘Aging’.
• Aging: gradually increases the priority of processes that wait in the system for a long
time.
• Context switch overhead is there.