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.

Leave a Reply

Your email address will not be published. Required fields are marked *