Deadlock & Synchronization

Complete infographic study notes on race conditions, semaphores, deadlock conditions, and Bankers algorithm.

Process Synchronization & Race Conditions

Race Condition

A **Race Condition** is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly.

Critical Section: The segment of code where shared resources (global variables, files, memory structures) are accessed. Only one process should be executing in its critical section at a time.

Requirements for a Critical Section Solution:

Mutual Exclusion: If process $P_i$ is running in its critical section, no other processes can.
Progress: If no process is running, only processes wishing to enter can choose who enters next; selection cannot be postponed indefinitely.
Bounded Waiting: There must be a limit on the number of times other processes can enter before a requesting process is granted entry.

Mutexes & Semaphores

Semaphores

A **Semaphore** is an integer variable $S$ accessed only via two atomic, indivisible operations:

`wait(S)` (often called P): Decrements $S$. If $S \le 0$, blocks the process.
`signal(S)` (often called V): Increments $S$. If blocked processes exist, wakes one up.

Types of Semaphores:
- **Binary Semaphore / Mutex**: Integer value ranges only between 0 and 1. Used to acquire locks.
- **Counting Semaphore**: Value can range over an unrestricted domain. Useful to manage resource counts (e.g. printer pool size).

Memory Trick: Think of a Mutex like a *key to a single-person restroom*. If the key is gone, you must wait. A Counting Semaphore is like *a bucket containing 5 keys for a study room pool*. Multiple people can enter until the keys run out.

Deadlock Concept & The 4 Conditions

Coffman Conditions

A deadlock arises if and only if **all four conditions** hold simultaneously:

Mutual Exclusion: At least one resource is held in a non-shareable mode.
Hold and Wait: A process holds a resource and waits for another one.
No Preemption: Resources cannot be forcibly taken from a process holding them.
Circular Wait: A closed chain of processes exists where each process waits for a resource held by the next process in the cycle.

Deadlock Avoidance: Banker's Algorithm

The Algorithm

Used in a multi-instance resource system. When a process requests resources, the OS simulates allocation to check if it results in a **Safe State**.

Matrices & Data Structures:
- `Available[m]`: Instances of each resource type available.
- `Allocation[n][m]`: Resources currently allocated to each process.
- `Max[n][m]`: Maximum resource demand of each process.
- `Need[n][m] = Max - Allocation`: Remaining resources each process may request.

Practice Now

Deadlock Simulator Banker's Algorithm Simulator Producer-Consumer Lab