Critical Section Problem

Problem Statement

When several cooperating processes access the same shared data, any segment of code that touches that data is called a critical section. A correct solution must ensure:

Assumptions for classic software proofs: each process executes at a non-zero but unpredictable speed, and single‐word load/store instructions are atomic.

Two-Process Software Algorithms

Let the processes be P1 and P1. turn is an integer (0 or 1); flag[2] is a Boolean array.

Algorithm 1 – Strict Alternation

1// shared: int turn = 0;
2// 0 → P1’s turn, 1 → P1’s turn
3
4while (true) {
5    while (turn != i) ;         // entry section (busy-wait)
6    /* critical section */
7    turn = j;                   // give turn to the other process
8    /* remainder section */
9}

Algorithm 2 – Individual Flags

 1// shared: bool flag[2] = {false,false};
 2
 3// code for Pi (j = 1 - i)
 4while (true) {
 5    flag[i] = true;          // I want to enter
 6    while (flag[j]) ;        // wait while the other is ready
 7    /* critical section */
 8    flag[i] = false;         // I’m done
 9    /* remainder section */
10}

Algorithm 3 – Peterson’s Algorithm

 1// shared: bool flag[2] = {false,false};
 2          int  turn     = 0;        // whose turn if conflict
 3
 4// code for Pi (j = 1 - i)
 5while (true) {
 6    flag[i] = true;                 // I want to enter
 7    turn    = j;                    // let the other go first
 8    while (flag[j] && turn == j) ;  // wait if j also wants in
 9    /* critical section */
10    flag[i] = false;                // I’m done
11    /* remainder section */
12}

N-Process Solution – Bakery Algorithm

Every process takes a “ticket” like customers at a bakery.

Shared Variables

1bool choosing[n] = {false};   // true while Pi is picking a number
2int  number[n]   = {0};       // ticket numbers (0 ⇒ not competing)

Pi’s Code

 1while (true) {
 2    // entry section
 3    choosing[i] = true;                     // announce intention
 4    number[i]   = 1 + max(number[0..n-1]);  // take next ticket
 5    choosing[i] = false;
 6
 7    fo*r (int j = 0; j < n; j++) {           // wait for turn
 8        while (choosing[j]) ;               // wait if Pj choosing
 9        while (number[j] != 0 &&
10              (number[j] <  number[i] ||
11              (number[j] == number[i] && j < i))) ;
12    }
13
14    /* critical section */
15
16    number[i] = 0;                          // exit section
17    /* remainder section */
18}

Why It Works

The Bakery Algorithm generalizes Peterson’s idea to any number of processes without special hardware, guaranteeing a fair, starvation-free ordering of critical-section access.

Here’s an example problem based on the Bakery Algorithm and the execution sequence you’ve described:

Example Problem:

Five processes P1 through P4 are competing for entry into their critical sections using Lamport’s Bakery Algorithm.

At a particular moment, the following occurs:

1. All five processes begin executing their entry sections at approximately the same time.

2. P1 does not intend to enter its critical section, and therefore skips taking a ticket (number[1] = 0).

3. All other processes (i.e., P1, P2, P3, P4) enter the entry section and begin executing the choosing[i] and number[i] assignment part.

4. The resulting ticket numbers are:

   • P1 gets ticket 1
   • P2 gets ticket 3
   • P3 gets ticket 2
   • P4 gets ticket 4

All processes now enter the second for loop of the Bakery Algorithm and start comparing their ticket numbers to others.

Part A: Waiting Table (simplified version)

Part B: Execution Sequence

1. P1 enters critical section first.
2. P1 exits CS and sets number[0] = 0.
3. Now P3 has the smallest active number (2) → enters CS.
4. P3 exits and resets number[3] = 0.
5. Now P2 has the next smallest ticket (3) → enters CS.
6. P2 exits and resets number[2] = 0.
7. P4 now has the smallest active ticket (4) → enters CS.

Execution Order: <P1, P3, P2, P4>