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, tag="think") %>%
seize(forks[[1]]) %>%
timeout(lag) %>%
seize(forks[[2]]) %>%
timeout(eating) %>%
release(forks[[1]]) %>%
release(forks[[2]]) %>%
rollback("think") # 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 }
#> Warning: Using `size` aesthetic for lines was deprecated in ggplot2 3.4.0.
#> ℹ Please use `linewidth` instead.
#> This warning is displayed once every 8 hours.
#> Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
#> generated.
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.