Module 3:
Process Synchroniza�on
Process synchroniza�on is a fundamental concept in opera�ng systems that ensures mul�ple
processes or threads can execute concurrently without interfering with each other,
especially when sharing resources such as memory, files, or I/O devices.
Background
In mul�programming systems, mul�ple processes may run at the same �me. If these
processes share data or resources, problems like race condi�ons can occur — where the
outcome depends on the non-determinis�c ordering of process execu�on. Synchroniza�on
prevents such issues and ensures:
• Mutual Exclusion: Only one process can access cri�cal resources at a �me.
• Progress: If no process is in its cri�cal sec�on, others should not be prevented from
entering.
• Bounded Wai�ng: Each process must get a chance to execute its cri�cal sec�on
within a bounded number of turns.
Cri�cal Sec�on Problem
A cri�cal sec�on is a part of the program where the process accesses shared resources (like
data structures or devices). The challenge is to design a protocol that ensures:
1. Mutual Exclusion – Only one process in the cri�cal sec�on at a �me.
2. Progress – No process should be unnecessarily delayed.
3. Bounded Wai�ng – A process wai�ng to enter the cri�cal sec�on must eventually get
a chance.
Solu�ons:
• So�ware-based (Peterson's Algorithm)
• Hardware-based (test-and-set, compare-and-swap)
• OS-based (semaphores, monitors)
Synchroniza�on Hardware
Hardware solu�ons rely on atomic (indivisible) machine instruc�ons. Common ones include:
a. Test-and-Set Instruc�on
Atomically tests and sets a value:
boolean TestAndSet(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
• Ensures mutual exclusion.
• May cause busy wai�ng (spinlock).
b. Compare-and-Swap (CAS)
int CompareAndSwap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
• Used in lock-free data structures.
Classical Problems of Synchroniza�on
These problems illustrate common synchroniza�on challenges.
a. Producer-Consumer Problem
• Producer creates data and places it in a buffer.
• Consumer takes data from the buffer.
• Buffer has limited size; requires synchroniza�on to avoid overfilling or reading empty
buffer.
b. Readers-Writers Problem
• Mul�ple readers can read at the same �me.
• Writers need exclusive access.
• The goal is to avoid conflicts and starva�on (writer or reader wai�ng forever).
c. Dining Philosophers Problem
• Five philosophers sit around a table, each needing two forks to eat.
• Forks are shared between neighbours.
• Illustrates deadlock, starva�on, and resource conten�on.
Semaphores
Semaphores are synchroniza�on tools used to control access to a common resource.
Types:
• Coun�ng Semaphore: Can take any integer value (useful for managing a pool of
resources).
• Binary Semaphore (Mutex): Only 0 or 1 (acts like a lock).
Opera�ons:
• wait(S) or P(S): Decrements the semaphore. If < 0, the process is blocked.
• signal(S) or V(S): Increments the semaphore. If processes are wai�ng, one is
unblocked.
// Example
semaphore mutex = 1;
wait(mutex);
// Cri�cal Sec�on
signal(mutex);
Used to solve classical problems like producer-consumer, dining philosophers, etc.
Deadlock
A deadlock is a situa�on where a group of processes are all wai�ng for each other to release
resources, and none of them can proceed. This creates an indefinite blocking scenario.
Deadlock Characteriza�on (Coffman’s Condi�ons)
A deadlock can occur only if all four of the following condi�ons hold simultaneously:
1. Mutual Exclusion
– At least one resource must be held in a non-shareable mode.
2. Hold and Wait
– A process holding at least one resource is wai�ng to acquire addi�onal resources
held by other processes.
3. No Pre-emp�on
– Resources cannot be forcibly taken from a process; they must be released
voluntarily.
4. Circular Wait
– A circular chain of processes exists, where each process is wai�ng for a resource
held by the next process in the chain.
Methods for Handling Deadlocks
There are four general strategies to handle deadlocks:
a. Deadlock Preven�on
– Ensure that at least one of the Coffman condi�ons never holds.
b. Deadlock Avoidance
– Dynamically check if the system is in a safe state before resource alloca�on.
– Example: Banker’s Algorithm.
c. Deadlock Detec�on and Recovery
– Allow deadlocks to occur, detect them, and then recover.
d. Ignore the Problem (Ostrich Algorithm)
– Assume deadlocks are rare and ignore them (used in many OSes like UNIX).
Deadlock Preven�on
Ac�vely prevent deadlocks by breaking one of the condi�ons:
• Mutual Exclusion: Not always possible (some resources are inherently non-
shareable).
• Hold and Wait: Require processes to request all needed resources at once.
• No Preemp�on: Allow OS to forcibly take resources.
• Circular Wait: Impose a global ordering of resource requests.
Example: Assign numerical IDs to resources and require processes to request resources in
increasing order.
Deadlock Avoidance
Safe State:
A state is safe if the system can allocate resources to each process in some order and s�ll
avoid deadlock.
Banker’s Algorithm:
• Works like a bank that doesn’t loan more than it can guarantee to reclaim.
• Each process must declare its maximum resource needs in advance.
• Before alloca�on, system checks if it's s�ll in a safe state.
Deadlock Detec�on
If preven�on/avoidance isn’t used, the system must detect deadlocks.
a. Resource Alloca�on Graph (RAG):
• A cycle in RAG with only single-instance resources implies a deadlock.
b. Deadlock Detec�on Algorithm (for mul�ple instances):
• Similar to Banker’s Algorithm but checks for processes that cannot proceed.
Recovery from Deadlock
Once detected, the system must recover:
a. Process Termina�on
• Abort all deadlocked processes.
• Abort one at a �me un�l the deadlock is resolved (choose based on priority,
resources held, etc.).
b. Resource Preemp�on
• Take resources away from processes and reassign them.
• Requires rollback and restart mechanisms.