Concurrency and synchronization

Concurrency and race conditions

Definition. Concurrent processes or threads make progress during overlapping time intervals; they need not run simultaneously on separate CPUs. A race occurs when program behavior depends on the timing or interleaving of accesses to shared state. A critical section accesses shared state that requires controlled entry.

Example. Two threads increment shared x with a read, add, write sequence; both can read the old value and lose one update.

Exam point. An operation that looks like one source statement may compile to multiple machine instructions and may not be atomic.

Solved examples

Example 1 — lost update. x starts at 0. T1 and T2 both execute x=x+1; enumerate a legal interleaving.

1. T1 reads x=0; T2 reads x=0.
2. T1 computes 1 and writes 1.
3. T2 computes 1 and writes 1.
4. Final x=1, although two increments were requested.

Example 2 — race freedom. A program protects every read and write of x with the same mutex.

1. Only the lock owner executes the protected region.
2. Other threads wait before accessing x.
3. Each increment completes before another begins.
4. The increments are serialized and final x is 2.

Critical-section requirements

Definition. A correct critical-section solution should provide mutual exclusion, progress, and bounded waiting. Mutual exclusion permits at most one process in the section; progress prevents unrelated delay when the section is free; bounded waiting limits how many entries other processes may take before a waiting process is served.

Example. A mutex gives mutual exclusion; fairness or queueing policy contributes to bounded waiting.

Exam point. A solution can satisfy mutual exclusion but still starve a process.

Solved examples

Example 1 — test a spin solution. Two threads repeatedly execute while(lock) {}; lock=true; before entering.

1. T1 reads lock=false.
2. Before T1 stores true, T2 also reads false.
3. Both store true and enter.
4. Mutual exclusion fails; the check and set must be atomic.

Example 2 — bounded waiting distinction. A thread repeatedly wins a mutex while another waits forever.

1. At most one thread holds the lock at a time, so mutual exclusion holds.
2. The waiting thread never receives service, so bounded waiting/fairness fails.
3. Correctness requires more than mutual exclusion.

Atomic instructions and locks

Definition. An atomic read-modify-write instruction such as test-and-set or compare-and-swap executes indivisibly with respect to competing threads. A lock uses such primitives to protect a critical section. A spinlock waits by repeatedly checking; a blocking mutex can sleep a waiter.

Example. while (test_and_set(&L)) {} acquires L when the old value was false.

Exam point. Spinlocks are useful for short waits in suitable environments; spinning wastes CPU if the holder is descheduled for long.

Solved examples

Example 1 — test-and-set trace. L=false. T1 and T2 each execute atomic test-and-set.

1. T1 atomically reads false and sets L=true; it acquires.
2. T2 atomically reads true and leaves L=true; it fails.
3. T1 exits and sets L=false.
4. Only one thread acquires at a time.

Example 2 — compare-and-swap. Atomic CAS(L,false,true) succeeds only when L currently equals false. L starts true.

1. Compare current L with expected false.
2. They differ, so CAS does not write true and reports failure.
3. L remains true; caller must retry or block.

Semaphores

Definition. A semaphore has an integer value and atomic operations wait (P/down) and signal (V/up). A counting semaphore tracks multiple identical resources; a binary semaphore has values used for exclusion or event signaling. In the classic model, wait decrements if positive or blocks until it can proceed; signal increments or wakes a waiter.

Example. A counting semaphore initialized to 3 can allow at most three concurrent users of a resource pool.

Exam point. Semaphore operations must be atomic; a semaphore is not simply an ordinary integer.

Solved examples

Example 1 — counting trace. Semaphore S starts at 2; three processes each wait once, and then one signals.

1. P1 waits: S becomes 1 and proceeds.
2. P2 waits: S becomes 0 and proceeds.
3. P3 waits: S is unavailable, so it blocks.
4. A signal releases one permit or wakes a waiter; P3 can proceed.
5. At most two processes use the resource concurrently.

Example 2 — binary mutex semaphore. S=1. T1 executes wait(S), critical section, signal(S); T2 requests wait while T1 holds it.

1. T1's wait changes S from 1 to 0.
2. T2's wait cannot decrement a positive value and blocks.
3. T1 signals; the semaphore makes a waiter eligible.
4. T2 proceeds only after the protected interval is released.

Producer-consumer bounded buffer

Definition. For a buffer of capacity N, empty counts free slots, full counts occupied slots, and mutex guards buffer state. Initialize empty=N, full=0, mutex=1. A producer waits for empty before mutex; a consumer waits for full before mutex.

Example. Capacity 4 means initial empty=4, full=0.

Exam point. Acquire the resource-count semaphore before mutex to avoid holding the buffer lock while blocked for space/data.

Solved example

Example — one produce and consume. N=3; initial (empty,full)=(3,0). One producer inserts then one consumer removes.

1. Producer wait(empty): empty=2; lock mutex; insert; unlock; signal(full): full=1.
2. Consumer wait(full): full=0; lock; remove; unlock; signal(empty): empty=3.
3. Final counts return to (3,0), and empty+full=3 throughout completed operations.

semaphore empty = N, full = 0, mutex = 1;
producer() {
    while (true) {
        item x = make_item();
        wait(empty); wait(mutex);
        put(x);
        signal(mutex); signal(full);
    }
}
consumer() {
    while (true) {
        wait(full); wait(mutex);
        item x = get();
        signal(mutex); signal(empty);
        use(x);
    }
}