June 2009

Volume 24 Number 06

Concurrent Affairs - Solving The Dining Philosophers Problem With Asynchronous Agents

By Rick Molloy | June 2009

This article is based on a prerelease version of Visual C++ 2010. All information is subject to change.

Contents

The Dining Philosophers
An Actor-Based Approach
A Solution In Five Classes
Message Blocks And Messages
Agents And The Join Message Block
Testing The Philosopher And Displaying State
Implementing The Table Class
Time For Lunch

Enabling C++ developers to write highly concurrent applications is a major focus of Visual Studio 2010. The beta release includes the Concurrency Runtime, parallel libraries, and development tools aimed at addressing several common problems preventing developers from unlocking the performance potential inherent to multicore hardware. Notably, this includes ensuring that developers can identify and take advantage of opportunities for concurrency in their code, productively manage shared state and its side effects, and not having to worry about building low-overhead concurrency infrastructure that is scalable at run time on a variety of hardware.

In this article, I'm going to demonstrate how to use the new Asynchronous Agents Library included as part of Visual C++ 2010 to manage the difficulties that can arise with shared state. To show you how this works, I will walk through an implementation of a classic concurrency problem: Djikstra's Dining Philosophers. You'll see how the actor-based programming construct of an agent in combination with asynchronous message-passing APIs can be used to provide a correct and easy to understand solution to this problem that doesn't rely directly on threading or synchronization primitives.

The Dining Philosophers

For those who aren't familiar with it, the Dining Philosophers problem is intended to illustrate the complexities of managing shared state in a multithreaded environment. Here's the problem:

At a round table sit five philosophers who alternate between thinking and eating from a large bowl of rice at random intervals. Unfortunately for the philosophers, there are only five chopsticks at the table (see Figure 1), and before the philosophers can begin eating, they must acquire a pair of chopsticks. Since the chopsticks are shared between the philosophers, access to the chopsticks must be protected, but if care isn't taken, concurrency problems arise. Most notably, starvation (pun intended) via deadlock can occur: if each philosopher picks up a chopstick as soon as it is available and waits indefinitely for the other, eventually they will all end up holding only one chopstick with no chance of acquiring another.

Figure 1 The Philosophers and Chopsticks

The Dining Philosophers problem is typically represented in code by a thread for each philosopher and some form of shared state used to represent each of the chopsticks. Straightforward solutions to this problem often involve introducing a waiter entity to coordinate access to the chopsticks, introducing lock ordering heuristics, and manually working with threading APIs, critical sections, semaphores, or monitors to manage the state.

Most developers will agree that building correct, nontrivial locking is considered challenging and fragile at best. As a result, most implementations of the Dining Philosophers problem tend to have implementation details leaked into them. For example, the Philosophers may be aware of the synchronization primitives or of their neighbors' chopsticks. This becomes particularly problematic if you want to generalize the problem to an arbitrary number of philosophers or refocus an implementation on the problem domain—such as what each philosopher does—rather than focusing on the synchronization and threading primitives.

An Actor-Based Approach

Let's walk through a design that is built on top of the Asynchronous Agents Library. Dining Philosophers really only has two moderately difficult sections: creating a thread for each philosopher to run in and coordinating the philosophers' access to the chopsticks. The Asynchronous Agents Library provides an actor-based programming model and asynchronous message passing APIs, and you'll need both of these in the implementation.

In the Asynchronous Agents Library, the agent class models an actor pattern and provides an asynchronous run method. I use an agent for each philosopher and take advantage of the run method to fulfill the requirement of each philosopher running in its own thread.

The second portion of a correct solution involves managing concurrent access to the chopsticks and, in contrast to traditional solutions using semaphores or locks, I'll use the message passing APIs in the Asynchronous Agents Library to move the chopsticks between the philosophers' hands and the table.

As each philosopher transitions between thinking and eating, he picks up the chopsticks and returns them to the table by sending messages. You'll see that in addition to providing some abstraction on top of threads and shared state, this will also allow the implementation to stay more focused on the domain of the problem than other solutions enable.

A Solution In Five Classes

The basic design is going to use five types:

• A Chopstick class that is relatively self explanatory.
• A ChopstickProvider class that will be used to hold the chopsticks on the table and provide them to the philosophers.
• A Philosopher class that is responsible for thinking and eating and is aware only of its two ChopstickProviders.
• A PhilospherState enum that can be thinking or eating.
• A Table class that contains a set of Philosophers and a set of Chopsticks. Table is responsible for setting the table by placing a single Chopstick in a ChopstickProvider between each Philosopher. Figure 2shows the relationships between the classes.

Figure 2 Classes Used In The Dining Philosophers Solution

Let's start with the simplest class: Chopstick. The purpose of the Chopstick is to simply exist as a chopstick and be able to identify itself. As a result, the implementation is a simple class that has an identifier member variable, a constructor that initializes the identifier, and a method to return the identifier.

class Chopstick { const std::string m_Id; public: Chopstick(std::string && Id): m_Id(Id) {}; const std::string GetID() { return m_Id; }; };

It's important to note that the identifier field m_Id is a const member variable. I don't want the chopstick to have any state on its own that can get changed accidentally by another thread. Also notice that the constructor is using an r-value reference in its parameter list (the &&). This is a new language construct in Visual Studio 2010 that is part of the draft C++0x standard. An r-value reference here allows the compiler to avoid a copy constructor call and move Id into m_Id within the Chopstick instance if Id is a temporary variable or r-value.

Message Blocks And Messages

ChopstickProvider is also straightforward. It can be thought of as a storage buffer whose purpose is to accept Chopsticks when they are sent to it and to provide Chopsticks to a Philosopher upon request.

Here's the first place where I use the agent APIs. I use what's known as a message block for the ChopstickProvider. A message block is defined as a class that is able to send and receive messages. More specifically, if you're able to send a message to message block, the block is referred to as a target and, if you're able to receive a message from a message block, it's referred to as a source.

In this example, I'll need the ChopstickProvider to be both a source and a target because the Philosophers will be both receiving chopsticks from the ChopstickProviders when the Philosophers are hungry and sending them back to the ChopstickProviders when the Philosophers are ready to think again. Here's an example of putting them to work:

//create a chopstick Chopstick chopstick("chopstick one"); //create a ChopstickProvider to store the chopstick ChopstickProvider chopstickBuffer; //put the chopstick in the chopstick holder Concurrency::send(chopstickBuffer, & chopstick); //request a chopstick from the chopstick buffer Chopstick * result = Concurrency::receive(chopstickBuffer);

You can see that, after declaring a chopstick and a chopstickBuffer (an instance of the still undefined ChopstickProvider), Concurrency::send is used to place the address of chopstick into the ChopstickBuffer and Concurrency::receive returns a pointer to a Chopstick from the chopstickBuffer. Concurrency::send is a template method that synchronously places a message in a message block. Concurrency::receive is a template method that returns a message from a message block. Concurrency::receive blocks until a message is available in the message block.

The Asynchronous Agents Library also provides Concurrency::asend and Concurrency::try_receive. Concurrency::asend asynchronously spawns a task to send the message without waiting for acknowledgement of receipt. Concurrency::try_receive is a non-blocking call that will acquire a message if one is available.

Now let's actually define the ChopstickProvider. Remember I said it was straightforward? It's a typedef:

typedef Concurrency::unbounded_buffer<Chopstick*> ChopstickProvider;

The agents library provides a message block called the unbounded_buffer that has the functionality you need. An unbounded_buffer is a template class that is both a source and a target. It stores a memory-limited number of messages in an internal queue. Messages are removed from the queue when they are requested. You won't need the unbounded quality in this implementation of Dining Philosophers as there is a limited number of chopsticks that will be moving between each chopstick holder. The key functionality you're interested in from the unbounded_buffer is its move semantics.

Agents And The Join Message Block

Now let's take a look at implementing the Philosopher class. This is the interesting portion of the Dining Philosophers problem, where you ensure that each philosopher is running on its own thread and that access to the shared resource is coordinated appropriately. The Philosopher class will use two additional constructs from the Asynchronous Agents Library, the abstract agent class and the join construct. First I'm going to describe the agent and how it's used.

The agent class is an abstract class that models what is sometimes referred to as an actor pattern or actor-based programming. Agents are intended to be used to facilitate removing dependencies and shared state between active components of an application by having the agents encapsulate state and communicate with each other solely via message passing through a small set of public interfaces. This sounds more complicated than it is, but hopefully you can see the similarities to the Philosopher class.

As I mentioned earlier, the Philosopher class needs to be running on its own thread. Translating this to the terminology of agents this means it needs to be an active task, so Philosopher is going to derive publicly from Concurrency::agent. The Philosopher class also needs to be aware of two ChopstickProviders (one for each hand) and then use them to transition successfully between thinking and eating. The Philosopher class isn't complete yet, but you can see how this is starting to translate into a class synopsis:

enum PhilosopherState { Thinking, Eating }; typedef Concurrency::unbounded_buffer < Chopstick * > ChopstickProvider; class Philosopher: public Concurrency::agent { ChopstickProvider * m_LeftChopstickProvider; ChopstickProvider * m_RightChopstickProvider; public: const std::string m_Name; const int m_Bites; Philosopher(const std::string && name, int bites = 500): m_Name(name), m_Bites(bites) {};... }

Philosopher has a pointer to two ChopstickProviders, a name, the number of bites or turns the Philosopher will take, and a constructor for initialization.

What is missing, though, is a way to initialize the ChopstickProviders in the agent. You don't want to initialize them at construction time because the Philosophers are independent from the Chopsticks and their ChopstickProviders. You could create an additional public method like AssignChopsticks (ChopstickProvider* left, ChopstickProvider* right), but then you would have to take some care—or a lock—to ensure that this method is thread safe.

Instead, I'm going to create a public interface so that the ChopstickProviders can be assigned asynchronously. I do this by adding two more public unbounded_buffer member variables and use these to send the Philosophers two ChopstickProviders:

Concurrency::unbounded_buffer<ChopstickProvider*> LeftChopstickProviderBuffer; Concurrency::unbounded_buffer<ChopstickProvider*> RightChopstickProviderBuffer;

Now I'm ready to start implementing the Philosopher method that will run in its own thread, wait for the ChopstickProviders to be initialized, and then start alternating between thinking and eating. I implement the virtual run method from the agent base class. agent::run will be started in its own task when a call to agent::start is made.

void run() {

The first thing I need to do inside run is initialize the ChopstickProviders by waiting for messages to be sent on the public methods with receive:

//initialize the ChopstickProviders m_LeftChopstickProvider = Concurrency::receive(LeftChopstickProviderBuffer); m_RightChopstickProvider = Concurrency::receive(RightChopstickProviderBuffer);

Now I need to transition between thinking and eating. To do this I'm going to use two additional methods, PickupChopsticks and PutDownChopsticks:

for (int i = 0; i < m_Bites; ++i) { Think(); std::vector < Chopstick * > chopsticks(PickupChopsticks()); Eat(); PutDownChopsticks(chopsticks); }

The only thing remaining to implement in the run method is to clean up by returning the ChopstickProviders so that they can be reused if needed, and to set the agent status to done.

Concurrency::send(LeftChopstickProviderBuffer, m_LeftChopstickProvider); Concurrency::send(RightChopstickProviderBuffer, m_RightChopstickProvider); this -> done(Concurrency::agent_done); }

Moving on, the additional methods Eat and Think are straightforward. In the original problem they are described as random spin loops:

private: void Eat() { RandomSpin(); }; void Think() { RandomSpin(); }; };

Implementing PickupChopsticks is significantly more interesting because it manages acquiring and releasing the chopsticks without introducing deadlocks or race conditions. To implement this I'm going to use another messaging block from the Asynchronous Agents Library called join. Concurrency::join is a message block that waits for messages from multiple sources, potentially of varying types. Once all messages have been received, it produces a conglomerate message. A join can support sources of the same or multiple types and will acquire messages in a greedy or non-greedy manner. This means that there are four variants of join in the agents library. The Philosopher class will use a single-type non-greedy join. Figure 3shows a simple example of a join in code.

Figure 3 A Simple Join

//create two chopsticks Chopstick chopstick1("chopstick one"); Chopstick chopstick2("chopstick two"); //create ChopstickProviders to store the chopstick ChopstickProvider chopstickBuffer1; ChopstickProvider chopstickBuffer2; //put a chopstick in each chopstick holder Concurrency::send(chopstickBuffer1, & chopstick1); Concurrency::send(chopstickBuffer2, & chopstick2); //declare a single-type non greedy join to acquire them. //the constructor parameter is the number of inputs Concurrency::join < Chopstick * , non_greedy > j(2); //connect the chopstick providers to the join so that messages //sent will propagate forwards chopstickBuffer1.link_target( & j); chopstickBuffer2.link_target( & j); //the single type join message block produces a vector of Chopsticks std::vector < Chopstick * > result = Concurrency::receive(j);

Now I'm ready to implement PickupChopsticks. The first thing to notice is that you return a set of chopsticks by returning a vector. To get a pair of chopsticks from the chopstick provider means using a non-greedy join. The non-greedy variant of join waits for an offer of messages from all linked sources, and then, once it has an offer from each source, confirms that it can actually take ownership of the message. This is what prevents deadlock in this example. If I had used greedy as the template parameter for the join, the message would be taken as soon as an offer is made, and sooner or later each Philosopher would have a single chopstick and they would all be deadlocked.

Here's the code for PickupChopsticks. I create a join, link it to the chopstick providers, and wait for the chopsticks to arrive:

std::vector < Chopstick * > PickupChopsticks() { //create the join Concurrency::join < Chopstick * , Concurrency::non_greedy > j(2); m_LeftChopstickProvider -> link_target( & j); m_RightChopstickProvider -> link_target( & j); //pickup the chopsticks return Concurrency::receive (j); }

Implementing PutDownChopsticks is straightforward as well. All I need to do is return the chopsticks that I've acquired from the vector using the asynchronous method asend:

void PutDownChopsticks(std::vector <Chopstick*>& v) { Concurrency::asend(m_LeftChopstickProvider, v[0]); Concurrency::asend(m_RightChopstickProvider, v[1]); };

Testing The Philosopher And Displaying State

The Philosopher class can be used as is, but you need to understand how to start the Philosopher class and have a way of reporting on its status—whether it is eating or thinking.

To start the philosopher, call the agent::start method, which spawns a task that invokes the virtual run method. To report on the status, I introduce two more message blocks from the agents library: Concurrency::overwrite_buffer and Concurrency::call.

Concurrency::overwite_buffer<T> is a message block that stores a single value that can be overwritten, and it produces a copy of the value when requested. As with the other message blocks, overwrite_buffer can be linked to additional targets, and message propagation happens in order. I'll add a public member variable to the Philosopher class that is an overwrite_buffer<PhilosopherState> and update it by sending messages to it as the Philosopher transitions from Thinking to Eating. Specifically, this will involve adding a member variable to the Philosopher class:

Concurrency::overwrite_buffer<PhilosopherState> CurrentState;

It also means modifying Eat and Think to update status:

void Eat() { send(&CurrentState, PhilosopherState::Eating); RandomSpin(); }; void Think() { send(&CurrentState, PhilosopherState::Thinking); RandomSpin(); };

Concurrency::call<T> is a message block that is constructed with a functor and spawns a task to execute the functor when it receives the message. You can use the call in combination with the newly defined overwrite_buffer on the Philosopher to report on its state, as shown in Figure 4.

Figure 4 Reporting Philosopher State

//create an instance of a Philosopher and have it take 5 bites Philosopher Descartes("Descartres",5); //create a pair of chopsticks Chopstick chopstick1("chopstick1"); Chopstick chopstick2("chopstick2"); //create a pair of ChopstickProviders ChopstickProvider chopstickBuffer1; ChopstickProvider chopstickBuffer2; //associate our chopstick providers with Descartes Concurrency::send(&Descartes.LeftChopstickProvider, chopstickBuffer1); Concurrency::send(&Descartes.RightChopstickProvider, chopstickBuffer2); //start the Philosopher asynchronously agent::start( & Descartes); //declare a call that will be used to display the philosophers state //note this is using a C++0x lambda Concurrency::call < PhilosopherState > display([](PhilosopherState state) { if (state == Eating) std::cout << "eating\n"; else std::cout << "thinking\n"; }); //link the call to the status buffer on our Philosopher Descartes.CurrentState.link_target(&display); //start our Philosopher eating / thinking by sending chopsticks asend(&chopstickBuffer1,&chopstick1); asend(&chopstickBuffer2,&chopstick2);

And that's it for the Philosopher class.

Implementing The Table Class

You've already seen everything needed to create the Table class. As mentioned previously, it will contain a set of Philosophers, a set of Chopsticks, and a set of ChopstickProviders. The Table will be responsible for seating the Philosophers at the table, placing a ChopstickProvider between each of them, and placing a Chopstick in each of the ChopstickProviders. For flexibility I've chosen to make it a template class, and it contains a reference to a list of Philosophers, a vector of Chopsticks, and a vector of Chopstick Holders.

template < class PhilosopherList > class Table { PhilosopherList & m_Philosophers; std::vector < ChopstickProvider * > m_ChopstickProviders; std::vector < Chopstick * > m_Chopsticks; ...

The only public method in the Table class is the constructor, which initializes the vectors and assigns ChopstickProviders to each Philosopher (see Figure 5).

Figure 5 Table Constructor

Table(PhilosopherList & philosophers): m_Philosophers(philosophers) { //fill the chopstick and the chopstick holder vectors for (size_t i = 0; i < m_Philosophers.size(); ++i) { m_ChopstickProviders.push_back(new ChopstickProvider()); m_Chopsticks.push_back(new Chopstick("chopstick")); //put the chopsticks in the chopstick providers send(m_ChopstickProviders[i], m_Chopsticks[i]); } //assign the philosophers to their spots for (size_t leftIndex = 0; leftIndex < m_Philosophers.size(); ++leftIndex) { //calculate the rightIndex int rightIndex = (leftIndex + 1) % m_Philosophers.size(); //send the left & right chopstick provider to the appropriate Philosopher Concurrency::asend(& m_Philosophers[leftIndex].LeftChopstickProviderBuffer, m_ChopstickProviders[leftIndex]); Concurrency::asend(& m_Philosophers[leftIndex].RightChopstickProviderBuffer, m_ChopstickProviders[rightIndex]); } }~Table() { m_ChopstickProviders.clear(); m_Chopsticks.clear(); }

Time For Lunch

Finally, to implement main, I need to declare the list of Philosophers, create a Table, start the Philosophers, hook up a reporting mechanism, and wait for them to eat (see Figure 6).

Figure 6 Mealtime

int main() { //create a set of Philosophers using the tr1 array std::tr1::array<Philosopher,5> philosophers = { "Socrates", "Descartes", "Nietzsche", "Sartre", "Amdahl" }; Table <std::tr1::array<Philosopher,5>> Table(philosophers); //create a list of call blocks to display std::vector <Concurrency::call<PhilosopherState>*> displays; //start the Philosophers and create display item std::for_each(philosophers.begin(), philosophers.end(), [&displays](Philosopher & cur) { //create a new call block to display the status Concurrency::call <PhilosopherState>* consoleDisplayBlock = new Concurrency::call<PhilosopherState>([&](PhilosopherState in ) { //cout isn't threadsafe between each output if (in == Eating) std::cout << cur.m_Name << " is eating\n"; else std::cout << cur.m_Name << " is thinking\n"; }); //link up the display and store it in a vector cur.CurrentState.link_target(consoleDisplayBlock); displays.push_back(consoleDisplayBlock); //and start the agent cur.start(); }); //wait for them to complete std::for_each(philosophers.begin(), philosophers.end(), [](Philosopher& cur) { cur.wait(&cur); }); displays.clear(); return 1; };

Hopefully, it's clear how the agent class and asynchronous message passing that the Asynchronous Agents Library provides can help avoid the difficulties of coordinating access to shared state. I've managed to implement the Dining Philosophers problem without using a single explicit lock and without having to call any threading APIs directly. I've also managed to keep the implementation within the terms of the domain—specifically, I've spent time working with Chopsticks, Philosophers, and Tables as opposed to arrays of integers and semaphores.

What I haven't done yet is added any inherent scalability to the Philosophers. This application as written won't run significantly faster on any more than four cores. But this can be fixed by replacing RandomSpin with something more meaningful, like an algorithm implemented with task-based parallelism using the Parallel Pattern Library (PPL). I encourage you to read about this on the native concurrency blog, where I've got the source code for this article, but where I've also added a few fine-grained parallel thinking algorithms implemented to demonstrate composability between the PPL and the agents library. I've also used the Concurrency Runtime's resource management features to manage the quality of service issues that can arise with an abundance of parallel work. When processing resources get scarce, I can ensure that the Philosophers still are able to get enough to eat.

Send your questions and comments to mmsync@microsoft.com.

Rick Molloy is a Program Manager on the Parallel Computing Platform team at Microsoft.