CS550 Advanced Operating Systems

Instructor: Xian-He Sun

Department of Computer Science

Homework 4 (Due Date: 3/31/08, Tuesday)

  1. Exercise 4.3 (Text: Tanenbaum and Steen, Prentice Hall v2)
  2. Exercise 4.7 (Text: Tanenbaum and Steen, Prentice Hall v2)
  3. Exercise 4.10 (Text: Tanenbaum and Steen, Prentice Hall v2)
  4. Exercise 4.12 (Text: Tanenbaum and Steen, Prentice Hall v2)
  5. Exercise 4.21 (Text: Tanenbaum and Steen, Prentice Hall v2)
  6. Exercise 5.2 (Text: Tanenbaum and Steen, Prentice Hall v2)
    Would you consider a URL such as http://www.acme.org/index.html to be location independent? What abo ut http://www.acme.nl/index.html?
  7. Exercise 5.5 (Text: Tanenbaum and Steen, Prentice Hall v2)
    Outline an efficient implementation of globally unique identifiers.
  8. Exercise 5.11 (Text: Tanenbaum and Steen, Prentice Hall v2)
    Considering that a two-tiered home-based approach is a specialization of a hierarchical location service, where is the root?
  9. Exercise 5.21 (Text: Tanenbaum and Steen, Prentice Hall v2)
    Consider a distributed file system that uses per-user name spaces. In other words, each user has his own, private name space. Can names from such name spaces be used to share resources between two different users?
  10. Exercise 6.10 (Text: Tanenbaum and Steen, Prentice Hall)
    Consider Fig. 6-14 again. Suppose that the coordinator crashes. Does this always bring the system down? If not, under what circumstances does this happen? Is there any way to avoid the problem and make the system able to tolerate coordinator crashes?
  11. Exercise 6.11 (Text: Tanenbaum and Steen, Prentice Hall)
    Ricart and Agrawala's algorithm has the problem that if a process has crashed and does not reply to a request from another process to enter a critical region, the lack of response will be interpreted as denial of permission. We suggested that all requests be answered immediately, to make it easy to detect crashed processes. Are there any circumstances where even this method is insufficient? Discuss.
  12. Exercise 6.12 (Text: Tanenbaum and Steen, Prentice Hall)
    How do the entries in Fig. 5-17 change if we assume that the algorithms can be implemented on a LAN that supports hardware broadcasts?
  13. Exercise 6.13 (Text: Tanenbaum and Steen, Prentice Hall)
    A distributed system may have multiple, independent critical regions. Imagine that process 0 wants to enter critical region A and process 1 wants to enter critical region B. Can Ricart and Agrawala's algorithm lead to deadlocks? Explain your answer.
  14. Exercise 12.8 (Text: Coulouris, Dollimore, and Kindberg, Addison Wesley)
    In the Bully algorithm, a recovering process starts an election and will become the new coordinator if it has a higher identifier than the current incumbent. Is this a necessary feature of the algorithm?
  15. Answer the question given on slides 23 of lecture 12.
  16. Answer the question given on slides 4 of lecture 13.

    17. Contact Information