Your answers should be submitted as a plain text file hw04.txt, a postscript file hw04.ps, or a PDF file hw04.pdf. Please use these filenames!

1. The Dining Savages. A tribe of savages eats communal dinners from a large pot that can hold M servings of stewed missionary. When a savage wants to eat, he helps himself from the pot, unless it is empty. If the pot is empty, the savage wakes up the cook and then waits until the cook has refilled the pot. The behavior of the savages and cook is defined by the following processes:

   Savage_i: while (1) { get serving from pot; eat; }
   Cook: while (1) { sleep; put M servings in pot; }

   Develop psuedocode (along the lines of the in-class Sleeping Barber solution) for the actions of the savages and the cook. Use semaphores for synchronization. You may assume the semaphores are fair. Your solution should avoid deadlock and awaken the cook only when the pot is empty. (10 points)

2. Show that semaphores and monitors are equivalent (show how to implement each using the other). (5 points)