Synchronization

1A race on unsaved_count

The UI thread and the save thread of maya both touch a shared integer unsaved_count, currently 10. Each thread wants to add 1. The safe story is: read 10, write 11, then the other reads 11, writes 12. The unsafe story is both read 10 before either writes, both compute 11, both write 11. One increment is lost. That lost update is a race condition: the final value depends on the uncontrolled interleaving.

The lines that touch unsaved_count are the critical section — the code that must not overlap. The next concepts are how to keep two threads from being in that section at once.

Figure. Both threads reach the same variable without ordering; whichever write lands last wins, and the other update is lost.

How it works

1. Unsynchronised accessTwo threads both read the same counter, both add one, both write back — one increment vanishes.
2. Critical sectionOnly the code that mutates shared data needs protection; the rest of each thread may run freely.
3. Three guaranteesMutual exclusion stops overlap; progress stops indefinite blocking when the section is free; bounded waiting stops one lucky thread from starving the rest.

2Three properties of a correct lock

A lock around unsaved_count is not just 'take turns'. Any correct critical-section solution must satisfy three properties together. Mutual exclusion: at most one thread is in the section. Progress: if the section is free and someone wants in, the choice of who enters cannot be postponed indefinitely. Bounded waiting: a thread that has asked to enter cannot be skipped forever.

A mutex that sometimes lets both threads in fails the first. A mutex that never picks a waiter when the section is free fails the second. A mutex that always favours the UI thread fails the third — the save thread starves.

Write the three names — mutual exclusion, progress, bounded waiting — and ask which one a broken lock violated. There is no diagram of 'progress'.

The three together

1. Mutual exclusionUI and save are never both incrementing unsaved_count.
2. ProgressIf the count is free, one of the waiters is allowed in.
3. Bounded waitingThe save thread cannot be skipped forever.

3Peterson's two-process lock

Before the machine offered an atomic swap, Peterson's algorithm locked a critical section for exactly two threads using ordinary memory. Call them UI (i) and save (j). Each thread has a flag meaning 'I want in' and they share a turn variable.

UI sets flag[i], yields the turn to save, and spins while save still wants in and still holds the turn. On the way out UI clears flag[i]. The protocol gives mutual exclusion for two participants. It does not generalise to three — a third thread needs a different algorithm.

Figure. Pi declares intent, yields turn to Pj, then spins only while Pj both wants in and holds the turn — software mutual exclusion for exactly two processes.

How it works

1. Declare intentProcess i sets flag[i] = true before trying to enter.
2. Yield turnProcess i sets turn = j, politely giving the other process priority if both want in.
3. Spin gateProcess i waits while flag[j] is true and turn still equals j — the other process both wants in and was given priority.
4. ExitAfter the critical section, process i sets flag[i] = false so the other can proceed.

Peterson's algorithm — process i

flag[i] = true;
turn = j;                    // yield to the other process
while (flag[j] && turn == j)
    ;                         // spin
// --- critical section ---
flag[i] = false;

4Semaphores, mutex and monitors

A semaphore is an integer the kernel (or a library) updates atomically. wait, also written P, subtracts one and blocks if the result would be negative. signal, also written V, adds one and wakes a waiter. The integer is the number of permits left.

A counting semaphore tracks a pool — say three identical printer slots. A binary semaphore, used as a mutex, only ever holds 0 or 1 and is released by the same thread that acquired it. A monitor is a different package: the data, the lock, and the condition waits live in one language construct so you do not pair wait/signal by hand.

Figure. Mutex is a lock; semaphore counts permits; a monitor bundles mutual exclusion with condition variables.

How it works

1. wait (P)Decrement the semaphore; if the value is now negative, block until another process signals.
2. signal (V)Increment the semaphore; if a process was blocked, wake one waiter.
3. Mutex disciplineA binary semaphore used as a mutex should be released by the same thread that acquired it.
4. Monitor entryEnter the monitor to access shared data; wait on a condition inside if the predicate is false; signal when it becomes true.

Semaphore operations

wait(S):
    S = S - 1
    if S < 0:
        block

signal(S):
    S = S + 1
    if any process blocked on S:
        wake one