parallel roads

I’ve been thinking a lot about continuations and directed graphs the last couple days and different ways to implement them.  I’ve also been looking closer at std::thread, std::future and std::async to ensure I fully understand them.  So I decided I’d make a (small) multi-part series out of this and show some simple sketches of implementations of continuation using the Parallel Pattern Library, std::future and std::async and the Agents Library.  

This is part 1 which will cover a simple implementation of ‘run_when’ and ‘wait_for_all’ using the PPL. 

First a simple dependency / continuation

Here’s an incredibly simple dependency, task 2 depends on task 1.

void ContinueableTask(int in)
{
   printf("building project: %d\n", in);
};

void SimpleContinuation()
{
   ContinueableTask(1);

   //task 2 depends on task 1
   ContinueableTask(2);
}

void SimpleContinuationTasks()
{
   //task1   task_group task1;
   task1.run([](){ContinueableTask(1);});

   //task2 depends on task 1 
   task_group task2;
   task2.run([&](){
      task1.wait();
      ContinueableTask(2);
   });   

   //wait for task 2
   task2.wait();
}

void SimpleContinuation()
{
   auto task1 = run_task([](){ContinueableTask(1);});    

   //task 2 depends on task 1
   auto task2 = run_when(task1, [](){ContinueableTask(2);});
   wait_for_all(task1, task2);
}

typedef shared_ptr<task_group> shared_task_ptr;

template<typename Func>inline shared_task_ptr run_task(Func& fn)
{
   shared_ptr<task_group> tasks = make_shared<task_group>();
   tasks->run(fn);
   return tasks;
}

template<typename Func>inline shared_task_ptr run_when(shared_task_ptr tasks, Func fn)
{
   tasks->wait();
   return run_task(fn);
}

inline void wait_for_all(shared_task_ptr t1, shared_task_ptr t2)
{
   t1->wait();
   t2->wait();
}

void MoreComplexContinuations()
{
   auto p1 = run_task([](){ContinueableTask(1);});
   auto p2 = run_task([](){ContinueableTask(2);});
   auto p3 = run_task([](){ContinueableTask(3);});
   auto p4 = run_when(p1, [](){ContinueableTask(4);});
   auto p5 = run_when(p2, p3, [](){ContinueableTask(5);});
   auto p6 = run_when(p3, p4, [](){ContinueableTask(6);});
   wait_for_all(p1, p2, p3, p4, p5, p6);
}

Inspired by some pretty cool slides by Mike Acton that came through my twitter feed last week, I implemented a version of the Sleeping Barber problem.

For those not familiar with the problem, it’s a story that illustrates some of the perils associated inter process / inter thread synchronization, wikipedia describes it as:

The analogy is based upon a hypothetical barber shop with one barber, one barber chair, and a number of chairs for waiting customers. When there are no customers, the barber sits in his chair and sleeps. As soon as a customer arrives, he either awakens the barber or, if the barber is cutting someone else’s hair, sits down in one of the vacant chairs. If all of the chairs are occupied, the newly arrived customer simply leaves.

Wikipedia was also kind enough to provide pseudo-code for he boring three semaphore solution so an implementation was straightforward and only took a few minutes. 

Here’s the skeleton of the outline

Here’s the snippets of the outline, first 3 semaphores and a counter:

 cooperative_semaphore customers_semaphore(0,num_customers,L"C");
 cooperative_semaphore barber_semaphore(0,num_barbers,L"B");
 cooperative_semaphore seats_semaphore (1,num_seats,L"S");
 int free_seat_counter = num_seats;