Dining Philosophers Problem

Problem description

The Dining Philosophers problem is a classical example in computer science to illustrate synchronisation issues in concurrent processes. It was originally formulated in 1965 by E. W. Dijkstra as a student exam exercise, and was later reworked in its current form by Tony Hoare:

\(N\) silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Dining Philosophers, with \(N=4\).

The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.

Simulation

Let us define each philosopher as a process executing a thinking + eating loop, and acting concurrently on shared resources (the forks). Each process will follow a similar trajectory in which they

Spend some random time thinking until they become hungry.
Take one fork, when available, following a given policy.
After some lag, take the other fork, when available.
Spend some random time eating.
Put both forks down and go back to 1.

The following function sets up a simulation of \(N\) dining philosophers as established above:

library(simmer)
library(simmer.plot)

simulate <- function(fork_seq, time, thinking=function() rexp(1, 1),
                     eating=function() rexp(1, 1), lag=0.1, seed=333)
{
  set.seed(seed)

  env <- simmer("Dining philosophers")

  for (i in seq_along(fork_seq)) {
    philosopher <- names(fork_seq)[[i]]
    forks <- paste0("fork_", fork_seq[[i]])

    dining <- trajectory() %>%
      timeout(thinking) %>%
      seize(forks[[1]]) %>%
      timeout(lag) %>%
      seize(forks[[2]]) %>%
      timeout(eating) %>%
      release(forks[[1]]) %>%
      release(forks[[2]]) %>%
      rollback(7) # back to think

    env %>%
      add_resource(paste0("fork_", i)) %>%
      add_generator(paste0(philosopher, "_"), dining, at(0))
  }

  run(env, time)
}

The fork_seq argument consists of a named list of fork sequences. For instance, given the numbering conventions in the image above, if we decide that philosopher 1, Socrates, must take fork 1 first and then fork 2, his fork sequence would be Socrates = c(1, 2). This function also expects the simulation time, and there are other arguments to play with, such as the thinking and eating random processes, the lag between forks, and the seed.

The following function would allow us to plot a kind of Gantt chart of the simulation:

states <- c("hungry", "eating")

philosophers_gantt <- function(env, size=15) env %>%
  get_mon_arrivals(per_resource=TRUE) %>%
  transform(philosopher = sub("_[0-9]*", "", name),
            state = factor(states, states)) %>%
  ggplot(aes(y=philosopher, yend=philosopher)) + xlab("time") +
  geom_segment(aes(x=start_time, xend=end_time, color=state), size=size)

With the simplest algorithm, each philosopher would take, for example, the right fork first and then the left one. But it is easy to see that this policy may result in starvation:

fork_seq <- list(
  Socrates   = c(1, 2),
  Pythagoras = c(2, 3),
  Plato      = c(3, 4),
  Aristotle  = c(4, 1)
)

simulate(fork_seq, time=50) %>%
  print() %>%
  philosophers_gantt() + theme_bw()
#> simmer environment: Dining philosophers | now: 3.89681179066325 | next: 
#> { Monitor: in memory }
#> { Resource: fork_1 | monitored: TRUE | server status: 1(1) | queue status: 1(Inf) }
#> { Resource: fork_2 | monitored: TRUE | server status: 1(1) | queue status: 1(Inf) }
#> { Resource: fork_3 | monitored: TRUE | server status: 1(1) | queue status: 1(Inf) }
#> { Resource: fork_4 | monitored: TRUE | server status: 1(1) | queue status: 1(Inf) }
#> { Source: Socrates_ | monitored: 1 | n_generated: 1 }
#> { Source: Pythagoras_ | monitored: 1 | n_generated: 1 }
#> { Source: Plato_ | monitored: 1 | n_generated: 1 }
#> { Source: Aristotle_ | monitored: 1 | n_generated: 1 }

As we can see, the simulation stopped very soon at a point in which every philosopher holds one fork and waits for the other to be available. The solution originally proposed by Dijkstra establishes the convention that all resources must be requested in order. This means that, in our simulation, Aristotle should pick fork 1 first instead:

fork_seq$Aristotle <- rev(fork_seq$Aristotle)

simulate(fork_seq, time=50) %>%
  print() %>%
  philosophers_gantt() + theme_bw()
#> simmer environment: Dining philosophers | now: 50 | next: 50.8360142024587
#> { Monitor: in memory }
#> { Resource: fork_1 | monitored: TRUE | server status: 1(1) | queue status: 0(Inf) }
#> { Resource: fork_2 | monitored: TRUE | server status: 1(1) | queue status: 1(Inf) }
#> { Resource: fork_3 | monitored: TRUE | server status: 1(1) | queue status: 0(Inf) }
#> { Resource: fork_4 | monitored: TRUE | server status: 1(1) | queue status: 0(Inf) }
#> { Source: Socrates_ | monitored: 1 | n_generated: 1 }
#> { Source: Pythagoras_ | monitored: 1 | n_generated: 1 }
#> { Source: Plato_ | monitored: 1 | n_generated: 1 }
#> { Source: Aristotle_ | monitored: 1 | n_generated: 1 }

There are multiple solutions to this starvation problem, but this is probably the most straightforward way to break the circularity of the initial algorithm by making one philosopher pick the left fork first.

Dining Philosophers Problem

Iñaki Ucar

2022-06-25

Problem description

Simulation