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;
}
}
