# Software approaches for Mutual Exclusion – Operating System

By | October 9, 2021

## 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:

1.  Preserves mutual exclusion.
2. It satisfies the progress requirement.
3. 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);``````