Reality Show Philosophers
Dijkstra created the dining philosopher’s problem as an example of deadlock in concurrent systems (dining philosophers on Wikipedia). Each philosopher must pick up two forks to eat his meal, but there are not enough forks for all of them to eat at once. The philosophers must have some sort of strategy to ensure that they don’t all pick up one fork and then wait forever for a second.
Many solutions are possible that avoid deadlock, but STM provides a particularly straightforward one. ScalaSTM’s atomic blocks provide a means for a philosopher to pick up both forks at the same time, a capability not available to most implementors.
This shows that a
Ref[Boolean] can act like a lock when combined with
Adding a camera
In this era it is more likely that diners would have to fight over forks on a reality TV show than behind closed doors. Unlike solutions based on semaphores or agents, the STM solution can easily add the camera’s outside perspective. In a real system the outside view might come from an administrative console (reading and writing), a checkpointing thread or a GUI component.
First, we’ll change the forks so that they use an
Option to record
both the existence of an owner and the owner’s name. Note that when
Ref factory method to create a
Ref[Option[String]] we need
to coerce the type of
None. If we didn’t do this then
end up as a
Ref[None], which isn’t very useful.
We’ll also give each philosopher a name and a
Ref[Int] in which to
record their progress. For convenience,
in-place arithmetic operations such as
+= for types
A that have an
Capturing a snapshot
Capturing an image of the state of the system is now as easy as
iterating over the forks and philosophers inside an atomic block. It is
important that transactions don’t access a mutable object (or a
that is declared outside the atomic block. The mutable
below is created inside the atomic block, so it is safe.
The full source for this example is available as part of the ScalaSTM source on github: RealityShowPhilosophers.scala. It includes a camera thread that prints an image 60 times a second, as well as a bit of machinery to handle thread shutdown.
Below is an excerpt from running
RealityShowPhilosophers. Note that
since forks are picked up and put down instantaneously, the camera never
observes a philosopher holding only a single fork.