Critical-Section Problem in Operating System

Critical-Section Problem in Operating System:

A section of code or collection of operations in which only one process may be executing at a given time, is called critical section. Consider a system containing n processes {P0, P1, 2, ..., Pn }. Each process has a segment of code called a critical section in which the process may be changing common variables, updating a table, writing into files etc. When such a system works, only one process may be allowed to execute within a critical section. The execution of critical sections by the processes is mutually exclusive in time.

The critical-section problem is to design a protocol that the processes can cooperate. Each process must request permission to enter its critical section. The section of code implementing this request is called entry section. The critical section may be followed by a section of code known as exit section. The remaining code is known as remainder section.

Example:

Here is a general structure of a typical process:

while (1)

{
entry section;
critical section;
exit section;
remainder section;
}

1. Criterion to Solve Critical-Sections Problem:

Any solution to critical section problem must satisfy the following three requirements:

1. Mutual Exclusion:

If a process PI is executing in its critical section, .then-no other processes can be executing in their critical sections.

2. Progress:

If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing their remainder section can participate in the decision on which will enter its critical section next. 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.

Note: No assumptions can be made about the speeds, No. of CPUs and No. of processes.

2. Two-Process Solution for Critical Section:

First of all, we will consider the algorithms that can be applied only on two processes at a time. The processes are Pi and Pj (where i = 0 and j = 1).

1. Algorithm 1:

Suppose a shared variable s is initialized to 0 or 1. If s is 0, then P0 can execute its critical section and if s is 1, then P1 can execute. This algorithm ensures that there is only one process in its critical section at a time. Here is a representation of this algorithm for Pi.
while (1)

{

while (s ! = i);

critical section;

s = j;

remainder section;

}

Now, let's see the representation of the same algorithm for Pj.

while (1)

{

while (s ! = j);

critical section;

s = i;

remainder section;

How it Works?

Suppose, s is initialized to 1 so P0 cannot enter its critical section as only P1 is allowed to enter its critical section at start. P0 can enter its critical section only if the value of s is 0. s is set to 0 by P1 when it executes its exit section. In this way, mutual exclusion is guaranteed.

Problem in Algorithm 1

In this algorithm, the progress requirement is not satisfied. For example, if s is set to 1 and P0 is ready to enter its critical section, it cannot enter even if P1 is in its remainder section. P0 has to wait until P1 enters its critical section, executes it and then sets the value of s to 0.

2. Algorithm 2

Algorithm 1 only remembers which process is allowed to enter it's critical section. It does not know any other information about the processes. We can use a Boolean array flag[2] that is initialized to false. If flag[i] is true, it indicates that Pi is ready to enter its critical section.

The structure of Pi in this algorithm is as follows:

while (1)
{

flag[i] = true;

while (flag[j]);

critical section;

flag[i] = false;

remainder section;

}

The structure of Pj for this algorithm is as follows:

while (1)

{

flag[j] = true;

while (flag[i]);

critical section;

flag[j] = false;

remainder section;

}

How it Works?

First, Pi sets flag[i] to true that indicates that Pi is ready to enter its critical section. Secondly, it checks whether Pj wants to enter its critical section. If Pj wants, then Pi will wait until Pj exits its critical section and sets flag[j] to false. Now, Pi can enter its critical section. It will set flag[I] to false thus allowing Pj to enter its critical section again, if needed.

Problem in Algorithm 2

This algorithm depends on the timing of the processes. Suppose, P0 sets flag[0] to true and context switch occurs and shifts the control to P1. Now, P1 also sets flag[1] to true. At this point, both processes will wait for the other and none will be able to enter its critical section.

3. Algorithm 3

We can use a third algorithm by combining the previous two algorithms. It provides a solution for critical section problem. In this algorithm, both flag[2] and s are used. The structure of this algorithm for Pi is as follows:

while (1)

}

flag[i] = true;

s = j;

while (flag[j] && s == j);

critical section;

flag[i] = false;

remainder section;

}

The structure of this algorithm for Pj is as follows:

while (1)

}

flag[j] = true;

s = i;

while (flag[i] && s == i);

critical section;

flag[j] = false;

remainder section;

}

How it Works?

Suppose, both flag[0] and flag[1] are set to false. If Pi tries to enter its critical section, it sets flag[i] to true. Then it set s to j to ensure that Pj may enter its critical section, if needed. If both processes try to enter critical sections, both will set their corresponding flag value to true. Then, Pi will set s to j and Pj will set s to i. The value of s will then decide which process can enter its critical section.

In this solution:

Mutual exclusion is guaranteed
Progress requirement is satisfied
Bounded-waiting is met

Proof

Mutual Exclusion: PI can enter its critical section only if either flag[j] is false or s = i. If both processes try to enter critical sections, then the value of s will decide, as discussed earlier, which ensure mutual exclusion.

Progress & Bounded-waiting: Only while loop of Pi can stop it from entering its critical section (while (flag[j] && s == true. If Pj is not ready to enter its critical section, then flag[j] is false Pi can enter its critical section. But if Pj has set flag[j] to true and is executing its while statement, then the value of s will decide which process can enter its critical section. Suppose Pj enters its critical section. When it exists its critical section, it will set flag[j] to false and Pi will be able to enter its critical section. If Pj sets flag[j] to true, it should also set turn s to i. As Pi does not change the value of s in while statement, it will enter its critical section (progress) after a maximum of one entry by Pj (bounded-waiting).

3. Bakery Algorithm Multiple-Process Solution:

This algorithm solves the critical section problem for n processes. The basic idea is that of a bakery; customers take numbers,, and the customer with the lowest number gets service next. Here, of course, "service" means entry to the critical section. The structure of Pi for bakery algorithm is as follows:

while (1)

{

choosing[i] = true;

number[i] = max (number [0],number[1],... ,number[n-l]) + 1; choosing[i] = false;

for(j=0; j

{

while (choosing[j];

while ((number[j] != 0) && (number[j,j] < number[i,i]));

}

critical section;

number[i] = 0;

remainder section;

}

How it Works?

First, choosing[i] is true if Pi is choosing a number. The number that Pi will use to enter the critical section is in number[i]. It is 0 if Pi is not trying to enter its critical section. First three lines indicate that the process is choosing a number, and then tries to assign a unique number to the process Pi; but it doesn't always happen.

In for loop, we select which process goes into the critical section. Pi waits until it has the lowest number of all the processes waiting to enter the critical section. If two processes have the same number, the one with the smaller name - the value of the subscript - goes in. The notation "(a,b) < (c,d)" means true if a < c or if both a = c and b < d. Note that if a process is not trying to enter the critical section, its number is 0. Also, if a process is choosing a number when Pi tries to look at it, Pi waits until it has done so before looking.

After exiting from its critical section, Pi is no longer interested in entering its critical section, so it. sets number[i] to 0.