Critical section problem; why execute quickly

The critical section problem

Several threads (or processes) share data. The part of the code that accesses shared data is the critical section. If two threads execute it at the same time, the data may be corrupted and the result depends on the order of execution (a race condition). The critical section problem is to design a protocol that all threads follow, so that when one thread is inside its critical section no other thread is allowed to be inside its own critical section for the same data.

Each thread consists of:

• entry section: request permission to enter;
• critical section: access to shared data;
• exit section: release permission;
• remainder section: other code.

A correct solution satisfies three requirements:

1. Mutual exclusion: only one thread in the critical section at a time.
2. Progress: if no thread is in the critical section, one of those wanting to enter is chosen without indefinite delay; threads outside do not block it.
3. Bounded waiting: a limit on how many times others can enter before a waiting thread gets in (no starvation).

Typical solutions are Peterson's algorithm, TSL/atomic instructions, mutex locks, semaphores and monitors.

Why should a thread leave its critical section quickly?

• While one thread holds the lock, all the other threads that want it are blocked or spinning; a long critical section makes them wait, reducing concurrency and throughput.
• With spin locks waiting threads waste CPU cycles in busy waiting.
• A long critical section increases lock contention and the response time of the whole system, and may lead to starvation of waiting threads.
• A higher-priority thread waiting for a lock held by a low-priority thread is delayed (priority inversion).
• If the holder is slow or blocks (e.g. waits for I/O inside the critical section), it can cause long delays or even deadlock.

Hence critical sections should hold only the minimum code needed to access shared data, and do no I/O or lengthy work inside.