This fourth lab will get you playing with semaphores in the context of the Dining Philosopher's Problem discussed in class.
This lab will use Python and the Colab Jupyter Notebook environment. First, to give you a bit of exposure to that language and environment, and second, because Python code is highly readable and traceable, which is great for the purposes of this lab.
This lab is an individual deliverable.
Submit your Python Notebook including the answers to the several questions below.
Email me your deliverable before midnight 1 November 2024.
Access the Colab Notebook with the starter code here. If you are unfamiliar with Colab Notebooks, read a short beginner's guide.
In this lab, you'll explore the starter code and add a few "enhancements".
As you will note from the starter code, each philosopher requires two chopsticks to eat, as in the traditional problem. The code also contemplates the availability of chopsticks, one placed between every pair of philosophers, in an amount equal to the number of philosophers.
Run the code a few times and observe the output. Confirm that the chopstick semaphores are working properly.
Let's add another constraint to the problem. The philosophers are in a very cheap restaurant where there is a very low supply of chopsticks. Instead of there being an equal amount of chopsticks and philosophers, available on the table, philosophers must now share a smaller number of chopsticks (i.e. less than 5, but greater than 2), and must request chopsticks from a waiter.
Task A:
Add a “waiter” (a semaphore) to manage the allocation of a fixed number of chopsticks.
Add logic so that as chopsticks become available, the waiter takes control of them and distributes them so that there are never more than the permitted number of chopsticks in use at any point in time.
Modify each philosopher’s behaviour to request permission from the waiter to get a chopstick once hunger arrives.
When chopsticks are unavailable, philosophers must wait until a chopstick is released.
Task B:
Think about how a degree of philosopher starvation may occur in this simulation. Add some code to track how long each philosopher waits before they can eat, and report this once they start eating. Provide a short summary after the simulation.
Hints:
You may want to use a counting semaphore for Task A.
Think carefully about what the critical section is and protect this with waiter mediated access.
To help ensure your solution works, you may want to print a report of the number of available chopsticks, as the simulation proceeds.
The actual amount of code addition/modification required is not significant.
Once you have it working, answer the following questions in a Markdown cell after your code and output:
Run the simulation multiple times with different numbers of philosophers and chopsticks. Record any notable patterns you observe in how often each philosopher gets a chance to eat, and how long they need to wait. Do you notice any potential unfairness?
How might we address any potential unfairness, i.e., ensure that every philosopher gets a fair (i.e. relatively equal) chance to eat?