Synchronization: races, critical sections and locks

Learning goals and model

Learn to construct a lost-update trace, identify a critical section, distinguish safety from progress, and reason about a correctly used mutex. Prerequisite: threads share an address space but have separate execution contexts. The examples use abstract pseudocode, not executable C or C++. Each displayed read or write is atomic, interleavings preserve each thread's statement order, and all threads observe one sequentially consistent memory history. Ordinary unsynchronized C/C++ accesses do not inherit this model: a data race can make program behavior undefined.

This foundation covers basic mutual exclusion. Semaphores, condition variables, formal deadlock analysis and memory-order primitives require later lessons. Do not use the deliberately broken pseudocode below as a programming recipe.

1. Why one source statement may not be one operation

Suppose two threads each intend to increment a shared count once, with count initially 0. An abstract increment expands into three steps:

1. Read shared count into the thread's private register r.
2. Set that private r to r+1.
3. Write r back to shared count.

T1 uses register r1 and T2 uses r2. Even when individual reads and writes are atomic, the full read–modify–write sequence is not automatically atomic. Correct isolated increments should leave count=2, but interleaving may lose an update.

Both threads executed their increment instructions, yet the final count is 1. In the serial order “all of T1, then all of T2,” T2 instead reads 1 and the result is 2. Under exactly this two-thread, one-increment-per-thread model, possible final values are 1 and 2, not 0 or an arbitrary number. Enumerating legal interleavings is a checkable way to establish this, not merely guessing that “anything can happen.”

A race condition means an outcome depends on the timing or ordering of concurrent actions in a way that can violate the intended requirement. The more specific language-level term data race has a formal definition in a language's memory model. Keep that distinction when moving from these abstract traces to real code.

2. Protect the logical operation, not just the last write

The critical section is the part that accesses shared state and must not overlap with other conflicting accesses. For the increment above, the protected operation includes reading, changing and writing count. If only the final write is protected, both threads can still read 0 before either writes, so the lost update remains possible.

An entry section obtains permission; an exit section releases it. Code not needing this protection is the remainder section. A correct shared mutex m starts unlocked, and each participating thread follows:

lock(m)
read count into private r
r = r+1
write r to count
unlock(m)

Assume lock acquisition is atomic and the mutex's memory-synchronization guarantees apply. At most one thread owns m at a time. If T1 owns it, T2 cannot enter the protected section until T1 releases it. T2 then reads the count produced by the completed first increment, giving count=2 after both finish. The order may be T1 then T2 or T2 then T1; either is correct.

Both threads must use the same mutex, and every conflicting access must obey the chosen protocol. Two different locks do not coordinate the threads. A third thread that changes count without acquiring m bypasses the protection. For a larger invariant spanning several fields, an atomic increment of one field may still be insufficient; protect the whole consistency requirement.

3. A tempting but broken lock

Consider a shared Boolean busy initially false. Each thread repeatedly reads busy until it sees false, then writes busy=true, enters the critical section, and eventually writes busy=false.

The test and the claim are separate operations. T1 may read false; before it writes true, T2 may also read false. Both then write true and enter. Atomic reads and atomic writes alone do not make the combined “test and claim” atomic. A proper mutex needs a correct underlying mechanism, such as an appropriate atomic read–modify–write primitive together with a complete locking protocol. Adding a normal flag or assuming an unlucky schedule will not happen is not a proof.

4. Safety and liveness ask different questions

Mutual exclusion is a safety property: two participants must not be in the protected section simultaneously. It rules out a bad event. But a protocol that never lets anyone enter also has mutual exclusion, while being useless.

Progress asks that entry not be postponed indefinitely when the critical section is free and some participants wish to enter; the relevant contenders must be able to make a selection. Bounded waiting asks for a bound on how many times others may enter after a participant requests entry and before its request is granted. These ideas are related but not identical.

Worked counterexample: a strict-turn rule lets T1 enter only when turn=1 and T2 only when turn=2; leaving changes turn to the other thread. If turn=2 but T2 stays forever in its remainder section, T1 cannot enter an empty critical section. This shows a progress failure, even if no simultaneous entry occurs. It is not necessary for two threads to collide to have a bad synchronization design.

A mutex interface alone does not establish fairness or a bounded-waiting guarantee. State assumptions about eventual scheduling, finite critical sections and eventual release before claiming everyone will finish. A thread that acquires a non-reentrant mutex and tries to acquire the same mutex again before releasing it may block itself; “more locking” is not automatically safer.

5. Spinning, blocking and one-CPU reasoning

A spinning waiter repeatedly checks a condition and consumes CPU while doing so. A blocking mutex can put the waiter to sleep until it can try again. Neither strategy by itself proves fairness. On a preemptively scheduled single CPU, a spinning thread can be preempted so the owner can run and release the lock. Without such scheduling, a spinner that prevents the owner from ever running can prevent progress. Always identify the scheduling assumptions rather than asserting that a spinlock always works or never works on one CPU.

Races do not require two physical CPUs. A context switch between a read and its later write is enough to create the earlier lost-update trace. Conversely, a mutex does not “stop all threads”: it excludes only participants following that particular locking protocol from the protected operation. Unrelated work can continue.

Key points and common mistakes

• Specify the atomic steps and the intended invariant before tracing.
• Per-thread registers can hold stale copies of a shared value.
• Protect the whole conflicting read–modify–write sequence with one shared lock.
• An ordinary check followed by a set is not an atomic test-and-set.
• Mutual exclusion does not by itself imply progress, fairness or bounded waiting.
• Do not treat abstract pseudocode outcomes as guarantees for a data-racy C/C++ program, or assume that one CPU eliminates races.

Original practice: six single-correct MCQs

Original questions, not previous-year questions. Choose exactly one option. All question assumptions continue to apply.

C01. Two threads each perform read count; increment a private register; write count once, starting at count=0. Under the stated atomic-step, sequentially consistent model, what final values are possible?

A. Only 2 B. Only 1 C. 0, 1 and 2 D. 1 and 2

Answer: D

A: A lost-update interleaving makes 1 possible as well.

B: A serial execution makes 2 possible as well.

C: Every final write stores an incremented value; no legal execution in this specific model ends at 0.

D: If both reads see 0, the result is 1; if one complete increment precedes the other read, the result is 2.

C02. Both threads use one correct mutex, but only around the final write of their increment. Can the final count still be 1?

A. No, atomic writes always make the full increment atomic. B. Yes, both can read 0 and compute 1 before the separately protected writes. C. No, a shared mutex protects all code in the process automatically. D. Yes, but only on two physical CPUs.

Answer: B

A: Atomicity of the last step does not protect the earlier read–modify sequence.

B: The writes serialize, but each can still write the same stale-derived value 1.

C: Only accesses following the intended locked protocol are coordinated.

D: An interleaving on one preemptive CPU can produce the same lost update.

C03. A proposed lock separately reads busy=false and later writes busy=true before entry. Why can mutual exclusion fail?

A. Both threads can observe false before either claims the flag. B. A Boolean cannot represent two states. C. Every read changes busy to true. D. Mutual exclusion requires an infinite critical section.

Answer: A

A: The test and claim are not one atomic operation, allowing both entrants through.

B: A Boolean represents two states; the problem is atomicity of the protocol.

C: A read alone does not perform the following write.

D: An infinite section would undermine progress, not solve the entry race.

C04. A strict-turn protocol leaves turn=2 while T2 stays forever in its remainder section. T1 wants to enter an empty critical section but cannot. Which requirement is directly violated?

A. Mutual exclusion, because both threads are inside B. Atomicity of every individual read C. Progress, because an eligible request is indefinitely obstructed by the turn rule D. The requirement that each thread have its own register state

Answer: C

A: The example has no simultaneous entry; exclusion can still hold.

B: The failure remains even if each read and write is atomic.

C: The section is free, yet T1 cannot enter because a non-contending thread does not hand over the turn.

D: Register ownership is unrelated to this progress counterexample.

C05. Two threads each increment count once inside the same correctly implemented mutex. Count begins at 7; both threads finish; every conflicting access follows the lock protocol. What is the final count?

A. 7 B. 8 C. Either 8 or 9 D. 9

Answer: D

A: Both completed protected increments must take effect.

B: Eight would lose an update, which this correctly protected complete operation prevents.

C: The assumptions serialize the full increments and rule out 8.

D: The increments serialize: 7→8→9, whichever thread enters first.

C06. A lock guarantees mutual exclusion but its specification gives no fairness guarantee. Which conclusion is justified from mutual exclusion alone?

A. Every waiting thread enters within two turns. B. At most one complying thread is in the protected critical section at a time. C. Every thread eventually enters regardless of scheduling. D. The CPU never spends time spinning.

Answer: B

A: A numerical waiting bound needs an additional guarantee and assumptions.

B: This is exactly the safety guarantee of mutual exclusion, limited to threads obeying the protocol.

C: Eventual entry needs liveness and scheduling assumptions; safety alone is insufficient.

D: Mutual exclusion can be implemented with spinning or blocking; it does not determine waiting behavior.

Sources and scope

This original introductory lesson aligns with Section 8, Operating System, of the official GATE 2027 CS syllabus. It does not complete OS or the full syllabus. The syllabus verifies topic relevance; the primary textbook references verify foundational concepts. Examples, timelines and practice are original.

• Official GATE 2027 CS syllabus
• OSTEP: Concurrency: An Introduction
• OSTEP: Locks
• C++ working draft: Data races

Sources checked 2026-10-14.