2.5 Synchronization and Mutual Exclusion

1. Synchronization vs. Mutual Exclusion

Synchronization constrains the relative ordering of concurrent operations. For example, a consumer must not consume an item before a producer publishes it.

Mutual exclusion ensures that only one execution context enters a protected critical section at a time.

A critical section is code that accesses shared state whose invariants would be violated by uncontrolled concurrent execution.

2. Semaphores

A semaphore maintains a count.

Conceptually:

• wait/down/P decrements the count when capacity is available; otherwise the caller waits;
• post/up/V increments the count and may wake a waiter.

A counting semaphore is useful for bounded resources such as connection slots.

3. Mutexes

A mutex represents ownership of a critical section. Although a binary semaphore and a mutex can look similar, mutexes usually have ownership semantics and may integrate priority inheritance or other scheduler behavior.

Use a mutex when one invariant spans multiple reads/writes that must be protected as a unit.

4. Condition Variables / Monitors

A condition variable lets a thread sleep until some state predicate may have changed.

The typical pattern is:

lock mutex
while predicate is false:
    wait(condition, mutex)
perform operation
unlock mutex

The predicate is checked in a loop because wakeups do not imply the desired state is definitely true.

5. Classic Problems

Important models include:

• producer/consumer;
• readers/writers;
• dining philosophers.

They are useful because they expose the same issues that appear in production systems: ordering, bounded capacity, fairness, starvation, and deadlock.