Solution of a Problem in Concurrent Programming Control

Solution of a Problem in Concurrent Programming Control

September, 1965 | E. W. Dijkstra
This paper presents a solution to a problem in concurrent programming control, which has been an open question since at least 1962. The problem involves N computers, each running a cyclic process with a "critical section" that must be mutually exclusive. The solution ensures that at any moment, only one computer is in its critical section, using a common store for communication. The solution must be symmetric among all computers, not assume any relative speeds, and avoid potential blocking if a computer is stopped outside its critical section. It also must prevent infinite "after you" blocking. The solution uses a common store containing a Boolean array b, c[1:N], and an integer k. Each computer sets its own b[i] and c[i], and checks others' values. The program for the ith computer involves a loop that checks if it can enter its critical section. If not, it waits until another computer has finished its critical section. The proof shows that the solution is safe, ensuring no two computers are in their critical sections at the same time. It also demonstrates that infinite "after you" blocking is impossible. The key idea is that the integer k points to the computer that has completed its critical section, allowing others to enter. Once k is set, it remains until the computer it points to finishes its critical section. This ensures that eventually, one computer will enter its critical section, preventing infinite blocking. The solution is efficient and ensures mutual exclusion without assuming any priority or speed differences between computers.This paper presents a solution to a problem in concurrent programming control, which has been an open question since at least 1962. The problem involves N computers, each running a cyclic process with a "critical section" that must be mutually exclusive. The solution ensures that at any moment, only one computer is in its critical section, using a common store for communication. The solution must be symmetric among all computers, not assume any relative speeds, and avoid potential blocking if a computer is stopped outside its critical section. It also must prevent infinite "after you" blocking. The solution uses a common store containing a Boolean array b, c[1:N], and an integer k. Each computer sets its own b[i] and c[i], and checks others' values. The program for the ith computer involves a loop that checks if it can enter its critical section. If not, it waits until another computer has finished its critical section. The proof shows that the solution is safe, ensuring no two computers are in their critical sections at the same time. It also demonstrates that infinite "after you" blocking is impossible. The key idea is that the integer k points to the computer that has completed its critical section, allowing others to enter. Once k is set, it remains until the computer it points to finishes its critical section. This ensures that eventually, one computer will enter its critical section, preventing infinite blocking. The solution is efficient and ensures mutual exclusion without assuming any priority or speed differences between computers.
Reach us at info@study.space
[slides and audio] Solution of a problem in concurrent programming control