Monthly Archives: July 2013

Avian Solution to Producer-Consumer Problem

In the next few blogs, we’ll look at some of the classic thought problems for parallel programming, including the Producer-Consumer problem, the Dining Philosophers problem, and the Barbershop problem. In this blog, we’ll look at the Producer-Consumer problem and see how it becomes a trivial task to solve in the Avian Computing environment using the Concurrency Explorer (ConcX).

Wikipedia describes the Producer-Consumer problem this way, “The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer’s job is to generate a piece of data, put it into the buffer and start again. At the same time, the consumer is consuming the data (i.e., removing it from the buffer) one piece at a time. The problem is to make sure that the producer won’t try to add data into the buffer if it’s full and that the consumer won’t try to remove data from an empty buffer.”

In the simplest ConcX implementation, two birds are created, one named Producer and one named Consumer. One bird, for example, eats Red food and stores Blue food while the other bird eats Blue food and stores Red food. The type of food doesn’t matter, as long as the Producer and Consumer each eat the type of food that the other bird stores.

For this example, the Producer stores a Blue food in the tree and then takes a nap (per the Avian framework). When the Producer awakens, it looks for a Red food, which is provided by the Consumer bird. If it doesn’t find a Red food, it takes a nap for a while (again per the Avian framework).

The Consumer wakes after its nap(s) and finds a Blue food in the tree. It eats (removes) the Blue food, does whatever real-world task would be done, and then stores a Red food in the tree and then takes a nap (per the Avian framework). When it awakens, it looks for Blue food again and, if it doesn’t find it, takes another nap.  The diagram below illustrates the process:

 

ProducerConsumer One may ask how the Producer first stored a Blue food because it cannot store it until it has eaten a Red food and the Consumer cannot store a Red food until it has eaten a Blue food. Several methods can overcome this initial deadlock; the firstTime() method of the Producer bird can be used to create a Blue food or a helperBird can be used that puts a Blue food into the tree the first time; as long as the helperBird doesn’t ever find any of it’s food in the tree, it will exhaust its stamina setting and die.

Once you have it running, you can experiment with various bird parameters to verify that only a single unit is being passed. For example, you can set the nap time of the Producer bird to a high value, such as 5 seconds, and you can watch the results to see that the Consumer bird is waiting until a Blue food finally arrives before it eating it and putting a Red food back in the tree. Or you can reverse the nap times, so the Consumer bird takes a long nap, forcing the Producer bird to wait before it can put another Blue food back into the tree.

Some might argue that this simple solution doesn’t fully address the stated problem since it doesn’t allow multiple food chunks to be stored; instead only one unit of each would be allowed instead of a buffer of them. In Avian Computing, though, the solution described above is an acceptable solution because multiple Producer & Consumer birds can easily be added to the solution.

For example, add Producer1 and Consumer1 that eat Blue1 food and Red1 food; add Producer2 and Consumer2 that eat Blue2 food and Red2 food, and so on. This is in fact one of the strengths of ACE – instead of building buffers and queues and stacks and then deal with their attendant complexities, you can just throw more birds at the problems as required and let them sort it out. You don’t have to know the details of the buffer or stack (FIFO vs LIFO, etc). If one Producer-Consumer pair is insufficient, add another pair and see if that meets the requirements. If not, keep adding more pairs until they meet their requirements. Note that in this example, each Producer-Consumer pair shares exclusively with each other.

An even simpler way of providing a “buffer” exists using the TupleTree as the buffer. Add multiple Producers that all eat Red food and store Blue food and add multiple Consumers with correspondingly opposite diets and then just let them run. All of the complexity of synchronizing access to the buffer (the heart of the original problem) is eliminated by the Avian framework.

Although you could work real hard to set things up to have a specific buffer size, in the real world, this is a totally artificial requirement. The real goal is to share information between independent threads and not have any items dropped or missed or have excess items accumulate, and this is exactly what ConcX does best.

In the Avian Computing environment, the traditional Producer-Consumer problem becomes a non-issue because it represents exactly the model that the ConcX supports, that Linda supports. Something is unavailable until one of the Producer threads makes it available in the tuplespace. Once it is available in the TupleTree, a Consumer bird eats it. It behaves exactly the way that you’d expect of birds in the real world to behave, making it easy to understand and easy to scale up or scale down to meet the requirements.

Here’s a challenge to the traditional Producer-Consumer problem:  modify your proposed solution so an arbitrary number of Producers can produce at various arbitrary rates and provide an arbitrary number of Consumers and have them consume at various arbitrary rates and don’t overrun the buffer and don’t try to get an item from an empty buffer. It’s easy in ConcX.

Avian Solution – Dining Philosophers Problem

In the next few blogs, we’ll look at some of the classic thought problems for parallel programming, including the Producer-Consumer problem, the Dining Philosophers problem, and the Barbershop problem. In this blog, we’ll look at the Dining Philosophers problem and see how it becomes an easy task to solve using the Avian Computing environment and the Concurrency Explorer (ConcX).

diningPhilsThe Dining Philosophers problem has been a classic in parallel programming since the 1980’s when it was first proposed. In this scenario, five philosophers are seated around a table with one fork between them, one fork on their left and one on their right. To eat, they need to get the fork to their left (which is shared with their neighbor on their left) and then get the fork on their right (which is shared with their neighbor on their right). If they don’t have both forks, they can’t eat.

Several solutions have been proposed over the years:

  • Waiter controls who eats
  • Resource hierarchy – forks requested in order
  • Philosophers monitor their neighbors – eat when they are not eating

In ConX, the solution is actually quite simple. All five of the birds are different instances of the same type of Philosopher birds and they all just try to eat, just like in any other Avian scenario. The only differences between each of the philosophers is which forks they try to use to eat. The hardest part of the solution is making sure that each philosopher is trying to access the correct two forks.

In the original Avian solution, a Waiter (helperBird) was used to set the table and put the correct forks out on the table. And conceptually this makes sense because in the real world a waiter really would set the table. Once the Waiter has done his job, he has nothing else to do or eat and eventually starves and dies off.

phil1thumbIn Avian 2.0, the firstTime method is used to have each philosopher try to put out the forks that he cares about (the ones that are at the sides of his own plate) before sitting down. If a fork is already in position between plates, the philosopher does not put out a second. The philosopher then begins to eat whenever both forks are available; if no other philosophers join him, the first one is free to make a pig of himself.

Click on the screenshot and the full size image will show that Aquinas uses Fork1 and Fork2. Burke, sitting next to him, uses Fork2 and Fork3. Chomsky, sitting next to Burke, uses Fork3 and Fork4, and so on.

phil5thumbAs philosophers are added, the contention for forks begins. Each philosopher is trying to get the two forks beside his plate, effectively making him compete with his immediate neighbors for them. Fortunately, this contention is handled easily and automatically in ConcX. Because all five philosophers are based on the Philosopher bird, they are all configured the same so they share forks (and dinner) nicely and all eat about the same amount, moderated by the random lengths of each of their naps.

Each philosopher is set up to need both the left fork AND the right fork; in the above image, Aquinas needs Fork1 and Fork2 to eat. If Aquinas cannot get both forks, he can’t eat so he puts down any fork that he might have. It’s all handled by configuring the behavior of the Philosopher birds. And since the Philosopher bird extends the StdBird just to override two functions, it’s pretty easy to do.

What is extremely interesting in Avian Computing is that once the problem is set up and running, you can adjust parameters and study the effects of the changes. For example, if you reduce the length of time that the philosopher waits before trying to get a fork, will they be better at getting two forks and eat more? It’s easy to try; just stop them and shorten the Nap Length of Aquinas or Diogenes and restart them all and see who eats the most.

In the original Dining Philosophers description, a philosopher who has eaten will then be rejuvenated enough begin speaking at length on a philosophical subject near and dear to his heart before putting down his forks. This can be accomplished by incorporating a mandatory delay into the Philosopher birds; the birds sitting on either side of the speaking philosopher will patiently wait until he finishes speaking before snatching up one of his forks.

What if a sixth philosopher joins them, how will this affect the dinner party? It’s pretty easy to add another philosopher by clicking the Add New Bird button and having the new Philosopher bring another fork. The hard part is setting which philosophers share which forks. Adding 2 or 3 more philosophers is just as easy, as long as you keep straight who uses which fork. How much will the other diners be affected?  Will the philosophers eat less when 9 of them are seated at the table?

What if Aquinas and Chomsky get mad at Bacon and team up and try to prevent Bacon from getting a fork? That could be configured without any problems just by changing which forks they try to get.  What if Bacon got mad and teamed up with Diogenes? Would Emerson be able to “rise above” their pettiness and eat unaffected or would he be affected, even though he wasn’t on either team.

What if one of the philosophers is exceptionally hungry (or greedy)? By shortening his nap times, he’ll eat more frequently, but to the detriment of his neighbors. If they also shorten up their nap times to better compete with the first hungry philosopher, their neighbors will also suffer. The greed of the first philosopher eventually spreads thru all the philosophers seated at the table. And in this state, with every philosopher trying to eat as often as possible, the overall amount that is eaten at the table is reduced because it is so much harder to successfully get both forks.

It is tempting to extend this simple example to society at large and speculate that as long as greed is isolated and not excessive, everyone can eat OK. However, once greed is commonplace, the actual amount eaten as a group goes down because too much time is wasted competing.

Using ConcX, it is much easier to think about a parallel problem than using traditional code methods. It’s also much easier and try out different solutions. It also allows you to explore different possibilities than when using traditional coding approaches. The birds in ConcX map directly to the dining philosophers, so thinking about the Avian model makes it easy to develop a solution (and feed the hungry philosophers).