The dining philosophers problem is a classical concurrency problem. This post shows an example of how you can use Scala 3 and the Cats Effect (CE) libraryto implement a solution of that problem.
You can run the final solution using scala-cli or download using git command:
# run the solution
$ scala-cli https://gist.github.com/lrodero/4f6194bcffc3ce32a1780d55176a1ba4
# clone and then run the solution
$ git clone https://gist.github.com/lrodero/4f6194bcffc3ce32a1780d55176a1ba4 dining_philosophers
$ scala-cli dining_philosophers/DiningPhilosophers.scala
Problem description
There are 5 philosophers, and all that they do is thinking, eating, and go back to thinking again. The 5 philosophers share a table with a seat per philosopher and 5 forks, each fork is placed between two philosophers. The key is that a philosopher needs the two forks at her left and right. If some other philosopher is using any of the two forks our hungry philosopher will have to wait. So the table layout looks like this:
Coding our forks and philosophers
A fork is a shared resource that can be used at most by one philosopher. A good way to control access to shared resources is using semaphores. In this case we will use CE's semaphores.
import cats.effect.IO
import cats.effect.std.Semaphore
type Fork = Semaphore[IO]
We will code our philosophers in their own class. Each instance will need to know which are its left and right forks. Also we will compute the time a philosopher spends eating or thinking as a random value, for simplicity we will use a random uniform distribution with a max value. And what does our philosopher do? Well she iterates once and again these steps: think, wait to get forks, eat, release forks.
import cats.effect.IO
import scala.concurrent.duration.*
class Philosopher(
forkLeft: Fork,
forkRight: Fork
) {
private val think: IO[Unit] = ???
private val getForks: IO[Unit] = ???
private val eat: IO[Unit] = ???
private val releaseForks: IO[Unit] = ???
// a >> b is the same as a.flatMap(_ => b), a sequence of two
// where the output of the first is ignored by the second
val doYourThing: IO[Unit] =
think >> getForks >> eat >> releaseForks >> philosophicalLoop
}
Implementing think and eat
Defining think and eat is easy, we can implement them by invoking IO.sleep. But we need a random time generator that computes the time that the philosopher has to be thinking or eating. CE's Random can be used here. We are going to pass the random generator to each philosopher and use it in a new function randomTime that does exactly what its name says: it computes random times. With that function we can easily implement think and eat:
import cats.effect.IO
import cats.effect.std.Random
import scala.concurrent.duration.*
def randomTime(
max: FiniteDuration
): IO[FiniteDuration] =
randomGen
.nextLongBounded(max.toNanos)
.map(FiniteDuration, NANOSECONDS)
val think = randomTime(60.milliseconds)>>= IO.sleep
val eat = randomTime(30.milliseconds) >>= IO.sleep
We have picked 60 milliseconds and 30 milliseconds as the max thinking and eating times just for convenience. Of course we could pick any other value or define it in a parameter of Philosopher constructor. We choose to do it like that for the sake of simplicity.
Defining getForks and releaseForks
Ok, what about getting and releasing forks? Well, they are semaphores, so their definition is pretty obvious, just acquire and release them! So our philosopher implementation looks like this:
val getForks = forkLeft.acquire >> forkRight.acquire
val releaseForks = forkLeft.release >> forkRight.release
Final philosopher implementation
That's all folks! Our philosopher implementation looks like this:
import cats.effect.IO
import cats.effect.std.Random
import scala.concurrent.duration.*
class Philosopher(
forkLeft: Fork,
forkRight: Fork,
randomGen: Random[IO]
) {
private def randomTime(max: FiniteDuration: IO[FiniteDuration] =
randomGen
.nextLongBounded(max.toNanos)
.map(FiniteDuration, NANOSECONDS)
private val think = randomTime(60 minutes) >>= IO.sleep
private val eat = randomTime(30 minutes) >>= IO.sleep
private val getForks = forkLeft.acquire >> forkRight.acquire
private val releaseForks = forkLeft.release >> forkRight.release
val doYourThing: IO[Unit] =
think >> getForks >> eat >> releaseForks >> philosophicalLoop
}
Running the philosophers in parallel
Now we will define a function that instantiates forks and philosophers and then makes then work in parallel using parSequence:
import cats.effect.IO
import cats.effect.std.{Random, Semaphore}
val createForks = Semaphore[IO](1).replicateA(5)
val createPhilosophers: IO[List[Philosopher]] =
for
forks <- createForks
randomGenerator <- Random.scalaUtilRandom[IO]
philosophers = forks.indices.toList.map: i =>
val leftFork = if (i == 0) forks.last else forks(i - 1)
val rightFork = forks(i)
Philosopher(leftFork, rightFork, randomGenerator)
yield philosophers
val runPhilosophers: IO[Unit] =
for
philosophers <- createPhilosophers
_ <- philosophers.map(_.doYourThing).parSequence
yield ()
Running the program
Running the program is trivial, just use CE's IOSimple.App. We can force it to run for a limited time using timeout:
import cats.effect.{IO, IOApp}
import scala.concurrent.duration.*
object DiningPhilosophers extends IOApp.Simple:
override val run: IO[Unit] =
runPhilosophers.timeoutTo(1.minute, IO.unit)
Aaaand that's mainly it? Well, in a way it is. The problem of this naive implementation is that it might deadlock e.g. if all philosophers take the left fork at the same time then none will be able to take their right fork... and will keep waiting for it, then no releasing the left fork, so blocking the philosopher at her left.
Fixing the deadlock issue
There are several ways to fix this issue. We will implement here the resource hierarchy solution, which it's pretty straightforward. Here the 'hierarchy' of the shared resources (forks) is simple: we numerate them (1 to 5) and change the getForks function of philosophers so it always gets first the fork that has a higher hierarchy.
Note this means that most philosophers will pick the left and then the right forks (1 and then 2, or 2 and then 3, and so on) but one of the philosophers will pick first 1 and then 5, i.e. it will pick first the right fork and then the left fork. Releasing can be done in any order. Note that although this fix solves the deadlock issue it's not perfect, for example it cannot ensure fairness. But it is good enough for our purposes.
Implementing this is straightforward. When instantiating each philosopher we will pass as parameter which is the fork to pick first and the one to pick second. Only thing we have to be careful, the last philosopher will have these forks 'reversed'. So now our Philosopher implementation looks like this:
import cats.effect.IO
import cats.effect.std.Random
import scala.concurrent.duration.*
class Philosopher(
firstFork: Fork,
secondFork: Fork,
randomGen: Random[IO]
) {
private val getForks = firstFork.acquire >> secondFork.acquire
private val releaseForks = firstFork.release >> secondFork.release
// all other methods are defined as before
private def randomTime(max: FiniteDuration: IO[FiniteDuratio]) = ???
private val think = ???
private val eat = ???
val doYourThing: IO[Unit] = ???
}
And the way we instantiate the philosophers takes into account that one of them will use its right fork as the first one to acquire:
import cats.effect.IO
import cats.effect.std.Random
val createPhilosophers: IO[List[Philosopher]] =
for
forks <- createForks
randomGenerator <- Random.scalaUtilRandom[IO]
philosophers = forks.indices.toList.map: i =>
val leftFork = if (i == 0) forks.last else forks(i - 1)
val rightFork = forks(i)
val (firstFork, secondFork) = if (i == 0) (rightFork, leftFork) else (leftFork, rightFork)
Philosopher(firstFork, secondFork, randomGenerator)
yield philosophers
And that's it! We have been able to easily forge an implementation of the dining philosophers problem thanks to the CE library!