Algorithmic Problems
The practice of generalizing issues in algorithmic design as “problems” predates the invention of computers. One such example is “The hamiltonian circuits problem” in graph theory which is a generalization of the “traveling salesman problem”. Using the depth first search technique to solve a maze is another.
In 1965 Edsgar W. Dijkstra, of “Dijkstra’s Algorithm” fame (among many other algorithms) proposed a problem to his students about processes competing for access to a computers tape drive in a concurrent system. Tony Hoare, of Quicksort fame, reworked the problem in to what has become known as “The dining philosophers problem.”
The Dining Philosophers
There are five philosophers who spend entire their lives alternating between thinking and easting. They live in a shared living space, which has in the middle of the dining room a circular table with five chairs. The table has a big bowl of spaghetti in the middle. However, there are only five forks available at the table, of which two are required for one philosopher to eat.
Each philosopher spends most of his time thinking. When he gets hungry, he sits down at the table and picks up the two closest forks to him. If a philosopher can pick up both forks, he may eat. After a philosopher finishes eating, he puts down the forks and goes back to thinking.
The problem is to write a concurrent algorithm (multi threaded) to simulate the philosophers in such a way that all philosophers may eat, while avoiding both dead lock and starvation.
Dijkstra’s proposed solution to the problem was to apply what has become known today as the semaphore and the mutex, both of which are central themes in modern concurrent program design.
What? No Chickens?
Sometime later, a programmer named Peter Welch proposed a problem in an effort to draw attention to issues with Javas built in thread handling system in regard to resource starvation. He comedically called his program “Wot!? No Chicken!?”. You can read the original discussion on the Java mailing list, as well as view the source code of the program he wrote to demonstrate it at https://www.cs.kent.ac.uk/projects/ofa/java-threads/0.html
Hungry, Hungry, Programmers.
I have fused both examples together to demonstrate the use of semaphores in concurrent algorithm design in what i call the Hungry Hungry Programmers:
Donald Knuth, Robert Sedgewick, Tony Hoare, Nicholas Wirth, and Edsgar Dijkstra have all congregated on the distinguished campus of Plattsburgh State University in upstate New York, USA. They have been tasked with writing a program of critical importance require millions of lines of code that only masters such as themselves could produce. A long debate ensued in which language they would use to develope this mission critical program in.
——————————————-INTERLUDE——————————————
Knuth wanted to first build an actual MMIX computer for their project and write the code in MMIX assembly. Reminding everyone of what happened the last time knuth put a project on hold so he could create a technology to do the project in, Robert Sedgewick set to the task of trying to get everyone to see how great java has become. Wirth, of course, wanted to use pascal, or at least Modula-2. Tony Hoare was just glad he was invited at all and kept profusely appologozing to anyone who would listen over the “null reference” thing, especially to Sedgewick, who he knew had a fondness for C and C-like languages. Edsgar Dijkstra flat REFUSED to code in anything but ALGOL, and only ALGOL 60 at that. Wirth could get behind that! But how about Algol W he said? Dijkstra just glared, and replied through gritted teeth: THERE IS ONLY ONE ALGO: 60. So it was settled: Dijkstra had spoken, Hoare was anxiously looking around, Wirth was still mumbling about Pascal, and Knuth and Sedgewick had gotten distracted talking about the amortized running time of a data structure nobody else had even heard of.
—————————BACK TO OUR REGULARLY SCHEDULED PROGRAM—————————-
After a lively discussion, the programmers were all famished, so they decided to retire to Clinton Dining Hall for supper This is when the real problems began: There was five of them, but the chef could only cook four chickens at a time. How could five diners eat without splitting chickens and all get fed?
When in doubt, talk it out
As Dijkstra proposed over 40 years ago, the solution to this problem is the use of semaphores. Semaphores are named for the flags used on naval vessels to send signals to other ships. In terms of concurrent programming, semaphores are used to signal state between processes.
My solution makes extensive use of semaphores in the form of message passing. Seeing as we’re using a restaurant analogy, the diner threads communicate with the restaurant thread through a “waiter” – a function used to track state variables within the restaurant thread, and signal the diner threads of that state.
This can be visualized through the output the program generates:
Robert Sedgewick: I'm Hungry! garcon, one chicken please! waiter: Here you go, there is 3 chickens left. Robert Sedgewick: mmm, yummy! Donald Knuth: I'm Hungry! garcon, one chicken please! waiter: Here you go, there is 2 chickens left. Donald Knuth: mmm, yummy! Nick Wirth: I'm Hungry! garcon, one chicken please! waiter: Here you go, there is 1 chickens left. Nick Wirth: mmm, yummy! The chef is preparing many good chickens Edsgar Dijkstra: I'm Hungry! garcon, one chicken please! waiter: So sorry monsieur, there is no more chicken. But the cook is preparing more!. Edsgar Dijkstra: What!? no chickens!? Fine. I'll write some code while i wait. Edsgar Dijkstra: I'm Hungry! garcon, one chicken please! waiter: Here you go, there is 4 chickens left. Edsgar Dijkstra: mmm, yummy!
As you can see, In this instance Hoare, Sedgewick, Knuth, and Wirth got the first four available chickens. When it came time for Dijkstra to ask for chicken, the waiter had already passed the message to the kitchen that more chicken would be needed, but the chef had not yet completed the cooking process. However, because the message passing had done its job, Dijkstra is placed on a waiting queue, and when the chickens become available, he is the first to be served, in this way we avoid “Resource Starvation” (In Dijkstra’s case, real starvation as well).
Resource Starvation
If we do not implemented a holding queue for requests that occur between running out of chickens, and before the new chciekens are ready, then requests that arrive after the initial unfullfilled request have the opportunity to be served first, and thus entering a cycle of:
diner 1) “can i have chicken?”
Restaurant) Please wait.
diner 2) “can i have chicken?”
Restaurant) Sure
diner 3) “can i have chicken?”
Restaurant) Sure
diner 4) “can i have chicken?”
Restaurant) Sure.
diner 5) “cani have chicken?”
Restaurant) Sure.
diner 1) “NOW, can i have Chicken?”
Restaurant) Please Wait.
In the above scenario, Diner 1 will be continually skipped until either another diner has decided it has had enough chicken and leaves. If the other diners are greedy and never have enough, Diner 1 will never be served.
The Key to Concurrency is Management
Just as any regular restaurant needs a manager to keep the show running, Concurrent programs need strict management. In practice, this is accomplished through the use of Semaphores (message passing), Mutexes, and Queues, in this way resources are doled out as they become available, and threads know when to wait, where to wait, and when to repeat requests.
While this article has barely scratched the surface of concurrent programming, i strongly encourage anyone interested in the topic to study it in detail, as it is both fascinating and rewarding, and in todays world of “Cloud Computing” increasingly important.
If you would like to see my C++ implementation of “Hungry Hungry Programmers” visit my github at:
