CSE 451

Introduction to Operating Systems

Spring 1999



Problem Set #4

Due: In class or via email, Monday May 17, 10:20 A.M.

1. Consider the dining philosophers' problem and the semaphore solution given in class or in Figure 6.17, page 176, of the text. Describe how an ordered resource policy, e.g., Section 7.4.4 of text, can be employed to avoid deadlock. Give a deadlock-free semaphore solution that uses this policy

2. Consider the specifications for Program #2. Remove the restriction 1 (i) on the Executer thread; that is, a job is now removed from the Bounded_Buffer if one is there.

(a) Prove that the Executers can not deadlock on the storage resource.  Show how an Executer could starve on the storage resource.
(b) Remove the restriction as we did in (a). Suppose further that each  Run_User_Job phase is now a sequence:

(Get_Storage Compute Get_Storage Compute . . . Compute) Release_Storage.
Get_Storage obtains one or more blocks of storage. Release_Storage returns all of the blocks previously obtained. Show how deadlock could occur in this variation of the system. Use the graph representations discussed in class.

3. A subsystem has two processes, p and q, and two resources, R1 and R2, each with two units. p has a maximum claim or need for 1 unit of R1 and 2 units of R2. q has a maximum claim of 2 units of R1 and 1 unit of R2.  Exhibit a non-deadlocked state of the subsystem having outstanding but immediately satisfiable request(s) for p and/or q, that would not be granted by the banker's algorithm. Show how deadlock could result if the banker's algorithm were not used in your example.



cse451-webmaster@cs.washington.edu