CriticalSection

Back to ComputerTerms

A critical section contains the execution of code that must be executed exlusive of other processes. This is to avoid a RaceCondition.

Each process goes through the following:

• Entry Section: request to enter the critical section
• Critical Section
• Exit Section (Optional)
• Remainder Section (Essentially the "other" section in that it has no impact on the entry into the critical section)

KEY: A solution to the critical-section problem must satisfy the following three requirements:

1. Mutual Exclusion: If process Pi is executing in the critical section, then no other processes can be executing in their critical sections.

2. Progress: If no process Pi is executing in it's critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.

3. Bounded Waiting: There exists a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

We assume that each process is executing at a non-zero speed, but we make no assumption concerning the relative speed of the n processes

Two examples:

Correct Critical Region for two processes

Do {
//Entry section
  Flag[i]=true;
  Turn = j;
  While (flag[j] && turn == j);
//End Entry Section
//Critical section:
  some code
  ...
//Exit Section
  Flag[i]=false
//Remainder Section

Bakery Algorithm

do {
  choosing[i] = true;
  number[i] = max(number[0], number[1], ..., number[n-1]) + 1
  choosing[i] = false;
  for (j=0; j<n; j++) {
    while(choosing[j]);
    while((number[j]!=0) && ((number[j],j)<(number[i],i)));
  }

  critical section

  number[i] = 0;

  //remainder section

} while(1);

Back to ComputerTerms