Unit-3 Notes
Inter-process communication (IPC) and Deadlock: Principle of Concurrency, Producer /
Consumer Problem, Mutual Exclusion, Critical Section Problem, Semaphores, Classical
synchronization Problems, Dinning philosopher problem, Inter Process Communication models
and Schemes. Deadlock characterization, Prevention, Avoidance and detection, Recovery from
deadlock.
1. Principle of Concurrency (in OS)
Definition
Concurrency refers to the execution of multiple processes/threads overlapping in time, not
necessarily simultaneously (true parallelism requires multiple CPUs).
Why Concurrency?
• Efficient CPU utilization
• Better system throughput
• Supports multitasking (e.g., OS running multiple apps)
OS-Level Example
• While you are:
o Downloading a file
o Listening to music
o Browsing Chrome
The OS scheduler manages all these concurrent processes.
Key Issues in Concurrency
1. Resource sharing conflicts
2. Process synchronization
3. Deadlock possibility
4. Data inconsistency
2. Mutual Exclusion (ME)
Definition
During concurrent execution of processes, processes need to enter the critical section (or the section
of the program shared across processes) at times for execution. It might happen that because of the
execution of multiple processes at once, the values stored in the critical section become inconsistent.
In other words, the values depend on the sequence of execution of instructions - also known as a
race condition. The primary task of process synchronization is to get rid of race conditions while
executing the critical section.
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.
Ensures that only one process at a time accesses shared resources
OS Example
• Printing:
o Multiple processes want to print
o Only one process should access printer at a time
Why Needed?
Without ME:
• Data corruption
• Race conditions
Example 2: Shared Variable (Bank Account)
Consider a shared variable:
balance = 5000
Two processes are running:
Process 1 (Deposit):
adds 1000 to balance
Process 2 (Withdraw):
subtracts 500 from balance
Step-by-step Execution (Without Mutual Exclusion)
Both processes execute in three steps:
Read → Modify → Write
Process 1 (Deposit 1000)
1. Read balance (5000)
2. Add 1000 → New value = 6000
3. Write 6000 back
Process 2 (Withdraw 500)
1. Read balance (5000)
2. Subtract 500 → New value = 4500
3. Write 4500 back
Problem: Race Condition
If both processes run simultaneously, this situation can occur:
Step 1:
Process 1 reads balance = 5000
Process 2 also reads balance = 5000
Step 2:
Process 1 computes 6000
Process 2 computes 4500
Step 3:
Process 1 writes 6000
Process 2 writes 4500 (overwrites previous value)
Final Result
Final balance = 4500
But correct result should be:
5000 + 1000 − 500 = 5500
Why Error Occurs
Both processes accessed the shared variable at the same time.
Their operations overlapped, and one update was lost.
This situation is called a race condition, where the final result depends on the order of execution.
Solution: Mutual Exclusion
To prevent this problem, we define a critical section:
Critical Section:
The part of the program where the shared variable (balance) is accessed and updated.
Correct Execution Using Mutual Exclusion
Only one process can enter the critical section at a time.
Execution will be like:
Process 1 executes completely:
5000 → 6000
Then Process 2 executes:
6000 → 5500
Final Correct Result
Final balance = 5500
3. Critical Section Problem
Definition
A critical section is a code segment where shared resources are accessed.
Structure of a Process
Entry Section
Critical Section
Exit Section
Remainder Section
Requirements
1. Mutual Exclusion
2. Progress
3. Bounded Waiting
OS Example
• Updating a shared file:
o Two processes writing simultaneously → corrupted file
4. Semaphores
Definition: A synchronization tool used to control access to shared resources using an integer
variable.
Semaphores help prevent race conditions and ensure proper coordination between processes.
• Controls entry into the critical section.
• Maintains a counter representing available resources.
• Ensures mutual exclusion among processes.
• Can block and wake up processes during execution.
• Widely used in concurrent programming.
Types of Semaphores
1. Counting Semaphore
Counting semaphores are signaling integers that can take on any integer value. Using
these Semaphores we can coordinate access to resources and here the Semaphore count is the
number of resources available. If the value of the Semaphore is anywhere above 0, processes can
access the critical section or the shared resources. The number of processes that can access the
resources/code is the value of the semaphore. However, if the value is 0, it means that there aren't
any resources that are available or the critical section is already being accessed by a number of
processes and cannot be accessed by more processes. Counting semaphores are generally used
when the number of instances of a resource is more than 1, and multiple processes can access the
resource. It is used when multiple instances of a resource are available and need to be managed.
a) Value ranges from 0 to n.
b) Manages multiple resource instances.
c) Controls access to limited resources.
d) Example: Managing access to 5 printers or 3 database connections.
2. Binary Semaphore
A binary semaphore has only two possible values: 0 and 1. It is mainly used for mutual exclusion,
ensuring that only one process enters the critical section at a time. In these types of Semaphores the
integer value of the semaphore can only be either 0 or 1. If the value of the Semaphore is 1, it means
that the process can proceed to the critical section (the common section that the processes need to
access). However, if the value of the binary semaphore is 0, then the process cannot continue to
the critical section of the code.
a) Value is either 0 or 1.
b) Used for mutual exclusion.
c) Similar to a mutex lock.
Operations: A semaphore in OS uses two primary atomic operations:
1. wait (P): wait ( S )
{
While (S<=0);
S=S-1;
}
• Decrements value
• If < 0 → process waits
2. signal (V) Signal( S )
{
S=S+1;
}
• Increments value
• Wakes up waiting process
OS Example
• Disk access control:
o Only limited number of processes can access disk blocks
Example: Let’s consider two processes P1 and P2 sharing a semaphore S, initialized to 1:
a) State 1: Both processes are in their non-critical sections, and S = 1.
b) State 2: P1 enters the critical section. It performs wait(S), so S = 0. P2 continues in the non-
critical section.
c) State 3: If P2 now wants to enter, it cannot proceed since S = 0. It must wait until S > 0.
d) State 4: When P1 finishes, it performs signal(S), making S = 1. Now P2 can enter its critical
section and again sets S = 0.
This mechanism guarantees mutual exclusion, ensuring that only one process can access the
shared resource at a time, see the image below for reference:
Features of Semaphores
a) Mutual Exclusion: Semaphore ensures that only one process accesses a shared resource at a
time.
b) Process Synchronization: Semaphore coordinates the execution order of multiple
processes.
c) Resource Management: Limits access to a finite set of resources, like printers, devices, etc.
d) Reader-Writer Problem: Allows multiple readers but restricts the writers until no reader is
present.
e) Avoiding Deadlocks: Prevents deadlocks by controlling the order of allocation of
resources.
5. Producer-Consumer Problem
The Producer-Consumer problem is a classic example of a synchronization problem in operating
systems. It demonstrates how processes or threads can safely share resources without conflicts.
This problem belongs to the process synchronization domain, specifically dealing with coordination
between multiple processes sharing a common buffer.
Concept
Two processes share a common buffer:
• Producer → produces data and inserts into buffer
• Consumer → consumes data from buffer
Problem
• Buffer may be:
o Full → producer must wait
o Empty → consumer must wait
o Multiple producers and consumers do not access the buffer simultaneously,
preventing race conditions.
OS Example
• Keyboard input buffer:
o User typing → Producer
o OS reading input → Consumer
Solution using Semaphores
A semaphore is an integer-based signaling mechanism used to coordinate access to shared
resources. It supports two atomic operations:
• wait(S): Decreases the semaphore value by 1. If the value is ≤0, the process waits.
• signal(S): Increases the semaphore value by 1, potentially unblocking waiting processes.
Let:
• mutex = 1 (for mutual exclusion)
• empty = n (empty slots)
• full = 0 (filled slots)
Producer:
Void Producer()
{
While(T)
{
Produce()
wait(empty)
wait(mutex)
add item to buffer
signal(mutex)
signal(full)
}
Consumer:
Void Consumer()
{
While(T)
{
wait(full)
wait(mutex)
remove item from buffer
signal(mutex)
signal(empty)
}
Problem Statement
Consider a fixed-size buffer shared between a producer and a consumer.
• The producer generates an item and places it in the buffer.
• The consumer removes an item from the buffer.
The buffer is the critical section. At any moment:
• A producer cannot place an item if the buffer is full.
• A consumer cannot remove an item if the buffer is empty.
To manage this, we use three semaphores:
• mutex – ensures mutual exclusion when accessing the buffer.
• full – counts the number of filled slots in the buffer.
• empty – counts the number of empty slots in the buffer.
Explanation:
• Empty ensures that producers don’t overfill the buffer.
• Full ensures that consumers don’t consume from an empty buffer.
• Mutex ensures mutual exclusion, so only one process accesses the buffer at a time.
The Producer-Consumer problem is a fundamental example of process synchronization in
operating systems. Using semaphores and mutexes, we can ensure:
• Producers don’t overfill the buffer.
• Consumers don’t consume from an empty buffer.
• Mutual exclusion is maintained when accessing the buffer.
This approach prevents race conditions, data inconsistency, and deadlocks, making it a reliable
solution for coordinating multiple processes.
6. Classical Synchronization Problems
These are standard problems used to understand concurrency in OS
A. Dining Philosophers Problem
Problem
• 5 philosophers sitting at a table
• Need 2 chopsticks to eat
• Each shares chopsticks with neighbors
Issues
• Deadlock
• Starvation
OS Analogy
• Processes competing for limited resources (e.g., CPU, I/O devices)
B. Cigarette Smokers Problem
Problem
• 3 smokers with one resource each:
o Tobacco, Paper, Match
• Agent provides remaining two
Goal
• Only the correct smoker proceeds
OS Analogy
• Resource allocation and synchronization between processes
C. Readers-Writers Problem
Problem
• Multiple readers can read simultaneously
• Writers need exclusive access
OS Example
• Database access:
o Many users reading
o One user updating
Variants
1. Reader priority
2. Writer priority
3. Fair solution
D. Sleeping Barber Problem
Problem
• Barber sleeps if no customers
• Limited waiting chairs
•
OS Analogy
• Process scheduling / queue management
OS-Based Scenarios Summary
Concept Real OS Scenario
Concurrency Running multiple apps
Producer-Consumer Keyboard buffer
Mutual Exclusion Printer access
Critical Section Shared file writing
Semaphores Resource allocation
Dining Philosopher Resource deadlock
Readers-Writers Database systems
Sleeping Barber CPU scheduling queues
Deadlock
INTRODUCTION
Deadlock is a situation in which a set of processes are blocked because each process is holding at
least one resource and waiting for another resource held by some other process in the set. None of
the processes can proceed, leading to indefinite waiting.
Example in OS:
Initial Stage
1) Process A holds Resource X and requests Resource Y
2) Process B holds Resource Y and requests Resource X
Execution Sequence
1) Process A starts and acquires Resource X
2) Process B starts and acquires Resource Y.
Stalemate
1) Process A requires Resource Y to complete its task, but it can’t proceed because Process B is
holding it.
2) Process B requires Resource X to complete its task but can’t proceed because Process A is
holding it.
Neither Process A nor Process B can release their held resource because they are still waiting for
another resource to be released. This circular waiting condition fulfils one of the necessary
conditions for Deadlock, leading to a Deadlock situation.
DEADLOCK CHARACTERIZATION
Deadlock can occur only if the following four conditions hold simultaneously. These are known as
Coffman conditions.
1. Mutual Exclusion
• At least one resource must be held in a non-shareable mode.
• Only one process can use the resource at a time.
Example: Printer cannot be shared by multiple processes simultaneously.
2 Hold and Wait
• A process holding at least one resource is waiting to acquire additional resources held by
other processes.
Example: A process holding a file is waiting for access to a printer.
3 No Preemption
• Resources cannot be forcibly taken from a process.
• They must be released voluntarily.
Example: A printer cannot be taken away from a process until it finishes printing.
4 Circular Wait
• A set of processes exists such that each process is waiting for a resource held by the next
process in the chain.
Example: P1 waits for P2, P2 waits for P3, P3 waits for P1.
RESOURCE ALLOCATION GRAPH
A Resource Allocation Graph is used to represent the state of processes and resources.
• Nodes represent processes and resources.
• Edges represent allocation and request.
Types of edges:
• Request edge: from process to resource
• Allocation edge: from resource to process
If the graph contains a cycle:
• In case of a single instance of each resource, deadlock exists.
• In case of multiple instances, cycle indicates possibility of deadlock.
Methods of Handling Deadlock
The following are the methods of handling Deadlocks.
1) Deadlock Prevention: Deadlock prevention is focused on removing the chance of Deadlocks by
making sure that one of the required conditions for Deadlock is always avoided. This can be done
by managing resource distribution and enforcing protocols to prevent circular wait, hold and wait,
and no preemption.
2) Deadlock Detection and Recovery: In this approach, the system regularly looks for Deadlocks.
If a Deadlock is found, the system can resolve it by either ending or undoing one or multiple
processes in order to eliminate the Deadlock loop and enable other processes to proceed.
3) Deadlock Avoidance: This method involves the system making real-time resource allocation
decisions to maintain its safety. The banker's algorithm assesses resource requests and only
approves them if they do not result in possible Deadlocks.
4) Wound-wait Schemes: Wound-wait schemes give preference to process execution according to
their length of time waiting. If a younger process is holding a resource and an older process requests
it, the younger process is interrupted to allow the older one to continue. This method reduces the
risk of Deadlocks by making sure that older processes are not deprived.
5) Limit Resource Utilisation: By limiting the total resources a process can ask for, the system can
decrease the chances of Deadlocks. This technique imposes more strict restrictions on resource
allocation, reducing the likelihood of processes reaching a state where they could potentially hinder
each other.
Benefits of Deadlock Method
The following are the benefits of the Deadlock method:
1) Proactive Approach: The Deadlock Method ensure that Deadlock cannot occur by eliminating
one or more necessary conditions.
2) Resource Reclamation: The recovery method can potentially free up resources, allowing another
process to continue execution. This can minimise the impact of Deadlock on system performance.
3) Risk Reduction: By restricting the maximum number of resources that can be allocated to the
process, this method reduces the risk of Deadlock. It provides a very easy way to make sure that
processes do not consume an excessive number of resources.
4) Resource Guarantees: It can provide resource guarantees to critical processes and ensure that
certain resources remain available for essential tasks.
5) Detection and Resolution: Deadlock detection and recovery methods allow systems to detect
and resolve Deadlocks when they do occur. This capability ensures that the system can continue
functioning even in Deadlocks, improving system robustness.
DEADLOCK PREVENTION
Deadlock prevention ensures that at least one of the four necessary conditions never holds.
1 Eliminating Mutual Exclusion
• Make resources sharable wherever possible.
• Not always feasible, especially for non-sharable resources like printers.
2 Eliminating Hold and Wait
• Require processes to request all resources at once.
• Or release all held resources before requesting new ones.
Disadvantages:
• Low resource utilization
• Possible starvation
3 Eliminating No Preemption
• Allow the system to preempt resources from processes.
• If a process holding resources requests another resource that is not available, all its resources
are released.
4 Eliminating Circular Wait
• Impose a strict ordering of resource types.
• Processes must request resources in increasing order of numbering.
DEADLOCK AVOIDANCE
Deadlock avoidance ensures that the system never enters an unsafe state. It ensures that there exists
at least one sequence of processes such that each process can obtain the needed resources, complete its
execution,
• It helps prevent situations where programs get stuck and can not finish their tasks.
• It keeps track of resources each program needs and what's available
Key idea:
• Make resource allocation decisions dynamically.
• Check whether the system remains in a safe state after allocation.
1 Safe State
A state where there exists a sequence of processes such that each process can complete with the
available resources.
2 Unsafe State
A state that may lead to deadlock.
BANKER’S ALGORITHM
Used for deadlock avoidance when multiple instances of resources exist.
Components of the Banker's Algorithm
The following Data structures are used to implement the Banker’s Algorithm:
Data Structures:
• Available: number of available resources
• Max: maximum demand of each process
• Allocation: resources currently allocated
• Need: remaining resources required
Need is calculated as:
Need = Max – Allocation
Steps:
1. Check if request is less than or equal to Need.
2. Check if request is less than or equal to Available.
3. Pretend to allocate resources and update data structures.
4. Check if the system is in a safe state.
5. If safe, grant request; otherwise, roll back.
Link for the practice questions based on Banker’s Algorithm:
[1] [Link]
content/uploads/2011/11/[Link]
DEADLOCK DETECTION
In this approach, the system allows deadlock to occur and then detects it.
1 Single Instance of Resources
• Use Resource Allocation Graph.
• If a cycle exists, deadlock is present.
2 Multiple Instances of Resources
• Use a detection algorithm similar to Banker’s algorithm.
Data Structures:
• Available
• Allocation
• Request
Steps:
1. Initialize work and finish arrays.
2. Find a process whose request can be satisfied.
3. If found, mark it finished and release its resources.
4. Repeat until no such process is found.
5. If some processes are not finished, deadlock exists.
RECOVERY FROM DEADLOCK
Once deadlock is detected, the system must recover.
1 Process Termination
a. Abort all deadlocked processes
• Simple but expensive
b. Abort one process at a time
• Continue until deadlock is eliminated
Selection criteria:
• Process priority
• Amount of work done
• Resources held
• Time required to complete
2 Resource Preemption
• Temporarily take resources from processes and allocate to others.
Steps:
1. Select a victim process
2. Preempt resources
3. Rollback process to a safe state
4. Restart process later
Issues:
• Starvation may occur if the same process is repeatedly selected
COMPARISON OF METHODS
1 Prevention
• Guarantees no deadlock
• Low resource utilization
2 Avoidance
• Requires prior knowledge of maximum resource needs
• Better utilization than prevention
3 Detection and Recovery
• Allows deadlock to occur
• More flexible but requires overhead for detection and recovery
9. REAL LIFE OS SCENARIOS
1. File locking
• Multiple processes accessing files can lead to deadlock
2. Database transactions
• Transactions waiting for locks on data items
3. Printer allocation
• Multiple jobs waiting for printers
4. Memory allocation
• Processes waiting for memory blocks held by others