Does Peterson's 2-process mutual exclusion algorithm account for dying processes?

Question

I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the critical section.

In the picture, if process 1 is stopped, the rest of the processes behind process 1 will execute up to where of process 1 is but then loop.

What happens if the process that reaches the critical section first dies before leaving it?

Answer 1

This depends on how locks are implemented. If you do it as in the Wikipedia article, i.e. guarding the critical section with one boolean per process¹, you are certainly in trouble. If one process dies, it never resets its flag so the other process loops forever.

In practice, you can safeguard your code against many ways of dying. For example, take this Java-style implementation:

flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

This will make sure the flag is reset whatever happens in the critical section, as long as the system is handling the error. In Java, that is true even for stack and heap overflows. So unless the process literally vanishes (kill², processor failure, network disconnect, ...) you are safe. Note that most non-critical software fails in these cases -- how can it handle an error it it's not running? -- so that has to be accepted in many cases. You can handle inconsistencies upon restart if necessary.

If you use proper, language-level locks, the runtime system may handle vanishing lock owners, i.e. release locks with dead owners. You can simulate this yourself by giving each process a dead man's switch the others can read, or check directly whether the lock owning process is still alive (if the system supports it).

---

1. That does not scale well, anyway.
2. In Java, I think finalize should execute even on kill, but this is not guarenteed by the spec. kill -9 is probably a death sentence for any solution that requires the dying process to do something.

Answer 2

Look at the assumptions, specifically that no process stays in the critical section indefinitely (that certainly includes just going away). I don't think there is a way to solve that general problem with any synchronization mechanism.

This solution is also only for two processes, there are solutions for $n$ processes around.