Concurrency is a fundamental concept in computer science, and one of the most common challenges in concurrent programming is managing access to shared resources such as memory, files, and network connections. The problem of mutual exclusion arises when multiple processes or threads attempt to access a shared resource concurrently, leading to potential conflicts and data corruption. Two classical algorithms for achieving mutual exclusion in concurrent programs are Dekker's algorithm and Peterson's algorithm. In this post, we will explain these algorithms in detail and compare their strengths and weaknesses.

Dekker's Algorithm

Dekker's algorithm is a mutual exclusion algorithm for two concurrent processes, originally proposed by Th. J. Dekker in 1965. The algorithm is based on two shared flags and a turn variable, which indicate which process is allowed to access the shared resource. Here is the basic outline of the algorithm:

The algorithm works as follows. Each process sets its flag to 1, indicating that it wants to enter the critical section. Then, it waits in a busy-wait loop until the other process's flag is 0 or the turn variable indicates that it is the other process's turn. If the other process's flag is 1 and it is not its turn, the process sets its own flag to 0 and waits until the other process sets its flag to 0 or the turn variable changes. When the process enters the critical section, it sets its flag to 0, allowing the other process to enter the critical section if it is ready.

One of the advantages of Dekker's algorithm is that it avoids deadlock and starvation, meaning that both processes can eventually enter the critical section if they are ready. However, the algorithm suffers from a potential race condition when both processes attempt to enter the critical section simultaneously. Also, the algorithm is not scalable to more processes, as it requires shared flags and a turn variables per process increasing the complexity and potential for race conditions.

Peterson's Algorithm

Peterson's algorithm is another mutual exclusion algorithm for two concurrent processes, proposed by G. L. Peterson in 1981. The algorithm is based on two shared flags and a turn variable, similar to Dekker's algorithm. However, Peterson's algorithm uses a simpler condition for waiting, which avoids the race condition of Dekker's algorithm. Here is the basic outline of the algorithm:

in a busy-wait loop until the other process's flag is 0 or the turn variable indicates that it is the other process's turn. If the other process's flag is 1 and it is its turn, the process waits until the other process sets the turn variable to its own ID or sets its flag to 0. When the process enters the critical section, it sets its flag to 0, allowing the other process to enter the critical section if it is ready.

One of the advantages of Peterson's algorithm is that it avoids the race condition of Dekker's algorithm and ensures mutual exclusion, meaning that only one process can enter the critical section at a time. Also, the algorithm is scalable to more than two processes, as it requires only two shared flags and a turn variable for all the processes.

Comparison

Both Dekker's algorithm and Peterson's algorithm are classical algorithms for mutual exclusion in concurrent programs, and they have their strengths and weaknesses. Here is a comparison of the two algorithms:

• Complexity: Dekker's algorithm requires more complex conditions for waiting, which can lead to a potential race condition when both processes attempt to enter the critical section simultaneously. Peterson's algorithm uses a simpler condition for waiting, which avoids the race condition and ensures mutual exclusion.
• Scalability: Dekker's algorithm is not scalable, as it requires two shared flags and a turn variable per process. Peterson's algorithm is scalable to more than two processes, as it requires only two shared flags and a turn variable for all the processes.
• Deadlock and starvation: Dekker's algorithm avoids deadlock and starvation, meaning that both processes can eventually enter the critical section if they are ready. Peterson's algorithm also avoids deadlock and starvation, but it may suffer from starvation if one process is always ready to enter the critical section.

You can checkout a contrived Dekker's algorithm example here: dekker.c

You can also view the corresponding Peterson's algorithm example here: petterson.c

Conclusion

In conclusion, mutual exclusion is a fundamental problem in concurrent programming, and Dekker's algorithm and Peterson's algorithm are classical algorithms for achieving mutual exclusion in two concurrent processes. While both algorithms have their strengths and weaknesses, Peterson's algorithm is generally preferred due to its simplicity, scalability, and avoidance of race conditions. However, more complex algorithms may be required for more complex scenarios, and developers should choose the appropriate algorithm based on the specific requirements of their concurrent program.