Why Synchronize?

Concurrent processes that share data risk race conditions: the final value depends on the unpredictable interleaving of their instructions. Classic example — two processes incrementing a shared counter concurrently can lose updates because counter++ is not atomic; it is read-modify-write.

The Critical-Section Problem

Each process has a critical section (CS) of code where it accesses the shared resource. We need a protocol so that at most one process is inside its CS at any time.

A correct solution must satisfy three properties:

1. Mutual Exclusion — only one process inside the CS.
2. Progress — if no process is in the CS, one of the contenders must be allowed in.
3. Bounded Waiting — there is a bound on the number of times other processes may enter their CS after a process has requested entry and before that request is granted (no starvation).

Generic Structure of a Process

Pseudo-code:

do { entry section critical section exit section remainder section } while (TRUE);

Hardware Support

Modern CPUs provide atomic instructions:

• Test-and-Set — atomically read and set a variable.
• Compare-and-Swap (CAS) — atomic compare and conditional update; the building block for lock-free data structures.

Software Solutions — Peterson's Algorithm (two processes)

flag[i] = true; turn = j; while (flag[j] && turn == j); / busy wait / critical section flag[i] = false;

Peterson satisfies all three properties on machines with sequentially consistent memory.

Higher-level Tools

• Mutex locks — acquire()/release(). Simpler API than Peterson's algorithm.
• Semaphores — counters that support wait (P) and signal (V) operations (next lesson).
• Monitors — language-level construct (Java's synchronized).

Producer–Consumer Sketch

The producer must wait when the buffer is full; the consumer must wait when it is empty. Both must access the buffer in mutual exclusion.

Common Pitfalls

• Deadlock — every contender is blocked waiting for someone else.
• Livelock — processes keep changing state but make no progress.
• Priority inversion — low-priority process holds a lock needed by a high-priority one.

Summary

• Race conditions arise when interleavings of unsynchronized accesses produce inconsistent results.
• The critical-section problem requires mutual exclusion, progress and bounded waiting.
• Hardware atomics, Peterson's algorithm and semaphores are increasingly higher-level solutions.