The dining philosophers problem with Ruby and Celluloid

Celluloid describes itself as a concurrent object oriented programming framework for Ruby which lets you build multithreaded programs out of concurrent objects just as easily as you build sequential programs out of regular objects. It is an actor-based framework for Ruby inspired by Erlang. Tony Arcieri, the creator of Celluloid, suggested on a Ruby Rouges episode to try to solve one of the basic concurrency problems using it if you want to learn using Celluloid. So let's do that and solve the dining philosophers problem. Wikipedia defines the problem likes this

Five 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 he has both left and right forks [...] The problem is how to design a discipline of behavior (a concurrent algorithm) such that each philosopher won't starve; i.e., can forever continue to alternate between eating and thinking assuming that any philosopher cannot know when others may want to eat or think.

We will model the problem with two classes: Philosopher and Fork, and they will both be implemented as Celluloid Actors.

To create a concurrent object in celluloid we create a normal Ruby class and include the Celluloid module in it. Let's create a skeleton for the Philosopher class and make it an Actor.

require 'celluloid'

class Philosopher
  include Celluloid

  def initialize(number)
    @number = number
  end

  def start
    send([:eat, :think].sample)
  end

  private

  def eat
    puts "Philosopher #{@number} eating"
    sleep(1)
    think
  end

  def think
    puts "Philosopher #{@number} thinking"
    sleep(1)
    eat
  end
end

The Philosopher will randomly either think or eat. When we create instances of this class they will actually be instances of Celluloid::ActorProxy, and run in their own threads. To be able to run multiple methods concurrently we have to invoke them chained after the async method that the Celluloid module provides, this is Celluloids way of passing a message to an Actor.

  1.9.3p429 :001 > p1 = Philosopher.new(1)
   => #<Celluloid::ActorProxy(Philosopher:0x3fcfe141f050)>
  1.9.3p429 :002 > p2 = Philosopher.new(2)
   => #<Celluloid::ActorProxy(Philosopher:0x3fcfe1413cc8)>
  1.9.3p429 :003 > p1.async.start; p2.async.start
Philosopher 1 eating
 => nil
Philosopher 2 thinking1.9.3p429 :004 >
Philosopher 1 eating
Philosopher 2 thinking
Philosopher 1 thinking
Philosopher 2 eating

The output is mixed up with the console output because the output is happening in separate threads. To solve the real problem at hand we need some forks as well and we need to make sure that only one Philosopher is using each fork at any given time. We can achieve this in a number of different ways. But the main idea is that we need to synchronize access to the shared recourses, i.e. the forks. In classical concurrent programming we would use a lock or mutex to make sure that only one thread (Philosopher) is using the shared resource (Fork) at once. But with Actors we generally don't need to use locks but instead rely on passing messages (call methods chained after the async method with Celluloid), between the actors in the system.

We will use the resource hierarchy solution to avoid deadlocks. All forks will be numbered and each philosopher has to pick up the lowest numbered fork first.

require 'celluloid'

class Fork
  include Celluloid

  def initialize(number)
    @free = true
    @number = number
    @waiting = :none_waiting
  end

  def pick_up(philosopher)
    if @free
      @free = false
      philosopher.async.fork_picked_up(@number)
    else
      @waiting = philosopher
    end
  end

  def put_down
    if @waiting == :none_waiting
      @free = true
      @waiting = :none_waiting
    else
      @waiting.async.fork_picked_up(@number)
    end
  end
end

The Fork keeps track of both weather if it currently in use and if there is a Philosopher waiting on it. When it is free to pick up it sends the #fork_picked_up message to the Philosopher, passing in its own number so that the Philosopher knows which fork it managed to get hold of. The Philosopher skeleton we saw earlier needs a few changes, before starting to eat it needs to pick up both its forks and wait for the #fork_picked_up message.

NUM_PHILOSOPHERS = 5

class Philosopher
  include Celluloid

  def initialize(number, forks)
    @number = number
    @forks = forks
    @has_eaten = false
  end

  def start
    send([:eat, :think].sample)
  end

  # To be able to ask all philosopher if they got to eat
  def hungry?
    !@has_eaten
  end

  def fork_picked_up(fork_number)
    if fork_number == first_fork
      @forks[second_fork].async.pick_up(Actor.current)
    else
      ready_to_eat
    end
  end

  private

  def think
    puts "#{name} thinking"
    random_sleep
    eat
  end

  def eat
    @forks[first_fork].async.pick_up(Actor.current)
  end

  def ready_to_eat
    puts "#{name} eating"
    @has_eaten = true
    random_sleep
    put_down_forks
    think
  end

  def put_down_forks
    @forks[first_fork].put_down
    @forks[second_fork].put_down
  end

  def name
    "Philosopher #{@number + 1}"
  end

  # Do the selected activity for a random amount of time
  def random_sleep
    sleep((1 + rand(10)) * 0.1)
  end

  def first_fork
    @number % (NUM_PHILOSOPHERS - 1)
  end

  def second_fork
    [4, @number + 1].min 
  end
end

To ease running of the simulation we can add a small Manager class that creates the necessary instances and starts the simulation.

class Manager
  include Celluloid

  def run
    puts "Philosophers sitting down to eat"
    Celluloid.logger = nil # To avoid Celluloid debug output
    forks = (0...NUM_PHILOSOPHERS).map { |i| Fork.new_link(i) }
    philosophers = (0...NUM_PHILOSOPHERS).map { |i| Philosopher.new_link(i, forks) }

    # Start the simulation
    philosophers.each { |p| p.async.start }
    sleep 5 # Let the simulation run for 5 seconds
    puts "Time to break up the party"

    # Check if all philosophers have gotten to eat
    puts "All philosophers have eaten? #{philosophers.none? { |p| p.hungry? } ? 'Yes' : 'No'}"
  end
end

We put all these classes in a file called philosophers.rb and one more line to get everything going.

Manager.new.run

We can now run the simulation from the console.

> ruby philosophers.rb
  Philosophers sitting down to eat
  Philosopher 1 thinkingPhilosopher 3 thinking

  Philosopher 4 thinking
  Philosopher 2 eating
  Philosopher 5 eating
  Philosopher 5 eating
  Philosopher 2 thinking
  Philosopher 3 eating
  ...
  Time to break up the party
  All philosophers have eaten? Yes

To see that it is the ordering in which the philosophers pick up their forks that ensures that we don't get into a deadlock, we can change the Philosophers first_fork and second_fork methods to always return the left fork first then the right fork.

class Philosopher
  include Celluloid

  ...

  def start
    eat   # Try to get into a deadlock by making all philosophers start with eating
  end

  ...

  def fork_picked_up(fork_number)
    if fork_number == first_fork
      sleep(1)  # Sleep after first fork picked up to allow all philosophers to try to pick up their first fork
      @forks[second_fork].async.pick_up(Actor.current)
    else
      ready_to_eat
    end
  end

  private

  ...

  def first_fork
    @number
  end

  def second_fork
    (@number + 1) % NUM_PHILOSOPHERS
  end
end

If we run the simulation again with this new code we will immediately get into a deadlock. So Actors cannot ensure that we never get a deadlock, and we still have to be careful when designing concurrent programs that share resources. But Actors (and Celluloid) certainly makes it easier to write correct concurrent code.