Process synchronisation and deadlocks notes — Unit 3

When multiple processes execute concurrently and share data, data inconsistency can occur if their execution interleaves incorrectly.

⇒1.1 The Race Condition

Consider a banking server. Two processes (P1 and P2) try to deposit $100 to an account with a$1000 balance simultaneously.

The C code `balance = balance + 100` is actually 3 machine instructions:
1. Read balance from memory to register.
2. Add 100 to register.
3. Write register back to memory.

If P1 executes Step 1 (reads 1000), but then a context switch occurs, and P2 executes Steps 1, 2, and 3 (reads 1000, writes 1100). Then P1 resumes, adds 100 to its register, and writes 1100.
The final balance is $1100 instead of$1200! This is a Race Condition.

A Critical Section is the specific segment of code where a process modifies shared variables, tables, or files. To prevent race conditions, we must ensure that when one process is executing in its critical section, NO other process is allowed to enter its critical section.

⇒2.1 Requirements for a Valid Solution

Any solution to the critical section problem must satisfy three conditions:

• 1. Mutual Exclusion: If Process A is in the critical section, no other process can be in the critical section.
• 2. Progress: If no process is in the critical section, and some processes wish to enter, the selection of who enters next cannot be postponed indefinitely.
• 3. Bounded Waiting: There must be a limit on how many times other processes can enter their critical sections after a process has made a request to enter its own. (No process should starve).

Peterson's Solution is a classic software-based solution to the critical section problem, specifically restricted to two processes ($P_0$ and $P_1$).

It uses two shared variables:

• `int turn`: Indicates whose turn it is to enter.
• `boolean flag[2]`: Indicates if a process wants to enter. Initialized to `[false, false]`.

⇒3.1 The Algorithm for P0

```c
flag[0] = true; // P0 states it wants to enter
turn = 1; // P0 politely offers the turn to P1
while (flag[1] && turn == 1);
// wait (do nothing) if P1 wants to enter AND it's P1's turn

/ CRITICAL SECTION /

flag[0] = false; // P0 is done
```

This satisfies Mutual Exclusion, Progress, and Bounded Waiting. However, it only works for two processes and is not guaranteed to work on modern CPU architectures with out-of-order execution.

To build robust locks, we need help from the hardware. The root of the race condition is that reading a variable and modifying it takes multiple clock cycles, allowing preemption in the middle.

⇒4.1 Atomic Instructions

Modern CPUs provide special hardware instructions (like `TestAndSet` or `CompareAndSwap`) that perform a read and a write in a single, uninterrupted, atomic clock cycle. They cannot be preempted.

⇒4.2 Mutex Locks

OS designers use these atomic instructions to build higher-level software tools. The simplest is a Mutex (Mutual Exclusion) Lock.

Before entering a critical section, a process calls `acquire()`. If the lock is available, it takes it. If the lock is held by someone else, the process loops continuously until it is free (Spinlock). After the critical section, it calls `release()`.

A Semaphore (invented by Dijkstra) is a more robust synchronization tool. It is essentially an integer variable $S$ that, apart from initialization, is accessed only through two standard atomic operations: `wait()` and `signal()` (originally `P()` and `V()`).

⇒5.1 The Operations

```c
wait(S) {
while (S <= 0)
; // busy wait
S--;
}

signal(S) {
S++;
}
```

⇒5.2 Types of Semaphores

• Binary Semaphore: The integer value can only be 0 or 1. Behaves exactly like a Mutex Lock.
• Counting Semaphore: The integer value can range over an unrestricted domain. Used to control access to a resource with multiple identical instances (e.g., A database with 5 connection slots. Initialize $S=5$).

The basic semaphore definition wastes CPU cycles by forcing a blocked process to loop continuously (`while(S <= 0)`). This is called "busy waiting".

To fix this, the OS modifies the semaphore to include a waiting queue.

• When a process executes `wait()` and finds $S \le 0$, instead of busy waiting, it invokes a `sleep()` system call. The OS moves the process to the Waiting state and puts its PCB in the semaphore's queue.
• When another process executes `signal()`, it increments $S$. If there are processes in the queue, it uses a `wakeup()` system call to remove one process from the queue and move it to the Ready state.

This ensures the CPU is never wasted on spinning loops.

Also known as the Bounded-Buffer problem.
- A Producer creates items and puts them into a fixed-size buffer.
- A Consumer takes items out of the buffer.

Constraints:
1. Producer cannot add if the buffer is full.
2. Consumer cannot take if the buffer is empty.
3. They cannot access the buffer simultaneously.

⇒7.1 The Semaphore Solution

Requires 3 semaphores:

• `mutex` (Binary, init 1): Provides mutual exclusion to the buffer.
• `empty` (Counting, init N): Tracks empty slots. Halts producer if 0.
• `full` (Counting, init 0): Tracks filled slots. Halts consumer if 0.

Producer code: `wait(empty); wait(mutex); [Add Item]; signal(mutex); signal(full);`

Consider a shared database.
- Readers: Only read data.
- Writers: Modify data.

Constraints:
1. Any number of Readers can read simultaneously.
2. Only ONE Writer can write at a time.
3. If a Writer is writing, NO Readers can read.

⇒8.1 The Semaphore Solution

Requires a counter `readcount` (init 0), a mutex `mutex` (init 1) to protect the counter, and a semaphore `rw_mutex` (init 1) to protect the database.

The trick: The first reader to enter locks the `rw_mutex` (locking out writers). Subsequent readers just enter. The last reader to leave unlocks the `rw_mutex`.

(Note: This basic solution suffers from Writer Starvation. If readers keep arriving, the last reader never leaves, and the writer waits forever).

5 philosophers sit around a circular table. There is a bowl of rice in the center and 5 chopsticks (one between each philosopher). A philosopher needs TWO chopsticks to eat.

Constraint: A chopstick can only be held by one person at a time.

⇒9.1 The Deadlock Danger

If we represent each chopstick as a semaphore, a naive solution is:
`wait(chopstick[i]);` (Pick up left)
`wait(chopstick[(i+1)%5]);` (Pick up right)
`eat();`

If all 5 philosophers grab their left chopstick at the exact same time, they will all turn to grab their right chopstick, find it taken, and wait forever. This is a Deadlock.

A set of processes is in a Deadlock state when every process in the set is waiting for an event that can only be caused by another process in the set.

⇒10.1 The Four Necessary Conditions

A deadlock can arise if and ONLY IF the following four conditions hold simultaneously in a system:

• 1. Mutual Exclusion: At least one resource is held in a non-sharable mode (only one process can use it at a time).
• 2. Hold and Wait: A process is holding at least one resource and waiting to acquire additional resources held by other processes.
• 3. No Preemption: Resources cannot be forcibly taken away from a process; they must be voluntarily released.
• 4. Circular Wait: A closed chain of processes exists, such that P1 is waiting for P2, P2 for P3... and Pn is waiting for P1.

To prevent deadlocks, the OS must ensure that at least ONE of the four necessary conditions can never occur.

• Prevent Mutual Exclusion: Impossible for inherently non-sharable resources (like a printer).
• Prevent Hold and Wait: Force a process to request all its required resources at once before it starts execution. (Flaw: Terrible resource utilization, leads to starvation).
• Prevent No Preemption: If a process holding resources is denied a further request, the OS forcibly revokes all its current resources. (Flaw: State loss).
• Prevent Circular Wait: Impose a strict linear ordering of all resource types. A process can only request resources in increasing numerical order. (Most practical prevention method).

Avoidance is less strict than Prevention. The OS requires processes to declare the maximum number of resources they might need over their lifetime.
The OS then checks every single resource request. It simulates granting the request and checks if the system would end up in a Safe State.

⇒12.1 Safe State

A state is safe if there exists a sequence of processes such that every process can finish executing using currently available resources plus resources held by earlier processes in the sequence.

If a request leads to a Safe State, the OS grants it. If it leads to an Unsafe State (which might lead to a deadlock), the OS denies the request and makes the process wait.

To run the Banker's algorithm (named because it models a bank giving out loans without going bankrupt), the OS maintains matrices.

• Available: A vector of length $m$ indicating the number of available resources of each type.
• Max: An $n \times m$ matrix indicating the maximum demand of each process.
• Allocation: An $n \times m$ matrix defining the number of resources of each type currently allocated to each process.
• Need: An $n \times m$ matrix indicating the remaining resource need of each process. Mathematically: `Need[i,j] = Max[i,j] - Allocation[i,j]`.

The OS runs a Safety Algorithm to find a safe sequence. If one exists, the state is safe.

Unit 3 is highly conceptual and guaranteed to feature in university exams.

⇒14.1 University Exam Checklist

• Define the Critical Section problem. What are the three conditions for a valid solution?
• Explain Peterson's Solution.
• What is a Semaphore? Write the pseudo-code for `wait()` and `signal()`.
• Explain the difference between a Binary Semaphore (Mutex) and a Counting Semaphore.
• Write the Semaphore solution for the Producer-Consumer problem.
• List the four necessary conditions for Deadlock (Coffman conditions).
• Solve a numerical problem using Banker's Algorithm to find the Need matrix, determine if the system is in a Safe State, and find a Safe Sequence.