Peterson's Solution

Peterson's Solution

By combining the idea of taking turns with the idea of lock variables and warning variables, a Dutch mathematician, T. Dekker, was the first one to plan a software solution to the mutual exclusion problem that does not require strict alternation. For a discussion of Dekker's algorithm, see (Dijkstra, 1965).

In 1981, G.L. Peterson discovered a much simpler way to attain mutual exclusion, thus rendering Dekker's solution out of date. Peterson's  algorithm is shown in Figure 1. This algorithm comprises two procedures written in ANSI C, which means that function prototypes should be supplied for all the functions described and used. However, to save space, we will not show the prototypes in this or later examples.

Petersons solution for achieving mutual exclusion

Before using the shared variables (i.e., before entering its critical region), each process calls enter _region 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 leave_region to show that it is done and to allow the other process to enter, if it so desires.

Let us see how this solution works. At first neither process is in its critical region. Now process 0 calls enter _region. It specifies its interest by setting its array element and sets turn to 0. Since process 1 is not interested, enter _region returns immediately. If process 1 now makes a call to enter _region, it will hang there until interested [0] goes to FALSE, an event that only happens when process 0 calls leave_region to exit the critical region.

Now look at the case that both processes call enter _region almost at the same time. Both will store their process number in turn. Whichever store is done last is the one that counts; the first one is overwritten and lost. Assume that process 1 stores last, so turn is 1. When both processes come to the while statement, process 0 implements it zero times and enters its critical region. Process 1 loops and does not enter its critical region until process 0 exits its critical region.

The TSL Instruction

Now let us consider a proposal that needs a little help from the hardware. Some computers, particularly those designed with various processors in mind, have an instruction like

TSL REGISTER,LOCK

(Test and Set Lock) that works as follows. It reads the contents of the memory word lock into register RX and then stores a nonzero value at the memory address lock. The operations of reading the word and storing into it are guaranteed to be indivisible - no other processor can access the memory word until the instruction is completed. The CPU executing the TSL instruction locks the memory bus to forbid other CPUs from accessing memory until it is done.

It is important to note that locking the memory bus is very different from disabling interrupts. Disabling interrupts then performing a read on a memory word followed by a write does not prevent a second processor on the bus from accessing the word between the read and the write. In fact, disabling interrupts on processor 1 has no effect at all on processor 2. The only way to keep processor 2 out of the memory until processor 1 is finished is to lock the bus, which requires a special hardware facility (basically, a bus line declaring that the bus is locked and not available to processors other than the one that locked it).

To use the TSL instruction, we will use a shared variable, lock, to coordinate access to shared memory. When lock is 0, any process may set it to 1 using the TSL instruction and then read or write the shared memory. When it is done, the process sets lock back to 0 using an ordinary move instruction.

How can this instruction be used to prevent two processes from concurrently entering their critical regions? The solution is given in Figure 2. There a four-instruction subroutine in a fictitious (but typical) assembly language is shown. The first instruction copies the old value of lock to the register and then sets lock to 1. Then the old value is compared with 0. If it is nonzero, the lock was already set, so the program just goes back to the beginning and tests it again. Sooner or later it will become 0 (when the process presently in its critical region is done with its critical region), and the subroutine returns, with the lock set. Clearing the lock is very simple. The program just stores a 0 in lock No special synchronization instructions are required.

Entering and leaving a critical region using the TSL instruction

One solution to the critical region problem is now straightforward. Before entering its critical region, a process calls enter _region, which does busy waiting until the lock is free; then it obtains the lock and returns. After the critical region the process calls leave_region, which stores a 0 in lock. As with all solutions based on critical regions, the processes must call enter _region and leave_region at the correct times for the method to work. If a process cheats, the mutual exclusion will fail.

A substitute instruction to TSL is XCHG, which exchanges the contents of two locations atomically, for instance, a register and a memory word. The code is shown in Figure 3, and, as can be seen, is basically the same as the solution with TSL. All Intel x86 CPUs use XCHG instruction for low-level synchronization.

Entering and leaving a critical region using the XCHG instruction



Tags

shared memory, process calls, shared variables, mutual exclusion