A critical section is a code segment that accesses shared resources and must not be executed by more than one process simultaneously.

Three requirements for a valid solution:
1. Mutual Exclusion: Only one process in critical section at a time.
2. Progress: If no process is in CS and processes want to enter, selection cannot be postponed indefinitely. Processes not in remainder section participate in decision.
3. Bounded Waiting: After a process requests entry, there is a bound on how many times others can enter before it does (no starvation).

Structure of a process:

do {
    entry section      // request permission
    critical section   // access shared resource
    exit section       // release permission
    remainder section  // other code
} while (true);

Occurs when multiple processes access shared data concurrently and the final result depends on the interleaving of their operations.

Classic example — shared counter:

// Shared: int count = 5;
// P1: count++  (read count=5, compute 6, write 6)
// P2: count--  (read count=5, compute 4, write 4)
// If both read before either writes: final count = 4 or 6, NOT 5!

The correct value (5) is lost. This is a race condition.

At machine instruction level, count++ is three steps:
register = count; register = register + 1; count = register.
Context switch between any two steps causes incorrect result.

Uses two shared variables: turn (whose turn to enter) and flag[2] (who wants to enter).

// Process Pi (j = 1-i):
flag[i] = true;
turn = j;               // give other process chance
while (flag[j] && turn == j);  // busy wait
// critical section
flag[i] = false;
// remainder section

Satisfies all three requirements. Works for exactly 2 processes.
Limitation: Busy waiting (spin lock) — wastes CPU. Not scalable to n processes directly.

An integer variable S with two atomic operations:
wait(S) / P(S):

while (S <= 0);   // busy wait (or block)
S--;

signal(S) / V(S):

S++;

Types:
Binary semaphore: S ∈ {0, 1}. Equivalent to mutex (but no ownership).
Counting semaphore: S ∈ {0, 1, 2, …}. Used to control access to a pool of n resources.

Blocking implementation (no busy wait):
wait: if S≤0, add process to waiting queue and block. signal: if queue non-empty, wake one process; else S++.

Semaphore for mutual exclusion: init S=1. Enclose CS with wait(S) … signal(S).
Semaphore for ordering: init S=0. P2 does wait(S); P1 signals after completing its task.

Mutex (Mutual Exclusion Lock): Boolean variable indicating lock availability.
Operations: acquire() and release(), both atomic.

Key difference from semaphore: Mutex has ownership — only the thread that called acquire() can call release(). Binary semaphore allows any thread to signal.

Spinlock: Mutex with busy waiting. Good for short critical sections on multicore (no context switch overhead). Bad for long waits or uniprocessor.

Priority inversion: Low-priority process holds mutex needed by high-priority process — high priority is effectively blocked by low priority. Solution: Priority inheritance protocol.

High-level synchronisation construct. Only one process can be active inside a monitor at a time — mutual exclusion is built-in.

Condition variables: x.wait() — suspends calling process. x.signal() — resumes one suspended process.
Unlike semaphore signal, monitor signal() has no effect if no process is waiting (signal is lost).

Hoare monitor: signalling process waits while signalled process runs.
Mesa monitor (used in practice): signalling process continues; signalled process goes to ready queue and re-checks condition.
Mesa monitors require while loop (not if) around condition check.

Buffer of size n. Producer adds items; Consumer removes items. Must prevent: overflow, underflow, race on buffer.

Semaphore solution:

Semaphore mutex = 1;   // mutual exclusion on buffer
Semaphore empty = n;   // empty slots (init = n)
Semaphore full  = 0;   // filled slots (init = 0)

Producer:                    Consumer:
wait(empty);                 wait(full);
wait(mutex);                 wait(mutex);
  add item to buffer;          remove item from buffer;
signal(mutex);               signal(mutex);
signal(full);                signal(empty);

Order matters: wait(empty/full) must come BEFORE wait(mutex) — reversing causes deadlock.

Multiple readers can read simultaneously. Writers need exclusive access.

First Readers-Writers (readers-preference):

Semaphore rw_mutex = 1;  // writer/reader-writer exclusion
Semaphore mutex = 1;     // protect read_count
int read_count = 0;

Reader:                           Writer:
wait(mutex);                      wait(rw_mutex);
  read_count++;                     write;
  if (read_count==1) wait(rw_mutex);signal(rw_mutex);
signal(mutex);
  read;
wait(mutex);
  read_count--;
  if (read_count==0) signal(rw_mutex);
signal(mutex);

Problem: writers may starve if readers keep arriving.
Second Readers-Writers (writers-preference): New readers blocked if a writer is waiting. Prevents writer starvation but may starve readers.

5 philosophers, 5 forks. Each needs 2 adjacent forks to eat. Models processes competing for multiple shared resources.

Naive solution causes deadlock: Each picks left fork → all wait for right fork → circular wait.

Solutions:
1. Allow at most 4 philosophers to sit simultaneously (1 always blocked).
2. Pick both forks atomically (requires mutex on the pair).
3. Odd philosophers pick left-then-right; even pick right-then-left (breaks symmetry).
4. Use semaphore array: state[] = {THINKING, HUNGRY, EATING}; test() checks neighbours.

Semaphore solution:

Semaphore fork[5] = {1,1,1,1,1};
Philosopher i:
  wait(fork[i]);
  wait(fork[(i+1) % 5]);
  eat;
  signal(fork[i]);
  signal(fork[(i+1) % 5]);

This causes deadlock! Fix: philosopher 4 picks right fork first.

GATE 2018 — Semaphore trace:

// Shared: S=1
// P1: wait(S); CS1; signal(S)
// P2: wait(S); CS2; signal(S)
// Interleaving: P1 wait(S)→S=0; P2 wait(S)→blocked; P1 CS1; P1 signal(S)→wakes P2; P2 CS2

Mutual exclusion maintained. Only one in CS at a time. ✓

GATE 2020 — Which condition is violated?

// Process P1: while(true) { CS; }   // never leaves CS
// Process P2: entry section; while(turn != 2);  // waits forever

P1 never exits CS — P2 waits indefinitely. Bounded Waiting is violated.

GATE 2022 — Producer-Consumer deadlock:

// Bug: wait(mutex) before wait(empty)
Producer: wait(mutex); wait(empty); ...
Consumer: wait(mutex); wait(full); ...

If buffer full: Producer holds mutex, waits on empty. Consumer waits on mutex. Deadlock!
Fix: always acquire resource semaphore (empty/full) before mutex.