Tuesday, January 24, 2012

Dining Philosophers

The Dining Philosophers Problem is a well-known exercise in computer science for concurrent systems. Recently, I've found an implementation for Akka that's an adaption of this algorithm of Dale Schumacher. I think it's a pretty nice example program to introduce libcppa's event-based actor implementation. The following source code is an adaption of the Akka example implementation.


Let's start with the straightforward chopstick implementation.
#include "cppa/cppa.hpp"
using std::chrono::seconds;
using namespace cppa;
// either taken by a philosopher or available
struct chopstick : sb_actor<chopstick> {

  behavior& init_state; // a reference to available
  behavior available;

  behavior taken_by(const actor_ptr& philos) {
    // create a behavior new on-the-fly
    return (
      on<atom("take"), actor_ptr>() >> [=](actor_ptr other) {
        send(other, atom("busy"), this);
      },
      on(atom("put"), philos) >> [=]() {
        become(&available);
      }
    );
  }

  chopstick() : init_state(available) {
    available = (
      on<atom("take"), actor_ptr>() >> [=](actor_ptr philos) {
        send(philos, atom("taken"), this);
        become(taken_by(philos));
      }
    );
  }

};
The class fsm_actor uses the Curiously Recurring Template Pattern to initialize the actor with the behavior stored in the member init_state. We don't really have an initial state. Thus, init_state is a reference to the behavior available. You also could inherit from event_based_actor and override the member function init() by hand. But using an fsm_actor is more convenient. You change the state/behavior of an actor by calling become. It takes either a pointer to a member or an rvalue. The member function taken_by creates a behavior "on-the-fly". You could achieve the same by using a member storing the 'owning' philosopher. But why use member variables if you don't have to? This solution is easier to understand than manipulating some internal state.

Btw: you should always use [=] in lambda expressions for event-based actors. This copies the this pointer into the lambda and you have access to all members. You should never use references, because become always immediately returns. If your lambda finally gets called, everything that was previously on the stack is gone! All your references are guaranteed to cause undefined behavior.


The implementation of philosopher is a little bit longer. Basically, we implement the following state diagram.
/*
 *                +-------------+  {(busy|taken), Y}
 *      /-------->|  thinking   |<------------------\
 *      |         +-------------+                   |
 *      |                |                          |
 *      |                | {eat}                    |
 *      |                |                          |
 *      |                V                          |
 *      |         +-------------+ {busy, X}  +-------------+
 *      |         |   hungry    |----------->|   denied    |
 *      |         +-------------+            +-------------+
 *      |                |
 *      |                | {taken, X}
 *      |                |
 *      |                V
 *      |         +-------------+
 *      |         | wait_for(Y) |
 *      |         +-------------+
 *      |           |    |
 *      | {busy, Y} |    | {taken, Y}
 *      \-----------/    |
 *      |                V
 *      | {think} +-------------+
 *      \---------|   eating    |
 *                +-------------+
 *
 *
 * [ X = left  => Y = right ]
 * [ X = right => Y = left  ]
 */
This is a simplification of the original diagram. A philosopher becomes hungry after receiving an atom("eat") and then tries to obtain its left and right chopstick. A philosopher eats if it obtained both chopsticks, otherwise it will think again.
struct philosopher : sb_actor<philosopher> {

  std::string name; // the name of this philosopher
  actor_ptr left;   // left chopstick
  actor_ptr right;  // right chopstick

  // note: we have to define all behaviors in the constructor because
  //       non-static member initialization are not (yet) implemented in GCC
  behavior thinking;
  behavior hungry;
  behavior denied;
  behavior eating;
  behavior init_state;
A philosopher has a name, a left and a right chopstick and a bunch of possible behaviors. Hopefully, GCC has non-static member initialization in the next version. For now, we have to define all behavior in the constructor, except for wait_for, which is realized as a function similar to taken_by of chopstick.
  // wait for second chopstick
  behavior waiting_for(const actor_ptr& what) {
    return (
      on(atom("taken"), what) >> [=]() {
        // create message in memory to avoid interleaved
        // messages on the terminal
        std::ostringstream oss;
        oss << name
            << " has picked up chopsticks with IDs "
            << left->id()
            << " and "
            << right->id()
            << " and starts to eat\n";
        cout << oss.str();
        // eat some time
        delayed_send(this, seconds(5), atom("think"));
        become(&eating);
      },
      on(atom("busy"), what) >> [=]() {
        send((what == left) ? right : left, atom("put"), this);
        send(this, atom("eat"));
        become(&thinking);
      }
    );
  }
Our constructor defines all behaviors as well as the three member variables storing name and left and right and chopstick.
  philosopher(const std::string& n, const actor_ptr& l, const actor_ptr& r)
  : name(n), left(l), right(r) {
    // a philosopher that receives {eat} stops thinking and becomes hungry
    thinking = (
      on(atom("eat")) >> [=]() {
        become(&hungry);
        send(left, atom("take"), this);
        send(right, atom("take"), this);
      }
    );
    // wait for the first answer of a chopstick
    hungry = (
      on(atom("taken"), left) >> [=]() {
        become(waiting_for(right));
      },
      on(atom("taken"), right) >> [=]() {
        become(waiting_for(left));
      },
      on<atom("busy"), actor_ptr>() >> [=]() {
        become(&denied);
      }
    );
    // philosopher was not able to obtain the first chopstick
    denied = (
      on<atom("taken"), actor_ptr>() >> [=](actor_ptr& ptr) {
        send(ptr, atom("put"), this);
        send(this, atom("eat"));
        become(&thinking);
      },
      on<atom("busy"), actor_ptr>() >> [=]() {
        send(this, atom("eat"));
        become(&thinking);
      }
    );
    // philosopher obtained both chopstick and eats (for five seconds)
    eating = (
      on(atom("think")) >> [=]() {
        send(left, atom("put"), this);
        send(right, atom("put"), this);
        delayed_send(this, seconds(5), atom("eat"));
        cout << (  name
             + " puts down his chopsticks and starts to think\n");
        become(&thinking);
      }
    );
    // philosophers start to think after receiving {think}
    init_state = (
      on(atom("think")) >> [=]() {
        cout << (name + " starts to think\n");
        delayed_send(this, seconds(5), atom("eat"));
        become(&thinking);
      }
    );
  }

};
The source code is a straightforward implementation of the state diagram. Our main starts five chopsticks and five philosophers. We use an anonymous group to send the initial {think} message to all philosophers at once. You could send five single messages as well.
int main(int, char**) {
  // create five chopsticks
  cout << "chopstick ids:";
  std::vector<actor_ptr> chopsticks;
  for (size_t i = 0; i < 5; ++i) {
    chopsticks.push_back(spawn<chopstick>());
    cout << " " << chopsticks.back()->id();
  }
  cout << endl;
  // a group to address all philosophers
  auto dinner_club = group::anonymous();
  // spawn five philosopher, each joining the Dinner Club
  std::vector<std::string> names = { "Plato", "Hume", "Kant",
                                     "Nietzsche", "Descartes" };
  for (size_t i = 0; i < 5; ++i) {
    spawn_in_group<philosopher>(dinner_club,
                                names[i],
                                chopsticks[i],
                                chopsticks[(i+1) % chopsticks.size()]);
  }
  // tell philosophers to start thinking
  send(dinner_club, atom("think"));
  // real philosophers are never done
  await_all_others_done();
  return 0;
}
The full source code can be found in the examples folder on github.

Have fun!

No comments:

Post a Comment