6
$\begingroup$

There are numerous possibilities to implement a software mutex using only shared memory (e.g. Dekker's algorithm).

Recently I've read the following from a paper "Wait-free Synchronization" by M. Herlihy:

there exists no two-process consensus protocol using multireader/multiwriter atomic registers.

And then the theorem: "Read/Write registers have consensus number 1".

I guess I am missing something in my understanding of the definitions. Shared memory is an array of atomic registers, right? And Wikipedia says Dekker's algorithm is deadlock and starvation free. So how is that possible with consensus number 1?

$\endgroup$
4
$\begingroup$

Herlihy's result, indeed the whole paper, is about wait-free synchronization. Corollary 1 states that there is no wait-free two-process consensus protocols using atomic registers. Wait-free is defined informally at the beginning of the introduction, and defined formally in the automata model in §2.3.

Dekker's algorithm is not wait-free. The busy-wait loop to enter the critical section is a wait in the sense of Herlihy. It's possible to have P0 set its wants_to_enter flag, then P1 sets its own, then P0 sees that P1 wants to enter and one of the processes busy-waits (depending on the turn value).

Think of wait-free as “must work even with a hostile scheduler”, i.e. with a scheduler that always switches between processes at the most inconvenient time. Dekker's algorithm requires a scheduler that's at least weakly fair, i.e. guaranteeing that if a process is schedulable then it's eventually scheduled (as opposed to being locked in an order of execution that causes a livelock, such as never exiting the busy-wait loop). Wait-free algorithms complete in finite time with any scheduler that doesn't completely lock up the system if there's work to do (no fairness requirement).

Busy-wait loops require the scheduler to be preemptive (otherwise the loop runs forever). In practice a busy-wait loop would be written with a yield call, and even non-preemptive schedulers try to avoid immediately re-scheduling a process that just yielded. But even with a preemptive scheduler, busy-wait is generally bad: if nothing else it uses up CPU time and electricity. A case where Dekker's algorithm doesn't work at all is if the two processed have different priorities and the scheduler never schedules the process that would enter the loop because the busy-waiting process has a higher priority.

A naive solution to avoid waiting is to put in a time delay. It isn't a good solution because in practice it means an additional useless delay when there is contention on the mutex, and in theory the delay isn't enough since the scheduler could take that long to make its decision and so end up scheduling the busy-wait loop only anyway. A good solution avoid busy-wait altogether is to add a primitive that lets a process block until some shared variable is modified; with such a primitive, I think it's easy to achieve an infinite consensus number.

It is instructive to contrast Dekker's algorithm with a wait-free consensus solution, such as the one Herlihy gives for two processes (fig. 7).

prefer[P] := input
if RMW(r,f) = v
  then return prefer[P]
  else return prefer[Q]
end if

RMW is a primitive operation with a consensus number of at least 2, for example test-and-set. There's no busy-wait in the consensus protocol itself: both processes run pretty much instantly, without ever waiting for the other one. In a real scenario, the processes that doesn't acquire the mutex may well wait for it; but the process that does acquire the lock isn't stopped, and in practical terms that means at least an expected performance gain both when there is contention and when there isn't.

$\endgroup$
  • $\begingroup$ Dekker's algorithm is starvation free, so livelock shouldn't be possible. I think the turn variable fixes your senario. $\endgroup$ – Ariel Sep 26 '16 at 12:56
  • $\begingroup$ Temporarily removed answer mark because of @Ariel question :) $\endgroup$ – artemonster Sep 26 '16 at 14:03
  • 1
    $\begingroup$ @Ariel Thanks. Indeed, the turn variable prevents the loop-around-the-decision-process scenario, but the busy-wait is there anyway, and it's a wait. $\endgroup$ – Gilles 'SO- stop being evil' Sep 26 '16 at 15:30
  • 1
    $\begingroup$ @artemonster I've fixed that and expanded my answer, in particular to contrast with a wait-free protocol. $\endgroup$ – Gilles 'SO- stop being evil' Sep 26 '16 at 15:30
  • $\begingroup$ I'd argue that the relevant quote from the paper is "The wait-free condition provides fault-tolerance: no process can be prevented from completing an operation by undetected halting failures of other processes". Imagine that one of the two processes in Dekker's algorithm dies in the CS. It's game over for the other one however often it is scheduled to run. This is of course the same as a mean scheduler who never gives the process a go once it entered its CS. $\endgroup$ – Kai Dec 6 '16 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.