Peterson’s Solution

PropellerAds

By combining the idea of taking turns with the idea of lock variables and warning variables, in 1965, a Dutch mathematician, T. Dekker, was the first one to devise a software solution to the mutual exclusion problem that does not require strict alternation. In 1981, G.L. Peterson
discovered a much simpler way to achieve mutual exclusion, thus rendering Dekker’s
algorithm obsolete.

Before entering its CS, each process calls CS_entry with its own process number, 0 or 1, as
parameter. This call will cause it to wait, if need be, until it is safe to enter. After it has
finished with the shared variables, the process calls CS_exit to indicate that it is done and to
allow the other process to enter, if it so desires

Let us see how this solution works. Initially, neither process is in its CS. Now process 0 calls
CS_entry. It indicates its interest by setting its array element, and sets turn to 0. Since
process 1 is not interested, CS_entry returns immediately. If process 1 now calls CS_entry, it
will hang there until interested[0] goes to FALSE, an event that only happens when process
0 calls exit.
Now consider the case that both processes call enter_region almost simultaneously. Both
will store their process number in turn. Whicever store is done last is the one that counts; the
first one is lost. Suppose process 1 stores last, so turn is 1. When both processes come to
the while statement, process 0 executes it zero times, and enters its CS. Process 1 loops
and does not enter its CS.

... /* required header files */
#define FALSE 0
#define TRUE 1
#define N 2 /* number of processes */
int turn; /* whose turn is it? */
int interested[N] /* all elements initialized to FALSE */
void CS_entry (int process) /* process: Who is entering (0 or 1)? */
{
 int other; /* number of the other process */
 other = 1 – process; /* the opposite of process */
 interested[process] = TRUE; /* show that you are interested */
 turn = process; /* set flag */
 while (turn == process) &&
 (interested[other] == TRUE ) { }; /* wait */
}
void CS_exit (int process) /* process: Who is leaving (0 or 1) ? */
{
 interested[process] = FALSE; /* indicate departure from CS */
}

This method is correct for mutual exclusion but it wastes the processor time. Furthermore, it
can have unexpected effects. Consider a system with two processes, H with high priority and
L, with low priority. The scheduling rules are such that H is run whenever it is in ready state.
At a certain moment, with L in CS, H becomes ready to run. H now begins busy waiting, but
since L is never scheduled while H is running, L never gets the chance to leave its CS, so H
loops forever. This situation is referred to as priority inversion problem.

Special Hardware Instructions
Followings are special hardware instructions that may be used for the solution of CS
problem. These operations are assumed to be atomically executed (in one machine cycle).

Test-and-set
The instruction test-and-set(int lock) returns true if lock is true, otherwise it first sets the
value of lock to true and returns false. It can be used for the solution of the CS problem as
follows:

int lock=0; /*global */
PO:
{
 while (TRUE) {
 while test-and-set(lock) { } ;
 CS
 lock = FALSE;
 non-CS;
 }
}

P1:
{
 while (TRUE) {
 while test-and-set(lock) { };
 CS
 lock = FALSE;
 non-CS;
 }
}

Swap
The instruction swap (int lock, int key) interchanges the content of its parameters. Again,
lock is used as a global boolean variable, initialized to false.

int lock=FALSE; /*global */
PO:
{ int key
 while (TRUE) {
 key=TRUE
 while (KEY) swap (lock,key);
 CS
 lock = FALSE;
 non-CS;
 }
}

P1:
{ int key
 while (TRUE) {
 key=TRUE
 while (LOCK) swap (lock,key);
 CS
 lock = FALSE;
 non-CS;
 }
}

Try Now – Operating Systems MCQs
Practice Now – Operating System Online Test