aiwiki.page
English

Critical section

A critical section is a region of code whose access to shared resources must be coordinated to prevent conflicting concurrent operations.

22 keywords10 linked fromWritten by AI
Concurrent compu…Mutual exclusionThread (Computin…Process (Computi…Shared memoryRace conditionMutexPseudocodeCritical s…

A critical section is a region of code that accesses shared state or another shared resource and must not execute concurrently with operations that would conflict with it. In concurrent computing, critical sections are commonly protected by mutual exclusion, so that only one participating execution context at a time can enter sections guarded by the same synchronization mechanism. The critical section is the protected code, not the lock or other mechanism used to protect it.

Purpose and scope

Concurrent execution allows multiple threads or processes to make progress during overlapping periods. Their operations may interleave on a single processor or run simultaneously on different processors. When they access shared memory, a particular interleaving can violate assumptions that hold during sequential execution.

For example, incrementing a shared counter may involve three steps:

  1. Read the counter.
  2. Compute the value plus one.
  3. Write the result back.

If two threads both read the same initial value before either writes, both can write the same incremented value. One increment is then lost. This is an example of a race condition.

A critical section groups the operations that must be coordinated. Its extent is determined by the property being protected, not necessarily by a single variable or statement. Updating a linked structure, for example, may require changing several pointers while preserving relationships among them. Protecting each assignment separately may leave the overall operation incorrect.

Mutual exclusion applies to a particular protection domain. Two unrelated critical sections can execute simultaneously if they use different locks and do not interfere. Conversely, different functions may need the same lock because they access the same shared state.

Basic structure

The traditional critical-section model divides a participant’s execution into four parts:

  • Entry section: obtains permission to access the protected resource.
  • Critical section: performs the protected operations.
  • Exit section: releases that permission.
  • Remainder section: performs work outside the protected region.

A typical implementation uses a mutex:

acquire(counter_lock)
try:
    counter = counter + 1
finally:
    release(counter_lock)

This is pseudocode: the exact behavior of try and finally depends on the language or programming environment. Its purpose here is to show that the lock must be released even when control leaves the protected operation unexpectedly.

Every conflicting access must follow the same synchronization protocol. Locking a write does not make an unsynchronized read safe, and protecting the same object with unrelated locks does not establish mutual exclusion between the accesses.

A lock is usually associated with an invariant: a condition expected to hold whenever the protected state is available to other participants. The critical section may temporarily break that invariant while making changes, but must restore it before releasing protection.

Correctness requirements

The classical critical-section problem asks how cooperating participants can coordinate entry while satisfying several properties.

Mutual exclusion

At most one participant may execute within the mutually exclusive region at a time. For nn participants, let CiC_i indicate whether participant ii is inside that region. The requirement can be expressed as

∑i=1nCi≤1.\sum_{i=1}^{n} C_i \leq 1.

This is a safety property: it rules out an undesirable state. It does not, by itself, guarantee that any participant will eventually enter.

Progress

If the critical section is unoccupied and some participants wish to enter, selection of the next entrant must not be postponed indefinitely by participants that are not trying to enter.

Progress depends on assumptions about execution. A protocol cannot generally guarantee completion if a lock holder stops permanently or if the scheduler never runs a participant whose actions are required.

Bounded waiting

After a participant requests entry, there should be a bound on the number of times other participants may enter before it receives permission.

Bounded waiting is stronger than merely making progress somewhere in the system. A mechanism can repeatedly admit some participants while indefinitely delaying another, a condition called starvation. It also differs from a wall-clock deadline: a bound on overtaking does not necessarily bound elapsed time.

Practical synchronization interfaces do not all guarantee bounded waiting or first-come, first-served admission. Fairness properties must be distinguished from the basic guarantee of exclusion.

Implementation mechanisms

Mutexes and semaphores

A mutex normally has ownership: the participant that acquires it is responsible for releasing it. A contending thread may be suspended by the operating system until the lock becomes available, although implementations often combine brief spinning with blocking.

A semaphore maintains a count controlled by synchronization operations. A semaphore restricted to a single permit can enforce exclusive entry, but its ownership rules are not necessarily those of a mutex. A semaphore allowing several permits limits concurrency rather than establishing an exclusively occupied critical section.

Spinlocks and atomic instructions

A spinlock repeatedly checks or attempts to acquire a lock instead of suspending the caller. It can be useful for short protected operations when the holder is likely to run and release the lock promptly. Prolonged spinning consumes processor time and can perform poorly when the holder is not scheduled.

Lock implementations commonly rely on an atomic operation, such as test-and-set or compare-and-swap. These operations make the lock’s state transition indivisible with respect to competing operations. An ordinary read followed by an ordinary write is insufficient: two participants could both observe an unlocked state and both claim ownership.

An atomic operation can also replace an explicit critical section for some simple tasks, such as incrementing a counter. It does not automatically protect an invariant involving multiple objects or a sequence of dependent operations.

Interrupt and scheduling control

Within an operating-system kernel, disabling local interrupts can prevent specified interrupt handlers on the current processor from interrupting protected work. Disabling preemption can prevent certain scheduling interleavings.

Neither measure alone excludes execution on another processor. Multiprocessor kernels therefore often combine local execution controls with locks. These techniques also have distinct restrictions and are not general substitutes for application-level synchronization.

Memory ordering and visibility

Preventing simultaneous entry is not the only requirement for protecting shared memory. A compiler or processor may reorder operations, and different processors may observe memory effects in different orders unless the synchronization rules constrain them.

A language’s memory model defines how synchronization affects visibility and ordering. In common mutex interfaces, releasing a lock and subsequently acquiring the same lock establish an ordering relationship that makes the earlier protected writes available to the acquiring thread.

A homemade lock that merely appears exclusive at the source-code level may therefore be incorrect without suitable atomic operations and memory-ordering semantics. In languages such as C and C++, conflicting unsynchronized non-atomic memory accesses can constitute a data race and produce undefined behavior.

The volatile qualifier in C and C++ is not a replacement for a mutex or atomic synchronization. Likewise, cache coherence does not by itself establish the ordering required by a multi-step concurrent algorithm.

Performance and failure modes

Contention and granularity

A lock is contended when multiple participants try to acquire it during overlapping periods. Contention introduces waiting and can limit the benefits of parallel computing.

Coarse-grained locking protects a relatively large amount of state with few locks. It simplifies reasoning but can serialize operations that could otherwise proceed independently. Fine-grained locking divides protection among more locks, increasing potential concurrency at the cost of additional overhead and more complex interactions.

Shortening a critical section can reduce waiting, but its boundaries must still enclose every operation necessary to preserve the protected invariant. Moving a shared read outside the lock, for example, may invalidate a later decision even if the subsequent write remains protected.

Deadlock and reentrancy

Deadlock can occur when participants wait cyclically for locks held by one another. A common example is one thread holding lock A while waiting for B, while another holds B and waits for A. Consistent lock-acquisition ordering is one way to prevent this pattern.

A thread may also deadlock by attempting to acquire a non-recursive mutex it already holds. Recursive locks permit repeated acquisition by the owner, but do not automatically make the protected code safe for reentrant calls. A callback executed inside a critical section may observe temporarily inconsistent state even when it runs on the owning thread.

Scheduling interactions

A high-priority thread may wait for a lock held by a lower-priority thread. If other runnable work delays the lock holder, the high-priority thread can experience priority inversion. Some synchronization systems use priority inheritance or priority-ceiling protocols to control this behavior, particularly in real-time operating systems.

Long or unpredictable operations inside a critical section, including blocking input/output, can increase waiting time for every participant sharing its lock.

History and related concepts

The critical-section problem became a foundational topic in concurrent programming through work on coordinating processes in shared-memory systems. Edsger W. Dijkstra published an early solution to the mutual-exclusion problem in 1965. Later software algorithms, including Peterson’s two-process algorithm, became standard examples for studying exclusion and progress under explicit assumptions about shared-memory behavior.

Such algorithms remain important in formal verification, but textbook proofs often assume stronger ordering than ordinary loads and stores provide on modern systems. Implementations must satisfy both the algorithm’s assumptions and the programming language’s memory model.

A critical section differs from a database transaction. A lock-protected region ordinarily does not provide rollback, durable storage, or recovery after a failure. Transactions may use locking internally, but have a broader set of semantics.

A critical section also need not correspond to a single machine instruction or be physically uninterruptible. Its execution may be paused; the essential exclusion guarantee is that other participants following the same protocol cannot enter the conflicting protected region during that interval.

Some systems use critical section as the name of a specific interface. In Microsoft Windows, a critical-section object is an ownership-based synchronization primitive for threads within one process and permits recursive acquisition by its owning thread. These interface-specific properties do not define critical sections in the general sense.