• Table of Contents

Dining Philosophers Problem

Concurrency mechanisms are essential in modern operating systems, allowing multiple processes to execute concurrently without interfering with each other. To understand the different approaches used in various OSs, it's helpful to start with a classic problem in concurrent computing:

Figure 9.1 Dining arrangement for philosophers.

The Dining Philosophers problem illustrates the challenges in concurrent programming, by illustrating the basic problems in deadlock and starvation.

Solution Using Semaphores

Using semaphores:

• Each philosopher picks up the fork on the left and then the fork on the right.
• After eating, the forks are replaced on the table.

However, this approach can lead to deadlock if all philosophers are hungry at the same time, as they may all reach for the same fork, resulting in starvation.

Figure 9.2 A first solution to the dining philosophers problem.

To avoid deadlock and starvation, one approach is to use semaphores to limit the number of seated philosophers to four.

• This ensures that there's always at least one philosopher with access to two forks.
• If we limit the number of seated philosophers to four using semaphores, we prevent the possibility of deadlock and starvation.

However, this approach may limit the system's efficiency since only four philosophers can eat at a time. If the system is designed for a larger number of philosophers, this approach may not be optimal.

Solution Using a Monitor

The dining philosophers problem can also be solved using a monitor. This solution uses a vector of condition variables and a Boolean vector to track the availability of each fork.

Figure 9.3 A solution using a monitor.

Unlike the semaphore solution, only one process at a time may be in the monitor, preventing deadlock.