CS2005 - Lecture 11 - Process Synchronisation

Critical Section Problem

When multiple processes/threads access shared data simultaneously, leading to race conditions (unpredictable results)

Solution Requirements for the Critical Section Problem

Mutual Exclusion: Only one process in CS at a time

Progress: No process outside CS should block others

Bounded Waiting: No process waits forever

Peterson's Algorithm

Uses turn and flag[2] variables to ensure mutual exclusion for two processes

Mutex Lock

A binary lock [acquire()/release()] that ensures only one process enters critical section

Semaphore

A synchronisation tool that can manage access by multiple processes to a shared resource, an integer variable with atomic "wait()" (P) and "signal()" (V) operations:

Avoiding Busy Waiting with Semaphore

Uses blocking/wakeup: wait(S) { S-; if (S < 0) { block(); } } signal(S) { S++; if (S <= 0) { wakeup(P); } }

Semaphores in Producer-Consumer Problem

Use three semaphores:

1. mutex (1 for CS access)

2. empty (n for empty slots)

3. full (0 for filled slots)

Solution for Dining Philosophers

Allow only 4 philosophers to eat or make one pick right-first

Deadlock in Dining Philosophers Problem

All philosophers simultaneously pick up their left chopstick, waiting indefinitely for the right one.

Deadlock vs Starvation

Deadlock: Two+ processes wait forever for each other's resources

Starvation: A process is indefinitely denied resources

Monitor in Synchronisation

A high-level construct where methods auto-synchronise (only 1 thread executes at a time)

Monitor

A class-like structure ensuring only one thread executes its methods at a time + No manual lock management - Less flexible than semaphores