понедельник, 28 января 2019 г.

[prog.c++] "Modern" Dining Philosophers in C++ with Actors and CSP (part 1)

Some time ago a reference to an interesting article "Modern dining philosophers" was published on resources like Reddit and HackerNews. The article discusses several implementations of well-known "dining philosophers problem". All those solutions were built using task-based approach. I think the article is worth reading. Therefore, if you have not read it yet, I recommend read the article. Especially if your impressions of C++ are based on C++03 or more earlier versions of C++.

However there was something that hampered me during the reading and studying proposed solutions.

I think it was usage of task-based parallelism. There are too many tasks created and scheduled thru various executors/serializers and it's hard to understand how those tasks are related one to another, in which order they are executed and on which context.

Anyway the task-based parallelism is not the single approach to be used to solve concurrent programming problems. There are different approaches and I wanted to investigate how a solution of "dining philosophers problem" can looks like if Actors and CSP models will be used.

To do that I implemented some solutions of "dining philosopher problem" with Actors and CSP models. Source code can be found in this repository. In this post you will find description of Actors-based implementation. In the next part I will tell about CSP-based implementations.

Some Common Words

I had no goal to reimplement the same solutions from the article "Modern dining philosophers" by using different approaches. There is one thing I didn't like in the mentioned article: it is the separation in responsibility of 'philosopher' and 'protocol'. This separation allows to have just one implementation of 'philosopher' and different versions of 'protocol', but in that case 'philosopher' doesn't do anything interesting. For example 'philosopher' doesn't take forks by itself. 'Philosopher' just tell 'I want to eat' and forks are "magically" provided to it or not.

I think that it is more interesting to place some logic of grabbing forks into 'philosopher' entity. Let's allow 'philosopher' to try to take one fork first and then take another fork. And then we can try to adopt this behavior to different schemes: without or with the presence of arbiter (waiter).

For my implementations I used SObjectizer framework that allows to use Actor and CSP models in C++ applications. This framework is not widely known but it is one of a few live and evolving open-source "actor frameworks" for C++ (two other comparable alternatives are CAF and QP/C++). I hope the code will be a quite understandable even if a reader doesn't know anything about SObjectizer. And I will try to explain most important things.

Actors-Based Solutions

Let's start speak about solutions based on Actors.

We will start with one of the best known, simple and elegant solutions of "dining philosopher problem" proposed by Edsger Dijkstra. Then we discuss two different solutions and will see the difference in behavior.

Dijkstra's Solution

Edsger Dijkstra proposed beautiful solution for "dining philosopher problem" (that problem was also proposed by Dijkstra and reformulated with "spaghetti" and "forks" by Tony Hoar): forks can be acquired only from lower to higher forks numbers, and if a philosopher takes one fork then he/she holds and doesn't put this fork back until he/she takes the second fork.

For example, if a philosopher need forks with numbers 5 and 6 then philosopher have to take fork number 5 first and only then philosopher can take fork number 6. If forks with lower numbers lie on the left then philosopher have to take the left fork first and only then the one from the right.

The last philosopher (who have to deal with forks with numbers (N-1) and 0) takes forks in opposite direction: the right fork first and only then the left fork. It is because the right fork for him has lower number.

Two types of actors (agents in SObjectizer's terms) are used for implementation: one type for representation of forks and another for representation of philosophers. When a philosopher actor wants to eat it sends a message to corresponding fork actor and waits reply message from the fork.

The full code of this implementation can be found here.

Messages

Before we see the code of this actors let define some messages those necessary for actors' interaction:

struct take_t
{
   const so_5::mbox_t m_who;
   std::size_t m_philosopher_index;
};

struct taken_t : public so_5::signal_t {};

struct put_t : public so_5::signal_t {};

When a philosopher actor want to get a fork it sends a take_t message to the corresponding fork actor. Fork replies with taken_t. When philosopher finish eating it sends put_t signal to forks taken before.

Message take_t has two fields. The first one is message box of philosopher actor. In classical Actor Model a reference to target actor is necessary for message sending. But in SObjectizer messages are sent to message boxes and actor can receive messages from different mboxes. Because of that to receive taken_t reply philosopher actor has to pass its own message box in take_t message. The second field is not used in that implementation and we will see the usage of that field in other implementations.

Fork Actor

So now we can see the code of fork actor:

class fork_t final : public so_5::agent_t
{
public :
   fork_t( context_t ctx ) : so_5::agent_t{ std::move(ctx) } {}

   void so_define_agent() override
   {
      // The starting state is 'free' state.
      this >>= st_free;

      // In 'free' state just one message is handled.
      st_free
         .event( [this]( mhood_t<take_t> cmd ) {
               this >>= st_taken;
               so_5::send< taken_t >( cmd->m_who );
            } );

      // In 'taken' state we should handle two messages.
      st_taken
         .event( [this]( mhood_t<take_t> cmd ) {
               // The requester should wait for some time.
               m_queue.push( cmd->m_who );
            } )
         .event( [this]( mhood_t<put_t> ) {
               if( m_queue.empty() )
                  // Noone needs the fork. Can switch to 'free' state.
                  this >>= st_free;
               else
               {
                  // The first philosopher from wait queue should be notified.
                  const auto who = m_queue.front();
                  m_queue.pop();
                  so_5::send< taken_t >( who );
               }
            } );
   }

private :
   // Definition of agent's states.
   const state_t st_free{ this"free" };
   const state_t st_taken{ this"taken" };

   // Wait queue for philosophers.
   std::queue< so_5::mbox_t > m_queue;
};

Every actor in SObjectizer should be represented as C++ class derived from agent_t base class.

Class fork_t overrides so_define_agent() method. It is a special method. It is automatically called by SObjectizer Run-Time when new actor is introduced. This method allows to do necessary tuning for the actor. We see that actor changed its state and makes some subscriptions.

Every actor in SObjectizer is a finite state machine (even if actor has just one default state). Fork actor needs two states: 'free' and 'taken'. When actor is in 'free' state it can be taken by any philosophers. But when a philosopher takes the fork the state of fork should be changed to 'taken'. Those states are represented as fork_t's fields st_free and st_taken of special type state_t.

Actor's states allow to handle message differently. We can see that in the code above. For 'free' state only one message handler is defined:

st_free
   .event( [this]( mhood_t<take_t> cmd ) {
         this >>= st_taken;
         so_5::send< taken_t >( cmd->m_who );
      } );

It means that when actor in 'free' state and message of type take_t is arrived then this lambda will be called. Messages of other types will just be ignored in 'free' state.

For 'taken' state we see handlers for two message types:

st_taken
   .event( [this]( mhood_t<take_t> cmd ) {
         // The requester should wait for some time.
         m_queue.push( cmd->m_who );
      } )
   .event( [this]( mhood_t<put_t> ) {
         if( m_queue.empty() )
            // No one needs the fork. Can switch to 'free' state.
            this >>= st_free;
         else
         {
            // The first philosopher from wait queue should be notified.
            const auto who = m_queue.front();
            m_queue.pop();
            so_5::send< taken_t >( who );
         }
      } );

Message of type take_t is handled differently than in 'free' state: message box of requester is stored in queue.

The most interesting thing is handler for put_t message. If wait queue is not empty then the actor should stay in 'taken' state and the first philosopher from wait queue should receive taken_t signal. But if there is no more items in wait queue then the actor can return to 'free' state.

Philosopher Actor

The philosopher actor is more complex. I won't show the full actor's code here (source code can be seen here. We will discuss the most important parts only.

Philosopher actor has several states:

state_t st_thinking{ this"thinking.normal" };
state_t st_wait_left{ this"wait_left" };
state_t st_wait_right{ this"wait_right" };
state_t st_eating{ this"eating" };

state_t st_done{ this"done" };

Actor starts its work in 'thinking' state, then it switches to 'wait_left' state, then switches to 'wait_right', then it switches to 'eating'. After 'eating' actor can return to 'thinking' or can go to 'done' state where it will wait the completion of simulation. Actor's behavior can be represented by the following state diagram:

In the code the logic of philosopher actor is expressed in so_define_agent() method:

void so_define_agent() override
{
   // In 'thinking' state we wait only for delayed stop_thinking signal.
   st_thinking
      .event( [=]( mhood_t<stop_thinking_t> ) {
            // Try to get the left fork.
            this >>= st_wait_left;
            so_5::send< take_t >( m_left_fork, so_direct_mbox(), m_index );
         } );

   // When we wait for the left fork we react only to 'taken' reply.
   st_wait_left
      .event( [=]( mhood_t<taken_t> ) {
            // Now we have the left fork.
            // Try to get the right fork.
            this >>= st_wait_right;
            so_5::send< take_t >( m_right_fork, so_direct_mbox(), m_index );
         } );

   // When we wait for the right fork we react only to 'taken' reply.
   st_wait_right
      .event( [=]( mhood_t<taken_t> ) {
            // We have both forks. Can eat our meal.
            this >>= st_eating;
         } );

   // When we in 'eating' state we react only to 'stop_eating' signal.
   st_eating
      // 'stop_eating' signal should be initiated when we enter 'eating' state.
      .on_enter( [=] {
            so_5::send_delayed< stop_eating_t >( *this, eat_pause() );
         } )
      .event( [=]( mhood_t<stop_eating_t> ) {
         // Both forks should be returned back.
         so_5::send< put_t >( m_right_fork );
         so_5::send< put_t >( m_left_fork );

         // One step closer to the end.
         ++m_meals_eaten;
         if( m_meals_count == m_meals_eaten )
            this >>= st_done; // No more meals to eat, we are done.
         else
            think();
      } );

   st_done
      .on_enter( [=] {
         // Notify about completion.
         completion_watcher_t::done( so_environment(), m_index );
      } );
}

Another important moment that should be specially mentioned is simulation of time spent for 'thinking' and 'eating' activities. The working context on that the actor handles its incoming messages is not blocked by this_thread::sleep_for or any other kind of sleeps. Timer messages are used instead. For example when actor switches to 'eating' state it sends a stop_eating_t signal as a delayed message. This message will be passed to SObjectizer's timer and timer sends this message to the actor when specified timeout elapsed. The same with 'thinking' state and stop_thinking_t signal.

The usage of delayed messages allows to run all philosopher actors on the same execution context. The reader can think that there is some work thread inside SObjectizer Run-Time that reads some message queue and calls message handlers from corresponding actors when messages arrived. It will be rather good approximation of SObjectizer's message dispatching scheme for this very simple example.

The Results

The results of execution of this implementation can looks like (this is just a fragment):

       Socrates: tttttttttttLRRRRRRRRRRRRRREEEEEEEttttttttLRRRRRRRRRRRRRREEEEEEEEEEEEEEEEtt
          Plato: ttttttttttEEEEEEEEEEEEEEEEttttttttttRRRRRREEEEEEEEEEEEEEttttttttttLLLLLLEE
      Aristotle: ttttEEEEEtttttttttttLLLLLLRRRREEEEEEEEEEEEttttttttttttLLEEEEEEEEEEEEEEtttt
      Descartes: tttttLLLLRRRRRRRREEEEEEEEEEEEEtttLLLLLLLLLRRRRREEEEEEttttttttttLLLLLLLEEEE
        Spinoza: ttttEEEEEEEEEEEEEttttttttttLLLRRRREEEEEEEEEEEEEttttttttttRRRREEEEEEttttttt
           Kant: ttttttttttLLLLLLLRREEEEEEEEEEEEEEEttttttttttLLLEEEEEEEEEEEEEEttttttttttRRR
   Schopenhauer: ttttttEEEEEEEEEEEEEttttttLLLLLLLLLEEEEEEEEEttttttttLLLLLLLLLLRRRRRRRRRRRRR
      Nietzsche: tttttttttLLLLLLLLLLEEEEEEEEEEEEEttttttttLLLEEEEEEEEEttttttttRRRRRRRREEEEEE
   Wittgenstein: ttttEEEEEEEEEEtttttLLLLLLLLLLLLLEEEEEEEEEttttttttttttRRRREEEEEEEEEEEtttttt
      Heidegger: tttttttttttLLLEEEEEEEEEEEEEEtttttttLLLLLLREEEEEEEEEEEEEEEtttLLLLLLLLRRRRRR
         Sartre: tttEEEEEEEEEttttLLLLLLLLLLLLRRRRREEEEEEEEEtttttttLLLLLLLLRRRRRRRRRRRRRRREE

This trace can be read this way:

't' means that philosopher is in 'thinking' state.
'L' means that philosopher is in 'wait_left' state (the left fork is not taken yet).
'R' means that philosopher is in 'wait_right' state (the right fork is not taken yet).
'E' means that philosopher is in 'eating' state.

We can see that 'Socrates' can take the left fork only when 'Sartre' released it. Then 'Socrates' wait while 'Plato' released the right fork. Only then 'Socrates' starts eating.

Simple Solution Without Waiter

If we analyse trace of our implementation of Dijkstra's solution we can see how much time philosophers spend waiting for forks. It is not good because even hungry philosophers can think and invent something useful. There is even an opinion that hungry thinking can lead to more interesting and unexpected results :)

Let's see the simplest solution where philosopher returns the left fork if it can't take the right fork (it seems that the similar solution is implemented in "Modern dining philosophers" article as ForkLevelPhilosopherProtocol).

Source code of this implementation can be found here. Code of philosopher actor can be found here.

Messages

Almost the same set of messages will be used in this implementation:

struct take_t
{
   const so_5::mbox_t m_who;
   std::size_t m_philosopher_index;
};

struct busy_t : public so_5::signal_t {};

struct taken_t : public so_5::signal_t {};

struct put_t : public so_5::signal_t {};

The only difference is the presence of busy_t signal. This signal will be sent by fork actor if fork is already taken by another philosopher.

Fork Actor

The fork actor will be even simpler that in Dijkstra's implementation:

class fork_t final : public so_5::agent_t
{
public :
   fork_t( context_t ctx ) : so_5::agent_t( ctx )
   {
      this >>= st_free;

      st_free.event( [this]( mhood_t<take_t> cmd )
            {
               this >>= st_taken;
               so_5::send< taken_t >( cmd->m_who );
            } );

      st_taken.event( []( mhood_t<take_t> cmd )
            {
               so_5::send< busy_t >( cmd->m_who );
            } )
         .just_switch_to< put_t >( st_free );
   }

private :
   const state_t st_free{ this };
   const state_t st_taken{ this };
};

There is no need to have wait queue here. Only two states with very simple handlers for incoming messages.

Philosopher Actor

The philosopher actor is very similar to actor from Dijkstra's implementation. It has the same set of states. But have to handle additional busy_t messages in 'wait_left' and 'wait_right' states. So the state diagram for this philosopher actor can looks like that:

Similarly the main logic of philosopher agent is defined in so_define_agent() method:

void so_define_agent() override
{
   st_thinking
      .event< stop_thinking_t >( [=] {
         this >>= st_wait_left;
         so_5::send< take_t >( m_left_fork, so_direct_mbox(), m_index );
      } );

   st_wait_left
      .event< taken_t >( [=] {
         this >>= st_wait_right;
         so_5::send< take_t >( m_right_fork, so_direct_mbox(), m_index );
      } )
      .event< busy_t >( [=] {
         think( st_hungry_thinking );
      } );

   st_wait_right
      .event< taken_t >( [=] {
         this >>= st_eating;
      } )
      .event< busy_t >( [=] {
         so_5::send< put_t >( m_left_fork );
         think( st_hungry_thinking );
      } );

   st_eating
      .on_enter( [=] {
            so_5::send_delayed< stop_eating_t >( *this, eat_pause() );
         } )
      .event< stop_eating_t >( [=] {
         so_5::send< put_t >( m_right_fork );
         so_5::send< put_t >( m_left_fork );

         ++m_meals_eaten;
         if( m_meals_count == m_meals_eaten )
            this >>= st_done;
         else
            think( st_normal_thinking );
      } );

   st_done
      .on_enter( [=] {
         completion_watcher_t::done( so_environment(), m_index );
      } );
}

It is almost the same code but with two additional message handlers.

The Results

There is a fragment from trace from one of simulations:

       Socrates: tttttttttL..R.....EEEEEEEEEEEEttttttttttR...L.L...EEEEEEEttEEEEEE
          Plato: ttttEEEEEEEEEEEttttttL.....L..EEEEEEEEEEEEEEEttttttttttL....L....
      Aristotle: ttttttttttttL..L.R..EEEEEEtttttttttttL..L....L....R.....EEEEEEEEE
      Descartes: ttttttttttEEEEEEEEttttttttttttEEEEEEEEttttEEEEEEEEEEEttttttL..L..
        Spinoza: ttttttttttL.....L...EEEEEEtttttttttL.L......L....L..L...R...R...E
           Kant: tttttttEEEEEEEttttttttL.L.....EEEEEEEEttttttttR...R..R..EEEEEtttt
   Schopenhauer: tttR..R..L.....EEEEEEEttttttR.....L...EEEEEEEEEEEEEEEEttttttttttt
      Nietzsche: tttEEEEEEEEEEtttttttttEEEEEEEEEEEEEEEttttL....L...L..L....EEEEEEE
   Wittgenstein: tttttL.L..L.....R.R.....L.....L....L...EEEEEEEEEEEEEEEtttttttttL.
      Heidegger: ttttR..R......EEEEEEEEEEEEEttttttttttR..L...L...L..L...EEEEtttttt
         Sartre: tttEEEEEEEtttttttL..L...L....R.EEEEEEEtttttEEEEtttttttR.....R..R.

An additional symbol can be seen here: '.' means that actor is in 'hungry thinking' state, while 't' means that actor is 'normal thinking' state (after eating).

Even from that small fragment we can see that there are moments when actors can't get both forks for long period of time. It is because this solution is not fair one. It defends from presence of deadlock, but not defend from starvation.

Waiter With Queue

The simplest solution described just above has no defence from starvation of philosophers. Article "Modern dining philosophers" contains a version named WaiterFair that tries to solve starvation problem by introducing a waiter and wait queue. A philosopher ask the waiter for forks and waiter provides forks only if both forks are free now and there are no waiting neighbors in wait queue. If there is at least one waiting neighbor in the queue the request from waiting neighbor will be fulfilled first.

Let's see the same solution done with actors.

Source code of this implementation can be found here.

A Trick

The simplest way of implementation "waiter with queue" scheme is introduction of new set of messages and change the logic of philosopher actor. But I wanted to keep existing philosopher implementation and the same set of messages (e.g. take_t, taken_t, busy_t, put_t). So I had to solve a tricky task: a philosopher should have reference to two messages boxes (one for the left fork, another for the right fork), but there won't be fork actors anymore. A new waiter actor should receive and handle messages instead on fork actors.

I used the following trick: waiter actor creates N message boxes and those mboxes are used as mboxes of "forks". Waiter actor makes subscription for all those mboxes and this allows it to handle all necessary messages.

In the code it looks like:

class waiter_t final : public so_5::agent_t
{
public :
   waiter_t( context_t ctx, std::size_t forks_count )
      :  so_5::agent_t{ std::move(ctx) }
      ,  m_fork_states( forks_count, fork_state_t::free )
   {
      // Mboxes for every "fork" should be created.
      m_fork_mboxes.reserve( forks_count );
      for( std::size_t i{}; i != forks_count; ++i )
         m_fork_mboxes.push_back( so_environment().create_mbox() );
   }
   ...
   void so_define_agent() override
   {
      // We should make subscription for all mboxes of "forks".
      for( std::size_t i{}; i != m_fork_mboxes.size(); ++i )
      {
         // We need an index of fork. Because of that we use lambdas
         // as message handlers. Those lambdas capture indexes and
         // then pass indexes to actual message handlers.
         so_subscribe( fork_mbox( i ) )
            .event( [i, this]( mhood_t<take_t> cmd ) {
                  on_take_fork( std::move(cmd), i );
               } )
            .event( [i, this]( mhood_t<put_t> cmd ) {
                  on_put_fork( std::move(cmd), i );
               } );
      }
   }

private :
   ...
   // Mboxes for "forks".
   std::vector< so_5::mbox_t > m_fork_mboxes;

A vector of mboxes for "forks" is created in the constructor of waiter actor. Then in so_define_agent() a subscription for every mbox is created. But there is another trick: waiter actor has to know the index of requested fork. To provide this information lambda functions are used as message handlers during subscription. Lambda function captures index of a fork and passes this index to actual message handler.

Actual handler of take_t message is implemented in on_take_fork() method:

void on_take_fork( mhood_t<take_t> cmd, std::size_t fork_index )
{
   // Use the fact that index of left fork is always equal to
   // index of the philosopher itself.
   if( fork_index == cmd->m_philosopher_index )
      handle_take_left_fork( std::move(cmd), fork_index );
   else
      handle_take_right_fork( std::move(cmd), fork_index );
}

There we have index of fork (it is passed by lambda function) and index of philosopher (it is passed in take_t message). So we can distinguish between request for the left or for the right fork. These requests are handled differently.

Because every philosopher always asks for the left fork first all necessary checks are performed during handling take_t for the left message. As result we can have two cases:

  1. Both forks are free and can be taken by that philosopher. In that case taked_t is sent back to the philosopher. And the right fork is marked as 'reserved'. It can't be grabbed by any other philosopher.
  2. Forks can't be taken by philosopher. It doesn't matter why. Maybe some fork are already taken or reserved. Maybe there is a neighbor is wait queue. A busy_t reply is sent back to the philosopher.

By this logic when a philosopher receives taken_t as result for take_t for the left fork it can safely send next take_t for the right fork. This next take_t will always lead to taken_t reply because the right "fork" is already reserved for this philosopher.

The Results

There is a fragment from trace from one of simulations:

       Socrates: tttttttttttL....EEEEEEEEEEEEEEttttttttttL...L...EEEEEEEEEEEEEtttttL.
          Plato: tttttttttttL....L..L..L...L...EEEEEEEEEEEEEtttttL.....L....L.....EEE
      Aristotle: tttttttttL.....EEEEEEEEEttttttttttL.....L.....EEEEEEEEEEEtttL....L.L
      Descartes: ttEEEEEEEEEEtttttttL.L..EEEEEEEEEEEEtttL..L....L....L.....EEEEEEEEEE
        Spinoza: tttttttttL.....EEEEEEEEEttttttttttL.....L.....EEEEEEEEEEEtttL....L.L
           Kant: ttEEEEEEEEEEEEEtttttttL...L.....L.....EEEEEttttL....L...L..L...EEEEE
   Schopenhauer: ttttL...L.....L.EEEEEEEEEEEEEEEEEtttttttttttL..L...L..EEEEEEEttttttt
      Nietzsche: tttttttttttL....L..L..L...L...L.....L....EEEEEEEEEEEEttL.....L...L..
   Wittgenstein: tttttttttL....L...L....L....L...EEEEEEEttttL......L.....L.....EEEEEE
      Heidegger: ttttttL..L...L.....EEEEEEEEEEEEtttttL...L..L.....EEEEEEEEEEEttttttL.
         Sartre: ttEEEEEEEEEEEEEttttttttL.....L...EEEEEEEEEEEEttttttttttttL.....EEEEE

We can note that there is no 'R' symbols anymore. It is because a request for right fork is always fulfilled, only requests for left fork can fail in that scheme.

Yet Another Solution With Waiter

Some simulations with previous solution based on "waiter with queue" scheme shows results like that:

       Socrates: tttttEEEEEEEEEEEEEEtttL.....L.L....L....EEEEEEEEEttttttttttL....L.....EE
          Plato: tttttL..L..L....L.L....EEEEEEEEEEEEEEEttttttttttttL.....EEEEEEEEEttttttt
      Aristotle: tttttttttttL..L...L.....L.....L....L.....EEEEEEEEEEEEtttttttttttL....L..
      Descartes: ttttttttttEEEEEEEEEEttttttL.....L....L..L.....L.....L..L...L..EEEEEEEEtt
        Spinoza: tttttttttttL..L...L.....L.....L....L.....L..L..L....EEEEEEEEEEtttttttttt
           Kant: tttttttttL....L....L...L...L....L..L...EEEEEEEEEEEttttttttttL...L......E
   Schopenhauer: ttttttL....L..L...L...L.L....L...EEEEEtttttL....L...L.....EEEEEEEEEttttt
      Nietzsche: tttttL..L..L....EEEEEEEEEEEEEttttttttttttEEEEEEEEEEEEEEEttttttttttttL...
   Wittgenstein: tttEEEEEEEEEEEEtttL....L....L..EEEEEEEEEtttttL..L..L....EEEEEEEEEEEEEEEE
      Heidegger: tttttttttL...L..EEEEEEEEttttL..L.....L...EEEEEEEEEtttL.L..L...L....L...L
         Sartre: ttttttttttL..L....L...L.EEEEEEEEEEEtttttL...L..L....EEEEEEEEEEtttttttttt

We can see rather big periods of time where philosophers can't eat even when there are free resources. For example the left and right forks for 'Kant' are free for some time, but 'Kant' can't take them because there are neighbors in wait queue. And those neighbors depend on other neighbors and so on.

This "waiter with queue" scheme defends from starvation in that sense that starvation period will be finished sooner or later. But starvation periods can last for long time. And utilization of forks can be not optimal sometimes.

I implemented another solution with waiter but without wait queue. Instead of wait queue this solution uses priorities for philosopher's requests based on timestamps. If a philosophers doesn't eat too long its requests are processed with greater priorities than requests from its neighbors.

The source code of this solution can be found here. The code of this solution won't be discussed because the source code of waiter actor is very similar to the code of waiter actor for "waiter with queue" solution. The same trick with array of message boxes for "fork" was reused. This trick is the key point of both solutions with waiter actor and this trick has already been described. However I will answer any related to "waiter with timestamp" solution in comments.

Some Implementation Details I Want To Mention

There are a couple of implementation details I want to discuss separately because they show some interesting features of SObjectizer.

Working Context For Actors

In the solutions discussed above all major actors (like forks, philosophers and waiter) work on the same working context. But it doesn't mean that all actors in SObjectizer work on the single work thread. SObjectizer allows to bind different actors to different working context. And this can be seen in the source code. For example this is function that creates all actors in no_waiter_simple solution:

void run_simulation( so_5::environment_t & env, const names_holder_t & names )
{
   env.introduce_coop( [&]( so_5::coop_t & coop ) {
      coop.make_agent_with_binder< trace_maker_t >(
            so_5::disp::one_thread::create_private_disp( env )->binder(),
            names,
            random_pause_generator_t::trace_step() );

      coop.make_agent_with_binder< completion_watcher_t >(
            so_5::disp::one_thread::create_private_disp( env )->binder(),
            names );

      const auto count = names.size();

      std::vector< so_5::agent_t * > forks( count, nullptr );
      for( std::size_t i{}; i != count; ++i )
         forks[ i ] = coop.make_agent< fork_t >();

      for( std::size_t i{}; i != count; ++i )
         coop.make_agent< philosopher_t >(
               i,
               forks[ i ]->so_direct_mbox(),
               forks[ (i + 1) % count ]->so_direct_mbox(),
               default_meals_count );
   });
}

We can see creation of two additional actors: trace_maker_t and completion_watcher_t. They will work on separate working contexts. An instance of new dispatcher of type one_thread is created for every of these actors and these actors are bound to new dispatchers. It means that these actors will work as active objects: each actor will have a separate work thread.

SObjectizer provides a set of ready-to-use dispatchers. A programmer can create as many dispatcher instances in an application as he/she wants.

There is no need to rewrite an existing actor for binding the actor to another dispatcher. For example we can easily run fork_t actors on one thread_pool dispatcher and philosopher_t actors on another thread_pool dispatcher:

void run_simulation( so_5::environment_t & env, const names_holder_t & names )
{
   env.introduce_coop( [&]( so_5::coop_t & coop ) {
      coop.make_agent_with_binder< trace_maker_t >(
            so_5::disp::one_thread::create_private_disp( env )->binder(),
            names,
            random_pause_generator_t::trace_step() );

      coop.make_agent_with_binder< completion_watcher_t >(
            so_5::disp::one_thread::create_private_disp( env )->binder(),
            names );

      const auto count = names.size();

      // Params for tuning thread_pool behavior.
      so_5::disp::thread_pool::bind_params_t bind_params;
      bind_params.fifo( so_5::disp::thread_pool::fifo_t::individual );

      std::vector< so_5::agent_t * > forks( count, nullptr );
      // Create a thread_pool dispatcher for fork agents.
      auto fork_disp = so_5::disp::thread_pool::create_private_disp(
               env,
               3u // Size of the pool
            );
      for( std::size_t i{}; i != count; ++i )
         // Every fork actor will be bound to fork_disp dispatcher.
         forks[ i ] = coop.make_agent_with_binder< fork_t >(
               fork_disp->binder( bind_params ) );

      // Create a thread_pool dispatcher for philosopher agents.
      auto philosopher_disp = so_5::disp::thread_pool::create_private_disp(
               env,
               6u // Size of the pool
            );
      for( std::size_t i{}; i != count; ++i )
         coop.make_agent_with_binder< philosopher_t >(
               philosopher_disp->binder( bind_params ),
               i,
               forks[ i ]->so_direct_mbox(),
               forks[ (i + 1) % count ]->so_direct_mbox(),
               default_meals_count );
   });
}

Now fork_t and philosopher_t actors will work on different dispatcher (e.g. different working context) but we didn't change a line in their code.

Tracing Actors States

If you look at code examples from article "Modern dining philosophers" you easily find code related to tracing philosophers activity, for example:

void doEat() {
    eventLog_.startActivity(ActivityType::eat);
    wait(randBetween(1050));
    eventLog_.endActivity(ActivityType::eat);

There is no such code in SObjectizer-based implementations. But traces of philosophers actors are still collected. How was it done?

SObjectizer has a special feature: state listener. State listener is an object that implements agent_state_listener_t interface. This object can be installed for an agent and this object will be automatically notified when agent changes its state. We can see creation and installation of such listener in the constructors of greedy_philosopher_t and philosopher_t classes:

philosopher_t(...)
   ...
   {
      so_add_destroyable_listener(
            state_watcher_t::make( so_environment(), index ) );
   }

Where state_watcher_t looks like:

class state_watcher_t final : public so_5::agent_state_listener_t
{
   const so_5::mbox_t m_mbox;
   const std::size_t m_index;

   state_watcher_t( so_5::mbox_t mbox, std::size_t index );

public :
   static auto make( so_5::environment_t & env, std::size_t index )
   {
      return so_5::agent_state_listener_unique_ptr_t{
            new state_watcher_t{ trace_maker_t::make_mbox(env), index }
      };
   }

   void changed( so_5::agent_t &, const so_5::state_t & state ) override;
};

When an instance of state_watcher_t is installed for philosopher actor, SObjectizer calls state_watcher_t::changed method every time the actor changes its state. In state_watcher_t::changed() message of type state_changed_t is sent to special trace_maker_t agent:

void state_watcher_t::changed( so_5::agent_t &, const so_5::state_t & state ) 
{
   const auto detect_label = []( const std::string & name ) {...};

   const char state_label = detect_label( state.query_name() ); 
   if'?' == state_label )
      return;

   so_5::send< trace::state_changed_t >( m_mbox, m_index, state_label );
}

Agent of type trace_maker_t receives and handles state_changed_t messages and forms traces of philosophers actors.

Conclusion

This is all I wanted to tell about Actors-based implementations. If you have any question feel free to ask in comments.

In the next part I plan to talk about some CSP-based implementations. The same solutions, but expressed with std::threads and SObjectizer's mchains (which are very similar to CSP-channels).

If you want to get more information about SObjectizer you can take a look at a serie of slides about SObjectizer-5.5 and its features (this information in more detailed form can be found in project's Wiki). And maybe you can find a time and desire to review/discuss our plans about next major version of SObjectizer.

PS. The word "modern" in the title is enclosed in quotes because there is nothing modern in described implementations. Maybe except a usage of more or less modern C++.

Комментариев нет: