The Critical-Section Problem

• How do we avoid race conditions? What we need is mutual exclusion (see Fig. 14).

  Figure 14: Mutual exclusion using critical regions.

  
• Consider a system consisting of $n$ processes $\{P_0, P_1, \ldots , P_{n-1}\}$. Each process has a segment of code, called a critical section (CS), in which the process may be changing common variables, updating a table, writing a file, and so on.
• The important feature of the system is that, when one process is executing in its CS, no other process is to be allowed to execute in its CS.
• That is, no two processes are executing in their CSs at the same time.
• Each process must request permission to enter its CS. The section of code implementing this request is the entry section.
• The CS may be followed by an exit section.
• The remaining code is the remainder section (see Fig. 15).

  Figure 15: General structure of a typical process $P_i$.

  
• A solution to the CS problem must satisfy the following requirements:
  1. Mutual exclusion. If process $P_i$ is executing in its CS, then no other processes can be executing in their CSs.
  2. Progress. If no process is executing in its CS and some processes wish to enter their CSs, then only those processes that are not executing in their remainder sections can participate in the decision on which will enter its CS next, and this selection cannot be postponed indefinitely. (No process should have to wait forever to enter its CS.)
  3. Bounded waiting. There exists a bound, or limit, on the number of times that other processes are allowed to enter their CSs after a process has made a request to enter its CS and before that request is granted.
  4. Fault tolerance. Process running outside its CR should not block other processes accessing the CR.
  5. No assumptions may be made about speeds or the number of CPUs.
• Atomic operation. Atomic means either an operation happens in its entirely or NOT at all (it cannot be interrupted in the middle). Atomic operations are used to ensure that cooperating processes execute correctly.
• Machine instructions are atomic, high level instructions are not (count++; this is actually 3 machine level instructions, an interrupt can occur in the middle of instructions).
• Various proposals for achieving mutual exclusion, so that while one process is busy updating shared memory in its CS, no other process will enter its CS and cause trouble.
  • Disabling Interrupts
  • Lock Variables
  • Strict Alternation
  • Peterson's Solution
  • The TSL instructions (Hardware approach)