Process Synchronization in OS: Critical Section Problem, Semaphores, Peterson's Solution & Classical Problems
In modern multi-programmed and multi-threaded systems, processes execute concurrently. When multiple cooperating processes share common memory, data, or files, uncoordinated access leads to data inconsistency. Process Synchronization is the mechanism that ensures orderly execution of cooperating processes to maintain data consistency.
1. What is a Race Condition?
A Race Condition occurs when two or more processes read or write shared data concurrently, and the final outcome depends on the exact sequence and timing in which their execution steps are interleaved.
// Process P1 executes: count = count + 1
// Process P2 executes: count = count - 1
Register1 = count (P1: Reg1 = 5)
Register1 = Register1 + 1 (P1: Reg1 = 6) [Preempted]
Register2 = count (P2: Reg2 = 5)
Register2 = Register2 - 1 (P2: Reg2 = 4)
count = Register2 (count = 4)
count = Register1 (count = 6 -> Incorrect!)
2. The Critical Section Problem
The code of any concurrent process is partitioned into four structural segments:
- Entry Section: Requests permission to enter the critical section.
- Critical Section (CS): The code block where shared variables, tables, or files are accessed and modified.
- Exit Section: Releases access rights so waiting processes may enter.
- Remainder Section: The remaining code outside the synchronization block.
Three Mandatory Requirements for Any Critical Section Solution:
| Requirement | Definition | Mandatory / Optional |
|---|---|---|
| 1. Mutual Exclusion | If process $P_i$ is executing in its critical section, no other process may execute in its critical section simultaneously. | Strictly Mandatory |
| 2. Progress | If no process is in its critical section and some wish to enter, only processes not in their remainder section can participate in the decision. The selection cannot be postponed indefinitely. | Strictly Mandatory |
| 3. Bounded Waiting | There must be a bound on the number of times other processes are allowed to enter their critical sections after a process has requested entry, preventing starvation. | Strictly Mandatory |
3. Software Solutions: Peterson's Algorithm
Peterson's Algorithm is a classic two-process software synchronization solution that satisfies Mutual Exclusion, Progress, and Bounded Waiting on single-core / sequentially consistent systems.
int turn = 0;
// Code for Process P_i (other process is P_j)
do {
flag[i] = true; // Express desire to enter
turn = j; // Give turn to other process
while (flag[j] && turn == j); // Busy wait
/* CRITICAL SECTION */
flag[i] = false; // Exit Section
/* REMAINDER SECTION */
} while (true);
4. Semaphores and Mutex Locks
A Semaphore is a synchronization tool represented as an integer variable $S$ accessed strictly through two atomic standard operations: wait() (or $P$) and signal() (or $V$).
| Operation | Pseudocode Logic | Purpose |
|---|---|---|
| wait(S) / P(S) | while (S <= 0); S--; |
Acquires access / decrements resource count |
| signal(S) / V(S) | S++; |
Releases resource / wakes waiting processes |
Types of Semaphores:
- Binary Semaphore (Mutex): Takes values strictly $0$ or $1$. Used to provide mutual exclusion among multiple processes.
- Counting Semaphore: Value can range over an unrestricted domain. Used to control access to a finite resource pool having $N$ instances.
5. Classical Synchronization Problems
- Producer-Consumer (Bounded Buffer) Problem: Ensures the producer does not add data into a full buffer and the consumer does not remove data from an empty buffer.
- Readers-Writers Problem: Multiple readers can read simultaneously, but a writer requires exclusive access.
- Dining Philosophers Problem: Models concurrency allocation where philosophers need both left and right forks to eat, illustrating deadlock and starvation hazards.
6. Interactive Practice Quiz: Process Synchronization
Test your understanding with these exam-standard multiple-choice questions. Select an answer once to see instant feedback and explanation.
Score: 0 / 10
Quiz Completed!
Detailed Solutions:
7. Frequently Asked Questions (Quick Revision)
Spinlocks execute a busy-waiting loop, wasting CPU clock cycles while waiting for a lock to become free. They are only advantageous in multiprocessor architectures where lock wait times are shorter than context-switching overhead.
Not directly without memory barriers, because modern multi-core processors and optimizing compilers perform out-of-order execution and instruction reordering.
A single binary semaphore initialized to 1 is sufficient to provide mutual exclusion among any number of concurrent processes.
.png)