This chapter presents a sequence of attempts to solve the critical section problem for two processes, culminating in Dekker’s algorithm. The synchronization mechanisms will be built without the use of atomic statements other than atomic load and store. Following this sequence of algorithms, we will briefly present solutions to the critical section problem that use more complex atomic statements. In the next chapter, we will present algorithms for solving the critical section problem for N processes.

Algorithms like Dekker’s algorithm are rarely used in practice, primarily because real systems support higher synchronization primitives like those to be discussed in subsequent chapters (though see the discussion of “fast” algorithms in Section 5.4). Nevertheless, this chapter is the heart of the book, because each incorrect algorithm demonstrates some pathological behavior that is typical of concurrent algorithms. Studying these behaviors within the framework of these elementary algorithms will prepare you to identify and correct them in real systems.

The proofs of the correctness of the algorithms will be based upon the explicit construction of state diagrams in which all scenarios are represented. Some of the proofs are left to the next chapter, because they require more complex tools, in particular the use of temporal logic to specify and verify correctness properties.

We start with a specification of the structure of the critical section problem and the assumptions under which it must be solved:

The following diagram will help visualize the critical section problem:

The stick figures represent processes and the box is a critical region in which at most one process at a time may be executing the statements that form its critical section. The solution to the problem is given by the protocols for opening and closing the door to the critical region in such a manner that the correctness properties are satisfied.

The critical section problem is intended to model a system that performs complex computation, but occasionally needs to access data or hardware that is shared by several processes. It is unreasonable to expect that individual processes will never terminate, or that nothing bad will ever occur in the programs of the system. For example, a check-in kiosk at an airport waits for a passenger to swipe his credit card or touch the screen. When that occurs, the program in the kiosk will access a central database of passengers, and it is important that only one of these programs update the database at a time. The critical section is intended to model this operation only, while the non-critical section models all the computation of the program except for the actual update of the database.

It would not make sense to require that the program actually participate in the update of the database by programs in other kiosks, so we allow it to wait indefinitely for input, and we take into account that the program could malfunction. In other words, we do not require that the non-critical section progress. On the other hand, we do require that the critical section progress so that it eventually terminates. The reason is that the process executing a critical section typically holds a “lock” or “permission resource,” and the lock or resource must eventually be released so that other processes can enter their critical sections. The requirement for progress is reasonable, because critical sections are usually very short and their progress can be formally verified.

Obviously, deadlock (“my computer froze up”) must be avoided, because systems are intended to provide a service. Even if there is local progress within the protocols as the processes set and check the protocol variables, if no process ever succeeds in making the transition from the preprotocol to the critical section, the program is deadlocked.

Freedom from starvation is a strong requirement in that it must be shown that no possible execution sequence of the program, no matter how improbable, can cause starvation of any process. This requirement can be weakened; we will see one example in the algorithm of Section 5.4.

A good solution to the critical section problem will also be efficient, in the sense that the pre- and postprotocols will use as little time and memory as possible. In particular, if only a single process wishes to enter its critical section it will succeed in doing so almost immediately.

Here is a first attempt at solving the critical section problem for two processes:

    loop forever
p1:   non-critical section
p2:   await turn = 1
p3:   critical section
p4:   turn ← 2

    loop forever
q1:   non-critical section
q2:   await turn = 2
q3:   critical section
q4:   turn ← 1

The statement await turn=1 is an implementation-independent notation for a statement that waits until the condition turn=1 becomes true. This can be implemented (albeit inefficiently) by a busy-wait loop that does nothing until the condition is true.

The global variable turn can take the two values 1 and 2, and is initially set to the arbitrary value 1. The intended meaning of the variable is that it indicates whose “turn” it is to enter the critical section. A process wishing to enter the critical section will execute a preprotocol consisting of a statement that waits until the value of turn indicates that its turn has arrived. Upon exiting the critical section, the process sets the value of turn to the number of the other process.

We want to prove that this algorithm satisfies the three properties required of a solution to the critical section problem. To that end we first explain the construction of state diagrams for concurrent programs, a concept that was introduced in Section 2.2.

We are now in a position to try to prove the correctness of the first attempt. As noted above, the proof that mutual exclusion holds is immediate from an examination of the state diagram.

Next we have to prove that the algorithm is free from deadlock. Recall that this means that if some processes are trying to enter their critical section then one of them must eventually succeed. In the abbreviated algorithm, a process is trying to enter its critical section if it is trying to execute its await statement. We have to check this for the four states; since the two left states are symmetrical with the two right states, it suffices to check one of the pairs.

Consider the upper left state (await turn=1, await turn=2, turn = 2). Both processes are trying to execute their critical sections; if process q tries to execute await turn=2, it will succeed and enter its critical section.

Consider now the lower left state (await turn=1, turn ← 1, turn = 2). Process p may try to execute await turn=1, but since turn = 2, it does not change the state. By the assumption of progress on the critical section and the assignment statement, process q will eventually execute turn ← 1, leading to the upper right state. Now, process p can enter its critical section. Therefore, the property of freedom from deadlock is satisfied.

Finally, we have to check that the algorithm is free from starvation, meaning that if any process is about to execute its preprotocol (thereby indicating its intention to enter its critical section), then eventually it will succeed in entering its critical section. The problem will be easier to understand if we consider the state diagram for the unabbreviated algorithm; the appropriate fragment of the diagram is shown in Figure 3.3, where NCS denotes the non-critical section. Consider the state at the lower left. Process p is trying to enter its critical section by executing p2: await turn=1, but since turn = 2, the process will loop indefinitely in its await statement until process q executes q4: turn←1. But process q is at q1: NCS and there is no assumption of progress for non-critical sections. Therefore, starvation has occurred: process p is continually checking the value of turn trying to enter its critical section, but process q need never leave its non-critical section, which is necessary if p is to enter its critical section.

Figure 3.3. Fragment of the state diagram for the first attempt

Informally, turn serves as a permission resource to enter the critical section, with its value indicating which process holds the resource. There is always some process holding the permission resource, so some process can always enter the critical section, ensuring that there is no deadlock. However, if the process holding the permission resource remains indefinitely in its non-critical section—as allowed by the assumptions of the critical section problem—the other process will never receive the resource and will never enter its critical section. In our next attempt, we will ensure that a process in its non-critical section cannot prevent another one from entering its critical section.

The first attempt was incorrect because both processes set and tested a single global variable. If one process dies, the other is blocked. Let us try to solve the critical section problem by providing each process with its own variable (Algorithm 3.6). The intended interpretation of the variables is that wanti is true from the step where process i wants to enter its critical section until it leaves the critical section. await statements ensure that a process does not enter its critical section while the other process has its flag set. This solution does not suffer from the problem of the previous one: if a process halts in its non-critical section, the value of its variable want will remain false and the other process will always succeed in immediately entering its critical section.

    loop forever
p1:    non-critical section
p2:    await wantq = false
p3:    wantp ← true
p4:    critical section
p5:    wantp ← false

    loop forever
q1:    non-critical section
q2:    await wantp = false
q3:    wantq ← true
q4:    critical section
q5:    wantq ← false

Let us construct a state diagram for the abbreviated algorithm:

    loop forever
p1:    await wantq = false
p2:    wantp ← true
p3:    wantp ← false

    loop forever
q1:    await wantp = false
q2:    wantq ← true
q3:    wantq ← false

Unfortunately, when we start to incrementally construct the state diagram (Figure 3.4), we quickly find the state (p3: wantp←false, q3: wantq←false,true, true), showing that the mutual exclusion property is not satisfied. (await !want is used instead of await want=false because of space constraints in the node.)

Figure 3.4. Fragment of the state diagram for the second attempt

Paths in the state diagram correspond to scenarios; this portion of the scenario can also be displayed in tabular form:

To prove that mutual exclusion holds, we must check that no forbidden state appears in any scenario. So if mutual exclusion does in fact hold, we need to construct the full state diagram for the algorithm, because every path in the diagram is a scenario; then we must examine every state to make sure that it is not a forbidden state. When constructing the diagram incrementally, we check each state as it is created, so that we can stop the construction if a forbidden state is encountered, as it was in this case. It follows that if the incremental construction is completed (that is, there are no more reachable states), then we know that no forbidden states occur.

    loop forever
p1:    non-critical section
p2:    wantp ← true
p3:    await wantq = false
p4:    critical section
p5:    wantp ← false

    loop forever
q1:    non-critical section
q2:    wantq ← true
q3:    await wantp = false
q4:    critical section
q5:    wantq ← false

In the second attempt, we introduced the variables want that are intended to indicate when a process is in its critical section. However, once a process has successfully completed its await statement, it cannot be prevented from entering its critical section. The state reached after the await but before the assignment to want is effectively part of the critical section, but the value of want does not indicate this fact. The third attempt (Algorithm 3.8) recognizes that the await statement should be considered part of the critical section by moving the assignment to want to before the await. We leave it as an exercise to construct the state diagram for this algorithm, and to show that no state in the diagram violates mutual exclusion. In Section 4.2, we will use logic to prove deductively that the algorithm satisfies the mutual exclusion property.

Unfortunately, the algorithm can deadlock as shown by the following scenario:

This can also be seen in the following fragment of the state diagram:

In the rightmost state, both process are trying to enter the critical section, but neither will ever do so, which is our definition of deadlock.

The term deadlock is usually associated with a “frozen” computation where nothing whatsoever is being computed; the situation here—a scenario where several processes are actively executing statements, but nothing useful gets done—is also called livelock.

In the third attempt, when a process sets the variable want to true, not only does it indicate its intention to enter its critical section, but also insists on its right to do so. Deadlock occurs when both processes simultaneously insist on entering their critical sections. The fourth attempt to solve the critical section problem tries to remedy this problem by requiring a process to give up its intention to enter its critical section if it discovers that it is contending with the other process (Algorithm 3.9). The assignment p4: wantp←false followed immediately by an assignment to the same variable p5: wantp←true would not be meaningful in a sequential algorithm, but it can be useful in a concurrent algorithm. Since we allow arbitrary interleaving of statements from the two processes, the second process may execute an arbitrary number of statements between the two assignments to wantp. When process p relinquishes the attempt to enter the critical section by resetting wantp to false, process q may now execute the await statement and succeed in entering its critical section.

   loop forever
p1:   non-critical section
p2:   wantp ← true
p3:   while wantq
p4:     wantp ← false
p5:     wantp ← true
p6:   critical section
p7:   wantp ← false

   loop forever
q1:   non-critical section
q2:   wantq ← true
q3:   while wantp
q4:      wantq ← false
q5:      wantq ← true
q6:   critical section
q7:   wantq ← false

A state diagram or deductive proof will show that the mutual exclusion property is satisfied and that there is no deadlock. However, a scenario for starvation exists as shown by the cycle in Figure 3.5. The interleaving is “perfect” in the sense that the execution of a statement by process q is always followed immediately by the execution of the equivalently-numbered statement in process p. In this scenario, both processes are starved.

Figure 3.5. Cycle in a state diagram for the fourth attempt

At this point, most people object that this is not a “realistic” scenario; we can hardly expect that whatever is causing the interleaving can indefinitely ensure that exactly two statements are executed by process q followed by exactly two statements from p. But our model of concurrency does not take probability into account. Unlikely scenarios have a nasty way of occurring precisely when a bug would have the most dangerous and costly effects. Therefore, we reject this solution, because it does not fully satisfy the correctness requirements.

Dekker’s algorithm for solving the critical section problem is a combination of the first and fourth attempts:

boolean wantp ← false, wantq ← false
integer turn ← 1

    loop forever
p1:    non-critical section
p2:    wantp ← true
p3:    while wantq
p4:      if turn = 2
p5:         wantp ← false
p6:         await turn = 1
p7:         wantp ← true
p8:    critical section
p9:    turn ← 2
p10:   wantp ← false

    loop forever
q1:    non-critical section
q2:    wantq ← true
q3:    while wantp
q4:      if turn = 1
q5:         wantq ← false
q6:         await turn = 2
q7:         wantq ← true
q8:    critical section
q9:    turn ← 1
q10:   wantq ← false

Recall that in the first attempt we explicitly passed the right to enter the critical section between the processes. Unfortunately, this caused the processes to be too closely coupled and prevented correct behavior in the absence of contention. In the fourth attempt, each process had its own variable which prevented problems in the absence of contention, but in the presence of contention both processes insist on entering their critical sections.

Dekker’s algorithm is like the fourth attempted solution, except that the right to insist on entering, rather than the right to enter, is explicitly passed between the processes. The individual variables wantp and wantq ensure mutual exclusion. Suppose now that process p detects contention by finding wantq to be true at statement p3: while wantq. Process p will now consult the global variable turn to see if it is its turn to insist upon entering its critical section (turn ≠ 2, that is,turn = 1). If so, it executes the loop at p3 and p4 until process q resets wantq to false, either by terminating its critical section at q10 or by deferring in q5. If not, process p will reset wantp to false and defer to process q, waiting until that process changes the value of turn after executing its critical section.

Dekker’s algorithm is correct: it satisfies the mutual exclusion property and it is free from deadlock and starvation. The correctness properties by can be proved by constructing and analyzing a state diagram, but instead we will give a deductive proof in Section 4.5.

We have found that it is difficult to solve the critical section problem using just atomic load and store statements. The difficulty disappears if an atomic statement can both load and store. The solutions given here are shown for two processes, but they are correct for any number of processes.

The test-and-set statement is an atomic statement defined as the execution of the following two statements with no possible interleaving between them:

test −and−set(common, local) is
   local ← common
   common ← 1

    integer local1
    loop forever
p1:    non-critical section
       repeat
p2:       test-and-set(
             common, local1)
p3:    until local1 = 0
p4:    critical section
p5:    common ← 0

    integer local2
    loop forever
q1:    non-critical section
       repeat
q2:       test-and-set(
             common, local2)
q3:    until local2 = 0
q4:    critical section
q5:    common ← 0

   integer local1 ← 0
   loop forever
p1:   non-critical section
      repeat
p2:      exchange(common, local1)
p3:   until local1 = 1
p4:   critical section
p5:   exchange(common, local1)

   integer local2 ← 0
   loop forever
q1:   non-critical section
      repeat
q2:      exchange(common, local2)
q3:   until local2 = 1
q4:   critical section
q5:   exchange(common, local2)

Algorithm 3.11 is the simple solution to the critical section problem using test-and-set. We leave it as an exercise to prove that this solution satisfies the mutual exclusion property.

Note: A commonly used notation for specifying atomicity is to put angled brackets around the group of statements: <local ← common; common ← 1>. In Promela, the keyword atomic is used.

The exchange statement is an atomic statement defined as the atomic swap of the values of two variables:

exchange(a, b) is
   integer temp
   temp ← a
   a ← b
   b ← temp

The solution to the critical section problem with exchange is also very simple (Algorithm 3.12). Here too, the proof of correctness is left as an exercise.

We conclude with two other atomic statements that have been implemented in computers; in the exercises you are asked to solve the critical section problem using these statements.

The fetch-and-add statement is defined as the atomic execution of the following statements:

fetch −and−add(common, local, x) is
    local ← common
    common ← common + x

The compare-and-swap statement is defined as the atomic execution of the following statements:

compare−and−swap(common, old, new) is
  integer temp
  temp ← common
  if common = old
     common ← new
  return temp

These solutions use busy-wait loops, but this is not a disadvantage in a multiprocessor, especially if the contention is low.

boolean wantp ← false, wantq ← false
integer last ← 1

   loop forever
p1:   non-critical section
p2:   wantp ← true
p3:   last ← 1
p4:   await wantq = false or
           last = 2
p5:   critical section
p6:   wantp ← false

   loop forever
q1:   non-critical section
q2:   wantq ← true
q3:   last ← 2
q4:   await wantp = false or
           last = 1
q5:   critical section
q6:   wantq ← false

   loop forever
p1:   non-critical section
p2:   if wantq = −1
         wantp ← −1
      else wantp ← 1
p3:   await wantq ≠ wantp
p4:   critical section
p5:   wantp ← 0

   loop forever
q1:   non-critical section
q2:   if wantp = −1
         wantq ← 1
      else wantq ← −1
q3:   await wantp ≠ − wantq
q4:   critical section
q5:   wantq ← 0

boolean wantp ← false, wantq ← false
integer turn ← 1

   loop forever
p1:   non-critical section
p2:   wantp ← true
p3:   if wantq
p4:      if turn = 2
p5:         wantp ← false
p6:         await turn = 1
p7:         wantp ← true
p8:      await wantq = false
p9:   critical section
p10:  wantp ← false
p11:  turn ← 2

   loop forever
q1:   non-critical section
q2:   wantq ← true
q3:   if wantp
q4:      if turn = 1
q5:         wantq ← false
q6:         await turn = 2
q7:         wantq ← true
q8:      await wantp = false
q9:   critical section
q10:  wantq ← false
q11:  turn ← 1