Operating Systems

Process Scheduling

Dr. Pradeep K V
Associate Professor (Sr.)
School of Computer Science and Engineering
VIT - Chennai

Dr. Pradeep K V Operating Systems 1/ 77

Contents

Introduction to Process Scheduling

Scheduler and its Types
CPU Scheduling and its types
First Come First Serve
Short Job First
Preemptive and Non Preemptive
Priority
Round Robin
Multi-Level Queuing
Multi-Level Feedback Queuing
DeadLock
DeadLock Prevention
DeadLock Avoidance
DeadLock Detection and Recovery

Dr. Pradeep K V Operating Systems 2/ 77

Process Scheduling

It is the process of removing the running task from the processor and
selecting another task for processing. It schedules a process into different
states like ready, waiting, and running.
It’s a crucial component of a multiprogramming OS. It makes use of a
variety of scheduling queues (Job Queue, Waiting Queue, Device
Queue...).
The scheduler’s purpose is to implement the virtual machine so that each
process appears to be running on its own computer to the user.

Scheduling Categories
Non-preemptive : The resource can’t be taken from a process until the
process completes execution. The switching of resources occurs when the
running process terminates and moves to a waiting state.
Preemptive : The OS allocates the resources to a process for a fixed
amount of time. During resource allocation, the process switches from
running state to ready state or from waiting state to ready state.

Dr. Pradeep K V Operating Systems 3/ 77

Process Scheduling Queues

There are multiple states a process has to go through during execution. The
OS maintains a separate queue for each state along with the process control
blocks (PCB) of all processes. The PCB moves to a new state queue, after
being unlinked from its current queue, when the state of a process changes.

Job queue: Makes sure that processes stay in the system.

Ready queue: This stores a set of all processes in main memory, ready and
waiting for execution. The ready queue stores any new process.
Device queue: This queue consists of the processes blocked due to the
unavailability of an I/O device.

Dr. Pradeep K V Operating Systems 4/ 77

Process Scheduler

Dr. Pradeep K V Operating Systems 5/ 77

Types of Schedulers

Figure: Short and Long Term Scheduler

Figure: Middle Term Scheduler

Dr. Pradeep K V Operating Systems 6/ 77

1 Long Term Scheduler: (Job Schedular) It determines which program
should be admitted to the system for processing. It selects and loads the
processes into the memory for execution with the help of CPU scheduling.
It provides a balanced combo of jobs, such as I/O bound and processor
bound and controls the degree of multiprogramming.
A stable degree of multiprogramming means that the average rate of
process creation and the average departure rate of processes leaving the
system is equal. Many systems like time-sharing OS, do not have a long
term scheduler as it is only required when a process changes its state from
new to ready.
2 Short Term Scheduler: (CPU Schedular) It increases system performance
as per the chosen set of criteria. This is the change of ready state to
running state of the process.
It selects a process from the multiple processes that are in ready state in
order to execute it and also allocates the CPU to one of them. It is faster
than long-term schedulers and is also called a dispatcher as it makes the
decision on which process will be executed next.
3 Medium Term Scheduler: It removes processes from the memory and is
a part of swapping. It reduces the degree of multiprogramming and is
in-charge of handling the swapped out processes. Swapping is necessary to
improve the process mix.

Dr. Pradeep K V Operating Systems 7/ 77

Differences b/w Schedulers

Table: Long-Term Vs Short-Term Vs Medium-Term

Parameters Long-Term Short-Term Medium-Term

Type of
Job scheduler. CPU scheduler. Swapping scheduler.
Scheduler
Its speed is slowee It is the fastest Its speed is in b/w
Speed than that of the among both Long Term and
Short-Term scheduler. the other two. Short-Term .
It helps in controlling It provides much less It reduces the
Purpose the overall degree control over the degree overall degree of
of multiprogramming. of multiprogramming. multiprogramming.
Minimal
time-sharing Almost absent Minimal Present
system
Selects processes from Selects all those
Can re-introduce the
the pool and then loads processes that are
Function given process into
them into the ready
memory. .
memory for execution. to be executed.

Dr. Pradeep K V Operating Systems 8/ 77

Dispatcher

The dispatcher is done after the scheduler. It gives control of the CPU to the
process selected by the short-term scheduler. After selecting the process, the
dispatcher gives CPU to it.

Functions: The functions of the dispatcher are as follows :

Switching context.
Switching to user mode.

A dispatcher performs various tasks, including context switching, setting up

user registers and memory mapping. These are necessary for the process to
execute and transfer CPU control to that process. When dispatching, the
process changes from the ready state to the running state.

Dr. Pradeep K V Operating Systems 9/ 77

CPU Scheduling

Definition..!
It is a process that allows one process to use the CPU while the execution of
another process is on hold(in waiting state) due to unavailability of any
resource like I/O etc, thereby making full use of CPU.

The aim of CPU scheduling is to make the system efficient, fast, and fair. And
decisions may take place under the following four circumstances:
1 When a process switches from the running state to the waiting state(for
I/O request or invocation of wait for the termination of one of the child
processes).
2 When a process switches from the running state to the ready state (for
example, when an interrupt occurs).
3 When a process switches from the waiting state to the ready state(for
example, completion of I/O).
4 When a process terminates.
In circumstances 1 and 4 [Non-Preemptive], there is no choice in terms of
scheduling. A new process(if one exists in the ready queue) must be selected for
execution. There is a choice, however in circumstances 2 and 3 [Preemptive].
Dr. Pradeep K V Operating Systems 10/ 77
Preemptive and Non-Preemptive

Consider the below example :

Arrival CPU Burst
Process
Time Time
P0 3 2
P1 2 4
P2 0 6
P3 1 4

Figure: Gant Chart : Non Preemptive

Figure: Gant Chart : Preemtive

Dr. Pradeep K V Operating Systems 11/ 77

Preemptive Verses Non Preemptive I

PREEMPTIVE NON-PREEMPTIVE
Parameter
SCHEDULING SCHEDULING
CPU’s are allocated to a process,
CPU’s are allocated to a the process holds it till it
Basic
process for a limited time. completes its burst time or
switches to waiting state.
Process can be
Interrupt No Interrupt
interrupted in between.
If a process having high If a process with a long
priority frequently arrives burst time is running CPU,
Starvation in the ready queue, then later coming process
a low priority process with less CPU burst time
may starve. may starve.
Overhead Yes No
Flexibility flexible rigid
Cost cost associated no cost associated

Dr. Pradeep K V Operating Systems 12/ 77

Preemptive Verses Non Preemptive II

CPU
High Low.
Utilization
Waiting
Less High
Time
Response
Less High
Time
Decisions are made by the Decisions are made by the
Decision scheduler and are based process itself and the OS
making on priority and time slice just follows the process’s
allocation instructions
Process OS has greater control over The OS has less control over
control the scheduling of processes the scheduling of processes
Round Robin and
Examples FCFS
Shortest Remaining Time First.

Dr. Pradeep K V Operating Systems 13/ 77

CPU Scheduling Algorithms

Figure: Type of CPU Scheduling Algorithms

Dr. Pradeep K V Operating Systems 14/ 77

CPU Scheduling: Scheduling Criteria

CPU Utilization : To make out the best use of the CPU and not to waste
any CPU cycle, the CPU would be working most of the time(Ideally 100%
of the time). Considering a real system, CPU usage should range from
40% (lightly loaded) to 90% (heavily loaded.)
Throughput : It is the total number of processes completed per unit of
time or rather says the total amount of work done in a unit of time. This
may range from 10/second to 1/hour depending on the specific processes.
Turnaround Time : It is the amount of time taken to execute a particular
process, i.e. The interval from the time of submission of the process to the
time of completion of the process(Wall clock time).
Waiting Time : The sum of the periods spent waiting in the ready queue
amount of time a process has been waiting in the ready queue to acquire
get control on the CPU.
Load Average : It is the average number of processes residing in the
ready queue waiting for their turn to get into the CPU.
Response Time : Amount of time it takes from when a request was
submitted until the first response is produced. Remember, it is the time
till the first response and not the completion of process execution(final
response).
Dr. Pradeep K V Operating Systems 15/ 77
CPU Scheduling Algorithms - FCFS I

In the "First come first serve" scheduling algorithm, as the name suggests, the
process which arrives first, gets executed first, or we can say that the process
which requests the CPU first, gets the CPU allocated first. (FIFO - QUEUE).

Example : Buying tickets at ticket counter.

Characteristics of FCFS
It supports non-preemptive and preemptive CPU scheduling algorithms.
Tasks are always executed on a First-come, First-serve concept. FCFS is
easy to implement and use. [Using Queue Data Structure]
It is not much efficient in performance, and the wait time is quite high.
Advangtage of FCFS
Easy to implement in FCFS Order
DisAdvangtage of FCFS
FCFS suffers from Convoy effect.
The average waiting time is much higher than the other algorithms.
It is very simple and easy to implement, but not much efficient.

Dr. Pradeep K V Operating Systems 16/ 77

CPU Scheduling Algorithms - FCFS II

Consider the below example, where the processes are arrived in the order:
P1 , P2 , P3
Process Burst Time
P1 24
P2 3
P3 3
A Gantt chart is a commonly used graphical depiction of a Process schedule

Figure: FCFS - Gantt Chart

Waiting time for P1 = 0; P2 = 24; P3 = 27

Average waiting time: (0 + 24 + 27)/3 = 17
Turn Arround time for P1 = 24; P2 = 27; P3 = 30
Turn Arround time time: (24 + 27 + 30)/3 = 27

Dr. Pradeep K V Operating Systems 17/ 77

CPU Scheduling Algorithms - FCFS III

Consider the below example, where the processes are arrived in the order:
P1 , P2 , P3
Process Burst Time
P2 3
P3 3
P1 24
A Gantt chart is a commonly used graphical depiction of a Process schedule

Figure: FCFS - Gantt Chart

Waiting time for P2 = 0; P3 = 3; P1 = 6

Average waiting time: (0 + 3 + 6)/3 = 3
Turn Arround time for P1 = 30; P2 = 3; P3 = 6
Turn Arround time time: (30 + 3 + 6)/3 = 13

Dr. Pradeep K V Operating Systems 18/ 77

CPU Scheduling Algorithms - FCFS IV

Problems with FCFS Scheduling :

It is Non Pre-emptive algorithm, which means the process priority doesn’t
matter. If a process with very least priority is being executed, more like
daily routine backup process, which takes more time, and all of a sudden
some other high priority process arrives, like interrupt to avoid system
crash, the high priority process will have to wait, and hence in this case,
the system will crash, just because of improper process scheduling.
Not optimal Average Waiting Time.
Resources utilization in parallel is not possible, which leads to Convoy
Effect, and hence poor resource(CPU, I/O etc) utilization.

What is Convoy Effect? : Convoy Effect is a situation where many processes,

who need to use a resource for short time are blocked by one process holding
that resource for a long time.

This essentially leads to poort utilization of resources and hence poor

performance.

Dr. Pradeep K V Operating Systems 19/ 77

CPU Scheduling Algorithms - SJF I

It works on the process with the shortest burst time or duration first. And
minimizes waiting time and used in Batch Systems.
It is both Preemptive and Non-Preemptive.
To successfully implement it, the burst time/duration time of the
processes should be known to the processor in advance, which is
practically not feasible all the time.
It is optimal if all the jobs/processes are available at the same time.
(either Arrival time is 0 for all, or Arrival time is same for all)
Advantages of SJF:
It reduces the average waiting time thus, it is better than the first come
first serve scheduling algorithm.
It is generally used for long term scheduling
Disadvantages of SJF:
One of the demerit SJF has is starvation.
Many times it becomes complicated to predict the length of the upcoming
CPU request

Dr. Pradeep K V Operating Systems 20/ 77

CPU Scheduling Algorithms - SJF II

Non Preemptive SJF : Consider the below processes available in the ready
queue for execution, with arrival time as 0 for all and given burst times.
Process Burst Time
P1 21
P2 3
P3 6
P4 2

Waiting time for P4 = 0; P2 = 2; P3 = 5; P1 = 11

Average waiting time: (0 + 2 + 5 + 11)/4 = 4.5
Turn Arround time for P1 = 32; P2 = 5; P3 = 11; P4 = 2;
Turn Arround time time: (32 + 5 + 11 + 2)/4 = 12.5

Dr. Pradeep K V Operating Systems 21/ 77

CPU Scheduling Algorithms - SJF III

Problem with Non Preemptive SJF

If the arrival time for processes are different, which means all the processes
are not available in the ready queue at time 0, and some jobs arrive after
some time.
In such situation, sometimes process with short burst time have to wait for
the current process’s execution to finish, because in Non Pre-emptive SJF,
on arrival of a process with short duration, the existing job/process’s
execution is not halted/stopped to execute the short job first.
This leads to the problem of Starvation, where a shorter process has to
wait for a long time until the current longer process gets executed. This
happens if shorter jobs keep coming, but this can be solved using the
concept of aging.

Dr. Pradeep K V Operating Systems 22/ 77

CPU Scheduling Algorithms - SJF IV

Preemptive SJF : Here, jobs are put into ready queue as they arrive, but as
a process with short burst time arrives, the existing process is preempted or
removed from execution, and the shorter job is executed first.
Process Burst Time Arrival Time
P1 8 0
P2 4 1
P3 9 2
P4 5 3

Waiting time for P4 = (5-3) = 2; P2 = (1-1) = 0; P3 = (17-2) = 15;

P1 = (10-1) = 9;
Average waiting time: (2 + 0 + 15 + 9)/4 = 6.5
Turn Arround time for P1 = (17-1-0) = 16; P2 = (5-1) = 4;
P3 = (26-2) = 24; P4 = (10-3) = 7;
Turn Arround time time: (16 + 4 + 24 + 7)/4 = 12.75
Dr. Pradeep K V Operating Systems 23/ 77
CPU Scheduling Algorithms - Priority I

It works based on the priority of a process [ i.e, "The larger the burst
time the lower is the priority of that process."], and Preemptive and
Non-Preemptive.
A priority number (integer) is associated with each process
Characteristics of Priority Scheduling:
Schedules tasks based on priority.
When the higher priority work arrives while a task with less priority is
executed, the higher priority work takes the place of the less priority one
and the latter is suspended until the execution is complete.
Lower is the number assigned, higher is the priority level of a process.
Advantages of Priority Scheduling:
The average waiting time is less than FCFS and Less complex
Disadvantage of Priority Scheduling:
Problem "Starvation" : low priority processes may never execute
Solution "Aging" : as time progresses increase the priority of the process

Dr. Pradeep K V Operating Systems 24/ 77

CPU Scheduling Algorithms - Priority II

Types of Priority Scheduling Algorithm

Preemptive: If the new process arrived at the ready queue has a higher
priority than the currently running process, the CPU is preempted, which
means the processing of the current process is stoped and the incoming
new process with higher priority gets the CPU for its execution.
Non-Preemptive : If a new process arrives with a higher priority than the
current running process, the incoming process is put at the head of the
ready queue, which means after the execution of the current process it will
be processed.

Dr. Pradeep K V Operating Systems 25/ 77

CPU Scheduling Algorithms - Priority III

Consider the below table fo processes with their respective CPU burst times
and the priorities.
Process Burst Time Priority Time
P1 21 2
P2 3 1
P3 6 4
P4 2 3

Waiting time for P1 = 3; P2 = 0; P3 = 26; P4 = 24;

Average waiting time: (0 + 3 + 24 + 26)/4 = 13.25
Turn Arround time for P1 = 24; P2 = 3; P3 = 32; P4 = 26;
Turn Arround time time: (24 + 3 + 32 +26)/4 = 21.5

Dr. Pradeep K V Operating Systems 26/ 77

CPU Scheduling Algorithms - Priority IV

Consider the below table fo processes with their respective CPU burst times
and the priorities.
Process Burst Time Priority Time
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

Waiting time for P1 = 6; P2 = 0; P3 = 16; P4 = 18; P5 = 1

Average waiting time: (0 + 1 + 6 + 16 + 18)/5 = 8.5
Turn Arround time for P1 = 16; P2 = 1; P3 = 18; P4 = 19; P5 = 6
Turn Arround time time: (16 + 1 + 18 + 19 + 6)/5 = 12

Dr. Pradeep K V Operating Systems 27/ 77

CPU Scheduling Algorithms - Priority V

Non Preemptive Priority Scheduling : Consider the below table, consists of

processes P1 , P2 , P3 , P4 , P5 , P6 and P7 and their Priorities, Arrival Time and
burst time.
Process ID Priority Arrival Time Burst Time
P1 2 0 3
P2 6 2 5
P3 3 1 4
P4 5 4 2
P5 7 6 9
P6 4 5 4
P7 10 7 10

Turn Around Time = Completion Time - Arrival Time

Waiting Time = Turn Around Time - Burst Time

Dr. Pradeep K V Operating Systems 28/ 77

CPU Scheduling Algorithms - Priority VI

Table: Turnarround Time and Waiting Time

Process Arrival Burst Completion Turnaround Waiting

Priority
Id Time Time Time Time Time
1 2 0 3 3 3 0
2 6 2 5 18 16 11
3 3 1 4 7 6 2
4 5 4 2 13 9 7
5 7 6 9 27 21 12
6 4 5 4 11 6 2
7 10 7 10 37 30 18

Average Waiting Time == ?

Average TurnArround Time == ?

Dr. Pradeep K V Operating Systems 29/ 77

CPU Scheduling Algorithms - Priority VII

Preemptive Priority Scheduling : Consider the below table, consists of

processes P1 , P2 , P3 , P4 , P5 , P6 and P7 and their Priorities, Arrival Time and
burst time.
Process ID Priority Arrival Time Burst Time
P1 2 0 1
P2 6 1 7
P3 3 2 3
P4 5 3 6
P5 4 4 5
P6 10 5 18
P7 9 15 8

Dr. Pradeep K V Operating Systems 30/ 77

CPU Scheduling Algorithms - Priority VIII

Table: Turnarround Time and Waiting Time

Arrival Burst Completion Turn around Waiting

Process Priority
Time Time Time Time Time
1 2 0 1 1 1 0
2 6 1 7 22 21 14
3 3 2 3 5 3 0
4 5 3 6 16 13 7
5 4 4 5 10 6 1
6 10 5 15 45 40 25
7 9 6 8 30 24 16

Average Waiting Time == ?

Average TurnArround Time == ?

Dr. Pradeep K V Operating Systems 31/ 77

CPU Scheduling Algorithms - Round Robin I

It is mainly designed for time-sharing systems.

It is similar to FCFS scheduling, but in Round Robin(RR) scheduling,
preemption is added which enables the system to switch between
processes.
A fixed time is allotted to each process, called a quantum, for execution.
Once a process is executed for the given time period that process is
preempted and another process executes for the given time period.
Context switching is used to save states of preempted processes.
It is simple and easy to implement and the most important is thing is this
algorithm is starvation-free as all processes get a fair share of CPU.
It is important to note here that the length of time quantum is generally
from 10 to 100 milliseconds in length.

Important Terms
Completion Time : is the time, any process completes its execution.
Turn Around Time : Completion Time – Arrival Time
Waiting Time : Turn Around Time – Burst Time

Dr. Pradeep K V Operating Systems 32/ 77

CPU Scheduling Algorithms - Round Robin II

Dr. Pradeep K V Operating Systems 33/ 77

CPU Scheduling Algorithms - Round Robin III

Characteristics of Round Robin:

It resides under the category of Preemptive Algorithms. And oldest,
easiest, and fairest algorithm.
It is a real-time algorithm because it responds to the event within a
specific time limit.
Here, the time slice (Quantum) should be the minimum that is assigned to
a specific task that needs to be processed. Though it may vary for
different operating systems.
It is a hybrid model and is clock-driven in nature. And is a widely used
scheduling method in the traditional OS.
Let us consider the below example :
Process Burst Time
1 21
2 3
3 6
4 2

Note: If arrival time is not given, then consider it as 0. (For any Problem)

Dr. Pradeep K V Operating Systems 34/ 77

CPU Scheduling Algorithms - Round Robin IV

The below Gantt chart is based on Time Slice (Quantuam) = 5ms.

Table: Turnaround Time and Waiting Time

Burst Turn Around Waiting

Processes
Time Time Time
P1 21 32-0=32 32-21=11
P2 3 8-0=8 8-3=5
P3 6 21-0=21 21-6=15
P4 2 15-0=15 15-2=13

Dr. Pradeep K V Operating Systems 35/ 77

CPU Scheduling Algorithms - Round Robin V

Advantages
A fair amount of CPU is allocated to each job.
Because it doesn’t depend on the burst time, it can truly be implemented
in the system.
It is not affected by the convoy effect or the starvation problem as
occurred in First Come First Serve CPU Scheduling Algorithm.

Disadvantages
Low Operating System slicing times will result in decreased CPU output.
Round Robin CPU Scheduling approach takes longer to swap contexts.
Time quantum has a significant impact on its performance.
The procedures cannot have priorities established.

Dr. Pradeep K V Operating Systems 36/ 77

CPU Scheduling Algorithms - Round Robin VI

Consider the below Example-2 , where the time quantum of the system is 4
units.
Process ID Arrival Time Burst Time
1 0 5
2 1 6
3 2 3
4 3 1
5 4 5
6 6 4
Generate the Gantt Chart and verify with the below table table.
Process Arrival Burst Completion Turn Around Waiting
ID Time Time Time Time Time
1 0 5 17 17 12
2 1 6 23 22 16
3 2 3 11 9 6
4 3 1 12 9 8
5 4 5 24 20 15
6 6 4 21 15 11

Dr. Pradeep K V Operating Systems 37/ 77

CPU Scheduling Algorithms - Round Robin VII

Apply the Round Robin CPU Scheduling Algorithm to the Example-3 given
below, to determine the Average Waiting Time and Average Turn Arround
Time for the Time Slice (Quantum): 5 ms, 4 ms, and 2 ms, respectively.
Additionally, create a Gantt chart for the same.

Serial Process Arrival Burst

Number Id Time Time
1 P1 0 7
2 P2 1 4
3 P3 2 15
4 P4 3 11
5 P5 4 20
6 P6 4 9

Dr. Pradeep K V Operating Systems 38/ 77

CPU Scheduling Algorithms - Round Robin VIII

Apply the Round Robin CPU Scheduling Algorithm to the Example-4 & 5
given below, to determine the Average Waiting Time and Average Turn
Arround Time for the Time Slice (Quantum): 5 ms, 4 ms, and 2 ms,
respectively. Additionally, create a Gantt chart for the same.

Process Burst Time Arrival Time

P1 5 ms 0 ms
P2 4 ms 1 ms
P3 2 ms 2 ms
P4 1 ms 4 ms

Process name Arrival time Execute time

P0 0 250
P1 50 170
P2 130 75
P3 190 100
P4 210 130
P5 350 50

Dr. Pradeep K V Operating Systems 39/ 77

CPU Scheduling Algorithms - Mulitlevel Queue I

The ready queue consists of multiple queues

Multilevel queue scheduler defined by the following parameters
Number of queues
Scheduling algorithms for each queue
Method used to determine which queue a process will enter when that
process needs service
Scheduling among the queues
With priority scheduling, have separate queues for each priority.
Schedule the process in the highest-priority queue!

Dr. Pradeep K V Operating Systems 40/ 77

CPU Scheduling Algorithms - Mulitlevel Queue II

Prioritization based upon process type

Dr. Pradeep K V Operating Systems 41/ 77

CPU Scheduling Algorithms - Multilevel Feedback Queuing I

A process can move between the various queues.

Multilevel-feedback-queue scheduler defined by the following parameters:
Number of queues
Scheduling algorithms for each queue
Method used to determine when to upgrade a process
Method used to determine when to demote a process
Method used to determine which queue a process will enter when that
process needs service
Aging can be implemented using multilevel feedback queue
Example :
Three queues:
Q0 – RR with time quantum 8
milliseconds
Q1 – RR time quantum 16
milliseconds
Q2 – FCFS

Dr. Pradeep K V Operating Systems 42/ 77

 Operating Systems

Dead Locks

Dr. Pradeep K V
Associate Professor (Sr.)
School of Computer Science and Engineering
VIT - Chennai

Dr. Pradeep K V Operating Systems 43/ 77

What is Dead Lock?

Dr. Pradeep K V Operating Systems 44/ 77

Introduction to Deadlock? I

Every process needs some resources to complete its execution. However, the
resource is granted in a sequential order.
The process requests for some resource.
OS grant the resource if it is available otherwise let the process waits.
The process uses it and release on the completion.

A Deadlock is a situation where each of the process waits for a resource which
is being assigned to some another process. In this situation, none of the
process gets executed since the resource it needs, is held by some other process
which is also waiting for some other resource to be released.

Dr. Pradeep K V Operating Systems 45/ 77

Introduction to Deadlock? II

Sr. Deadlock Starvation

Deadlock is a situation where Starvation is a situation where
1 no process got blocked and the low priority process got blocked
no process proceeds and the high priority processes proceed.
Starvation is a long waiting
2 Deadlock is an infinite waiting.
but not infinite.
Every Deadlock is always Every starvation need
3
a starvation. not be deadlock.
The requested resource is The requested resource is continuously
4
blocked by the other process. be used by the higher priority processes.
Deadlock happens when
Mutual exclusion, hold and wait It occurs due to the uncontrolled
5
No preemption and circular wait priority and resource management.
occurs simultaneously.

Dr. Pradeep K V Operating Systems 46/ 77

Necessary conditions for Deadlocks
Mutual Exclusion A resource can only be shared in mutually exclusive
manner. It implies, if two process cannot use the same resource at the
same time.
Hold and Wait A process waits for some resources while holding another
resource at the same time.
No preemption The process which once scheduled will be executed till the
completion. No other process can be scheduled by the scheduler
meanwhile.
Circular Wait All the processes must be waiting for the resources in a
cyclic manner so that the last process is waiting for the resource which is
being held by the first process.

Dr. Pradeep K V Operating Systems 47/ 77

System Model

It is an ordered pair S(P,R);

System consists of various resources (Ri ) (CPU Cycles, Memory Space,
I/O Devices, and so on...) and a set of Process (Pi ), Where i = 1,2,3,4....
Each Resource types Ri have Wj instances.
Each process utilizes a resource as follows:
request
use
release

Dr. Pradeep K V Operating Systems 48/ 77

Resource Allocation Graph I

A Graph (G) can be defined as an ordered pair G(V,E), Where V - Set of

Vertices and E - Set of Edges.
A ’G’ is said to be Resource allocation Graph, if ’V’ - Set of Processes and
Resources and ’E’ - an Directed Edge b/w them.
The Vertices (V) = { P1 , P2 , ... Pn } and { R1 , R2 , ... Rm }, where ’i’ and
’j’ are instances of processes and resources respectively.
The Edges (E) :
Request Edge : Pi −→ Rj ; i.e., ith Process requesting jth resource.
Assignment Edge : Rj −→ Pi ; i.e., jth Resource assigned to ith process.

Dr. Pradeep K V Operating Systems 49/ 77

Resource Allocation Graph II

Figure: Single Instance RAG - No Deadlock

Dr. Pradeep K V Operating Systems 50/ 77

Resource Allocation Graph III

Figure: Multiple Instance RAG - No Deadlock

Dr. Pradeep K V Operating Systems 51/ 77

Resource Allocation Graph IV

Figure: RAG with DeadLock

Dr. Pradeep K V Operating Systems 52/ 77

Resource Allocation Graph V

Figure: Resource Allocation Graphs

Dr. Pradeep K V Operating Systems 53/ 77

Strategies Handling Deadlock

Methods to Handle Deadlock :

Deadlock Ignorance
Deadlock Prevention
Deadlock Avoidance
Deadlock Detection and Recovery

Facts
If Graph(G) contains no cycles −→ No Deadlock
If Graph(G) contains a cycle :
if only one instance per resource type, then deadlock
if several instances per resource type, possibility of deadlock

Dr. Pradeep K V Operating Systems 54/ 77

Methods to Handle Deadlock I

Deadlock Ignorance: It is the most widely used(OS) approach among all the
mechanism. Here, the OS assumes that deadlock never occurs. It simply
ignores deadlock.

It is best suited for a single end user system, where User uses the system only
for browsing and all other normal stuff.

There is always a tradeoff between Correctness and performance. The OS like

Windows and Linux mainly focus upon performance. However, the performance
of the system decreases if it uses deadlock handling mechanism all the time. If
deadlock happens 1 out of 100 times then it is completely unnecessary to
handle deadlock all the time.

In these types of systems, the user has to simply restart the computer in the
case of deadlock. Windows and Linux are mainly using this approach.

Dr. Pradeep K V Operating Systems 55/ 77

Methods to Handle Deadlock II

Deadlock prevention : Deadlock happens only when Mutual Exclusion, hold

and wait, No preemption and circular wait holds simultaneously. If it is possible
to violate one of the four conditions at any time then the deadlock can
never occur in the system.

If we model deadlock with a table standing on four legs(4-Necessary and

Sufficient Conditions ).

However, if one of the table’s legs is broken, the table will undoubtedly fall. In
the case of deadlock, we can avoid it if we can breach one of the four
required conditions and do not allow them to occur simultaneously.

Let’s look at how we may prevent each of these problems.

Dr. Pradeep K V Operating Systems 56/ 77

Methods to Handle Deadlock III

Mutual Exclusion : Multiple processes cannot use the same resource

simultaneously, which leads Deadlock.
If many processes can use the same resource simultaneously, there won’t
be any process waiting around for it.
However, if we can prevent the resources from acting in a mutually
exclusive manner, we can keep the system from becoming stuck.

Hold and Wait : !(Hold and wait) = !hold or !wait (the negation of hold
and wait is that either one doesn’t hold or they don’t wait)

No Preemption : Once the process starts, it cannot be stopped.

However, we can avoid deadlock by removing resources from the process
that could cause it.
However, this is not an right technique because bringing out a resource
that is used by the process will be inconsistent with the previous effort.

Dr. Pradeep K V Operating Systems 57/ 77

Methods to Handle Deadlock IV

Circular Wait : occurs when one or more processes wait in a circular order
for the resources they require. And can be solved by assigning a priority
number to each resource.
A resource with a lower priority value cannot be requested by the process.
It ensures that no process can demand a resource that is already in use by
another. As a result, no cycle will form.

Figure: Deadlock Prevention

Dr. Pradeep K V Operating Systems 58/ 77

Deadlock Avoidance I

The OS checks whether the system is in safe state or in unsafe state at every
step which the operating system performs. The process continues until the
system is in safe state. Suppose, if the system moves to unsafe state, then the
OS has to backtrack one step and reallocate resource.
or
The OS reviews each allocation so that the allocation doesn’t cause the
deadlock in the system.

Dr. Pradeep K V Operating Systems 59/ 77

Deadlock Avoidance II

The resource allocation state of a system can be defined by the instances of

available and allocated resources, and the maximum instance of the resources
demanded by the processes.

. A state of a system recorded at some random time is shown below:

Table: Resources Assigned

Process Type 1 Type 2 Type 3 Type 4

A 3 0 2 2
B 0 0 1 1
C 1 1 1 0
D 2 1 4 0

Let vector E : (7 6 8 4) , is the representation of total instances of each resource in

the system.

Vector P : (6 2 8 3) represents the instances of resources that have been assigned to

processes. Vector A represents the number of resources that are not in use.

Dr. Pradeep K V Operating Systems 60/ 77

Deadlock Avoidance III

Table: Resouces still needed

Process Type 1 Type 2 Type 3 Type 4
A 1 1 0 0
B 0 1 1 2
C 1 2 1 0
D 2 1 1 2

Vector A : (1 4 0 1) represents the number of resources that are not in use.

A state of the system is called safe if the system can allocate all the resources
requested by all the processes without entering into deadlock.

If the system cannot fulfill the request of all processes then the state of the
system is called unsafe.

The key of Deadlock avoidance approach is when the request is made for
resources then the request must only be approved in the case if the resulting
state is also a safe state.

Dr. Pradeep K V Operating Systems 61/ 77

Deadlock Avoidance Algorithms

Single instance of a resource type (RAG)

Multiple instances of a resource type (Banker’s Algorithm)

1. Resource Allocation Graphs (RAG)

Claim edge Ti −→ Rj indicated that process Ti may request resource Rj ;
represented by a dashed line
Claim edge converts to Request edge when a Process requests a resource
Request edge converted to an assignment edge when the resource is
allocated to the process
If process release resource, Assignment edge reconverts to a Claim edge
Resources must be claimed a priori in the system

Suppose that P2 requests R2 . although R2 is currently free, we can not allocate

it to P2 , since this action may create a cycle if P2 requests R2 as well.
Dr. Pradeep K V Operating Systems 62/ 77
Banker’s Algorithm - Deadlock Avoidance I

It used to avoid deadlock and allocate resources safely to each process in

the system.
The ’S-State’ examines all possible tests or activities before deciding
whether the allocation should be allowed to each process.
It also helps the operating system to successfully share the resources
between all the processes.
The banker’s algorithm is named because it checks whether a person
should be sanctioned a loan amount or not to help the bank system safely
simulate allocation resources.
Multiple instances of resources - Avoid Deadlock
Each process must a priori claim maximum use
When a process requests a resource it may have to wait
When a process gets all its resources it must return them in a finite
amount of time.

Banker’s Algorithm = Safety Algorithm + Algorithm

Dr. Pradeep K V Operating Systems 63/ 77

Banker’s Algorithm - Deadlock Avoidance II

Data Structures used :

Available[m] : If Available[j] = ’k’, there are ’k’ instances of resource

type Rj is available

Max[n,m] : If Max [i,j] = ’k’, then process Pi may request at most ’k’
instances of resource type Rj

Allocation[n,m] : If Allocation[i,j] = ’k’ then Pi is currently allocated ’k’

instances of Rj

Need[n,m] : If Need[i,j] = ’k’, then Pi may need k more instances of Rj

to complete its task

Need [i,j] = Max[i,j] – Allocation [i,j]

Dr. Pradeep K V Operating Systems 64/ 77

Banker’s Algorithm - Deadlock Avoidance III

Safety Algorithm

1 Let Work and Finish be vectors of length ’m’ and ’n’, respectively.
- Work = Available;
- Finish[i] = false, where ’i’ = 1,2,3,....n;

2 Find an ’i’ such that both:

- Finish [i] = false;
- Needi ≤ Work
If no such ’i’ exists, go to step 4

3 Compute
- Work = Work + Allocationi
- Finish[i] = true
Goto Step 2.

4 If Finish [i] == true for all i, then the system is in a Safe state

Dr. Pradeep K V Operating Systems 65/ 77

Banker’s Algorithm - Deadlock Avoidance IV

Resource Request Algorithm

Let Requesti , is a request vector for process Pi . If Requesti [j] = ’k’, then
process Pi wants ’k’ instances of resource type Rj .
1 If Requesti ≤ Needi go to step 2. Otherwise, raise error condition, since
process has exceeded its maximum claim
2 If Requesti ≤ Available, go to step 3. Otherwise Pi must wait, since
resources are not available
3 Pretend to allocate requested resources to Pi by modifying the state as
follows:
Available = Available - Requesti ;
Allocationi = Allocationi + Requesti ;
Needi = Needi - Requesti ;
If safe =⇒ the resources are allocated to Pi
If unsafe =⇒ Pi must wait, and the old resource-allocation state is
restored

Dr. Pradeep K V Operating Systems 66/ 77

Banker’s Algorithm - Examples I
Consider the below System Model :
5 Process {P0 , P1 , P2 , P3 and P4 } and
3 Resources { A (10 Instances), B (5 Instances) and C (7 Instances) }
Snapshot at Time T0 is given below:
Allocation Max Available
Process
ABC ABC ABC
P1 010 753 332
P2 200 322
P3 302 902
P4 211 222
P5 002 433
Answer the following questions using the banker’s algorithm:
What is the reference of the need matrix?
Determine if the system is safe or not.
What will happen if the resource request (1, 0, 2) for process P1 can the
system accept this request immediately?
Can request for (3,3,0) by P5 be granted?
Can request for (0,2,0) by P0 be granted?
Dr. Pradeep K V Operating Systems 67/ 77
Banker’s Algorithm - Examples II

Need Matrix can be computed as Need[i] = Max[i] - Allocation[i]

Need
Process
ABC
P1 743
P2 122
P3 600
P4 011
P5 431
Applying the Banker’s Algorithm [Safety Algorithm]: to find the safe state
sequence

Available Resources of (A, B, C) = (3, 3, 2)

Now we check if each type of resource request is available for each process.

Dr. Pradeep K V Operating Systems 68/ 77

Banker’s Algorithm - Examples III

Step-1 : For Process P1 : Need <= Available

(7, 4, 3) <= (3, 3, 2) is false.
So, we examine another process, P2 .
Step-2 : For Process P2 : Need <= Available
(1, 2, 2) <= (3, 3, 2) is true.
Available = Available + Allocation
(3, 3, 2) + (2, 0, 0) => 5, 3, 2
Similarly, we examine another process P3 .
Step-3 : For Process P3 : Need <= Available
(6, 0, 0) <= (5, 3, 2) is false.
So, we examine another process, P4 .
Step-4 : For Process P4 : Need <= Available
(0, 1, 1) <= (5, 3, 2) is true.
Available = Available + Allocation
(5, 3, 2) + (2, 1, 1) => 7, 4, 3
Similarly, we examine another process P5 .

Dr. Pradeep K V Operating Systems 69/ 77

Banker’s Algorithm - Examples IV

Step-5 : For Process P5 : Need <= Available

(4, 3, 1) <= (7, 4, 3) is true.
Available = Available + Allocation
(7, 4, 3) + (0, 0, 2) = (7, 4, 5)
Now, Again examine each type of resource request for processes P1 & P3 .
Step-6 : For Process P1 : Need <= Available
(7, 4, 3) <= (7, 4, 5) is true.
Available = Available + Allocation
(7, 4, 5) + (0, 1, 0) = (7, 5, 5)
So, we examine another process P3 .
Step-7 : For Process P3 : Need <= Available
(6, 0, 0) <= (7, 5, 5) is true.
Available = Available + Allocation
(7, 5, 5) + (3, 0, 2) = (10, 5, 7)
Hence, The safe sequence like < P2 , P4 , P5 , P1 and P3 >.
For granting the Ps1 Request (1, 0, 2) check if Request <= Available,
i.e., (1, 0, 2) <= (3, 3, 2), since the condition is true. So the process P1 gets
the request immediately.

Dr. Pradeep K V Operating Systems 70/ 77

Example-1

Let us consider the following snapshot for understanding the banker’s algorithm:

Dr. Pradeep K V Operating Systems 71/ 77

Example-2

Let us consider the following snapshot for understanding the banker’s algorithm:
Allocation Max
Process
Matrix Matrix
X Y Z X Y Z
P0 0 0 1 8 4 3
P1 3 2 0 6 2 0
P2 2 1 1 3 3 3

There are 3 units of type X, 2 units of type Y and 2 units of type Z still
available. The system is currently in a safe state. Consider the following
independent requests for additional resources in the current state:
Req1: P0 requests 0 units of X, 0 units of Y and 2 units of Z
Req2: P1 requests 2 units of X, 0 units of Y and 0 units of Z
Can the requests be granted immediately?

Dr. Pradeep K V Operating Systems 72/ 77

Deadlock Detection and Recovery I

How to Detect Deadlock ?

If a system does not use a deadlock prevention technique or the deadlock

avoidance technique, there is a probability that a deadlock will occur.

In order to avoid deadlocks, the operating system examines the system for any
deadlocks on a regular basis. The OS will recover from the deadlock using
recovery mechanisms after it has been discovered.

The OS’s primary responsibility is to detect deadlocks. With the help of the
resource allocation graph, the OS can detect deadlocks.

Dr. Pradeep K V Operating Systems 73/ 77

Deadlock Detection and Recovery II

Deadlock Detection Algorithm - Unsafety Algorithm

1 Let Work and Finish be vectors of length ’m’ and ’n’, respectively.
- Work = Available;
- if Requesti = 0, then Finish[i] = true;
otherwise, Finish[i]= false,
where ’i’ = 1,2,3,....n;

2 Find an ’i’ such that both:

- Finish [i] = false;
- Requesti ≤ Work
If no such ’i’ exists, go to step 4

3 Compute
- Work = Work + Allocationi
- Finish[i] = true
Goto Step 2.

4 If Finish [i] == false for all i, then the system is in a Deadlock state

Dr. Pradeep K V Operating Systems 74/ 77

Deadlock Detection and Recovery III
Allocation Max
Process Available
Matrix Matrix
X Y Z X Y Z X Y Z
P1 0 1 0 0 0 0 0 0 0
P2 2 0 0 2 0 2
P3 3 0 3 0 0 0
P4 2 1 1 1 0 0
P5 0 0 2 0 0 2

1 In this, Work = [0, 0, 0] & Finish = [false, false, false, false, false]
2 i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].
3 Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] & Finish = [true, false, false, false,
false].
4 i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1, 0].
5 Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] & Finish = [true, false, true, false,
false].
6 i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1, 3].
7 Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] & Finish = [true, true, true, false,
false].
Dr. Pradeep K V Operating Systems 75/ 77
Deadlock Detection and Recovery IV

8 i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1, 3]. Work
=[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] & Finish = [true, true, true, true, false].
9 i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2, 4].
10 Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] & Finish = [true, true, true, true,
true].
11 Since Finish is a vector of all true it means there is no deadlock in this
example.
How to Detect Recover ?

Dr. Pradeep K V Operating Systems 76/ 77

Dr. Pradeep K V Operating Systems 77/ 77