The Multithread Lock

A critical section is the code between acquiring a lock and releasing it. The standard model assumes this code runs on a single thread: one thread locks, executes the protected region, and unlocks. Lock-set analysis — the standard technique for detecting data races — relies on this assumption. Every access inside a critical section is attributed to the thread that holds the lock.

This paper shows the assumption is wrong for C/Pthread programs.

In real C/Pthread executions, a lock can be acquired on one thread and released on another. Thread A locks a mutex, spawns thread B, and thread B unlocks it. The protected events span both threads. The standard lock-set construction, which tracks locks per thread, misses this entirely — it attributes the critical section only to thread A and considers thread B’s accesses unprotected.

The authors develop a trace-based characterization of critical sections that drops the per-thread restriction. Critical sections become properties of execution traces, not of individual threads. A critical section is the set of events between a lock acquisition and its matching release, regardless of which threads execute those events.

Multi-thread critical sections arise naturally in producer-consumer patterns, thread pools, and work-stealing implementations. They’re not exotic corner cases — they’re standard concurrent programming idioms that the standard analysis framework gets wrong.

The semantic gap is concrete: data race detectors built on per-thread lock sets can report false positives (events that are actually protected) or miss true races (events that are unprotected despite appearing within a “critical section” on some thread). The fix is to define protection by the trace, not by the thread.