Computer Science 322
Operating Systems

• Announcements
• Exam recap
• Lab 5 due
• Deadlock
  • Deadlock prevention
  • Deadlock avoidance
    • augmented resource allocation graphs
    • Banker's Algorithm
  • Detection and recovery
• Memory Management
  • Binding time
    • Programming or compile time
    • Load time
    • Execution time
  • Logical vs. Physical Address Space

Due at the start of class, Wednesday, March 31.

Note: this is a larger lecture assignment than most. As such, you should plan to spend more time than usual and expect it to be worth a larger number of points than typical lecture assignments.

Please submit answers to these questions either as a hard copy (typeset or handwritten are OK) or by email to jteresco AT mtholyoke.edu by the start of class. We will discuss these questions at the start of class, so no late submissions are accepted.

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. The only operations permitted on the semaphores are initialization, wait, and signal. You may assume the semaphores are fair. Your solution should avoid deadlock and awaken the cook only when the pot is empty. You do not need to implement C code, just a list of shared variables and pseudocode describing the actions of the savages and the cook.

2. A system has two processes and three identical resources. Each process needs a maximum of two resources. Is deadlock possible? Why or why not?
3. SG&G Exercise 7.11, p. 308
4. SG&G Exercise 7.20, p. 310