Question 6: Conferencing researchers
There are 10 researchers attending a conference. At the conference, the researchers either eat or think. To eat they need a bowl, a fork, and a knife. To think, they need a notepad and a pen.
The conference has only 1 bowl, fork, knife, notepad, and pen because the conference organizers were not able to get sponsors. Clearly, at any point in time, a maximum of 1 researcher can eat and a maximum of 1 researcher can think.
The organizers want to ensure that at any point in time, at least 1 researcher is eating and 1 researcher is thinking. For example, they want to avoid a situation wherein researcher 1 has the bowl, researcher 2 has the fork, researcher 3 has the knife, researcher 4 has the notepad, researcher 5 has the pen, and researchers 6-10 have nothing.
Can you suggest a mechanism to ensure this?
Solution
This is a variant of the dining philosophers problem. There are different solutions to this problem. The one I prefer (for its simplicity) uses resource ordering.
If we can impose an ordering on the resources (bowl, fork, knife, notepad, pen) and require the researchers to acquire locks on the resources in order, we can avoid deadlocks. In this scenario, we need the following orders:
- bowl, fork, knife
- notepad, pen
Researchers that want to eat need to acquire bowl, fork, and knife in that order. If they are not able to acquire them in order, they are supposed to give up trying to eat. This ensures that one of the researchers (the one that acquired the bowl first) would be able to acquire all the resources and eat. This researcher can then release the locks on all the three, and another researcher would be able to acquire all three.
Similarly, if a researcher wants to think, they need to acquire notepad and pen in that order. Only one of the researcher (the one who acquires the notepad first) would be able to acquire both and think.
There is the question of what if a researcher dies (morbid, I know, but we aren't actually talking about human researchers here, just some threads and processes :)) while holding a resource. Well, that requires using fault tolerant locks.