Software approaches for Mutual Exclusion

Software approaches for Mutual Exclusion: Several Software solutions to critical section problem were developed. Some of them can handle two process and some can handle multiple processes.

Algorithm 1

It is the algorithm that provides two process solutions.
The two processes are named as Px and Py where y = x-1. (for example P0 and P1)
In this algorithm the processes share a common integer variable turn initialized (or 1).
If turn == x then process Px is allowed to execute in its critical second.
The structure of process Px given below:

This algorithm ensures that only one process at a time can be in its critical section.
This algorithm confirms to mutual execution requirement but does not assure progress requirement.

do{ while(turn!=x);
//critical section
turn = y;
//remainder section
} while(1);

A process may terminate on its turn ; as a result bounded waiting requirement is breached.

Algorithm 2

Like algorithm 1, this algorithm also provides two process solution.
The main problem with algorithm 1 is that it does not retain sufficient information about the state of each process.
To solve this problem, the variable turn is replaced by an array :

Boolean flag [2];

The elements of the array initialized to false.
If flag [x] is true, this value indicates that Px is ready to enter critical section.
The structure of process Px shown in figure.

In this algorithm, process Px first sets flag [x] to be true, signaling that it is ready to enter critical section.
Then, process Px checks to verify that Py is not also ready to enter its critical section.
If Py were ready, then Px would wait until Py had indicated that it no longer needed to be in the critical section (that is, until flag [y]) was false). At this point Px would enter is critical section.

do {
flag[x] = true;  //Indicate Px is ready to enter critical section
while(flag[y]); //Px checks the status of Py about entering critical section Px enters only when indicated by Py
//Critical Section
flag[x] = false; //flag[x] is set to false on exit of Px form critical section
//Remainder Section
} While(1);

On exiting the critical section, Px would set flag [x] to be false, allowing the other process (if it is waiting) to enter its critical section.

In this algorithm, mutual exclusion requirement satisfied, but the progress requirement is not.

Algorithm 3-Peterson’s algorithm in Software approaches for Mutual Exclusion

This algorithm combines both algorithm 1 and algorithm 2 and fulfills all he requirements of critical section solution for two processes.
In this algorithm, both the process share two variables : turn and flag [2]

Boolean flag [2];

int turn;

Initially flag [0] = flag [1] = false, and the value of turn is immaterial (but is either 0 or 1 ).
The structure of process P, shown in figure.
To enter the critical section, process Px first sets flag [x] to be true and then sets a the value y. Thereby asserting that if the other process wishes to enter the critical sect it can do so.

Ii both processes try to enter at the same time, turn will set to both x and y at roughly same time W.

do{
flag[x] = true;
turn = y;  //mean other processes can enter if it was to
while (flag[y] && turn == y);
//Critical Section
flag[x] = false;
//Remainder Section
} while(1);

Only one of these assignments will ; the other will occur. but will overwritten immediately.
The eventual value of turn decides which of the two processes allowed to enter its critical section first.

The advantages of Peterson’s algorithm are:

Preserves mutual exclusion.
It satisfies the progress requirement.
It also meets the bounded-wait requirement.

Bakery Algorithm

Bakery algorithm gives solution to critical section problem of n processes.
It is based on a scheduling algorithm commonly used in bakeries, ice-cream stores. motor-vehicle registers and other locations where order must be made out of chaos.
In this algorithm, a process waiting to enter its critical section chooses a number that is greater than all other numbers currently in use.
Each process has an array of current numbers.
Conflicts resolved using process IDs that are unique.
The two common data structure used in this algorithm are

Shared number : int num [m]

Shared Choosing : Boolean Choosing [m]

The structure of process P, used in bakery algorithm, shown below:

do {
choosing[x] = true;
num[x] = max(num[0], num[1],....,num[m-1])+1;
choosing[x] = false;
for(y=0; y<x; y++)
{
  while(Choosing[y]);
  while((num[y]!=0) && (num[y,y]<num[x,x]));
}
//Critical Section
num[x] = 0;
//Remainder Section
} while(1);