Operating System

Unit III: Process Synchronization and Deadlock

Process Synchronization is a mechanism in operating systems used to manage the execution

of multiple processes that access shared resources. Its main purpose is to ensure data
consistency, prevent race conditions and avoid deadlocks in a multi-process environment.

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 is the coordination of multiple cooperating processes in a system to

ensure controlled access to shared resources, thereby preventing race conditions and other
synchronization problems.

mproper Synchronization in Inter Process Communication Environment leads to

following problems:

1. Inconsistency: When two or more processes access shared data at the same
time without proper synchronization. This can lead to conflicting changes, where
one process’s update is overwritten by another, causing the data to become
unreliable and incorrect.

2. Loss of Data: Loss of data occurs when multiple processes try to write or modify
the same shared resource without coordination. If one process overwrites the
data before another process finishes, important information can be lost, leading
to incomplete or corrupted data.
 3. Deadlock: Lack of proper Synchronization leads to Deadlock which means that
two or more processes get stuck, each waiting for the other to release a
resource. Because none of the processes can continue, the system becomes
unresponsive and none of the processes can complete their tasks.

Conditions That Require Process Synchronization

1. Critical Section: 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.

2. Race Condition: A race condition is a situation that may occur inside a critical
section. This happens when the result of multiple process/thread execution in the
critical section differs according to the order in which the threads execute.

3. Pre-emption: Preemption is when the operating system stops a running process to

give the CPU to another process. This allows the system to make sure that important
tasks get enough CPU time. This is important as mainly issues arise when a process has
not finished its job on shared resource and got preempted. The other process might end
up reading an inconsistent value if process synchronization is not done.

Types of Process Synchronization

The two primary type of process Synchronization in an Operating System are:

• Competitive: Two or more processes are said to be in Competitive Synchronization if

and only if they compete for the accessibility of a shared resource.
Lack of Proper Synchronization among Competing process may lead to either
Inconsistency or Data loss.

• Cooperative: Two or more processes are said to be in Cooperative Synchronization if

and only if they get affected by each other i.e. execution of one process affects the
other process.
Lack of Proper Synchronization among Cooperating process may lead to Deadlock.

Classical IPC Problems

Inter-Process Communication (IPC) allows processes to share data and coordinate tasks.
However, when multiple processes interact, problems such as synchronization errors,
resource conflicts, and deadlocks can occur. These challenges are often studied
through classical IPC problems, which provide models for understanding and solving real-
world issues in operating systems.

The main problems include:

 • Producer-Consumer Problem – managing shared buffers without overflow or
underflow.

• Readers-Writers Problem – balancing concurrent reads and exclusive writes.

• Dining Philosophers Problem – preventing deadlock and starvation in shared resource

usage.

• Sleeping Barber Problem – handling synchronization and fairness in service systems.

These problems highlight the need for proper synchronization techniques like
semaphores, mutexes, and monitors.

1. Producer-Consumer Problem

This problem involves two processes:

• Producer: generates data and adds it to a buffer.

• Consumer: removes data from the buffer for processing.

Challenges:

• Buffer Overflow – producer tries to add when the buffer is full.

• Buffer Underflow – consumer tries to remove when the buffer is empty.

Solution: Use synchronization tools like semaphores or mutexes to ensure controlled

access to the buffer.

Producer-Consumer Solution (using Semaphores)

2. Reader-Writer Problem

Here, multiple processes read and write to a shared resource.

• Readers: only read the data.

• Writers: modify the data.

Challenges:

• Allow many readers to access simultaneously.

• Ensure that only one writer writes at a time.

• Prevent readers from reading while a writer is writing.

3. Dining Philosophers Problem

This problem models philosophers seated around a table, each needing two chopsticks to eat.
Chopsticks are shared between neighbors, creating potential conflicts.

Challenges:

• Deadlock – if all philosophers pick up one chopstick and wait for the other.
• Starvation – some philosophers may never get to eat.

Solution: Use semaphores or monitors to coordinate chopstick use and avoid

deadlock.

4. Sleeping Barber Problem

In a barber shop:

• If no customers are present, the barber sleeps.

• If customers arrive and seats are available, they wait.

• If all seats are full, new customers leave.

Challenges:

• Prevent deadlock where no one gets served.

• Ensure fairness so no customer starves waiting too long.

Solution: Semaphores can manage customer queues, chair availability, and barber activity.

Critical Section in Synchronization

A critical section is a part of a program where shared resources (like memory, files, or
variables) are accessed by multiple processes or threads. To avoid problems such as race
conditions and data inconsistency, only one process/thread should execute the critical section
at a time using synchronization techniques. This ensures that operations on shared resources
are performed safely and predictably.

Structure of a Critical Section

1. Entry Section

• The process requests permission to enter the critical section.

• Synchronization tools (e.g., mutex, semaphore) are used to control access.

2. Critical Section: The actual code where shared resources are accessed or modified.
3. Exit Section: The process releases the lock or semaphore, allowing other processes to
enter the critical section.

4. Remainder Section: The rest of the program that does not involve shared resource access.
Critical Section Problem

Shared Resources and Race Conditions

• Shared resources include memory, global variables, files, and databases.

• A race condition occurs when two or more processes attempt to update shared data at
the same time, leading to unexpected results. Example: Two bank transactions
modifying the same account balance simultaneously without synchronization may
lead to incorrect final balance.

It could be visualized using the pseudo-code below

do{
flag=1;
while(flag); // (entry section)
// critical section
if (!flag)
// remainder section
} while(true);

Requirements of a Solution

A good critical section solution must ensure:

1. Correctness - Shared data should remain consistent.

2. Efficiency - Should minimize waiting and maximize CPU utilization.

3. Fairness - No process should be unfairly delayed or starved.

Examples of critical sections in real-world applications

Banking System (ATM or Online Banking)

• Critical Section: Updating an account balance during a deposit or withdrawal.

• Issue if not handled: Two simultaneous withdrawals could result in an incorrect final
balance due to race conditions.

Ticket Booking System (Airlines, Movies, Trains)

• Critical Section: Reserving the last available seat.

• Issue if not handled: Two users may be shown the same available seat and both may
book it, leading to overbooking.

Deadlock

A deadlock is a situation in a computing environment where a set of processes gets

permanently stuck because each process is waiting for a resource held by another process,
and none of them can proceed.
How Does Deadlock Occur in OS?

A process in an operating system typically uses resources in the following sequence:

• Request a resource

• Use the resource

• Release the resource

Deadlock arises when processes hold some resources while waiting for others.

Example:

• Process P1 holds Resource R1 and requests R2.

• Process P2 holds Resource R2 and requests R1.

Neither process can proceed causing a deadlock.

Necessary Conditions for Deadlock in OS

Deadlock can arise if the following four conditions hold simultaneously (Necessary
Conditions)

1. Mutual Exclusion: Only one process can use a resource at any given time i.e. the
resources are non-sharable.

2. Hold and Wait: A process is holding at least one resource at a time and is waiting to
acquire other resources held by some other process.

3. No Preemption: A resource cannot be taken from a process unless the process

releases the resource.
 4. Circular Wait: set of processes are waiting for each other in a circular fashion. For
example, imagine four processes P1, P2, P3, and P4 and four resources R1, R2, R3,
and R4.

The image demonstrates a circular wait deadlock,

here's how:

• P1 is holding R1 and waiting for R2 (which

is held by P2).
• P2 is holding R2 and waiting for R3 (which
is held by P3).
• P3 is holding R3 and waiting for R4 (which
is held by P4).

• P4 is holding R4 and waiting for R1 (which

is held by P1).

Methods of Handling Deadlocks

1. Deadlock Prevention

Deadlock Prevention is a method of handling deadlocks where the operating system ensures
that at least one of the necessary conditions for deadlock (mutual exclusion, hold and wait, no
preemption, circular wait) never occurs. By breaking these conditions in advance, the system
prevents deadlock from happening.

2. Deadlock Avoidance

Deadlock Avoidance is a method where the operating system makes decisions dynamically to
ensure the system never enters an unsafe state, thereby avoiding the possibility of deadlock.
This is usually done using algorithms like the Banker’s Algorithm.
Deadlock avoidance mainly relies on algorithms that check resource allocation before making
decisions. The two common types are:

1. Banker’s Algorithm: Used when multiple instances of resources exist. It simulates

allocation and ensures that the system remains in a safe state before granting
resources.

2. Resource Allocation Graph (RAG) Algorithm: Used when each resource has only
one instance. It checks for cycles in the graph to avoid unsafe states.
3. Deadlock Detection & Recovery

Deadlock Detection: Deadlock detection periodically checks for circular waits and resolves
deadlocks by aborting and restarting processes, releasing their resources. It allows
unrestricted resource access and immediate request fulfillment, enabling online handling. The
main drawback is potential loss due to preemption.

Deadlock Recovery is the process of handling a deadlock after it has occurred. It involves:

1. Process Termination: Aborting one or more deadlocked processes to break the cycle.
2. Resource Preemption: Temporarily taking resources from some processes and
reallocating them to others.
4. Deadlock Ignorance

In the Deadlock ignorance method the OS acts like the deadlock never occurs and completely
ignores it even if the deadlock occurs. This method only applies if the deadlock occurs very
rarely. The algorithm is very simple. It says, " if the deadlock occurs, simply reboot the
system and act like the deadlock never occurred." That's why the algorithm is called
the Ostrich Algorithm.

Resource Allocation Techniques for Processes

The Operating System allocates resources when a program need them. When the program
terminates, the resources are de-allocated, and allocated to other programs that need them.
Now the question is, what strategy does the operating system use to allocate these resources
to user programs?

There are two Resource allocation techniques:

1. Resource partitioning approach - In this approach, the operating system decides

beforehand, that what resources should be allocated to which user program. It divides the
resources in the system to many resource partitions, where each partition may include
various resources - for example, 1 MB memory, disk blocks, and a printer. Then, it allocates
one resource partition to each user program before the program's initiation. A resource table
records the resource partition and its current allocation status (Allocated or Free).
 Advantages:

• Easy to Implement

• Less Overhead

Disadvantages:
• Lacks flexibility - if a resource partition contains more resources than what a
particular process requires, the additional resources are wasted.

• If a program needs more resources than a single resource partition, it cannot execute
(Though free resources are present in other partitions).

An Example Resource Table may look like this:-

The above Resource Table is of the time of Booting. Resource Table is the core data structure
that is used in the resource allocation techniques. Resource Table contains resource partitions
as entries rather than single resources.

2. Pool based approach - In this approach, there is a common pool of resources. The
operating System checks the allocation status in the resource table whenever a program
makes a request for a resource. If the resource is free, it allocates the resource to the
program.

Advantages:

• Allocated resources are not wasted.

• Any resource requirement can be fulfilled if the resource is free (unlike Partitioning
approach)

Disadvantages:

• Overhead of allocating and de-allocating the resources on every request and release.

Banker's Algorithm
Banker's Algorithm is a resource allocation and deadlock avoidance algorithm used in
operating systems. It ensures that a system remains in a safe state by carefully allocating
resources to processes while avoiding unsafe states that could lead to deadlocks.
 • The Banker's Algorithm is a smart way for computer systems to manage how
programs use resources, like memory or CPU time.

• It helps prevent situations where programs get stuck and can not finish their tasks.
This condition is known as deadlock.

• By keeping track of what resources each program needs and what's available, the
banker algorithm makes sure that programs only get what they need in a safe order.

Components of the Banker's Algorithm

The following Data structures are used to implement the Banker’s Algorithm:

Let 'n' be the number of processes in the system and 'm' be the number of resource types.

1. Available

• It is a 1-D array of size 'm' indicating the number of available resources of each type.

• Available[ j ] = k means there are 'k' instances of resource type Rj

2. Max

• It is a 2-d array of size 'n*m' that defines the maximum demand of each process in a
system.

• Max[ i, j ] = k means process Pi may request at most 'k' instances of resource

type Rj.

3. Allocation

• It is a 2-d array of size 'n*m' that defines the number of resources of each type
currently allocated to each process.
• Allocation[ i, j ] = k means process Pi is currently allocated 'k' instances of resource
type Rj

4. Need

• It is a 2-d array of size 'n*m' that indicates the remaining resource need of each
process.

• Need [ i, j ] = k means process Pi currently needs 'k' instances of resource type Rj

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

Allocation specifies the resources currently allocated to process Pi and Need specifies the
additional resources that process Pi may still request to complete its task.

Key Concepts in Banker's Algorithm

• Safe State: There exists at least one sequence of processes such that each process can
obtain the needed resources, complete its execution, release its resources, and thus
allow other processes to eventually complete without entering a deadlock.
 • Unsafe State: Even though the system can still allocate resources to some processes,
there is no guarantee that all processes can finish without potentially causing a
deadlock.

Example of Unsafe State

Consider a system with three processes (P1, P2, P3) and 6 instances of a resource. Let's say:

1. The available instances of the resource are: 1

2. The current allocation of resources to processes is:

• P1: 2

• P2: 3

• P3: 1

3. The maximum demand (maximum resources each process may eventually request) is:

• P1: 4
• P2: 5

• P3: 3

In this situation:

Need = Maximum Demand - Allocation

Process Maximum Demand Allocation Need

P1 4 2 2

P2 5 3 2

P3 3 1 2

• P1 may need 2 more resources to complete.

• P2 may need 2 more resource to complete.

• P3 may need 2 more resources to complete.

However, there is only 1 resource available. Even though none of the processes are currently
deadlocked, the system is in an unsafe state because there is no sequence of resource
allocation that guarantees all processes can complete.