Critical Section Problem

The part of the process, where the code for accessing the shared resources is written, that part or section is the critical section (CS) of that process. Now the critical section problem is to implement such a solution, which can be used by the processes to cooperate when they share common resources.

To execute its critical section, a process must take care of the three properties mutual exclusion, progress and bounded wait. Possessing these three properties a process can execute its critical section successfully. In this section, we will discuss the definition of the critical section, properties important for implementing critical section, a solution to implement critical section.

Content: Critical Section (CS) Problem

1. Definition
2. Properties to Implement Critical Section
3. Solution to Implement Critical Section
4. Key Takeaways

Definition

We know that there are multiple processes in the system and these processes access shared resources. When these processes access the shared resources simultaneously then the results obtained are inconsistent.

To avoid such inconsistency in the result the processes must cooperate while accessing the shared resources. Therefore, the code to access shared resources is written under the critical section of the process. Let us understand the inconsistency in the result while accessing the shared resource simultaneously with the help of an example.

Look at the figure above, suppose there are two processes P0 and P1. Both share a common variable A=0. While accessing A both the processes increments the value of A by 1.

First case

The order of execution of the processes is P0, P1 respectively.

Process P0 reads the value of A=0, increments it by 1 (A=1) and writes the incremented value in A.

Now, process P1 reads the value of A =1, increments its value by 1 (A=2) and writes the incremented value in A.

So, after both the processes P0 & P1 finishes accessing the variable A. The value of A is 2.

Second case

Consider that process P0 has read the variable A=0. Suddenly context switch happens and P1 takes the charge, and start executing. P1 would increment the value of A (A=1). After execution P1 gives the charge again to P0.

Now the value of A for P0 is 0 & when it starts executing it would increment the value of A, from 0 to 1.

So here, when both the processes P0 & P1 end up accessing the variable A, the value of A =1 which is different from the value of A=2 in the first case.

Now, this type of condition where the sequence of execution of the processes affects the result is called race condition.

To avoid a race condition, the process should access the common resources under its critical section. So in simple words, the critical section is that section of the process where the code for accessing shared resources is written.

The critical section code must be design such that the process must initially request to enter its critical section. If permitted, then execute the critical section and there must be an exit section. The remaining code is under the remainder section. Below you can see the general structure to implement critical section.

Properties to Implement Critical Section

To avoid any inconsistency in the result the three properties that should be considered mandatorily to implement critical section are as follow:

1. Mutual Exclusion

Only one process can execute its critical section at a time. The other process must wait until the previous process has completed its critical section execution completely

2. Progress

If a process doesn’t want to enter in its critical section. It should not be permitted to block another process from entering it, in its critical section.

3. Bounded Waiting

There is a bounded time up to which the process has to wait to enter its critical section after making the request. The system can’t keep waiting, a process for the indefinite time to enter its critical section. Anyhow the execution of the critical section takes a short duration. So, every process requesting to enter its critical section get the chance within the finite amount of time.

Solution to Implement Critical Section

There can be many solutions to implement critical section but, as we studied above the solution must satisfy three criteria i.e. Mutual exclusion (only one process can enter critical section at a time), Progress (a process not wishing to enter its critical section should not block a process whishing to enter its critical section) and bounded wait (a process should not have to wait for indefinite time to enter its critical region).

Let us start to search for the solution to implement a critical section successfully. Though we have to find the solution for n number of processes but, let start with just two processes to make the understanding better and easy.

Case 1:

In the figure below you can see that we have two processes P0 and P1. Both have code to enter their critical section.

Suppose the value of turn is 0. Now, the process P0 tries to enter its critical section, it executes while(1) and further checks for the condition while (turn!=0)which turn out false. So, it exit while loop and enter the critical section and on exit make turn=1 and execute the remainder section.

Similarly, P1 checks while (1) and enter the while loop and checks for while (turn! = 1) which turn out to be false. So P1 exit loop and enter critical section then make turn 0 again and execute its remainder section.

Here, observe one thing that every time P0 need the value of turn=0 to enter its CS and every time P1 need value of turn=1 to enter its CS. So here, even if P0 after executing its CS immediately want to reenter its CS again. It has to wait for P1 to make the value of turn = 0. Here, we have achieved mutual exclusion but, progress is not achieved as if P1 does not want to enter CS it will block P0 to enter its CS.

Case 2:

Look at the figure below, we have now introduced a flag array, flag [0]=F, flag [1]=F.

Now, let us begin again, P0 execute while(1) which is true so, it enters the loop make flag [0]=T which confirm that P0 want to enter CS. Now P0 checks while(flag[1])to see whether P1 is in its CS, which is false so it exits the loop and enter its CS and on exit make flag[0]=F.

Now, P1 checks while (1) which is true so, it enters the loop and makes flag[1]=T which confirms that P1 wants to enter CS. Further check while (flag[0]) to check whether P0 is in its CS which is false as on exit P0 had made Flag[0]=F. So, it exit while(flag[0]) loop and enter its CS and on exit make flag[1]=F.

If after executing it’s CS, P1 again wants to reenter its CS, it can, as the condition for entry in CS flag[0]= F. Same is the case with P0. Here we have achieved mutual exclusion +progress.

Consider the case when P0 has just confirmed that it wants to enter CS by making flag[0]=T and just at that moment the context switch happens and P1 get charge and start executing. It makes flag[1]=T and further check for while(flag[0]) which is true now, it will get blocked in the loop and also blocks P0.

Case 3:

Here, we have implemented both flag array and the turn variable, flag[0]=F, flag[1]=F and turn=0.

Starting with P0, it enters while (1) and make flag[0]=T and turn =1 to confirm its entry in CS. Further checks for while(turn==1 && flag[1]==T) which turn out false as flag[1]=F. So, P0 enter CS and on exit make flag[0]=F.

Now, P1 enter while(1) and make flag[1]=T and turn =0 to confirm its entry in CS. Further checks for while(turn==0 && flag[0]==T) which turn out false as flag[0]=F. So P1 enter CS and on exit make flag[1]=F. Here even, if context switch happens the processes would not get into a deadlock as in the previous case.  This solution is called Peterson’s solution.

This is all about the critical section. The successful implementation of the critical section avoids the race condition.