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!