OPERATING SYSTEM

Unit 3: Concurrency Control

Process Synchronization is the coordination of execution of multiple processes in a

multi-process system to ensure that they access shared resources in a controlled and
predictable manner. It aims to resolve the problem of race conditions and other
synchronization issues in a concurrent system.
The main objective of process synchronization is to ensure that multiple processes
access shared resources without interfering with each other and to prevent the
possibility of inconsistent data due to concurrent access. To achieve this, various
synchronization techniques such as semaphores, monitors, and critical sections are used.
In a multi-process system, synchronization is necessary to ensure data consistency and
integrity, and to avoid the risk of deadlocks and other synchronization problems.
Process synchronization is an important aspect of modern operating systems, and it
plays a crucial role in ensuring the correct and efficient functioning of multi-process
systems.
On the basis of synchronization, processes are categorized as one of the following two
types:

• Independent Process: The execution of one process does not affect the
execution of other processes.
• Cooperative Process: A process that can affect or be affected by other processes
executing in the system.
Process synchronization problem arises in the case of Cooperative processes also
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
because resources are shared in Cooperative processes.
Race Condition
When more than one process is executing the same code or accessing the samememory
or any shared variable in that condition there is a possibility that the outputor the
value of the shared variable is wrong so for that all the processes doing the race to say
that my output is correct this condition known as a race condition. Several processes
access and process the manipulations over the same data concurrently, and then the
outcome depends on the particular order in which the access takes place.A race
condition is a situation that may occur inside a critical section. This happens when the
result of multiple thread execution in the critical section differs according to the order
in which the threads execute. Race conditions in critical sections can be avoided if the
critical section is treated as an atomic instruction. Also, proper thread synchronization
using locks or atomic variables can prevent race conditions.
Example:
Let’s understand one example to understand the race condition better:
Let’s say there are two processes P1 and P2 which share a common variable
(shared=10), both processes are present in – queue and waiting for their turn to be
executed. Suppose, Process P1 first come under execution, and the CPU store a common
variable between them (shared=10) in the local variable (X=10) and increment it by
1(X=11), after then when the CPU read line sleep(1),it switches from current process
P1 to process P2 present in ready-queue. The process P1 goes in a waiting state for 1
second.
Now CPU execute the Process P2 line by line and store common variable (Shared=10)
in its local variable (Y=10) and decrement Y by 1(Y=9), after then when CPU read
sleep(1), the current process P2 goes in waiting for state and CPU remains idle for some
time as there is no process in ready-queue, after completion of 1 second of process P1
when it comes in ready-queue, CPU takes the process P1 under execution and execute
the remaining line of code (store the local variable (X=11) in common variable
(shared=11) ), CPU remain idle for sometime waiting for any process in ready-
queue,after completion of 1 second of Process P2, when process P2 comes in ready-
queue, CPU start executing the further remaining line of Process P2(store the local
variable (Y=9) in common variable (shared=9) ).
Initially Shared = 10

Note: We are assuming the final value of a common variable(shared) after execution
of Process P1 and Process P2 is 10 (as Process P1 increment variable (shared=10) by
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
1 and Process P2 decrement variable (shared=11) by 1 and finally it becomes
shared=10). But we are getting undesired value due to a lack of
propersynchronization.
Actual meaning of race-condition
• If the order of execution of the process(first P1 -> then P2) then we will get the
value of common variable (shared) =9.
• If the order of execution of the process(first P2 -> then P1) then we will get the
final value of common variable (shared) =11.
• Here the (value1 = 9) and (value2=10) are racing, If we execute these two
processes in our computer system then sometime we will get 9 and sometime we
will get 10 as the final value of a common variable(shared). This phenomenon is
called race condition.
Critical Section Problem
A critical section is a code segment that can be accessed by only one process at a time.
The critical section contains shared variables that need to be synchronized to maintain
the consistency of data variables. So the critical section problem means designing a way
for cooperative processes to access shared resources without creating data
inconsistencies.

In the entry section, the process requests for entry in the Critical Section.
Any solution to the critical section problem must satisfy three requirements:
• Mutual Exclusion: If a process is executing in its critical section, then no other
process is allowed to execute in the critical section.
• Progress: If no process is executing in the critical section and other processes are
waiting outside the critical section, then only those processes that are not
executing in their remainder section can participate in deciding which will enter
the critical section next, and the selection can not be postponed indefinitely.
• Bounded Waiting: A bound must exist on the number of times that other
processes are allowed to enter their critical sections after a process has made a
request to enter its critical section and before that request is granted.
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
Peterson’s Solution
Peterson’s Solution is a classical software-based solution to
the critical section problem. In Peterson’s solution, we have
two shared variables:
• boolean flag[i]: Initialized to FALSE, initially no one is interested in entering the
critical section
• int turn: The process whose turn is to enter the critical section.

Peterson’s Solution preserves all three conditions:

• Mutual Exclusion is assured as only one process can access the critical section at
any time.
• Progress is also assured, as a process outside the critical section does not block
other processes from entering the critical section.
• Bounded Waiting is preserved as every process gets a fair chance.
Disadvantages of Peterson’s Solution
• It involves busy waiting. (In the Peterson’s solution, the code statement-
“while(flag[j] && turn == j);” is responsible for this. Busy waiting is not favored
because it wastes CPU cycles that could be used to perform other tasks.)
• It is limited to 2 processes.
• Peterson’s solution cannot be used in modern CPU architectures.

Mutual Exclusion
Mutual Exclusion is a property of process synchronization that states that “no two
processes can exist in the critical section at any given point of time”. The term was
first coined by Dijkstra. Any process synchronization technique being used must
satisfy the property of mutual exclusion, without which it would not be possible to
get rid of a race condition.
The need for mutual exclusion comes with concurrency. There are several kinds of
concurrent execution:
1. Interrupt handlers
2. Interleaved, preemptively scheduled processes/threads
3. Multiprocessor clusters, with shared memory
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
4. Distributed systems
Mutual exclusion methods are used in concurrent programming to avoid the
simultaneous use of a common resource, such as a global variable, by pieces of
computer code called critical sections.

The requirement of mutual exclusion is that when process P1 is accessing a shared

resource R1, another process should not be able to access resource R1 until process
P1 has finished its operation with resource R1.
Examples of such resources include files, I/O devices such as printers, and shared
data structures.
Conditions Required for Mutual Exclusion
According to the following four criteria, mutual exclusion is applicable:
1. When using shared resources, it is important to ensure mutual exclusion between
various processes. There cannot be two processes running simultaneously in
either of their critical sections.
2. It is not advisable to make assumptions about the relative speeds of the unstable
processes.
3. For access to the critical section, a process that is outside of it must not obstruct
another process.
4. Its critical section must be accessible by multiple processes in a finite amount of
time; multiple processes should never be kept waiting in an infinite loop.
Approaches To Implementing Mutual Exclusion
1. Software method: Leave the responsibility to the processes themselves. These
methods are usually highly error-prone and carry high overheads.
2. Hardware method: Special-purpose machine instructions are used for accessing
shared resources. This method is faster but cannot provide a complete solution.
Hardware solutions cannot give guarantee the absence of deadlock and starvation.
3. Programming language method: Provide support through the operating system
or through the programming language.
Requirements of Mutual Exclusion
1. At any time, only one process is allowed to enter its critical section.
2. The solution is implemented purely in software on a machine.
3. A process remains inside its critical section for a bounded time only.
4. No assumption can be made about the relative speeds of asynchronous
concurrent processes.
5. A process cannot prevent any other process from entering into a critical section.
6. A process must not be indefinitely postponed from entering its critical section.
In order to understand mutual exclusion, let’s take an example.
What is a Need for Mutual Exclusion?
An easy way to visualize the significance of mutual exclusion is to imagine a linked
list of several items, with the fourth and fifth items needing to be removed. By
changing the previous node’s next reference to point to the succeeding node, the
node that lies between the other two nodes is deleted.
To put it simply, whenever node “i” wants to be removed, node “with – 1″‘s
subsequent reference is changed to point to node “ith + 1” at that time. Two distinct
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
nodes can be removed by two threads at the same time when a shared linked list is
being used by many threads. This occurs when the first thread modifies node “ith –
1” next reference, pointing towards the node “ith + 1,” and the second thread
modifies node “ith” next reference, pointing towards the node “ith + 2.” Although
both nodes have been removed, the linked list’s required state has not yet been
reached because node “i + 1” still exists in the list because node “ith – 1” next
reference still points to it.
Now, this situation is called a race condition. Race conditions can be prevented by
mutual exclusion so that updates at the same time cannot happen to the very bit
about the list.
Example:
In the clothes section of a supermarket, two people are shopping for clothes.

Boy, A decides upon some clothes to buy and heads to the changing room to try
them out. Now, while boy A is inside the changing room, there is an ‘occupied’ sign
on it – indicating that no one else can come in. Girl B has to use the changing room
too, so she has to wait till boy A is done using the changing

room.
Once boy A comes out of the changing room, the sign on it changes from ‘occupied’
to ‘vacant’ – indicating that another person can use it. Hence, girl B proceeds to use
the changing room, while the sign displays ‘occupied’ again.
The changing room is nothing but the critical section, boy A and girl B are two
different processes, while the sign outside the changing room indicates the process
synchronization mechanism being used.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Semaphores in Process Synchronization
Semaphores are just normal variables used to coordinate the activities of multiple
processes in a computer system. They are used to enforce mutual exclusion, avoid race
conditions, and implement synchronization between processes.
The process of using Semaphores provides two operations: wait (P) and signal (V). The
wait operation decrements the value of the semaphore, and the signal operation
increments the value of the semaphore. When the value of the semaphore is zero, any
process that performs a wait operation will be blocked until another process performs
a signal operation.
Semaphores are used to implement critical sections, which are regions of code that must
be executed by only one process at a time. By using semaphores, processes can
coordinate access to shared resources, such as shared memory or I/O devices.
A semaphore is a special kind of synchronization data that can be used only through
specific synchronization primitives. When a process performs a wait operation on a
semaphore, the operation checks whether the value of the semaphore is >0. If so, it
decrements the value of the semaphore and lets the process continue its execution;
otherwise, it blocks the process on the semaphore. A signal operation on a semaphore
activates a process blocked on the semaphore if any, or increments the value of the
semaphore by 1. Due to these semantics, semaphores are also called counting
semaphores. The initial value of a semaphore determines how many processes can get
past the wait operation.
Semaphores are of two types:
1. Binary Semaphore –
This is also known as a mutex lock. It can have only two values – 0 and 1. Its
value is initialized to 1. It is used to implement the solution of critical section
problems with multiple processes.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
2. Counting Semaphore –
Its value can range over an unrestricted domain. It is used to control access to a
resource that has multiple instances.
Now let us see how it does so.
First, look at two operations that can be used to access and change the value of the
semaphore variable.

Some points regarding P and V operation:

1. P operation is also called wait, sleep, or down operation, and V operation is also
called signal, wake-up, or up operation.
2. Both operations are atomic and semaphore(s) is always initialized to one. Here
atomic means that variable on which read, modify and update happens at the
same time/moment with no pre-emption i.e. in-between read, modify and update
no other operation is performed that may change the variable.
3. A critical section is surrounded by both operations to implement process
synchronization. See the below image. The critical section of Process P is in
between P and V operation.

Now, let us see how it implements mutual exclusion. Let there be two processes P1 and
P2 and a semaphore s is initialized as 1. Now if suppose P1 enters in its critical section
then the value of semaphore s becomes 0. Now if P2 wants to enter its critical section
then it will wait until s > 0, this can only happen when P1 finishes its critical section
and calls V operation on semaphore s.
This way mutual exclusion is achieved. Look at the below image for details which is
a Binary semaphore.
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
Limitations :
1. One of the biggest limitations of semaphore is priority inversion.
2. Deadlock, suppose a process is trying to wake up another process that is not in a
sleep state. Therefore, a deadlock may block indefinitely.
3. The operating system has to keep track of all calls to wait and signal the
semaphore.
Problem in this implementation of a semaphore:
The main problem with semaphores is that they require busy waiting, If a process is
in the critical section, then other processes trying to enter the critical section will be
waiting until the critical section is not occupied by any process. Whenever any process
waits then it continuously checks for semaphore value (look at this line while (s==0);
in P operation) and waste CPU cycle.
There is also a chance of “spinlock” as the processes keep on spins while waiting for
the lock.
Advantages of Semaphores:
• A simple and effective mechanism for process synchronization
• Supports coordination between multiple processes
• Provides a flexible and robust way to manage shared resources.
• It can be used to implement critical sections in a program.
• It can be used to avoid race conditions.
Disadvantages of Semaphores:
• It Can lead to performance degradation due to overhead associated with wait and
signal operations.
• Can result in deadlock if used incorrectly.
• It was proposed by Dijkstra in 1965 which is a very significant technique to
manage concurrent processes by using a simple integer value, which is known as
a semaphore. A semaphore is simply an integer variable that is shared between
threads. This variable is used to solve the critical section problem and to achieve
process synchronization in the multiprocessing environment.
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
• It can cause performance issues in a program if not used properly.
• It can be difficult to debug and maintain.
• It can be prone to race conditions and other synchronization problems if not used
correctly.
• It can be vulnerable to certain types of attacks, such as denial of service attacks.

Difference Between Binary Semaphore and Mutex

Binary Semaphore Mutex

Its functions based up on signalling mechanism Its functions based up on locking mechanism

The thread which is having higher priority than

The thread which has acquired mutex can only
current thread can also release binary semaphore and
release Mutex when it exits from critical section.
take lock.

Semaphore value is changed according to wait () and Mutex values can be modified just as locked or
signal () operations. unlocked.

Multiple number of threads can acquire binary

Only one thread can acquire mutex at a time
semaphore at a time concurrently.

There is ownership associated with mutex

Binary semaphore have no ownership.
because only owner can release the lock.

They are slower than binary semaphores

They are faster than mutex because any other
because only thread which has acquired must
thread/process can unlock binary semaphore.
release the lock.

If you have number of instances for resource it is If you have single instance for resource it is
better to use Binary semaphore. better to use mutex.

Conclusion
In essence, both binary semaphores and mutexes help manage access to shared
resources in a multi-threaded environment, but their primary difference lies in their
intended use cases. Binary semaphores are often used for signaling and coordination
between threads, while mutexes are focused on providing mutual exclusion to ensure
thread-safe access to critical sections.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Synchronization Problems
These problems are used for testing nearly every newly proposed synchronization
scheme. The following problems of synchronization are considered as classical
problems:
Bounded-buffer (or Producer-Consumer) Problem,
Dining-Philosophers Problem,
Readers and Writers Problem.

Bounded-buffer (or Producer-Consumer) Problem

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
So to Avoid Bounded Buffer (i.e. Producer Consumer Problem ) we require Process
Synchronization.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Readers-Writers Problem
Consider a situation where we have a file shared between many people.
• If one of the person tries editing the file, no other person should be reading or
writing at the same time, otherwise changes will not be visible to him/her.
• However, if some person is reading the file, then others may read it at the same
time.

Precisely in OS, we call this situation the readers-writer, problem

Problem parameters: that

• One set of data is shared among a number of processes
• Once a writer is ready, it performs its write. Only one writer may write at a time
• If a process is writing, no other process can read it
• If at least one reader is reading, no other process can write
• Readers may not write and only read
Solution when Reader has the Priority over Writer
There are four types of cases that could happen here.
Case Process 1 Process 2 Allowed/Not Allowed

Case 1 Writing Writing Not Allowed

Case 2 Writing Reading Not Allowed

Case 3 Reading Writing Not Allowed

Case 4 Reading Reading Allowed

Here priority means, no reader should wait if the share is currently opened for
reading.

Three variables are used: mutex, wrt, readcnt to implement solution

1. semaphore mutex, wrt; // semaphore mutex is used to ensure mutual exclusion

when readcnt is updated i.e. when any reader enters or exit from the critical
section and semaphore wrt is used by both readers and writers
2. int readcnt; // readcnt tells the number of processes performing read in the
critical section, initially 0

Functions for semaphore :

– wait() : decrements the semaphore value.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
– signal() : increments the semaphore value.

Writer process:
1. Writer requests the entry to critical section.
2. If allowed i.e. wait() gives a true value, it enters and performs the write. If not
allowed, it keeps on waiting.
3. It exits the critical section.

do {
// writer requests for critical sectionwait(wrt);

// performs the write

// leaves the critical sectionsignal(wrt);

} while(true);

Reader process:
1. Reader requests the entry to critical section.
2. If allowed:

• it increments the count of number of readers inside the critical section. If this
reader is the first reader entering, it locks the wrt semaphore to restrict the
entry of writers if any reader is inside.
• It then, signals mutex as any other reader is allowed to enter while others are
already reading.
• After performing reading, it exits the critical section. When exiting, it checks
if no more reader is inside, it signals the semaphore “wrt” as now, writer can
enter the critical section.
3. If not allowed, it keeps on waiting.

do {

// Reader wants to enter the critical sectionwait(mutex);

// The number of readers has now increased by 1readcnt++;

// there is atleast one reader in the critical section

// this ensure no writer can enter if there is even one reader
// thus we give preference to readers here
if (readcnt==1)

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
 wait(wrt);

// other readers can enter while this current reader is inside

// the critical section
signal(mutex);

// current reader performs reading here wait(mutex); //

a reader wants to leave

readcnt--;

// that is, no reader is left in the critical section,if (readcnt == 0)

signal(wrt); // writers can enter

signal(mutex); // reader leaves

} while(true);

Thus, the semaphore ‘wrt‘ is queued on both readers and writers in a manner such
that preference is given to readers if writers are also there. Thus, no reader is waiting
simply because a writer has requested to enter the critical section.

Dining Philosopher Problem Using Semaphores

(In notes I have given you e.g of Rice and forks on dining table) as follow—

***here its noodles and chopstick Below

The Dining Philosopher Problem states that K philosophers are seated around a
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
circular table with one chopstick between each pair of philosophers. There is one
chopstick between each philosopher. A philosopher may eat if he can pick up the
two chopsticks adjacent to him. One chopstick may be picked up by any one of its
adjacent followers but not both.

Semaphore Solution to Dining Philosopher

Each philosopher is represented by the following pseudocode:
process P[i] while true
do
{ THINK;
PICKUP(CHOPSTICK[i], CHOPSTICK[i+1 mod 5]);EAT;
PUTDOWN(CHOPSTICK[i], CHOPSTICK[i+1 mod 5])
}

There are three states of the philosopher: THINKING, HUNGRY, and EATING.
Here there are two semaphores: Mutex and a semaphore array for the philosophers.
Mutex is used such that no two philosophers may access the pickup or put it down at
the same time. The array is used to control the behavior of each philosopher
The Dining Philosopher Problem is a classic synchronization problem in computer
science that involves multiple processes (philosophers) sharing a limited set of
resources (forks) in order to perform a task (eating). In order to avoid deadlock or
starvation, a solution must be implemented that ensures that each philosopher can access
the resources they need to perform their task without interference from other
philosophers.
One common solution to the Dining Philosopher Problem uses semaphores, a
synchronization mechanism that can be used to control access to shared resources. In
this solution, each fork is represented by a semaphore, and a philosopher must acquire
both the semaphore for the fork to their left and the semaphore for the fork to their right
before they can begin eating. If a philosopher cannot acquire both semaphores, they
must wait until they become available.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
The steps for the Dining Philosopher Problem solution using semaphores are
as follows
1. Initialize the semaphores for each fork to 1 (indicating that they are available).
2. Initialize a binary semaphore (mutex) to 1 to ensure that only one philosopher can
attempt to pick up a fork at a time.
3. For each philosopher process, create a separate thread that executes the following
code:
• While true:
Think for a random amount of time.
Acquire the mutex semaphore to ensure that only one philosopher can
attempt to pick up a fork at a time.
Attempt to acquire the semaphore for the fork to the left.
• If successful, attempt to acquire the semaphore for the fork to the right.
• If both forks are acquired successfully, eat for a random amount of time and then
release both semaphores.
• If not successful in acquiring both forks, release the semaphore for the fork to the
left (if acquired) and then release the mutex semaphore and go back to thinking

By using semaphores to control access to the forks, the Dining Philosopher Problem can
be solved in a way that avoids deadlock and starvation. The use of the mutex semaphore
ensures that only one philosopher can attempt to pick up a fork at a time, while the use
of the fork semaphores ensures that a philosopher can only eat if both forks are
available.

Overall, the Dining Philosopher Problem solution using semaphores is a classic

example of how synchronization mechanisms can be used to solve complex
synchronization problems in concurrent programming.
Problem with Dining Philosopher
We have demonstrated that no two nearby philosophers can eat at the same time from
the aforementioned solution to the dining philosopher problem. The problem with the
above solution is that it might result in a deadlock situation. If every philosopher picks
their left chopstick simultaneously, a deadlock results, and no philosopher can eat. This
situation occurs when this happens.
Some of the solutions include the following:
1. The maximum number of philosophers at the table should not exceed four; in this
case, philosopher P3 will have access to chopstick C4; he will then begin eating,
and when he is finished, he will put down both chopsticks C3 and C4; as a result,
semaphore C3 and C4 will now be incremented to 1.
2. Now that philosopher P2, who was holding chopstick C2, will also have
chopstick C3, he will do the same when finished eating, allowing other
philosophers to eat.
3. While a philosopher in an odd position should select the right chopstick first, a
philosopher in an even position should select the left chopstick and then the right
chopstick.
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
4. A philosopher should only be permitted to choose their chopsticks if both of the
available chopsticks (the left and the right) are available at the same time.
5. All four of the initial philosophers (P0, P1, P2, and P3) should choose the left
chopstick before choosing the right, while P4 should choose the right chopstick
before choosing the left. As a result, P4 will be forced to hold his right chopstick
first because his right chopstick, C0, is already being held by philosopher P0 and
its value is set to 0. As a result, P4 will become trapped in an infinite loop and
chopstick C4 will remain empty. As a result, philosopher P3 has both the left C3
and the right C4. chopstick available, therefore it will start eating and will put
down both chopsticks once finishes and let others eat which removes the problem
of deadlock.

Deadlock
A 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.

Consider an example when two trains are coming toward each other on the same
track and there is only one track, none of the trains can move once they are in front
of each other. A similar situation occurs in operating systems when there are two or
more processes that hold some resources and wait for resources held by other(s). 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.

Examples Of Deadlock
1. The system has 2 tape drives. P0 and P1 each hold one tape drive and each needs
another one.
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
2. Semaphores A and B, initialized to 1, P0, and P1 are in deadlock as follows:
• P0 executes wait(A) and preempts.
• P1 executes wait(B).
• Now P0 and P1 enter in deadlock.

P0 P1

wait(A); wait(B)

wait(B); wait(A)

3. Assume the space is available for allocation of 200K bytes, and the following
sequence of events occurs.

P0 P1

Request 80KB; Request 70KB;

Request 60KB; Request 80KB;

Deadlock occurs if both processes progress to their second request.

Deadlock can arise if the following four conditions hold simultaneously
(Necessary Conditions)
Mutual Exclusion: Two or more resources are non-shareable (Only one process can
use at a time)
Hold and Wait: A process is holding at least one resource and waiting for
resources.
No Preemption: A resource cannot be taken from a process unless the process
releases the resource.
Circular Wait: A set of processes waiting for each other in circular form.

Conditions(Characterization) for Deadlock in

Operating System
Necessary Conditions for the Occurrence of a Deadlock
Let’s explain all four conditions related to deadlock in the context of the scenario
with two processes and two resources:
Mutual Exclusion
This condition requires that at least one resource be held in a non-shareable mode,
which means that only one process can use the resource at any given time. Both
Resource 1 and Resource 2 are non-shareable in our scenario, and only one process
can have exclusive access to each resource at any given time.
Course Name--Operating Systems
Unit 3: Concurrency Control Semester III
Course Code
As an example:
• Process A obtains Resource 1.
• Process B acquires Resource 2.
Hold and Wait
The hold and wait condition specifies that a process must be holding at least one
resource while waiting for other processes to release resources that are currently held
by other processes. In our example,
• Process A has Resource 1 and is awaiting Resource 2.
• Process B currently has Resource 2 and is awaiting Resource 1.
• Both processes hold one resource while waiting for the other, satisfying the hold
and wait condition.
No Preemption
Preemption is the act of taking a resource from a process before it has finished its
task. According to the no preemption condition, resources cannot be taken forcibly
from a process a process can only release resources voluntarily after completing its
task. In our scenario, neither Process A nor Process B can be forced to release the
resources in their possession. The processes can only release resources voluntarily.
Circular Wait
This condition implies that circular processes must exist, with each process waiting
for a resource held by the next process in the chain. In our scenario, Process A is
waiting for Resource 2, which is being held by Process B.
Process B is awaiting Resource 1 from Process A.
This circular chain of dependencies causes a deadlock because neither process can
proceed, resulting in a system shutdown.

Disadvantages in Deadlock
Deadlock is an infinite Process it means that once a process goes into deadlock it will
never come out of the loop and the process will enter for an indefinite amount of time.
There are only detection, resolution, and prevention techniques. But, there are no
Deadlock-stopping techniques.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Deadlock Detection And Recovery
Deadlock detection and recovery is the process of detecting and resolving deadlocks
in an operating system. A deadlock occurs when two or more processes are blocked,
waiting for each other to release the resources they need. This can lead to a system-
wide stall, where no process can make progress.

There are two main approaches to deadlock detection and recovery:

1. Prevention: The operating system takes steps to prevent deadlocks from

occurring by ensuring that the system is always in a safe state, where deadlocks
cannot occur. This is achieved through resource allocation algorithms such as the
Banker’s Algorithm.
2. Detection and Recovery: If deadlocks do occur, the operating system must
detect and resolve them. Deadlock detection algorithms, such as the Wait-For
Graph, are used to identify deadlocks, and recovery algorithms, such as the
Rollback and Abort algorithm, are used to resolve them. The recovery algorithm
releases the resources held by one or more processes, allowing the system to
continue to make progress.
Difference Between Prevention and Detection/Recovery: Prevention aims to
avoid deadlocks altogether by carefully managing resource allocation, while
detection and recovery aim to identify and resolve deadlocks that have already
occurred.
Deadlock detection and recovery is an important aspect of operating system design
and management, as it affects the stability and performance of the system. The
choice of deadlock detection and recovery approach depends on the specific
requirements of the system and the trade-offs between performance, complexity, and
risk tolerance. The operating system must balance these factors to ensure that
deadlocks are effectively detected and resolved.
In the previous post, we discussed Deadlock Prevention and Avoidance. In this post,
the Deadlock Detection and Recovery technique to handle deadlock is discussed.

Deadlock Detection :

1. If resources have a single instance –

In this case for Deadlock detection, we can run an algorithm to check for the cycle in
the Resource Allocation Graph. The presence of a cycle in the graph is a sufficient
condition for deadlock.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
In the above diagram, resource 1 and resource 2 have single instances. There is a
cycle R1 → P1 → R2 → P2. So, Deadlock is Confirmed.

2. If there are multiple instances of resources –

Detection of the cycle is necessary but not a sufficient condition for deadlock
detection, in this case, the system may or may not be in deadlock varies according to
different situations.
3. Wait-For Graph Algorithm –
The Wait-For Graph Algorithm is a deadlock detection algorithm used to detect
deadlocks in a system where resources can have multiple instances. The algorithm
works by constructing a Wait-For Graph, which is a directed graph that represents
the dependencies between processes and resources.

Deadlock Recovery :
A traditional operating system such as Windows doesn’t deal with deadlock
recovery as it is a time and space-consuming process. Real-time operating systems
use Deadlock recovery.
1. Killing the process –
Killing all the processes involved in the deadlock. Killing process one by one.
After killing each process check for deadlock again and keep repeating the
process till the system recovers from deadlock. Killing all the processes one by
one helps a system to break circular wait conditions.
2. Resource Preemption –
Resources are preempted from the processes involved in the deadlock, and
preempted resources are allocated to other processes so that there is a possibility
of recovering the system from the deadlock. In this case, the system goes into
starvation.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
3. Concurrency Control – Concurrency control mechanisms are used to prevent
data inconsistencies in systems with multiple concurrent processes. These
mechanisms ensure that concurrent processes do not access the same data at the
same time, which can lead to inconsistencies and errors. Deadlocks can occur in
concurrent systems when two or more processes are blocked, waiting for each
other to release the resources they need. This can result in a system-wide stall,
where no process can make progress. Concurrency control mechanisms can help
prevent deadlocks by managing access to shared resources and ensuring that
concurrent processes do not interfere with each other.

ADVANTAGES & DISADVANTAGES:

Advantages of Deadlock Detection and Recovery in Operating Systems:

1. Improved System Stability: Deadlocks can cause system-wide stalls, and

detecting and resolving deadlocks can help to improve the stability of the system.
2. Better Resource Utilization: By detecting and resolving deadlocks, the
operating system can ensure that resources are efficiently utilized and that the
system remains responsive to user requests.
3. Better System Design: Deadlock detection and recovery algorithms can provide
insight into the behavior of the system and the relationships between processes
and resources, helping to inform and improve the design of the system.

Disadvantages of Deadlock Detection and Recovery in Operating Systems:

1. Performance Overhead: Deadlock detection and recovery algorithms can

introduce a significant overhead in terms of performance, as the system must
regularly check for deadlocks and take appropriate action to resolve them.
2. Complexity: Deadlock detection and recovery algorithms can be complex to
implement, especially if they use advanced techniques such as the Resource
Allocation Graph or Timestamping.
3. False Positives and Negatives: Deadlock detection algorithms are not perfect
and may produce false positives or negatives, indicating the presence of
deadlocks when they do not exist or failing to detect deadlocks that do exist.
4. Risk of Data Loss: In some cases, recovery algorithms may require rolling back
the state of one or more processes, leading to data loss or corruption.
Overall, the choice of deadlock detection and recovery approach depends on the
specific requirements of the system, the trade-offs between performance,
complexity, and accuracy, and the risk tolerance of the system. The operating system
must balance these factors to ensure that deadlocks are effectively detected and
resolved.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Resource Allocation Graph (RAG) in Operating
System
Resource Allocation Graph (RAG)
A resource allocation graphs shows which resource is held by which process and which
process is waiting for a resource of a specific kind. It is amazing and straight – forward
tool to outline how interacting processes can deadlock. Therefore, resource allocation
graph describe what the condition of the system as far as process and resources are
concern like what number of resources are allocated and what is the request of each
process. Everything can be represented in terms of graph. One of the benefit of having
a graph is, sometimes it is conveivable to see a deadlock straight forward by utilizing
RAG and however you probably won’t realize that by taking a glance at the table. Yet
tables are better if the system contains bunches of process and resource and graph is
better if the system contains less number of process and resource.
. So, resource allocation graph is explained to us what is the state of the system in terms
of processes and resources. Like how many resources are available, how many are
allocated and what is the request of each process. Everything can be representedin
terms of the diagram. One of the advantages of having a diagram is, sometimes itis
possible to see a deadlock directly by using RAG, but then you might not be able to
know that by looking at the table. But the tables are better if the system contains lots
of process and resource and Graph is better if the system contains less number of process
and resource. We know that any graph contains vertices and edges.
Types of Vertices in RAG
So RAG also contains vertices and edges. In RAG vertices are two types
1. Process Vertex: Every process will be represented as a process vertex. Generally,
the process will be represented with a circle.
2. Resource Vertex: Every resource will be represented as a resource vertex. It is
also two types:
• Single instance type resource: It represents as a box, inside the box, there will
be one dot.So the number of dots indicate how many instances are present of
each resource type.
• Multi-resource instance type resource: It also represents as a box, inside the
box, there will be many dots present.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
How many Types of Edges are there in RAG?
Now coming to the edges of RAG.There are two types of edges in RAG –
• Assign Edge: If you already assign a resource to a process then it is called
Assign edge.
• Request Edge: It means in future the process might want some resource to
complete the execution, that is called request edge.

So, if a process is using a resource, an arrow is drawn from the resource node to the
process node. If a process is requesting a resource, an arrow is drawn from the
process node to the resource node.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
(Single instances RAG)

If there is a cycle in the Resource Allocation Graph and each resource in the cycle
provides only one instance, then the processes will be in deadlock. For example, if
process P1 holds resource R1, process P2 holds resource R2 and process P1 is
waiting for R2 and process P2 is waiting for R1, then process P1 and process P2 will

be in deadlock.
Here’s another example, that shows Processes P1 and P2 acquiring resources R1 and
R2 while process P3 is waiting to acquire both resources. In this example, there is no
deadlock because there is no circular dependency. So cycle in single-instance
resource type is the sufficient condition for deadlock.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
(Multi-instances RAG)

From the above example, it is not possible to say the RAG is in a safe state or in an
unsafe state.So to see the state of this RAG, let’s construct the allocation matrix and
request matrix.

The total number of processes are three; P1, P2 & P3 and the total number of
resources are two; R1 & R2.
• Allocation matrix –
• For constructing the allocation matrix, just go to the resources and see to which
process it is allocated.
• R1 is allocated to P1, therefore write 1 in allocation matrix and similarly, R2 is
allocated to P2 as well as P3 and for the remaining element just write 0.
• Request matrix –
• In order to find out the request matrix, you have to go to the process and see the
outgoing edges.
• P1 is requesting resource R2, so write 1 in the matrix and similarly, P2
requesting R1 and for the remaining element write 0.
• So now available resource is = (0, 0).
• Checking deadlock (safe or not) –

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Deadlock Avoidance
A deadlock avoidance policy grants a resource request only if it can establish that
granting the request cannot lead to a deadlock either immediately or in the future. The
kernal lacks detailed knowledge about future behavior of processes, so it cannot
accurately predict deadlocks. To facilitate deadlock avoidance under these conditions,
it uses the following conservative approach: Each process declares the maximum
number of resource units of each class that it may require. The kernal permits a process
to request these resource units in stages- i.e. a few resource units at a time- subject to
the maximum number declared by it and uses a worst case analysis technique to check
for the possibility of future deadlocks. A request is granted only if there is no possibility
of deadlocks; otherwise, it remains pending until it can be granted. This approach is
conservative because a process may complete its operation without requiring the
maximum number of units declared by it.
Banker’s Algorithm
Bankers’s Algorithm is a resource allocation and deadlock avoidance algorithm which
test all the request made by processes for resources, it checks for the safe state, and after
granting a request system remains in the safe state it allows the request, and if there is
no safe state it doesn’t allow the request made by the process.
Inputs to Banker’s Algorithm
1. Max needs of resources by each process.
2. Currently, allocated resources by each process.
3. Max free available resources in the system.
The request will only be granted under the below condition
1. If the request made by the process is less than equal to the max needed for that
process.
2. If the request made by the process is less than equal to the freely available
resource in the system.
Timeouts: To avoid deadlocks caused by indefinite waiting, a timeout mechanism can
be used to limit the amount of time a process can wait for a resource. If the help is
unavailable within the timeout period, the process can be forced to release its current
resources and try again later.

Example:
Total resources in system:A B C D
6576

The total number of resources are

Available system resources are:A B C D
3112

Available resources are

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Processes (currently allocated resources):
A B CD
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

Maximum resources we have for a process

Processes (maximum resources):
A B CD
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

Need = Maximum Resources Requirement – Currently AllocatedResources.

Need = maximum resources - currently allocated resources.
Processes (need resources):
A B CD
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

Conclusion
Operating Systems employ deadlock avoidance to prevent deadlock by using the
Banker’s Algorithm or the resource allocation graph.Deadlock
avoidance works by informing the operating system of the resources needed by the
process to finish execution, and the operating system then determines whether or not
the requirements can be met.
The System is said to be in a Safe state if all the resources required by the Process are
satisfied with the resources that are currently available. The
System is said to be in an unsafe state if all of the resource requirements of the Process
cannot be met by the available resources in any way.

NOTE Refer to the example given in class through Galvins Book

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
Deadlock Recovery –
Approaches To Breaking a Deadlock
Process Termination
To eliminate the deadlock, we can simply kill one or more processes. For this, we use
two methods:
1. Abort all the Deadlocked Processes: Aborting all the processes will certainly
break the deadlock but at a great expense. The deadlocked processes may have
been computed for a long time, and the result of those partial computations must
be discarded and there is a probability of recalculating them later.

2. Abort one process at a time until the deadlock is eliminated: Abort one
deadlocked process at a time, until the deadlock cycle is eliminated from the
system. Due to this method, there may be considerable overhead, because, after
aborting each process, we have to run a deadlock detection algorithm to check
whether any processes are still deadlocked.
Advantages of Process Termination
• It is a simple method for breaking a deadlock.
• It ensures that the deadlock will be resolved quickly, as all processes involved in
the deadlock are terminated simultaneously.
• It frees up resources that were being used by the deadlocked processes, making
those resources available for other processes.
Disadvantages of Process Termination
• It can result in the loss of data and other resources that were being used by the
terminated processes.
• It may cause further problems in the system if the terminated processes were
critical to the system’s operation.
• It may result in a waste of resources, as the terminated processes may have
already completed a significant amount of work before being terminated.
For Process

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code
1. Destroy a process: Although killing a process can solve our problem, choosing
which process to kill is more important. The operating system typically
terminates a process after it has completed the least amount of work.
2. End all processes: Although not suggestible, this strategy can be used if the
issue worsens significantly. Because each process will have to start from scratch
after being killed, the system will become inefficient.
Resource Preemption
To eliminate deadlocks using resource preemption, we preempt some resources from
processes and give those resources to other processes. This method will raise three
issues –
1. Selecting a victim: We must determine which resources and which processes are
to be preempted and also in order to minimize the cost.

2. Rollback: We must determine what should be done with the process from which
resources are preempted. One simple idea is total rollback. That means aborting
the process and restarting it.

3. Starvation: In a system, it may happen that the same process is always picked as
a victim. As a result, that process will never complete its designated task. This
situation is called Starvation and must be avoided. One solution is that a process
must be picked as a victim only a finite number of times.

Advantages of Resource Preemption

1. It can help in breaking a deadlock without terminating any processes, thus
preserving data and resources.
2. It is more efficient than process termination as it targets only the resources that
are causing the deadlock.
3. It can potentially avoid the need for restarting the system.
Disadvantages of Resource Preemption
1. It may lead to increased overhead due to the need for determining which
resources and processes should be preempted.
2. It may cause further problems if the preempted resources were critical to the
system’s operation.
3. It may cause delays in the completion of processes if resources are frequently
preempted.

Course Name--Operating Systems

Unit 3: Concurrency Control Semester III
Course Code