Jingle Bells time again...

Yesterday we had a snow shower, today is the first Sunday of Advent.. What should be more appropriate for a practical example than Jingle Bells? =)

Trono designed the Santa Claus problem as a new exercise in concurrent programming. He wished to have an exercise harder to solve than the ususal mutual exclusion problems, and indeed the Santa Claus problem involves three sorts of process that need to synchronize and cooperate at certain moments. The problem may be stated as follows:

Santa repeatedly sleeps until wakened by either all of his nine reindeer,
back from their holidays, or by a group of three of his ten elves.
If awakened by the reindeer, he harnesses each of them to his sleigh,
delivers toys with them and finally unharnesses them (allowing them
to go off on holiday). If awakened by a group of elves, he shows each
of the group into his study, consults with them on toy R&D and
finally shows them each out (allowing them to go back to work).
Santa should give priority to the reindeer in the case that there is
both a group of elves and a group of reindeer waiting.

Some parts of the problem, if solved with simple primitives like monitors or semaphores, are very tricky: Trono's original implementation had a bug itself, as pointed out by Ben Ari. Ben Ari solved the problem in a quite simple way using Ada95 synchronization primitives. He also showed how java monitors ar not much better at this task than the simple P-V semaphores used by Trono.
Unlike Java, Ada 95 do not use monitors with condition variables which must be explicitly signalled and waited upon. The language uses instead a construct similar to our wait preconditions: a boolean expression (called a barrier) associated with each method. If the barrier evaluates to true, the thread calling the method is allowed to execute it, it nobody is already 'holding' that object (access to objects is mutual exclusive).
If the barrier is false, threads calling the method are queued. When a method exits, other threads are signalled, so they can re-evaluate therir barrier and see if they are allowed to execute the method.

Wait preconditions acts in the same manner, with two exceptions:

it is possible to use temporal logic
it is possible to refer to meta-variables representing methods.

Later, Nick Benton solved the problem using Polyphonic C# (now Comega). Comega is based on a paradigm derived from join calculus, whose basis are chords and asynch methods. To make it short, synchronization is message-based, and execution derives from the ability of a chord to 'consume' messages.

For example:

static void reindeerBack() & static async  reinWaiting(int r)
{
  if (r == 8)
    reindeerReady(); // last reindeer
  else
    reinWaiting(r + 1);
}

the method reindeerBack will be executed only if there is a reinWaiting 'message' ready to be consumed. Then will send the reindeerReady 'message' that will be consumed by the Santa's thread. This will wake up and do its job with the reindeer.

Polyphonic C# solution is nice, and the code very compact. However, it could be quite hard to understand if you are not familiar with process algebras, or with concurrency based on messages.

For our solution, we take an approach that combines the two. Synchronization contracts let us do so, since it is possible to use wait preconditions like Ada95 write barriers. On the other side, we can mimick (in a very restricted way, but sufficient for this example) the method/message consumption of Comega.

We use the Room class from Ben-Ari solution (we'll call it Queue, and this class will replace class nway in the Comega solution, since they solve the same problem).

class Queue
{
   private int queueSize;
     
   public Queue(int size)
   {
      queueSize = size;
   }
  
   void Accept() //Open_Door
   {
      queue.clear();
      enterPossible = true;
   }
  
   public void Entry(Object o)
      requires_wait(enterPossible == true)
   {
      queue.add(o);
      waiting = waiting + 1;
      if (waiting < queueSize)
      {
         waitForLastMember();
      }
      else
      {
         waiting = waiting - 1;
         enterPossible = false;
         roomDoor = true;
      }
   }
  
   private void waitForLastMember(Object o)
      requires_wait(queue.size() == groupSize)
   {
      waiting = waiting - 1;
      if (waiting = 0)
      {
         //i'm the last one
         roomDoor = false;        
         santa.Wake(this.queue);
      }
   }

   public bool Full()
   {
      return queue.size() == queueSize;
   }
  
   public void WaitFull()
      requires_wait(queue.size() == queueSize);
  
}

Then, to wake Santa, we do not use a special keyword like Ada95 (we do not have one, at this point), but somethig similar to Comega:

class Santa
{
   //...

   void WakedByReindeer()
   {
      harness.WaitFull();   
      DeliverToys();
      unharness.WaitFull();     
      ReindeerQueue.Accept();
   }
  
   void Wake() { }
  
   void Sleep()
      require_wait(pre(@Wake))
   {
      if (ReindeerQueue.Full())
      {
         //Santa's wake and Go to Deliver (when all harnessed..)
         WakedByReindeer();
      }
      else
         WakedByElves();
   }
}

We do not allow, with the actual implementation, to override methods with same signature but different wait preconditions, otherwise the Comega solution:

static void waittobewoken() & static async reindeerready() { }
static void waittobewoken() & static async elvesready() { }

could be mapped to:

void Sleep()
      require_wait(pre(@ReindeerWake));
void Sleep()
      require_wait(pre(@ElvesWake));

Surely, Comega solution is more elegant in this point, but our solution is not so bad, and we hadn't the need to introduce a keyword, like select in Ada95.

The key point is that synchronization contracts are flexible; they allow the programmer to use the style best tailored to the task, or best tailored to her own experience.

References:

N. Benton
Jingle Bells: Solving the Santa Claus Problem in Polyphonic C#
Microsoft Research, 2003

M. Ben-Ari
How to solve the santa claus problem.
Concurrency: Practice & Experience, 1998.