Last night I had a dream. In my dream, an angel showed me heaven and hell. The first place we went to was a large hall filled with round tables. Around each table were 5 souls. All of them wearing white. The place was quiet and the only sound you can hear are the noise of the chopsticks as each soul eats the spaghetti from his or her plate. The spaghetti was unlimited and placed in a big bowl at the center of each table. The chopsticks were placed in such a way that there is one stick between each plate. No soul can eat unless he or she has taken his or her left and right chopsticks. If a soul is not eating, he or she spends this time thinking.
I asked the angel “What is this place?” The angel said “This is hell.” I asked the angel “But why is this hell? This seems to be a very peaceful place with people doing nothing but eat and think.” Then the angel pointed me to one table and said “What do you see?”. I looked at the table and I saw souls starving but never dying. As I looked closer, I noticed that all of them were able to pick their right chopsticks but not the left chopsticks. Suddenly I realized that many tables have souls starving forever.
I was about to ask the angel why they starved when the angel suddenly showed me another place. People were also wearing white and they also have a bowl of spaghetti at the center of each table. Two things were noticeably different from hell. Each table was inside its own room and there was a waiting area per room that can accommodate 4 souls. There were 5 seats per table, but the maximum number of souls per table was only 4. I observed the entire hall and I did not see a single soul starved. Everyone had a happy look on their face and were either eating or thinking. I asked the angel “What is this place?” The angel said “This is heaven. You can see that there are a maximum of 4 souls per table. A soul that is not seated at the table is in the waiting area.”
Suddenly, I woke up from my dream without any idea of what it means. What could the dream mean? I spent the whole day thinking about it.
Interpretation of the Dream
The chopsticks used by the souls are binary semaphores since no two of them can grab the same stick at any time. To model the behavior of the souls in hell, we need an array of 5 semaphores (chopsticks) and the following algorithm:
#loop forever think() wait(left chopstick) wait(right chopstick) eat() signal(left chopstick) signal(right chopstick)
The figure below shows a round table with 5 plates. The chopsticks are colored green and placed in between the plates. For a soul to eat, he/she should have both chopsticks first.
Since the chopsticks are semaphores, then no two souls can be holding the same chopstick at the same time. To see this, let’s make use of the following properties from the previous post:
1. . For chopstick i, the number of souls holding this chopstick at any time is equal to .
2. . Using this property to compute , we get
Since , then , that is, at most one soul is holding the chopstick i at any given time.
The reason why the souls got starved is because it is possible that all of the souls grabbed their right forks at the same time leaving no single left fork to use.
The setup in heaven is subtly different. Instead of having 5 souls eating on the table at the same time, at least one of them waits for his turn in the waiting area (which is guarded by a room semaphore). To model this, we need an array of 5 semaphores (chopsticks) and a room semaphore initialized to 4. The following is the algorithm used by the souls in heaven:
# loop forever think() wait(room) wait(left chopstick) wait(right chopstick) eat() signal(left chopstick) signal(right chopstick) signal(room)
The diagram below shows a round table inside a room. The plates and chopsticks are arranged as before, but at least one seat is empty as indicated by the red plate corresponding to it. Any soul that is not inside the room is in the waiting area as shown by the stick figure.
Initially, all the souls are in the waiting area and the door to the room is guarded by the room semaphore. Since the initial value of the room semaphore is 4, at most 4 souls can enter the room at a time. Inside the room, the souls take their seats. Since at most 4 souls can be in the room, at least one seat is not taken. No soul is ever left starved in this system. Otherwise, a soul[i] can be blocked in one of three cases:
1. Blocked on his/her left chopstick. This means there is a soul[i-1] to his/her left that is using chopstick[i] as his/her right chopstick. By assumption of progress, this means that soul[i-1] will eventually execute signal(right chopstick). Hence, soul[i] will be able to pickup his/her left chopstick.
2. Blocked on his/her right chopstick. Soul[i] is not able to pick up his/her right chopstick because soul[i+1] is using this chopstick as his/her left chopstick and will never release it until he/she has eaten. But the only way for soul[i+1] to eat is if he/she is able to pick up the right chopstick which, by induction, is also being used by another soul to the right of soul[i+1]. However, since there is at least one seat that is vacant, there is a right chopstick that is not being used by any soul and hence by progress, at least one soul can eat and eventually soul[i] can eat.
3. Blocked from entering the room. If we use a first come first served policy, eventually, all souls can enter the room.
By using an extra locking mechanism, the souls in heaven are infinitely happier than the ones in hell.
* Disclaimer: This is a work of fiction and should not be taken literally aside from it’s algorithmic content. In concurrency literature, this is called the Dining Philosophers problem. For more information, please consult the book “Principles of Concurrent and Distributed Programming” by M. Ben-Ari.