Operating Systems - Process Synchronization Notes (Test Prep Edition)
4. Process Synchronization
==========================
1. Introduction
---------------
When multiple processes execute concurrently, they may share resources (like variables, files, or
devices).
**Process Synchronization** ensures that only one process accesses shared data at a time,
preventing inconsistencies.
**Goal:** To maintain **data consistency** in concurrent execution.
---
2. Critical Section Problem (CSP)
---------------------------------
A **critical section** is a part of the program where shared resources are accessed.
**Problem:** Ensure that when one process is executing in its critical section, no other process is
allowed to execute in its own.
**Solution must satisfy three conditions:**
1. **Mutual Exclusion:** Only one process in the critical section at a time.
2. **Progress:** If no process is in its critical section, selection of next process cannot be postponed
indefinitely.
3. **Bounded Waiting:** A limit must exist on how many times other processes can enter before a
waiting process gets a chance.
---
3. Software Solution - Peterson's Algorithm
-------------------------------------------
Used for **two processes** (P0 and P1) to achieve mutual exclusion.
**Algorithm:**
```
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
// Critical Section
flag[i] = false;
// Remainder Section
} while (true);
```
**Explanation:**
- `flag[i]` indicates if process wants to enter its critical section.
- `turn` gives priority to one process.
- Satisfies **all three CSP requirements.**
**Limitation:** Works only for two processes and assumes atomic read/write operations.
---
4. Hardware Support for Synchronization
--------------------------------------
Hardware provides atomic instructions to simplify mutual exclusion.
### (a) Test-and-Set Instruction
Atomically tests and sets a lock variable.
```
boolean TestAndSet(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
```
**Usage:**
```
while (TestAndSet(&lock));
// critical section
lock = false;
```
### (b) Compare-and-Swap Instruction
Compares the contents of a memory location with a value and updates it atomically.
```
int CompareAndSwap(int *reg, int old, int new) {
int temp = *reg;
if (*reg == old) *reg = new;
return temp;
}
```
Used in modern CPUs to implement locks efficiently.
---
5. Semaphores
-------------
A **Semaphore** is a synchronization tool introduced by Dijkstra, used to control access to shared
resources.
**Types of Semaphores:**
1. **Binary Semaphore (Mutex):**
- Values: 0 or 1.
- Used for **mutual exclusion.**
2. **Counting Semaphore:**
- Values range over a domain of integers.
- Used for **resource management** (like limited buffer slots).
**Operations:**
```
wait(S): while S <= 0; S--;
signal(S): S++;
```
**Example:**
```
wait(mutex);
// Critical Section
signal(mutex);
```
**Note:** Improper semaphore use may cause **deadlock** or **starvation.**
---
6. Classic Synchronization Problems
-----------------------------------
### (a) Producer-Consumer Problem
- **Producer:** Generates data and stores it in buffer.
- **Consumer:** Removes data from buffer.
- **Constraint:** Buffer should not overflow or underflow.
**Solution using Semaphores:**
```
Semaphore full = 0, empty = n, mutex = 1;
Producer:
while (true) {
produce_item();
wait(empty);
wait(mutex);
add_to_buffer();
signal(mutex);
signal(full);
}
Consumer:
while (true) {
wait(full);
wait(mutex);
remove_from_buffer();
signal(mutex);
signal(empty);
consume_item();
}
```
---
### (b) Readers-Writers Problem
- **Readers:** Can read simultaneously.
- **Writers:** Require exclusive access.
**Goal:** Avoid writer starvation while allowing concurrent readers.
**Solution:** Use semaphores to control read/write access.
---
### (c) Dining Philosophers Problem
- Five philosophers sit at a table, alternating between eating and thinking.
- Each needs two forks to eat (one on each side).
**Issue:** If all pick up one fork, a **deadlock** occurs.
**Solution:** Use semaphores to represent forks and ensure at least one philosopher eats at a time.
---
7. Monitors
-----------
A **monitor** is a **high-level synchronization construct** that encapsulates shared variables,
operations, and synchronization mechanisms.
**Structure:**
```
monitor example {
// Shared variables
procedure P1() { ... }
procedure P2() { ... }
initialization_code() { ... }
}
```
**Features:**
- Only one process executes inside the monitor at a time.
- Uses **condition variables** for waiting and signaling.
**Example:**
```
condition x;
[Link](); // process waits
[Link](); // wakes up waiting process
```
**Advantages:**
- Easier to use than semaphores.
- Reduces risk of synchronization errors.
---
8. Summary Table
----------------
| Concept | Key Points |
|----------|-------------|
| CSP | Ensures one process at a time in critical section |
| Requirements | Mutual Exclusion, Progress, Bounded Waiting |
| Peterson's Algorithm | Software solution for 2 processes |
| Test-and-Set | Hardware atomic instruction for locking |
| Compare-and-Swap | Hardware-supported atomic operation |
| Semaphores | wait/signal mechanism for synchronization |
| Producer-Consumer | Coordination between producer & consumer using semaphores |
| Readers-Writers | Allows concurrent reads but exclusive write |
| Dining Philosophers | Illustrates deadlock problem |
| Monitors | High-level synchronization abstraction |
---
**In Short:**
- Use **Peterson's algorithm** for software-only mutual exclusion.
- Use **hardware instructions** for fast locking.
- Use **semaphores** for practical synchronization.
- Use **monitors** for structured and safer concurrency.