Process Synchronization is the task of coordinating the execution of processes in a

way that no two processes can have access to the same shared data and [Link] is
specially needed in a multi-process system when multiple processes are running
together, and more than one processes try to gain access to the same shared resource
or data at the same time.
This can lead to the inconsistency of shared data. So the change made by one process
not necessarily reflected when other processes accessed the same shared data. To avoid
this type of inconsistency of data, the processes need to be synchronized with each
other.
For Example, process A changing the data in a memory location while another process
B is trying to read the data from the same memory location. There is a high probability
that data read by the second process will be erroneous.

Sections of a Program
 Entry Section: It is part of the process which decides the entry of a particular
process.
 Critical Section: This part allows one process to enter and modify the shared
variable.
 Exit Section: Exit section allows the other process that are waiting in the Entry
Section, to enter into the Critical Sections. It also checks that a process that
finished its execution should be removed through this Section.
 Remainder Section: All other parts of the Code, which is not in Critical, Entry,
and Exit Section, are known as the Remainder Section.

What is Critical Section Problem?

A critical section is a segment of code which can be accessed by a signal process at a
specific point of time. The section consists of shared data resources that required to be
accessed by other processes.
The critical section is a code segment where the shared variables can be accessed. An
atomic action is required in a critical section i.e. only one process can execute in its
critical section at a time. All the other processes have to wait to execute in their critical
sections.
A diagram that demonstrates the critical section is as follows −

 The entry to the critical section is handled by the wait() function, and it is
represented as P().
 The exit from a critical section is controlled by the signal() function, represented
as V().
In the critical section, only a single process can be executed. Other processes, waiting
to execute their critical section, need to wait until the current process completes its
execution.

The solution to the critical section problem must satisfy the following conditions −
 Mutual Exclusion
Mutual exclusion implies that only one process can be inside the critical section
at any time. If any other processes require the critical section, they must wait
until it is free.
 Progress
Progress means that if a process is not using the critical section, then it should
not stop any other process from accessing it. In other words, any process can
enter a critical section if it is free.
 Bounded Waiting
Bounded waiting means that each process must have a limited waiting time. Itt
should not wait endlessly to access the critical section.
 Peterson’s Solution

do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
/* critical section */
flag[i] = false;
/* remainder section */
}
while (true);

The structure of process Pi in Peterson’s solution. This solution is restricted to

two processes that alternate execution between their critical sections and
remainder sections. The processes are numbered P0 and P1.
int turn;
boolean flag[2];
The variable turn denotes whose turn it is to enter its critical section. I.e., if turn == i,
then process Pi is allowed to execute in its critical section. If a process is ready to enter
its critical section, the flag array is used to indicate that. For E.g., if flag[i] is true, this
value indicates that Pi is ready to enter its critical section. With an explanation of these
data structures complete, we are now ready to describe the algorithm shown in above.
To enter the critical section, process Pi first sets flag[i] to be true and then sets turn to
the value j, thereby asserting that if the other process wishes to enter the critical
section, it can do so. Turn will be set to both i and j at roughly the same time, if both
processes try to enter at the same time. Only one of these assignments will occur
ultimately; the other will occur but will be overwritten immediately. The final value
of turn determines which of the two processes is allowed to enter its critical section
first. We now prove that this solution is correct. We need to show that −
 Mutual exclusion is preserved.
 The progress requirement is satisfied.
 The bounded-waiting requirement is met.

To prove 1, we note that each Pi enters its critical section only if either flag[j] == false
or turn == i. Also note that, if both processes can be executing in their critical sections
at the same time, then flag[0] == flag[1] == true. These two observations indicate that
P0 and P1 could not have successfully executed their while statements at about the
same time, since the value of turn can be either 0 or 1 but cannot be both. Hence, one
of the processes — say, Pj — must have successfully executed the while statement,
whereas Pi had to execute at least one additional statement (“turn == j”). However, at
that time, flag[j] == true and turn == j, and this condition will persist as long as Pj is
in its critical section; as a result, mutual exclusion is preserved.
To prove properties 2 and 3, we note that if a process is stuck in the while loop with
the condition flag[j] == true and turn == j, process Pi can be prevented from entering
the critical section only; this loop is the only one possible. flag[j] will be == false, and
Pi can enter its critical section if Pj is not ready to enter the critical section. If Pj has
set, flag[j] = true and is also executing in its while statement, then either turn == i or
turn == j. If turn == i, Pi will enter the critical section then. Pj will enter the critical
section, If turn == j. Although once Pj exits its critical section, it will reset flag[j] to
false, allowing Pi to enter its critical section. Pj must also set turn to i, if Pj resets
flag[j] to true. Hence, since Pi does not change the value of the variable turn while
executing the while statement, Pi will enter the critical section (progress) after at most
one entry by Pj (bounded waiting).

Peterson Solution

Peterson's solution is widely used solution to critical section problems. This algorithm
was developed by a computer scientist Peterson that's why it is named as a Peterson's
solution.

In this solution, when a process is executing in a critical state, then the other process
only executes the rest of the code, and the opposite can happen. This method also helps
to make sure that only a single process runs in the critical section at a specific time.

Semaphores
Semaphores(S) are integer variables that are used to solve the critical section problem
by using two atomic operations, wait() and signal(), apart from initialization that are
used for process synchronization.
The definitions of wait and signal are as follows −

 Wait() [to test]

The wait operation decrements the value of its argument S, if it is positive. If S
is negative or zero, then no operation is performed.

wait(S)
{
 while (S<=0);
//no-operation
S--;
}

 Signal() [to increment]

The signal operation increments the value of its argument S.

signal(S)
{
S++;
}

Types of Semaphores
There are two main types of semaphores i.e. counting semaphores and binary
semaphores.
 Counting Semaphores
These are integer value semaphores and have an unrestricted value domain.
These semaphores are used to coordinate the resource access, where the
semaphore count is the number of available resources. If the resources are added,
semaphore count automatically incremented and if the resources are removed,
the count is decremented.

 Binary Semaphores
The binary semaphores are like counting semaphores but their value is restricted
to 0 and 1. The wait operation only works when the semaphore is 1 and the signal
operation succeeds when semaphore is 0.

Counting Semaphore vs. Binary Semaphore

Counting Binary Semaphore

Semaphore
No mutual exclusion Mutual exclusion

Any integer value Value only 0 and 1

More than one slot Only one slot

Provide a set of It has a mutual exclusion

Processes mechanism.

Advantages of Semaphores
Some of the advantages of semaphores are as follows −

 Semaphores allow only one process into the critical section. They follow the
mutual exclusion principle strictly and are much more efficient than some other
methods of synchronization.
 There is no resource wastage because of busy waiting in semaphores as
processor time is not wasted unnecessarily to check if a condition is fulfilled to
allow a process to access the critical section.
 Semaphores are implemented in the machine independent code of the
microkernel. So they are machine independent.

Disadvantages of Semaphores
Some of the disadvantages of semaphores are as follows −

 Semaphores are complicated so the wait and signal operations must be

implemented in the correct order to prevent deadlocks.
 Semaphores may lead to a priority inversion where low priority processes may
access the critical section first and high priority processes later.
The main disadvantages of the Semaphore are that it requires busy waiting. While a
process is in its critical section, any other process tries to enter its critical section must
loop continuously in the entry code.
The mutual exclusion implementation with semaphore is given as:
Do
{
Wait(mutex)
//critical section
Signal (mutex)
//remainder section
}while (TRUE)
Difference between Semaphore vs. Mutex

Parameters Semaphore Mutex

Mechanism It is a type of It is a locking

signaling mechanism.
mechanism.

Data Type Semaphore is Mutex is just an

an integer object.
variable.

Modification The wait and It is modified

signal only by the
operations can process that
modify a may request or
semaphore. release a
resource.

Classic problems of Synchronization

1. Bounded buffer problem
2. Readers-Writers Problem
3. Dining Philosophers Problem

Bounded buffer problem, which is also called producer consumer problem, is one of
the classic problems of synchronization.

What is the Problem Statement?

There is a buffer of n slots and each slot is capable of storing one unit of data. There
are two processes running, namely, producer and consumer, which are operating on the
buffer.

A producer tries to insert data into an empty slot of the buffer. A consumer tries to
remove data from a filled slot in the [Link] two processes won't produce the
expected output if they are being executed concurrently.
There needs to be a way to make the producer and consumer work in an independent
manner.
One solution of this problem is to use semaphores.
 m, a binary semaphore which is used to acquire and release the lock.
 empty, a counting semaphore whose initial value is the number of slots in the
buffer, since, initially all slots are empty.
 full, a counting semaphore whose initial value is 0.

At any instant, the current value of empty represents the number of empty slots in the
buffer and full represents the number of occupied slots in the buffer.
Producer operation
do
{
// wait until empty > 0 and then decrement 'empty'
//produce an item in nextp
wait(empty);
// acquire lock
wait(mutex);
// perform the insert operation in a slot I,e add nextp to buffer */
// release lock
signal(mutex);
// increment 'full'
signal(full);
}
while(TRUE)

 Producer first waits until there is at least one empty slot.

 Then it decrements the empty semaphore because, there will now be one less
empty slot, since the producer is going to insert data in one of those slots.

 Then, it acquires lock on the buffer, so that the consumer cannot access the buffer
until producer completes its operation.

 After performing the insert operation, the lock is released and the value of full is
incremented because the producer has just filled a slot in the buffer.

The Consumer Operation

do
{
// wait until full > 0 and then decrement 'full'
 wait(full);
// acquire the lock
wait(mutex);

/* perform the remove operation in a slot */

// release the lock
signal(mutex);
// increment 'empty'
signal(empty);
}
while(TRUE);
 The consumer waits until there is at least one full slot in the buffer.
 Then it decrements the full semaphore because the number of occupied slots will
be decreased by one, after the consumer completes its operation.
 After that, the consumer acquires lock on the buffer.
 Following that, the consumer completes the removal operation so that the data
from one of the full slots is removed.
 Then, the consumer releases the lock.
 Finally, the empty semaphore is incremented by 1, because the consumer has
just removed data from an occupied slot, thus making it empty.

Readers-Writers Problem

The readers-writers problem relates to an object such as a file that is shared between
multiple processes. Some of these processes are readers i.e. they only want to read
the data from the object and some of the processes are writers i.e. they want to write
into the object.
The Problem Statement
There is a shared resource which should be accessed by multiple processes. There
are two types of processes in this context. They are reader and writer. Any number
of readers can read from the shared resource simultaneously, but only
one writer can write to the shared resource. When a writer is writing data to the
resource, no other process can access the resource. A writer cannot write to the
resource if there are non zero number of readers accessing the resource at that time
The Solution
From the above problem statement, it is evident that readers have higher priority
than writer. If a writer wants to write to the resource, it must wait until there are no
readers currently accessing that resource.
Here, we use one mutex m and a semaphore w. An integer variable read_count is used
to maintain the number of readers currently accessing the resource. The
variable read_count is initialized to 0. A value of 1 is given initially to m and w.
Instead of having the process to acquire lock on the shared resource, we use the
mutex m to make the process to acquire and release lock whenever it is updating
the read_count variable.
.
The code for the writer process looks like this:
while(TRUE)
{
wait(w);

/* perform the write operation */

signal(w);
}

And, the code for the reader process looks like this:
while(TRUE)
{
//acquire lock
wait(m);
read_count++;
if(read_count == 1)
wait(w);

//release lock
signal(m);

/* perform the reading operation */

// acquire lock
wait(m);
read_count--;
if(read_count == 0)
signal(w);

// release lock
 signal(m);
}

 As seen above in the code for the writer, the writer just waits on the w semaphore
until it gets a chance to write to the resource.
 After performing the write operation, it increments w so that the next writer can
access the resource.
 On the other hand, in the code for the reader, the lock is acquired whenever
the read_count is updated by a process.
 When a reader wants to access the resource, first it increments
the read_count value, then accesses the resource and then decrements
the read_count value.
 The semaphore w is used by the first reader which enters the critical section and
the last reader which exits the critical section.
 The reason for this is, when the first readers enters the critical section, the writer
is blocked from the resource. Only new readers can access the resource now.
 Similarly, when the last reader exits the critical section, it signals the writer using
the w semaphore because there are zero readers now and a writer can have the
chance to access the resource.

The readers-writers problem is used to manage synchronization so that there are no

problems with the object data.
For example - If two readers access the object at the same time there is no problem.
However if two writers or a reader and writer access the object at the same time,
there may be problems.
To solve this situation, a writer should get exclusive access to an object i.e. when a
writer is accessing the object, no reader or writer may access it. However, multiple
readers can access the object at the same time.
This can be implemented using semaphores. The codes for the reader and writer
process in the reader-writer problem are given as follows −
Reader Process
The code that defines the reader process is given below −
wait (mutex);
rc ++;
if (rc == 1)
wait (wrt);
signal(mutex);
.
. READ THE OBJECT
 .
wait(mutex);
rc --;
if (rc == 0)
signal (wrt);
signal(mutex);
In the above code, mutex and wrt are semaphores that are initialized to 1. Also, rc
is a variable that is initialized to 0. The mutex semaphore ensures mutual exclusion
and wrt handles the writing mechanism and is common to the reader and writer
process code.
The variable rc denotes the number of readers accessing the object. As soon as rc
becomes 1, wait operation is used on wrt. This means that a writer cannot access
the object anymore. After the read operation is done, rc is decremented. When re
becomes 0, signal operation is used on wrt. So a writer can access the object now.
Writer Process
The code that defines the writer process is given below:
wait(wrt);
.
. WRITE INTO THE OBJECT
.
signal(wrt);
If a writer wants to access the object, wait operation is performed on wrt. After that
no other writer can access the object. When a writer is done writing into the object,
signal operation is performed on wrt.
Dining Philosophers Problem
The dining philosophers problem is another classic synchronization problem which is
used to evaluate situations where there is a need of allocating multiple resources to
multiple processes.
Problem Statement
Consider there are five philosophers sitting around a circular dining table. The dining
table has five chopsticks and a bowl of rice in the middle as shown in the below figure.
At any instant, a philosopher is either eating or thinking. When a philosopher wants to
eat, he uses two chopsticks - one from their left and one from their right. When a
philosopher wants to think, he keeps down both chopsticks at their original place.

From the problem statement, it is clear that a philosopher can think for an indefinite
amount of time. But when a philosopher starts eating, he has to stop at some point of
time. The philosopher is in an endless cycle of thinking and eating.
An array of five semaphores, stick[5], for each of the five chopsticks.
while(TRUE)
{
wait(stick[i]);
i=5
(5+1)%5=1

i=2
(2+1)%5=3
/* mod is used because if i=5, next chopstick is 1 (dining table is circular) */
wait(stick[(i+1) % 5]);
/* eat */
signal(stick[i]);
signal(stick[(i+1) % 5]);
 /* think */
}
When a philosopher wants to eat the rice, he will wait for the chopstick at his left and
picks up that chopstick. Then he waits for the right chopstick to be available, and then
picks it too. After eating, he puts both the chopsticks down.
But if all five philosophers are hungry simultaneously, and each of them pickup one
chopstick, then a deadlock situation occurs because they will be waiting for another
chopstick forever. The possible solutions for this are:

 A philosopher must be allowed to pick up the chopsticks only if both the left and
right chopsticks are available.
 Allow only four philosophers to sit at the table. That way, if all the four
philosophers pick up four chopsticks, there will be one chopstick left on the
table. So, one philosopher can start eating and eventually, two chopsticks will be
available. In this way, deadlocks can be avoided.

Monitors
Monitors and semaphores are used for process synchronization and allow processes to
access the shared resources using mutual exclusion. Monitors are a synchronization
construct that were created to overcome the problems caused by semaphores
Monitors are abstract data types and contain shared data variables and procedures. The
shared data variables cannot be directly accessed by a process and procedures are
required to allow a single process to access the shared data variables at a time.
This is demonstrated as follows:
monitor monitorName
{
data variables;

Procedure P1(....)
{
}

Procedure P2(....)
{
}
 Procedure Pn(....)
{
}

Initialization Code(....)
{

}
}
Only one process can be active in a monitor at a time. Other processes that need to
access the shared variables in a monitor have to line up in a queue and are only provided
access when the previous process release the shared variables.
A monitor has four components: initialization, private data, monitor procedures, and
monitor entry queue.
The initialization component contains the code that is used exactly once when the
monitor is created,
The private data section contains all private data, including private procedures,that can
only be used within the monitor. Thus, these private items are not visible from outside
of the monitor. The monitor procedures are procedures that can be called from outside
of the monitor. The monitor entry queue contains all threads that called monitor
procedures but have not been granted permissions.

Monitors are supposed to be used in a multithreaded or multi process environment in

which multiple threads/processes may call the monitor procedures at the same time
asking for service. Thus, a monitor guarantees that at any moment at most one thread
can be executing in a monitor.
If a thread calls a monitor procedure, this thread will be blocked if there is another
thread executing in the monitor. Those threads that were not granted the entering
permission will be queued to a monitor entry queue outside of the monitor. When the
monitor becomes empty (i.e., no thread is executing in it), one of the threads in the
entry queue will be released and granted the permission to execute the called monitor
procedure.
Condition x, y
[Link]();
[Link]();

Signal & Wait-P either waits until Q leaves the monitor or waits for the conditions
Signal & Continue- Q either waits until P leaves the monitor or waits for the conditions

CPU Scheduling Algorithms in Operating Systems

What is CPU Scheduling?

CPU Scheduling is a process of determining which process will own CPU for
execution while another process is on hold.

P1,P2,P3

P1-run state-I/o—Waiting state

P2,P3 ready state

P2 run/P3 run state

The main task of CPU scheduling is to make sure that whenever the CPU remains idle,
the OS at least select one of the processes available in the ready queue for execution.
The selection process will be carried out by the CPU scheduler. It selects one of the
processes in memory that are ready for execution.

Types of CPU Scheduling

There are two kinds of Scheduling methods:

Preemptive Scheduling
In Preemptive Scheduling, the tasks are assigned with their priorities. Sometimes it is
important to run a task with a higher priority before another lower priority task, even
if the lower priority task is still running. The lower priority task holds for some time
and resumes when the higher priority task finishes its execution.

P1-priority(2)
P2-Priority(3)
P3-Priority(1)
P1 & P2 are in ready state
P1 Goes to run state-----
P3 enters in to ready state
P2,P3 are in ready state.
Since P3 has highest priority thanP1 and P2 though p1 has not completed its task, it
has to be removed and OS allocates P3.
P3 completes it’s job
P1 enters the run state then P2.
Non-Preemptive Scheduling
In this type of scheduling method, the CPU has been allocated to a specific process.
The process that keeps the CPU busy will release the CPU either by switching context
or terminating. It is the only method that can be used for various hardware platforms.
P1 enters first (5msec)—run state
P2 enters(50msec)
P3 enters(3msec)
P2-25mesc—request for I/O---
Context Switching involves storing the context or state of a process so that it can be
reloaded when required and execution can be resumed from the same point as earlier.
This is a feature of a multitasking operating system and allows a single CPU to be
shared by multiple processes.
Let Process 1 is running. Process 1 is switched out and Process 2 is switched in because
of an interrupt or a system call. Context switching involves saving the state of Process
1 into PCB1 and loading the state of process 2 from PCB2. After some time again a
context switch occurs and Process 2 is switched out and Process 1 is switched in again.
This involves saving the state of Process 2 into PCB2 and loading the state of process
1 from PCB1.

CPU scheduling algorithms

There are various CPU Scheduling algorithms such as-

 First Come First Served (FCFS)
 Shortest Job First (SJF)
 Shortest Job Remaining First (SJRF)
 Priority Scheduling
 Round Robin (RR)

Different CPU scheduling algorithms have different properties and choice of a

particular algorithm depends on the various factors.
The criteria include the following:
[Link] utilization –The main objective of any CPU scheduling algorithm is to keep
the CPU as busy as possible.

[Link] –A measure of the work done by CPU is the number of processes being
executed and completed per unit time. This is called throughput. The throughput may
vary depending upon the length or duration of processes.

[Link] around time –For a particular process, an important criteria is how long it takes
to execute that process. The time elapsed from the time of submission of a process to
the time of completion is known as turnaround time.
Turnaround time is the sum of times spent waiting to get into memory, waiting in ready
queue, executing in CPU and waiting for I/O.

[Link] time –A scheduling algorithm does not affect the time required to complete
the process once it starts execution. It only affects the waiting time of a process i.e.
time spent by a process waiting in the ready queue.

[Link] time –The time taken from submission of process of request until the first
response is produced. This measure is called response time.

First Come First Serve (FCFS): Simplest scheduling algorithm that schedules
according to arrival times of processes. First come first serve scheduling algorithm
states that the process that requests the CPU first is allocated the CPU first. It is
implemented by using the FIFO queue. FCFS is a non-preemptive scheduling
algorithm.
First come first serve suffers from convoy effect.

Convoy Effect is a situation where many processes need to use a resource for short
time are blocked by one process holding that resource for a long time. This essentially
leads to poor utilization of resources and hence poor performance.
Shortest Job First (SJF) Scheduling in OS
Shortest Job First is a Preemptive or Non-Preemptive algorithm. In the shortest job first
algorithm, the job having shortest or less burst time will get the CPU first. It is the best
approach to minimize the waiting time. It is simple to implement in the batch operating
system because in this CPU time is known in advance.
Characteristics of Shortest Job First Scheduling
 SJF algorithm is helpful in batch operating where the waiting time for job
completion is not critical.

P1-8msec
P2-3msec
P3-5msec

 SJF improves the throughput of the process by ensuring that the shorter jobs are
executed first, thus the possibility of less turnaround time.
 SJF enhances the output of the job by executing the process, which is having the
shortest burst time.

Advantages of Shortest Job First (SJF) Scheduling

The advantages of Shortest Job First scheduling are:
 SJF is basically used for Long Term Scheduling.
 The average waiting time of Shortest Job First (SJF) is less than the FCFS (First-
Come, First Serve) algorithm.
 For a particular set of processes, SJF provides the lowest average waiting
 In terms of the average turnaround time, it is optimal.

Disadvantages of Shortest Job First (SJF) Scheduling

 In SJF process completion time needs to be known earlier. Although prediction
is difficult.
 Sometimes the problem of starvation occurs in SJF.
 SJF needs the knowledge to know how long a process will run.
 It is not easy to know the upcoming CPU request length.

Types of Shortest Job First (SJF) Scheduling

There are two types of Shortest Job First Scheduling.
 Non-Preemptive SJF
 Preemptive SJF
If the processor knows the Burst time of the processes in advance, the scheduling of
the process can be implemented successfully. But practically it’s impossible.
When all the processes are available at the same time, then the Shortest Job Scheduling
algorithm becomes optimal.
 Non-Preemptive SJF: – In Non-Preemptive Scheduling, if a CPU is allocated
to the process, then the process will hold the CPU until the process enters into
the waiting state or terminated.
 Preemptive SJF:-

Round Robin Scheduling algorithm:

The name of this algorithm comes from the round-robin principle, where each person
gets an equal share of something in turns. It is the oldest, simplest scheduling
algorithm, which is mostly used for multitasking.
In Round-robin scheduling, each ready task runs turn by turn only in a cyclic queue for
a limited time slice. This algorithm also offers starvation free execution of processes.

Characteristics of Round-Robin Scheduling

 Round robin is a pre-emptive algorithm

 The CPU is shifted to the next process after fixed interval time, which is called
time quantum/time slice.
 The process that is preempted is added to the end of the queue.
 Round robin is a hybrid model which is clock-driven
 Time slice should be minimum, which is assigned for a specific task that needs
to be processed. However, it may differ OS to OS.
 It is a real time algorithm which responds to the event within a specific time
limit.
 Round robin is one of the oldest, fairest, and easiest algorithm.
 Widely used scheduling method in traditional OS.

Priority Scheduling algorithm

Each process is assigned a priority. Process with highest priority is to be executed first
and so on.
● Processes with same priority are executed on first come first served basis.
● Priority can be decided based on memory requirements, time requirements or
any other resource requirement.
Advantages of Priority Scheduling
• The priority of process is selected on the basis of memory requirement, user
preference or the requirement of time.
• Processes are executed on the basis of priority. So high priority does not need to
wait
for long which saves time.
• It is easy to use.
• It is a user friendly algorithm.
• Simple to understand.
• it has reasonable support for priority.

Disadvantages of Priority Scheduling

• The major disadvantage of priority scheduling is the process of indefinite blocking

or starvation. This problem appears when a process is ready to be executed but it
 has to wait for the long time for execution by CPU because other high priority
processes are executed by the CPU.

Deadlock is a situation that occurs in OS when any process enters a waiting state
because another waiting process is holding the demanded resource. Deadlock is a
common problem in multi-processing where several processes share a specific type of
mutually exclusive resource known as a soft lock or software.

Example of Deadlock

 A real-world example would be traffic, which is going only in one direction.

 Here, a bridge is considered a resource.
 So, when Deadlock happens, it can be easily resolved if one car backs up
(Preempt resources and rollback).
 Several cars may have to be backed up if a deadlock situation occurs.
 So starvation is possible.

Example of deadlock

Deadlock is a situation where a set of processes are blocked because each process is
holding a resource and waiting for another resource acquired by some other process.

For example, in the below diagram, Process 1 is holding Resource 1 and waiting for
resource 2 which is acquired by process 2, and process 2 is waiting for resource 1.

Deadlocks can be avoided by avoiding at least one of the four conditions, because all
this four conditions are required simultaneously to cause deadlock.

A process in operating systems uses different resources and uses resources in the
following way.
1) Requests a resource – If the request is not granted immediately, then the requesting
process must wait until it can acquire the resource
2) Use the resource – operate on the resource.

3) Releases the resource –release the resource once the operation is completed.

Deadlock Characterization
A deadlock situation occurs if the following four conditions hold simultaneously

 Mutual Exclusion
There should be a resource that can only be held by one process at a time. In the
diagram below, there is a single instance of Resource 1 and it is held by Process
1 only.

 Hold and Wait

A process can hold multiple resources and still request more resources from
other processes which are holding them. In the diagram given below, Process 2
holds Resource 2 and Resource 3 and is requesting the Resource 1 which is held
by Process 1.

 No Preemption
A resource cannot be preempted from a process by force. A process can only
release a resource voluntarily. In the diagram below, Process 2 cannot preempt
 Resource 1 from Process 1. It will only be released when Process 1 relinquishes
it voluntarily after its execution is complete.

 Circular Wait
A process is waiting for the resource held by the second process, which is
waiting for the resource held by the third process and so on, till the last process
is waiting for a resource held by the first process. This forms a circular chain.
For example: Process 1 is allocated Resource2 and it is requesting Resource 1.
Similarly, Process 2 is allocated Resource 1 and it is requesting Resource 2. This
forms a circular wait loop.

Resource Allocation Graph

Resource allocation graph is the pictographic representation of the state of a system.

The resource allocation graph contains all the information related to the processes that
are holding some resources and also waiting for some more resources.

Resource allocation graph consists of all the information which is related to all the
instances of the resources means the information about available resources and the
resources which the process is being using. In the Resource Allocation Graph, we use
a circle to represent the process and rectangle to represent the resource.

Components of RAG (Resource Allocation Graph)

There are two components of the resource allocation graph:
1. Vertices
2. Edges
1. Vertices: – In the resource allocation graph, we use two kinds of vertices:

 Process Vertices
 Resource Vertices

Process Vertices: – To represent a process, we use process vertices. We draw the

process vertices by using a circle, and inside the circle, we mention the name of the
process.
Resource Vertices: – To represent a resource, we use resource vertices. We draw the
resource vertices by using a rectangle, and we use dots inside the rectangle to mention
the number of instances of that resource.
According to the number of instances that may exist in the system, there are two types
of resource vertices, i.e., single instance and multiple instances.

Single instance resource type: – In single instance resource type, we use only a single
dot inside the box. The single dot indicates that there is one instance of the resource.

Multiple instance resource type: – In multiple instance resource type, we use multiple
dots inside the box. Multiple dots indicate that there are various instances of the
resources.

2. Edges: – There are two types of edges we use in the resource allocation graph:
 Assign Edges
 Request Edges

Assign Edges: – We use an assign edge to represent the allocation of resources to the
process. We draw assign edges with the help of arrow in which the arrow head points
the process, and the process tail points the instance of the resource.

Request Edges: – We use request edge to signify the waiting state of the process. Just
like in assign edge, an arrow is used to draw arrow edge. Here, the arrow head points
the instance of a resource, and tail of the process points to the process. For example, if
a process needs ‘n’ instances of resource type, then we will draw ‘n’ assign edges.

 Resource-Allocation Graphs, having the following properties:

o A set of resource categories, { R1, R2, R3, . . ., RN }, which appear as
square nodes on the graph. Dots inside the resource nodes indicate specific
instances of the resource. ( E.g. two dots might represent two laser
printers. )
o
o A set of processes, { P1, P2, P3, . . ., PN }
o Request Edges - A set of directed arcs from Pi to Rj, indicating that
process Pi has requested Rj, and is currently waiting for that resource to
become available.
o Assignment Edges - A set of directed arcs from Rj to Pi indicating that
resource Rj has been allocated to process Pi, and that Pi is currently
holding resource Rj.
o Note that a request edge can be converted into an assignment edge by
reversing the direction of the arc when the request is granted.

For example:
Resource allocation graph

 If a resource-allocation graph contains no cycles, then the system is not

deadlocked.
 If a resource-allocation graph does contain cycles AND each resource category
contains only a single instance, then a deadlock exists.
 If a resource category contains more than one instance, then the presence of a
cycle in the resource-allocation graph indicates the possibility of a deadlock, but

does not guarantee one.

Resource allocation graph with a deadlock

Resource allocation graph with a cycle but no deadlock

Example of (RAG) Resource Allocation Graph

Example of Single Instance Resource Type

In the following example, we have two processes P1, and P2 and two resources which
are R1, and R2. This example is a kind of single instance resource type, and it contain
a cycle, so there is a deadlock in the system.
 Allocation Request

R1 R2 R1 R2

Process
1 0 0 1
P1

Process
0 1 1 0
P2

Available = [R1 R2] = [0 0]

We can see in the following table, there is no instance of resource available, and to
execute the process we need a resource. So, no process will be executed, and both the
processes keep waiting for a long time. So, we can say that there is a deadlock in the
system.

Example of Multiple Instance Resource Type

The term multiple instances means the resources are having more instances. In the
following example, we have three processes, which are P1, P2, and, P3 and three
resources, which are R1, and R2.
 Allocation Request

R1 R2 R2
R1

Process
1 0 0 1
P1

Process
0 1 1 0
P2

Process
0 1 0 0
P3

Now we check the current Availability = [R1 R2] = [0 0]

Now by using this availability, we check whether we can fulfill the request of any of
the processes or not.
We can fulfill the demand or request of P3 because P3 is demanding nothing. So, when
the process P3 gets successfully executed, we terminate the process P3.
Then we calculate availability,

Availability = [0 0] + [0 1]
= [ 0 1]
Now, based on the current availability, we can fulfill the requirement of the P1 process.
So, we assign the requested resource to the process P1. When the process P1 executes
successfully, then we terminate the process P1.
Now we again calculate availability
Availablity = [0 1] [1 0]
= [1 1]
Now, again based on the current availability we fulfill the requirement of process P2
because the P2 process satisfies the requirement. So, we allocate the requested resource
to the Process P2. When the process P2 executes successfully, then it terminates, and
we again calculate the availability.
Availability = [1 1] + [0 1]
= [1 2]
So, in this example, there is a safe sequence P3, P1, P2, and all the processes are
executed successfully. So, we can say that system is in a safe state, and there is no
deadlock in the system.
←
Methods for Handling Deadlocks

 There are three ways of handling deadlocks:

1. Deadlock prevention or avoidance - Do not allow the system to get into a
deadlocked state.
2. Deadlock detection and recovery - Abort a process or preempt some
resources when deadlocks are detected.
3. Ignore the problem all together - If deadlocks only occur once a year or
so, it may be better to simply let them happen and reboot as necessary than
to incur the constant overhead and system performance penalties
associated with deadlock prevention or detection. This is the approach that
both Windows and UNIX take.
 In order to avoid deadlocks, the system must have additional information about
all processes. In particular, the system must know what resources a process will
or may request in the future. ( Ranging from a simple worst-case maximum to a
complete resource request and release plan for each process, depending on the
particular algorithm. )
 Deadlock detection is fairly straightforward, but deadlock recovery requires
either aborting processes or preempting resources, neither of which is an
attractive alternative.
 If deadlocks are neither prevented nor detected, then when a deadlock occurs the
system will gradually slow down, as more and more processes become stuck
waiting for resources currently held by the deadlock and by other waiting
processes. Unfortunately this slowdown can be indistinguishable from a general
system slowdown when a real-time process has heavy computing needs.

1. Deadlock Prevention

 Deadlocks can be prevented by preventing at least one of the four required

conditions:

Mutual Exclusion

 Shared resources such as read-only files do not lead to deadlocks.

 Unfortunately some resources, such as printers and tape drives, require exclusive
access by a single process.
Hold and Wait

 To prevent this condition processes must be prevented from holding one or more
resources while simultaneously waiting for one or more others. There are several
possibilities for this:
o Require that all processes request all resources at one time. This can be
wasteful of system resources if a process needs one resource early in its
execution and doesn't need some other resource until much later.
o Require that processes holding resources must release them before
requesting new resources, and then re-acquire the released resources along
with the new ones in a single new request. This can be a problem if a
process has partially completed an operation using a resource and then
fails to get it re-allocated after releasing it.
o Either of the methods described above can lead to starvation if a process
requires one or more popular resources.

No Preemption

 Preemption of process resource allocations can prevent this condition of

deadlocks, when it is possible.
o One approach is that if a process is forced to wait when requesting a new
resource, then all other resources previously held by this process are
implicitly released, ( preempted ), forcing this process to re-acquire the
old resources along with the new resources in a single request, similar to
the previous discussion.
o Another approach is that when a resource is requested and not available,
then the system looks to see what other processes currently have those
resources and are themselves blocked waiting for some other resource. If
such a process is found, then some of their resources may get preempted
and added to the list of resources for which the process is waiting.
o Either of these approaches may be applicable for resources whose states
are easily saved and restored, such as registers and memory, but are
generally not applicable to other devices such as printers and tape drives.

Circular Wait

 One way to avoid circular wait is to number all resources, and to require that
processes request resources only in strictly increasing ( or decreasing ) order.
 In other words, in order to request resource Rj, a process must first release all Ri
such that i >= j.
 One big challenge in this scheme is determining the relative ordering of the
different resources
[Link] Avoidance

 The general idea behind deadlock avoidance is to prevent deadlocks from ever
happening, by preventing at least one of the aforementioned conditions.
 This requires more information about each process, and tends to lead to low
device utilization. ( I.e. it is a conservative approach. )
 In some algorithms the scheduler only needs to know the maximum number of
each resource that a process might potentially use. In more complex algorithms
the scheduler can also take advantage of the schedule of exactly what resources
may be needed in what order.
 When a scheduler sees that starting a process or granting resource requests may
lead to future deadlocks, then that process is just not started or the request is not
granted.
 A resource allocation state is defined by the number of available and allocated
resources, and the maximum requirements of all processes in the system.

Safe State

 A state is safe if the system can allocate all resources requested by all processes
( up to their stated maximums ) without entering a deadlock state.
 More formally, a state is safe if there exists a safe sequence of processes { P0,
P1, P2, ..., PN } such that all of the resource requests for Pi can be granted using
the resources currently allocated to Pi and all processes Pj where j < i. ( I.e. if all
the processes prior to Pi finish and free up their resources, then Pi will be able
to finish also, using the resources that they have freed up. )
 If a safe sequence does not exist, then the system is in an unsafe state,
which MAY lead to deadlock. ( All safe states are deadlock free, but not all
unsafe states lead to deadlocks. )

Safe, unsafe, and deadlocked state spaces.

  For example, consider a system with 12 tape drives, allocated as follows. Is this
a safe state? What is the safe sequence?

Maximum Needs Current Allocation

P0 10 5
P1 4 2
P2 9 2

 What happens to the above table if process P2 requests and is granted one more
tape drive?
 Key to the safe state approach is that when a request is made for resources, the
request is granted only if the resulting allocation state is a safe one.

7.5.2 Resource-Allocation Graph Algorithm

 If resource categories have only single instances of their resources, then

deadlock states can be detected by cycles in the resource-allocation graphs.
 In this case, unsafe states can be recognized and avoided by augmenting the
resource-allocation graph with claim edges, noted by dashed lines, which point
from a process to a resource that it may request in the future.
 In order for this technique to work, all claim edges must be added to the graph
for any particular process before that process is allowed to request any resources.
( Alternatively, processes may only make requests for resources for which they
have already established claim edges, and claim edges cannot be added to any
process that is currently holding resources. )
 When a process makes a request, the claim edge Pi->Rj is converted to a request
edge. Similarly when a resource is released, the assignment reverts back to a
claim edge.
 This approach works by denying requests that would produce cycles in the
resource-allocation graph, taking claim edges into effect.
 Consider for example what happens when process P2 requests resource R2:
Figure 7.7 - Resource allocation graph for deadlock avoidance

 The resulting resource-allocation graph would have a cycle in it, and so the
request cannot be granted.

Figure 7.8 - An unsafe state in a resource allocation graph

7.5.3 Banker's Algorithm

 For resource categories that contain more than one instance the resource-
allocation graph method does not work, and more complex ( and less efficient )
methods must be chosen.
 The Banker's Algorithm gets its name because it is a method that bankers could
use to assure that when they lend out resources they will still be able to satisfy
all their clients. ( A banker won't loan out a little money to start building a house
unless they are assured that they will later be able to loan out the rest of the
money to finish the house. )
 When a process starts up, it must state in advance the maximum allocation of
resources it may request, up to the amount available on the system.
 When a request is made, the scheduler determines whether granting the request
would leave the system in a safe state. If not, then the process must wait until
the request can be granted safely.
 The banker's algorithm relies on several key data structures: (where n is the
number of processes and m is the number of resource categories. )

o Available[ m ] indicates how many resources are currently available of

each type.
o Max[ n ][ m ] indicates the maximum demand of each process of each
resource.
o Allocation[ n ][ m ] indicates the number of each resource category
allocated to each process.
o Need[ n ][ m ] indicates the remaining resources needed of each type for
each process. ( Note that Need[ i ][ j ] = Max[ i ][ j ] - Allocation[ i ][ j ]
for all i, j. )
o One row of the Need vector, Need[ i ], can be treated as a vector
corresponding to the needs of process i, and similarly for Allocation and
Max.
o A vector X is considered to be <= a vector Y if X[ i ] <= Y[ i ] for all i.

[Link] Safety Algorithm

 In order to apply the Banker's algorithm, we first need an algorithm for

determining whether or not a particular state is safe.
 This algorithm determines if the current state of a system is safe, according to
the following steps:
1. Let Work and Finish be vectors of length m and n respectively.
 Work is a working copy of the available resources, which will be
modified during the analysis.
 Finish is a vector of booleans indicating whether a particular
process can finish. ( or has finished so far in the analysis. )
 Initialize Work to Available, and Finish to false for all elements.
2. Find an i such that both
 (A) Finish[ i ] == false, and

(B) Need[ i ] < Work.

This process has not finished, but could with the given available
working set. If no such i exists, go to step 4.

3. Set Work = Work + Allocation[ i ], and set Finish[ i ] to true. This

corresponds to process i finishing up and releasing its resources back into
the work pool. Then loop back to step 2.
4. If finish[ i ] == true for all i, then the state is a safe state, because a safe
sequence has been found.

[Link] Resource-Request Algorithm ( The Bankers Algorithm )

 Now that we have a tool for determining if a particular state is safe or not, we
are now ready to look at the Banker's algorithm itself.
 This algorithm determines if a new request is safe, and grants it only if it is safe
to do so.
 When a request is made ( that does not exceed currently available resources ),
pretend it has been granted, and then see if the resulting state is a safe one. If so,
grant the request, and if not, deny the request, as follows:
1. Let Request[ n ][ m ] indicate the number of resources of each type
currently requested by processes. If Request[ i ] > Need[ i ] for any process
i, raise an error condition.
2. If Request[ i ] > Available for any process i, then that process must wait
for resources to become available. Otherwise the process can continue to
step 3.
3. Check to see if the request can be granted safely, by pretending it has been
granted and then seeing if the resulting state is safe. If so, grant the request,
and if not, then the process must wait until its request can be granted
safely. The procedure for granting a request ( or pretending to for testing
purposes ) is:
 Available = Available - Request
 Allocation = Allocation + Request
 Need = Need - Request

[Link] An Illustrative Example

 Consider the following situation:

  And now consider what happens if process P1 requests 1 instance of A and 2
instances of C. ( Request[ 1 ] = ( 1, 0, 2 ) )

 What about requests of ( 3, 3,0 ) by P4? or ( 0, 2, 0 ) by P0? Can these be safely

granted? Why or why not?

7.6 Deadlock Detection

 If deadlocks are not avoided, then another approach is to detect when they have
occurred and recover somehow.
 In addition to the performance hit of constantly checking for deadlocks, a policy
/ algorithm must be in place for recovering from deadlocks, and there is potential
for lost work when processes must be aborted or have their resources preempted.

7.6.1 Single Instance of Each Resource Type

 If each resource category has a single instance, then we can use a variation of
the resource-allocation graph known as a wait-for graph.
 A wait-for graph can be constructed from a resource-allocation graph by
eliminating the resources and collapsing the associated edges, as shown in the
figure below.
  An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for a
resource that process Pj is currently holding.

Figure 7.9 - (a) Resource allocation graph. (b) Corresponding wait-for graph

 As before, cycles in the wait-for graph indicate deadlocks.

 This algorithm must maintain the wait-for graph, and periodically search it for
cycles.

7.6.2 Several Instances of a Resource Type

 The detection algorithm outlined here is essentially the same as the Banker's
algorithm, with two subtle differences:
o In step 1, the Banker's Algorithm sets Finish[ i ] to false for all i. The
algorithm presented here sets Finish[ i ] to false only if Allocation[ i ] is
not zero. If the currently allocated resources for this process are zero, the
algorithm sets Finish[ i ] to true. This is essentially assuming that IF all of
the other processes can finish, then this process can finish also.
Furthermore, this algorithm is specifically looking for which processes
are involved in a deadlock situation, and a process that does not have any
resources allocated cannot be involved in a deadlock, and so can be
removed from any further consideration.
o Steps 2 and 3 are unchanged
o In step 4, the basic Banker's Algorithm says that if Finish[ i ] == true for
all i, that there is no deadlock. This algorithm is more specific, by stating
that if Finish[ i ] == false for any process Pi, then that process is
specifically involved in the deadlock which has been detected.
  Now suppose that process P2 makes a request for an additional instance of type
C, yielding the state shown below. Is the system now deadlocked?

7.6.3 Detection-Algorithm Usage

There are two approaches, each with trade-offs:

1. Do deadlock detection after every resource allocation which cannot be

immediately granted. This has the advantage of detecting the deadlock
right away, while the minimum number of processes are involved in the
deadlock.
2. Do deadlock detection only when there is some clue that a deadlock may
have occurred, such as when CPU utilization reduces to 40%. The
advantage is that deadlock detection is done much less frequently.

7.7 Recovery From Deadlock

 There are three basic approaches to recovery from deadlock:

1. Inform the system operator, and allow him/her to take manual
intervention.
2. Terminate one or more processes involved in the deadlock
3. Preempt resources.
7.7.1 Process Termination

 Two basic approaches, both of which recover resources allocated to terminated

processes:
o Terminate all processes involved in the deadlock. This definitely solves
the deadlock, but at the expense of terminating more processes than would
be absolutely necessary.
o Terminate processes one by one until the deadlock is broken. This is more
conservative, but requires doing deadlock detection after each step.
 In the latter case there are many factors that can go into deciding which processes
to terminate next:
1. Process priorities.
2. How long the process has been running, and how close it is to finishing.
3. How many and what type of resources is the process holding.
4. How many more resources does the process need to complete.
5. How many processes will need to be terminated

7.7.2 Resource Preemption

 When preempting resources to relieve deadlock, there are three important issues
to be addressed:
1. Selecting a victim - Deciding which resources to preempt from which
processes involves many of the same decision criteria outlined above.
2. Rollback - Ideally one would like to roll back a preempted process to a
safe state prior to the point at which that resource was originally allocated
to the process. Unfortunately it can be difficult or impossible to determine
what such a safe state is, and so the only safe rollback is to roll back all
the way back to the beginning.
3. Starvation - How do you guarantee that a process won't starve because
its resources are constantly being preempted? One option would be to use
a priority system, and increase the priority of a process every time its
resources get preempted.