Last week I met a friend at a restaurant. We had a good talk and managed to catch up on each other lives. After few cups of coffee and numerous glasses of water, it was time for him to leave. Before hitting the road, I decided to visit an “important place”, i.e. the bathrooms. I borrowed the key from the hostess and followed her instructions to the bathrooms which were next door. All went “as planned”, until I tried to exit the bathroom and discovered I was locked inside.
|The Dining Philosophers Problem|
I did have a key to the bathroom, that’s how I got in the first place. But the key proved to be useless in helping me exit the bathroom. As I examined the key hole, I realized that it was blocked from the inside using a small aluminum plate. This was no accident or malfunction… Someone put an effort to block people from using the key while inside the bathrooms.
How did that happen? I certainly couldn’t have locked the bathroom door from the inside. And why would anyone lock the door from the outside? Was I the victim of some potential crime? Was I being kidnapped in broad daylight? Was I detained by the secret service? All sort of weird thoughts rush through your head in moments like that.
Wait… These bathrooms have two stalls, and there were some sounds in the next stall. Someone must have been in the other stall, finished his business before me, left the bathrooms and locked the door behind. Mystery solved. But how do I get out??
Calm down! I ordered myself. Remember there is enough water and air supply to last you a few days… Just think about a possible solution!
I checked to see if there was another possible exit besides the door. The only other opening was a narrow window close to the ceiling. I would have to somehow climb up, break the glass and possibly cut myself. Even then I wasn’t sure I could squeeze through the narrow opening.
“Use your phone!” was my next thought. I should call the restaurant and ask them to send someone over to open the door. All I need is the restaurant phone number… Alas, I carry with me a “regular” phone and there is nothing “smart” about it. Being able to search the Internet from my phone never seemed more important. I took a mental note - “must buy smart phone” – and proceeded.
I dialed my wife’s number - no answer. I dialed home - no answer. I finally dialed my daughter’s number - she picked up. “Listen, I need your help” I said. “I am in the middle of studying for a final exam with a friend” was her answer. “This is urgent” I said. “OK, what do you need?” she replied. “I am locked in a restaurant bathroom. Can you get their number and ask them to bail me out?” I said. “You’re what???” was her response, and I could hear some giggles in the background.
Suddenly I heard some voices behind the door. The knob turned and the restaurant hostess showed up. Turns out she was helping one of the guests find the bathroom. “Thank you!!!” I exclaimed, “You saved me from spending the rest of my days in your bathroom…” The hostess was really sorry and said she didn’t understand how that could have happened. She promised to report the problem to management a.s.a.p.
As I headed home, I was still contemplating the scenario that led to me being locked in the bathroom. Why did anyone bother to block the keyhole from the inside? What were they thinking? I then had an epiphany. It was a “deadlock” problem - a variant of the classical Dining Philosophers Problem, which goes as follows:
“Five silent philosophers sit at a table around a bowl of spaghetti. A fork is placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat. A philosopher can only eat while holding both the fork to the left and the fork to the right. Each philosopher can pick up an adjacent fork, when available, or put a fork he is holding down. The problem is how to design a discipline of behavior (an algorithm) such that each philosopher won't starve.”
If you run scenarios in your mind, you’ll easily find possible deadlocks, whereby one or more philosophers are “stuck” without being able to eat. For example, if each philosopher picks up the fork to their left first, then nobody can gain access to the second fork and they all starve...
“That’s it”, I thought. Someone designed an algorithm for the bathroom but forgot to rule out deadlocks. Here’s what the restaurant must have thought: There are two stalls in the bathroom; if guest A walks in and locks the door behind, guest B can’t access the bathroom; or, a guest might lock himself in and prevent emergency access from the outside.
They came up with a “solution”: simply block access to the lock from the inside… But that created a potential deadlock: Guest A walks in. Guest B walks in after him. Guest A finishes first, exists the bathroom and locks the door behind. Guest B is stuck.
I was guest B!
Oh well. I suppose this incident helped me brush up my knowledge of algorithms and deadlocks . And yes, I should buy a smartphone, just in case…