Operating Systems Take Home Midterm

Notes: There are four questions with equal weight. You are expected to answer them all, working by yourself. You should return the answers on Monday when you come to class. Do not return the questions with your answers.

You must start each answer on a separate sheet, order them by question number, and staple all of your sheets firmly together to make sure that individual sheets cannot get lost. I assume no responsibility for any lost page in your answer. Do NOT bind your answers, and do NOT put inside a folder; just staple your sheets at the upper left corner.

I will be out of town until Monday, so if there is any urgent matter that you need to resolve with me in regards to this test, use your common sense judgment about how to deal with it. If it is such a critical issue that it cannot be resolved without my involvement, it will just have to wait until Monday, and I will consider extending the submission deadline.

Good luck.

Question 1:

We have seen that the message passing mechanism can be used for synchronizing distributed computations. Assuming a blocking receive and non-blocking send with a mailbox, we have seen an algorithm for solving the mutual exclusion problem and another algorithm for solving the bounded-buffer problem.

1. Use these techniques to design, a solution for the readers-writers problem (weak reader-preference).
2. Compare desirability of this solution to a straight implementation of Lamport’s distributed mutual exclusion algorithm, where readers would simply send their read requests to the nearest server whenever they need to read, and writers would implement a distributed mutual exclusion algorithm for writing only. How would read requests be handled in such a system, and what would be the limitations and advantages of the entire mechanism.

Question 2:

In centralized deadlock detection, we have studied a number of special cases, all under the AND model. Suppose the system is expedient, but we have the OR model. In this case:

1. If each resource has a single-unit inventory, what is the sufficient condition for deadlock?
2. If each process can request one unit of some resource at a time (resources may have multiple units of inventory), what is the sufficient condition for deadlock?

Prove your answer in each case.

Question 3:

We studied two algorithms for causally ordering messages in distributed systems: One based on broadcast messages, and one without broadcast messages, based on sending a “history list” of prior messages that the sender of a message is aware of. The second algorithm is significantly more efficient than the first one since it uses far fewer messages. Still, the history lists can get long and waste valuable communication resources. Your task is to improve this algorithm further by removing unnecessary (Pj, Tj) entries from the history list maintained by a site when they are no longer needed. How does a site know that a particular (Pj, Tj) entry is no longer needed?

Question 4:

We have seen a simple algorithm for global state recording, correctness of which depends on the FIFO channels assumption.

1. Give an example to show that the algorithm wouldn’t work correctly if the channels were not FIFO.
2. How would you modify the algorithm so that it still works when communication channels are not FIFO.