Unit 3:-Process Synchronization

- Riti Thakor

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 COEP Technological University
A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Introduction
• Process Synchronization means controlling multiple processes when they
use the same resource.
• It makes sure that processes do not disturb each other while running.
• It is needed when many processes run at the same time.
Why do we need it?
• To avoid errors in data
• To manage shared resources properly
Problems it prevents:
• Data inconsistency → wrong data due to multiple updates
• Race condition → result depends on which process runs first

 Needed for processes that share data (cooperating processes)

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Types of Process

1. Independent Process
Does not share data or resources with other processes
Its execution does not affect others
Runs separately and independently
2. Cooperating Process
Shares data or resources (like memory, files, variables)
Can affect or be affected by other processes
Needs proper coordination

 Synchronization is required only for cooperating processes because they

share resources

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Need for Synchronization
• In an operating system, multiple processes run at the same time.
• These processes often share resources such as:
• Memory (RAM)
• Files
• Variables / Data
• When many processes try to access the same resource simultaneously, problems
can occur.
 Problems Without Synchronization:
• Data Corruption
Data gets changed incorrectly due to simultaneous access
• Incorrect Results
Final output becomes wrong or unpredictable
• Race Condition
Result depends on which process runs first

Synchronization is required to control access to shared resources and

ensure correct execution of processes
COEP Technological University
A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
  Producer–Consumer Problem

•To understand cooperating processes, we use the Producer–

Consumer problem
•Also called the Bounded Buffer Problem
•There are two processes:
• Producer → creates data and puts it into buffer
• Consumer → removes data from buffer and uses it
•Both share a common buffer (memory area)
 Types of Buffer
 Unbounded Buffer
No limit on buffer size
Producer never waits
 Bounded Buffer
Fixed size buffer
Producer waits if buffer is full
Consumer waits if buffer is empty
 A buffer is a temporary storage area used to hold data before it is processed or
transferred.

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Basic Synchronization Requirements
•Producer should NOT write into a full buffer
•Consumer should NOT read from an empty buffer
•Each item should be:
•Produced once
•Consumed once
 Shared Memory Solution
• The buffer is implemented using shared memory
• Uses a circular array
Two pointers:
IN → points to next empty position
OUT → points to next filled position

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Buffer Conditions
•Buffer is empty → when IN = OUT
Means nothing is inside
•Buffer is full → when next position of IN = OUT
Means no space left
 Shared Data
• BUFFER_SIZE = 10 → buffer can store 10 items
• buffer[] → storage area
• in = 0 → where producer will put data
• out = 0 → where consumer will take data

 IN → put data
 OUT → take data

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Producer Process
What producer does:
Check → “Is buffer full?”
If yes → wait
If no → put item in buffer
Move IN forward •IN = where data is added
 Producer = check → insert → move IN •OUT = where data is removed
 Consumer Process •Always check:
• What consumer does: •Don’t add if full
• Check → “Is buffer empty?” •Don’t remove if empty
• If yes → wait
• If no → take item from buffer
• Move OUT forward
 Consumer = check → remove → move OUT

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Critical Section Problem
•A Critical Section is a part of code where shared data is accessed
•Only one process should execute it at a time
•Used to maintain data consistency
 If one process is using shared data, others must wait

do {
Entry section
Critical section
Exit section
Reminder section
} while (1);

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Sections of a Process
• Entry Section
o Decides which process is allowed to enter the critical section
o Checks if the shared resource is free or busy
o If busy → process is made to wait
o Uses mechanisms like lock, flag, etc.
• Critical Section
o Most important part of the program
o Only one process can execute at a time
o Shared data is accessed or modified here
o Prevents data inconsistency and race condition
• Exit Section
o Process finishes its work in critical section
o Releases the resource (like unlock)
o Allows other waiting processes to enter
• Remainder Section
o Remaining part of the program
Key Flow
o Does not use shared resources
Entry → Critical → Exit → Remainder
o Can run without any restriction

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Solution to Critical Section Problem
A correct solution must satisfy three conditions:
1. Mutual Exclusion
Only one process can be in the critical section at a time
Prevents simultaneous access to shared data
Ensures data consistency
2. Progress
If no process is in the critical section, then:
One of the waiting processes must be allowed to enter
Decision should not be delayed unnecessarily
3. Bounded Waiting
Every process will get a chance to enter
There is a limit on waiting time
Prevents starvation (infinite waiting)

 These conditions ensure safe, fair, and efficient execution of

processes

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
Advantages of Critical Section
1. Reduces CPU Utilization
• Avoids unnecessary CPU usage
• Processes wait properly instead of running continuously
• Improves overall system efficiency
2. Provides Mutual Exclusion
• Ensures only one process accesses shared resource at a time
• Prevents data conflicts and errors
• Maintains data consistency
3. Simplifies Synchronization
• Makes coordination between processes easy and manageable
• No need for complex control mechanisms
• Helps in safe sharing of resources

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Synchronization Hardware
 Hardware support for synchronization includes Lock & Unlock technique,
disabling interrupts, and Test-and-Set operation, which ensure mutual exclusion
while accessing shared resources.
• Many systems provide hardware support for solving the critical section problem
• These techniques help in:
• Fast execution
• Safe access to shared data
• Ensures proper process synchronization
 Lock & Unlock Technique
Uses a lock variable to control access
Working:
Process enters → Lock is applied (Entry Section)
Only one process allowed in critical section
After execution → Unlock is done (Exit Section)
Other processes can now enter
o Ensures Mutual Exclusion, Progress, and Bounded Waiting

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Using Interrupts
Synchronization can be done by disabling interrupts
Working:
When interrupts are disabled:
No context switching occurs
Only one process executes
 Simple method but not suitable for multiprocessor systems
 Test-and-Set Operation
A hardware instruction used for synchronization
Works using a lock variable (0 or 1)
Lock Values:
0 → Unlock (free)
1 → Lock (busy)
Working of Test-and-Set
Process checks lock:
If 0 (free) → takes lock and enters
If 1 (busy) → keeps waiting
 Ensures Mutual Exclusion and Progress
 But does NOT guarantee Bounded Waiting

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Peterson’s Algorithm

•Peterson’s Algorithm is a software solution for synchronization

•Used for 2 processes only
•Proposed by Gary L. Peterson (1981)
Ensures:
•Mutual Exclusion
•Safe access to shared data

Variables Used
flag[i] → shows process i wants to enter a critical section
turn → shows whose turn it is to enter critical section
Meaning:
flag[i] = true → process wants to enter
turn = j → give chance to other process

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Steps of Algorithm
1. Set flag[i] = true (process wants to enter)
2. Set turn = j (give other process chance)
3. Check condition: If other process wants AND it’s their turn → wait
4. Enter critical section
5. After work → set flag[i] = false
6. Go to remainder section

 Working of Peterson’s Algorithm

• When a process wants to enter:
It sets its flag = true (means “I want to enter”)
• Then it sets turn to the other process
Means “You can go first”
• Now it checks:
If the other process also wants to enter AND
It is the other process’s turn
• Then it waits
• If not:
It enters the critical section
 Both processes cooperate and take turns, so only one enters at a time

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Properties of Peterson’s Algorithm

Peterson’s Algorithm satisfies the following three conditions:

1. Mutual Exclusion
Only one process can enter the critical section at a time
Prevents data conflict and errors
2. Progress
• If no process is in the critical section:
• One of the waiting processes must be allowed to enter
• No unnecessary delay
3. Bounded Waiting
• Every process will get a chance to enter
• There is a limit on waiting time
• Prevents starvation (infinite waiting)

COEP Technological University

A Unitary Public Uersity of Govt. of Maharashtra
Formerly College of Engineering Pune
 Example Use Cases of Peterson’s Algorithm

1. Accessing Shared Resources

Used when two processes access:
• Files
• Memory
• Printer
Ensures only one process uses the resource at a time
 Example: Two processes using the same printer
2. Prevent Deadlocks
Ensures:
• Mutual Exclusion
• Bounded Waiting
• Prevents processes from waiting forever

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
3. Real-Time Systems
Used where timing is important
Ensures important tasks run without disturbance

Conclusion:-
• Peterson’s Algorithm is a simple software solution
• Works for 2 processes only
Uses:
flag → to show interest
turn → to decide order

 Ensures only one process enters critical section at a time, avoiding

conflicts

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Mutex Locks
• Mutex (Mutual Exclusion Lock) is a synchronization tool
• Used to prevent multiple processes/threads from accessing shared
resources at the same time
 Only one process/thread can use the resource at a time
What are Mutex Locks?
• Before accessing shared data, a process must take the lock
• If lock is:
Free → process gets access
Busy → process waits
• Working:
o Process requests lock
o If free → enters critical section
o After work → releases lock
o Next process gets chance

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Components of Mutex Locks

1. Mutex Variable
Represents the lock
Shows whether resource is free or busy
2. Lock Acquisition
Process tries to get the lock
If busy → goes to waiting state
3. Lock Release
After finishing work → process releases lock
Other waiting processes can now enter
 Mutex ensures mutual exclusion and safe access to shared resources

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Types of Mutex Locks
Mutex locks have different types based on their behavior:
•Recursive Mutex
•Error-Checking Mutex
•Timed Mutex
•Priority Inheritance Mutex
•Read-Write Mutex

 Recursive Mutex
• Same process can lock multiple times
• Must unlock same number of times
Useful when:
Same function is called repeatedly
Example:
Navigating folders (parent → subfolder)

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Error-Checking Mutex
• Checks for errors while locking
• Prevents a process from locking again if it already holds the lock
Helps in:
• Detecting programming mistakes
Example:
• Updating same counter variable
 Timed Mutex
Process tries to get lock for a fixed time
If not available → fails and moves on
Useful in:
Real-time systems
Example:
Task waits limited time for resource
 Priority Inheritance Mutex
Solves priority inversion problem
Working:
Low priority process holding lock → gets temporary high priority
Ensures:
High priority process is not delayed

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Read-Write Mutex
•Allows:
• Multiple readers at same time
• Only one writer at a time
Useful when:
•Data is read more than written
Example:
•Video streaming (many readers, one writer)

 Mutex types are designed to handle different synchronization problems in real

systems.

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Use Cases of Mutex Locks
1. Shared Resource Protection
Used to protect shared resources like memory, files, and variables
Ensures only one process or thread accesses the resource at a time
Prevents data corruption and race conditions
2. Critical Sections
Used to define critical sections in a program
Only one process can execute this part at a time
Ensures safe access to shared data
3. Synchronization
Helps processes coordinate their execution
Ensures operations happen in proper order
Maintains data consistency
4. Deadlock Avoidance
Helps avoid situations where processes wait indefinitely
Ensures proper locking sequence
Reduces chances of deadlock

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Benefits of Mutex Locks
 Mutual Exclusion
•Only one thread or process can hold the lock at a time
•Prevents race conditions
•Ensures predictable behavior
 Synchronization
•Helps coordinate access to shared resources
•Prevents unauthorized or simultaneous access
•Maintains controlled execution
 Simple and Portable
•Easy to use and implement
•Supported by most programming languages and operating systems
 Efficiency
•Works efficiently when there is low contention
•Minimal overhead when lock is free

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Drawbacks of Mutex Locks
• Potential Deadlocks
Incorrect use can cause deadlocks
Processes may wait forever for each other
• Priority Inversion
High-priority process may get blocked by low-priority process
• Resource Utilization
CPU resources may be wasted while waiting for locks
Can reduce system performance

 Conclusion
• Mutex locks are used for basic synchronization
• Ensure only one process accesses shared resource at a time
• Prevent race conditions and data inconsistency
• Simple, effective, and widely used mechanism

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Semaphores
Semaphores are used for process synchronization
Control access to shared resources
Prevent race conditions and data inconsistency
 What is a Semaphore?
• A semaphore is a variable (integer type)
• Used to manage access to shared resources
• Ensures controlled access by processes
 Semaphore Operations
• wait(S) decreases value
• signal(S) increases value

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Wait Operation
• Used before entering critical section
• If S > 0 process continues and S is decreased
• If S = 0 process waits
wait(S) {
while (S <= 0);
S--;
}
 Signal Operation
• Used after leaving critical section
• Increases value of S
• Allows waiting processes to continue
signal(S) {
S++;
}
 wait means check and decrease
 signal means increase and allow others

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Types of Semaphores
 Binary Semaphore
• Value is only 0 or 1
• Used when only one resource is available
• If value = 1 → resource is free
• If value = 0 → resource is busy
• Used for mutual exclusion
 Example
Single printer system
 Counting Semaphore
• Value can be any integer
• Used when multiple resources are available
• Value represents number of available resources
 Working
Resource taken → value decreases
Resource released → value increases
 Example
5 resources → S = 5

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
Working of Semaphore (Example) Step 6
Initial P2 finishes and executes signal(S)
S = 1 (resource free) S becomes 1
• Step 1
P1 and P2 are outside critical section • wait → decreases value and may block
• Step 2 process
P1 executes wait(S) • signal → increases value and allows next
S becomes 0 process
P1 enters critical section • Ensures only allowed processes access
• Step 3 resource
P2 executes wait(S)
S = 0 → P2 waits
• Step 4
P1 finishes and executes signal(S)
S becomes 1
• Step 5
P2 executes wait(S)
S becomes 0
P2 enters critical section

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
• Working of Counting Semaphore Step 4
• Initial value P4 performs wait(S)
• S = 3 (3 resources available) S = 0 → P4 waits
Step 5
• Processes
P1 finishes and performs signal(S)
• P1, P2, P3, P4 want to use resource
S becomes 1
• Step 1 P4 gets chance and enters
• P1 performs wait(S)
• S becomes 2 • Multiple processes can enter (based on S
• P1 enters critical section value)
• Step 2 • wait → decreases count
• P2 performs wait(S) • signal → increases count
• Used when multiple resources are available
• S becomes 1
• P2 enters
• Step 3
• P3 performs wait(S)
• S becomes 0
• P3 enters

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Binary Semaphore vs Counting Semaphore

Aspect Binary Semaphore Counting Semaphore

A semaphore that can A semaphore that can
Definition take only the values 0 take non-negative
and 1 integer values
0 to N (where N is a
Value Range 0 or 1
positive integer)
Managing access to
Mutual exclusion for a
Use Case multiple instances of a
single resource
resource
Operations wait() and signal() wait() and signal()
Blocks if the resource is Blocks if no resources
Blocking Behavior
unavailable (value is 0) are available (value is 0)

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Classical Synchronization Problems

•Used to understand process synchronization

•Help manage multiple processes accessing shared resources
•Ensure data consistency and avoid conflicts

 Types:
•Dining Philosophers Problem
•Producer Consumer Problem
•Reader Writer Problem
•Sleeping Barber Problem

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Dining Philosophers Problem
Classic synchronization problem proposed by Dijkstra
•Philosophers sit around a circular table
•Two states: thinking and eating
•Need two resources (fork and spoon) to eat
•Limited resources → synchronization issue
 Problem Explanation
•Each philosopher needs both left and right resources
•Only limited forks and spoons available
•Shared resources must be used carefully
 Deadlock Situation
•All philosophers pick left resource first
•Each waits for right resource
•No one can proceed
Result:
•Deadlock occurs
•No philosopher can eat

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Solution Using Semaphores
•Use semaphores for each resource
•Initialize each to 1 (available)
•Rules:
• Take both resources before eating
• Release after eating
 Algorithm
•Think
•wait(left resource)
•wait(right resource)
•Eat
•signal(right resource)
•signal(left resource) •No two philosophers use same resource
 Deadlock Prevention •Proper ordering prevents deadlock
•Problem: all pick left → deadlock Conclusion
•Solution: •Demonstrates resource sharing problems
• Allow only N-1 philosophers to try at a •Shows need for synchronization
time •Semaphores help avoid deadlock and
•Breaks circular waiting starvation

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Producer Consumer Problem

Also called Bounded Buffer Problem

 Two processes:
• Producer produces data
• Consumer consumes data
Both share a fixed-size buffer
 Problem Explanation
• Producer adds data to buffer
• Consumer removes data from buffer
• Both work simultaneously
 Main Challenges
• Producer should NOT add when buffer is full
• Consumer should NOT remove when buffer is empty

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Solution Using Semaphores
•Use three semaphores:
• empty → number of empty slots
• full → number of filled slots
• mutex → for mutual exclusion
•Initialization:
• empty = N
• full = 0
• mutex = 1

 Producer Working
•Produce item
•wait(empty)
•wait(mutex)
•Add item to buffer
•signal(mutex)
•signal(full)

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Consumer Working
•wait(full)
•wait(mutex)
•Remove item from buffer
•signal(mutex)
•signal(empty)
•Consume item
Example
•Buffer size = 3
•Producer adds item → empty decreases
•Consumer removes item → full decreases
•System ensures no overflow or underflow
 In Short
•empty controls free space
•full controls filled space
•mutex ensures only one process accesses buffer
 Conclusion
•Solves synchronization between producer and consumer
•Prevents buffer overflow and underflow
•Ensures safe and efficient data sharing
COEP Technological University
A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Sleeping Barber Problem
•Classic synchronization problem
•One barber, one barber chair, and N waiting chairs
•Models real-life queue system
 Problem Explanation
•Customer arrives:
• If chair available → waits
• If full → leaves
•Barber:
• Sleeps if no customers
• Works if customer arrives
 Requirements
•Barber sleeps when no customers
•Customers wait if barber is busy
•No customer leaves if chair is available
 Solution Using Semaphores
•waitingRoom → number of free chairs
•barberChair → barber chair availability (0/1)
•barberSleep → barber sleep/wake control

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Barber Process
•wait(barberSleep) → sleep if no customer
•wait(barberChair) → take chair
•Cut hair
•signal(barberChair) → release chair
 Customer Process
•Check waitingRoom
• If full → leave
• Else → sit and wait
•wait(barberChair) → get chair
•signal(barberSleep) → wake barber
•Get haircut
•signal(barberChair) → leave
 Key Idea
Synchronizes barber and customers
Ensures proper waiting and service
Avoids conflict and confusion
 Conclusion
Demonstrates real-life synchronization
Uses semaphores to manage resources
Ensures smooth and efficient operation

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Reader Writer Problem
• Synchronization problem with two types of processes
• Readers and Writers share a common resource
• Example: database or variable
 Problem Explanation
Readers can read data at the same time
Writers need exclusive access
While writing:
No reader allowed
No other writer allowed
 Main Requirement
Multiple readers allowed together
Only one writer allowed at a time
No reading during writing
 Data Inconsistency (Example)
Two writers update same data simultaneously
Readers may get different values
Leads to incorrect results

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Solution Using Semaphores  In short
•mutex → protects read_count •Many readers can read together
•writeBlock → controls access to resource •Writer gets exclusive access
•read_count → number of active readers •Ensures data consistency
 Reader Process  Conclusion
•wait(mutex) •Solves conflict between readers and writers
•read_count++ •Prevents data inconsistency
•If first reader → wait(writeBlock) •Ensures proper synchronization
•signal(mutex)
•Read data
•wait(mutex)
•read_count--
•If last reader → signal(writeBlock)
•signal(mutex)
 Writer Process
•wait(writeBlock)
•Write data
•signal(writeBlock)

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Synchronization within the Kernel

•Refers to how the operating system manages multiple processes

or threads inside the kernel
•Ensures safe access to shared kernel data and resources
•Prevents race conditions, data corruption, and system errors
•Needed because many processes execute simultaneously and use
OS services like memory, files, and CPU
•Methods used:
• Locks (Mutex, Spinlock) to allow only one process at a
time
• Disabling interrupts to avoid context switching
• Atomic operations to perform tasks without interruption
•Ensures correct and efficient execution of system operations

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Deadlocks

•Deadlock is a situation where two or more processes are waiting for each
other’s resources
•No process can proceed → system gets stuck
•Occurs due to circular dependency between processes
•Example:
P1 holds R1 and waits for R2
P2 holds R2 and waits for R1
Result: both are blocked
•Real-life example:
•One person has a pencil, another has an eraser
•Both need both items → no one proceeds

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Conditions for Deadlock (Coffman Conditions):
•Mutual Exclusion → resource used by one process at a time
•Hold and Wait → process holds one resource and waits for another
•No Preemption → resource cannot be taken forcefully
•Circular Wait → processes form a waiting cycle
 Effects:
•Wastage of resources
•Process starvation
•System becomes unresponsive
 Prevention Methods:
•Prevention → break one condition
•Avoidance → use algorithms like Banker’s
•Detection and Recovery → detect and resolve deadlock

 Deadlock stops system progress and must be avoided or handled properly

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Deadlock and Its Conditions
•Deadlock is a situation where processes are stuck waiting for each other’s resources
•No process can proceed → system gets blocked
•Occurs due to circular dependency of resources
•Deadlock Conditions (Coffman Conditions):
 Mutual Exclusion
•Resource can be used by only one process at a time
•Example: printer
 Hold and Wait
•Process holds one resource and waits for another
•Example: holding printer, waiting for scanner
 No Preemption
•Resource cannot be taken forcefully
•Process must release it voluntarily
 Circular Wait
Processes form a cycle
Each waits for resource held by next process

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 How to Avoid Deadlocks?

To avoid deadlock, the operating system can take measures to prevent one or
more of the four necessary conditions from occurring. This can be done in the
following ways −
•Prevent Mutual Exclusion − This is generally not feasible because many
resources (like printers, files, or memory) must be used exclusively by one
process at a time. However, for some resources (like read-only resources),
multiple processes can access them simultaneously.
•Prevent Hold and Wait − Require processes to request all resources they will
need at once before starting execution. This is called the "all-or-nothing"
approach. Another option is to require processes to release all the resources they
currently hold before requesting new ones.
•Prevent No Preemption − Allow preemption of resources. If a process
holding some resources is waiting for additional resources, the operating system
can preempt the resources currently held by the process and assign them to
other processes.

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Deadlock Prevention

•Deadlock prevention ensures that at least one of the four necessary

conditions does not occur
•Conditions:
• Mutual Exclusion
• Hold and Wait
• No Preemption
• Circular Wait
•Methods to Prevent Deadlock:
Prevent Mutual Exclusion
•Make resources shareable whenever possible
•Example: read-only files can be shared
Prevent Hold and Wait
•Request all resources at once before execution
•Or release held resources before requesting new ones

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
Prevent No Preemption
•Allow system to take resources from a process
•Resources reassigned to other processes
Prevent Circular Wait
•Assign order to resources
•Processes must request resources in increasing order

 Break any one condition to prevent deadlock

o Conclusion:
Prevention avoids deadlock before it occurs but may reduce system efficiency

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Deadlock Avoidance (Banker’s Algorithm)

•Deadlock avoidance ensures system never enters unsafe state

•Uses Banker’s Algorithm
•Resources are allocated only if system remains safe
•Idea:
• Like a banker giving loans safely
• Ensure enough resources remain for all processes
 Basic Working
•Each process declares maximum resource need
•OS checks before allocation:
• If safe → allocate
• If unsafe → process waits

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
•Available → free resources
•Max → maximum need of process
•Allocation → resources currently given
•Need = Max − Allocation
 Safety Algorithm
•Check if system is in safe state
•Find process whose Need ≤ Available
•Allocate resources and update Available
•Repeat for all processes
•If all complete → safe state
 Resource Request Algorithm
•If Request ≤ Need → valid
•If Request ≤ Available → check safety
•Temporarily allocate resources
•Run safety algorithm
•If safe → grant request
•Else → rollback

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Safe State
•System is safe if all processes can complete
•Safe sequence exists
Example:
•P1 → P3 → P4 → P0 → P2
 In Short
•Avoid deadlock by checking before allocation
•Only safe allocations are allowed
 Conclusion
•Banker’s Algorithm prevents deadlock
•Requires knowledge of maximum needs
•Ensures safe and efficient resource allocation

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Deadlock Detection and Recovery
•OS periodically checks system state
•Detects deadlock using algorithms
•Methods:
• Resource Allocation Graph (RAG)
• Wait-for Graph
• Banker’s Algorithm
 Resource Allocation Graph (RAG)
•Graph with processes and resources
•Edge:
• Process → Resource (request)
• Resource → Process (allocation)
•Cycle in graph → deadlock
 Wait-for Graph
•Only processes are nodes
•Edge shows one process waiting for another
•Cycle → deadlock

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Banker’s Algorithm (Detection)
•Used for multiple resource instances
•Checks if system is in unsafe state
•Unsafe state → possible deadlock
 Deadlock Recovery
•After detection, OS takes action
Methods:
•Process Termination
•Resource Preemption
 Process Termination
•Terminate one or more processes
•Releases resources
•Breaks deadlock

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Resource Preemption
•Take resources from processes
•Give to other processes
•Continue until deadlock is resolved

 In Short
•Detect deadlock first
•Then recover using suitable method
 Conclusion
•Detection finds deadlock
•Recovery removes deadlock
•Ensures system continues execution

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune
 Thank You!

COEP Technological University

A Unitary Public University of Govt. of Maharashtra
Formerly College of Engineering Pune