Critical Section Problem

When multiple process run in the system, they might at times want to access the same resource at same time. This situation can lead to unwanted results. To understand the issues – race condition and critical section problem, related with process synchronization lets consider a situation as below:

Let:  counter = 5
If I run two operations counter ++ and counter-- in any order:
  counter ++;
  counter--;
  or
  counter -- ;
  counter++ ;
What should be the value of counter?
Ans: 5

The machine implementation of counter++ and counter– will look like this:

counter++

counter–

register1 = counter
register1  = register1  + 1
counter = register1
register2 = counter
register2 = register2  - 1
counter = register2

Now, if these operations overlap as shown in the table below, you will notice that the final value of counter is not what is expected.

TimeEquationregister1Register2Counter
T=0register1 = counter55
T=1register1  = register1  + 1 register2 = counter655
T=2counter = register1 register2 = register2  – 1646
T=3counter = register244

Finally, the value of the variable counter is 4 but it should have been 5. Similarly, if the operations were reversed the final value of counter would be 6 and again not 5. This is because the second process accessed the variable counter while its value was being modified by the first process.

Therefore, a situation where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place is called a race condition.

PPT on Race Condition

Video on Race Condition

race condition in process synchronization

Critical Section Problem

Critical section is that portion of code in which a process may be changing variables, updating a table, writing a file and so on.
For instance, in a given code only a subset of instructions form the critical section. You never modify the shared resource in the entire code. Thus, only those lines which are concerned with the modification of the shared variable/resource form the critical section (as shown in code below)

int main()
{
  statement;
   statement;
   statement;
   statement;
  c++; //critical section part
   statement;
   statement;
   statement;
}

So, no two processes should be allowed to execute in their critical section at the same time. Lastly, Critical section problem is to design a protocol that the processes can use to cooperate. 

Solution Requirements

A solution to the critical section problem should satisfy three requirements:

  1. Mutual exclusion – which means that only one process will be able to enter the critical section at any time.
  2. Progress – if some processes want to enter the critical section then at least one of them should be able to do so.
  3. Bounded waiting – there should be a upper-bound on how long a process will have to wait for its turn to enter critical section after it has made a request to do so

Example

Consider the below solution for critical section problem and tell which of the conditions is not satisfied

begin
while true do
  begin
  while turn = proc2 do {keeptesting};
  critical_section;
  turn=proc2;
  other_p1_processing
end[while]
end ; {p1}
} 

Now let’s see which requirements are satisfied and which one is not
Mutual Exclusion is satisfied because only P1 or P2 will be able to enter the critical section at any given time.
Progress is Not satisfied because if one of the processes crashes outside the critical section it will not be able to change the value of “turn” variable.
Bounded Wait is satisfied because a process has to wait for only one other process

Peterson’s Solution

Peterson’s Solution is a software based solution which provides solution to critical section problem for two process only. The key points to note are:

  1. Software based solution
  2. Restricted to two processes
  3. Alternate execution between their critical sections and remainder sections
  4. Two processes – Pi and Pj (where j = 1 –i )
  5. Both share
    • int turn;
    • boolean flag[2];
  6. turn indicates whose turn it is to enter critical section
  7. Finally, flag array indicates if a process is ready to enter critical section

Peterson’s Solution Algorithm

do {
  flag[i] = TRUE;
  turn = j;
  while (flag[j] && turn ==j);   //keeptesting
  critical section
  flag[i] = FALSE;
  remainder section
 }while(TRUE);

PPT on Critical Section Problem

Video on Critical Section Problem

Critical section Problem

Previous                                 Next
Threads in OS                     Semaphores

Leave a Reply

Your email address will not be published. Required fields are marked *