The Critical Section Problem; Solutions

Tom Kelliher, CS42

Sept. 27, 1996

The Critical Section Problem

Recall cooperating processes --- they affect or are affected by other processes through access to shared variables.

E.g., threads.

Example

Producer/Consumer (again).

const int N = 10;
int in = 0, out = 0, count = 0;
data buffer[N];

producer()
{
   data next;

   while (1)
   {
      produce in next;

      while (counter ==  n)
         ;

      buffer[in] = next;
      in = ++in % N;
      ++counter;
   }
}

consumer()
{
   data next;

   while (1)
   {
      while (counter == 0)
         ;

      next = buffer[out];
      out = ++out % N;
      --counter;

      consume next;
   }
}

What variables are being shared?

What is the nature of the sharing?

• Read, modify, write.

Reasons for Synchronizing Processes

1. For getting shared access to resources (variables, buffers, devices, etc.).

   Critical variables; critical sections.

2. For communicating.

Cases where cooperating processes need not synchronize to share resources:

1. All processes are read only.

2. All processes are write only (CRT screen).

3. One process writes (atomically), all other processes read.

What does atomic mean?

Characteristics of ``trouble situations:''

1. Multiple processes doing updates non-atomically.

2. Non-atomic write processes coupled with read or update processes

Formal Definition of Critical Sections

The overlapping portion of each process, where the shared variables are being accessed.

Necessary and sufficient conditions for a solution to the c.s. problem:

1. Mutual Exclusion --- if is executing in one of its critical sections, no , , is executing in its critical sections.

2. Progress --- a process operating outside of its critical section cannot prevent other processes from entering theirs; processes attempting to enter their critical sections simultaneously must decide which process enters eventually.

3. Bounded Waiting --- a process attempting to enter its critical region will be able to do so eventually.

Assumptions:

1. No assumptions made about relative speed of processes

2. No process may remain in its critical section indefinitely (may not terminate in its critical section)

3. A memory operation (read or write) is atomic --- cannot be interrupted. For now, we do not assume indivisible RMW cycles.

Model

(for n processes, )

Pi:
do {
   mutexbegin;       /* CS entry */
   CSi;
   mutexend;         /* CS exit  */
   non-CS
} while (!done);

Hardware Solutions

• Disabling interrupts.

  mutexbegin()
  {
     disable_ints;
  }
  
  mutexend()
  {
     enable_ints;
  }
  

  Problems with this approach:

  1. Disabling interrupts for long periods of time.

  2. Making I/O calls during CS.

• Special machine instructions:
  1. Test and set:

     int TAS(int& val)
     {
        int temp;
     
        temp = val;   // Body performed atomically.
        val = 1;
        return temp;
     }
     

  2. Fetch and increment:

     int FAI(int& val)
     {
        return val++;   // Performed atomically.
     }
     

FAI solution to CS problem for n processes:

int nextTicket = 0, serving = 0;

mutexbegin()
{
   int myTicket;

   myTicket = FAI(nextTicket);

   while (myTicket != serving)
      ;
}

mutexend()
{
   ++serving;
}

Correctness proof:

1. Mutual exclusion: contradiction.

   Assumption: no process ``plays'' with control variables.

2. Progress: by inspection, there's no involvement from processes operating outside their CSs.

3. Bounded waiting: myTicket at most n more than serving.

Software Solutions

Two Process Solutions

Try 1

Critical section code:

int turn = 0;        /* shared control variable */

Pi:                  /* i is 0 or 1 */
while (turn != i)
   ;                 /* busy wait */
CSi;
turn = 1 - i;

1. Guarantees mutual exclusion.

2. Does not guarantee progress --- enforces strict alternation of processes entering CS's.

3. Bounded waiting violated --- suppose one process terminates while its its turn?

Try 2

Remove strict alternation requirement

int flag[2] = { FALSE, FALSE }   /* flag[i] indicates that Pi is in its */
                                 /*  critical section */

while (flag[1 - i])
   ;
flag[i] = TRUE;
CSi;
flag[i] = FALSE;

1. Mutual exclusion violated

2. Progress ok.

3. Bounded wait ok.

Try 3

Restore mutual exclusion

int flag[2] = { FALSE, FALSE }   /* flag[i] indicates that Pi wants to */
                                 /*  enter its critical section */

flag[i] = TRUE;
while (flag[1 - i])
   ;
CSi;
flag[i] = FALSE;

1. Guarantees mutual exclusion

2. Violates progress --- both processes could set flag and then deadlock on the while.

3. Bounded waiting violated

Try 4

Attempt to remove the deadlock

int flag[2] = { FALSE, FALSE }   /* flag[i] indicates that Pi wants to */
                                 /*  enter its critical section */

flag[i] = TRUE;
while (flag[1 - i]) {
   flag[i] = FALSE;
   delay;                  /* sleep for some time */
   flag[i] = TRUE;
}
CSi;
flag[i] = FALSE;

1. Mutual exclusion guaranteed

2. Progress violated (processes can ``dance'')

3. Bounded waiting violated

Peterson's Algorithm

int flag[2] = { FALSE, FALSE }   /* flag[i] indicates that Pi wants to */
                                 /*  enter its critical section */
int turn = 0;                    /* turn indicates which process has */
                                 /*  priority in entering its critical */
                                 /*  section

flag[i] = TRUE;
turn = 1 - i;
while (flag[1 - i] && turn == 1 - i)
   ;
CSi;
flag[i] = FALSE;

1. Satisfies all solution requirements

Multiple Process Solution

Lamport's Bakery algorithm

int choosing[NPROCS] = { FALSE }    /* cheating initializer */
int number[NPROCS] = { 0 }

choosing[i] = TRUE;
number[i] = max(number) + 1;
choosing[i] = FALSE;
for (j = 0; j < NPROCS; j++) {
   while (choosing[j])
      ;
   while (number[j] != 0 && (number[j] < number[i] || 
                             number[j] == number[i] && j < i) )
      ;
}
CSi;
number[i] = 0;