Nonmythical Generalization of Dekker's Algorithm and Its Ramifications

摘要

An algorithm to ensure mutual exclusion between processes is introduced. It is a straightforward generalization of Dekker's algorithm to an arbitrary number of processes. The algorithm is very simple and a process can be forced to wait at most once for every other process before being able to enter its critical section. Applying the same generalization technique to neighboring processes only, a solution to the Dining Philosophers Problem on a ring of processes of arbitrary number is easily derived. It is shown that the length of a contiguous string of blocked philosophers can be no more than four.