COS 318: Operating Systems, Fall 2013

Quiz 3: CPU Scheduling and Deadlocks

Due: 11:55pm, Wednesday, October 16

This quiz checks your understanding of the lectures and reading assignments during the past week. You may reference the textbook, lecture slides, and your notes. Online sites (e.g., Wikipedia) may also be consulted but you must cite them in your writeup.

Please strive for clarity and brevity in your answers. Essay questions should require no more than one short paragraph.

Submit your answers by clicking the "submit" link on the lecture schedule page. Only online submissions will be accepted. Please submit plain ASCII text files.

Questions:

    Job Arrival Time Duration Priority
    P1 0 6 2
    P2 2 8 5
    P3 4 7 7
    P4 7 3 1

  1. Recall that a job's Response Time is the time elapsed between its arrival in the system and its completion time. Given the workload in the table above, calculate the Average Response Time for the following CPU scheduling policies. Assume that, once a job starts to run, it does not yield or block; also, higher numbers mean higher priority. Show your calculations. (5 points)

    1. FCFS

      2. Answer: P1@6, P2@14, P3@21, P4@24. (6+(14-2)+(21-4)+(24-7))/4 = 13

    2. STCF (i.e., non-preemptive)

      3. Answer: P1@6, P3@13, P4@16, P2@24. (6+(13-4)+(16-7)+(24-2))/4 = 11.5

    3. SRTCF (i.e., preemptive)

      4. Answer: P1@6, P4@10, P3@16, P2@24. (6+(10-7)+(16-4)+(24-2))/4 = 10.75

    4. Non-preemptive priority scheduling

      5. Answer: Since the scheduler is nonpreemptive, a job with lower priority will continue running when a higher priority job enters the system.

      P1@6, P3@13, P2@21, P4@24. (6+(13-4)+(21-2)+(24-7))/4 = 12.75

    5. Preemptive priority scheduling

      6. Answer: P3@11, P2@17, P1@21, P4@24. ((11-4)+(17-2)+(21-0)+(24-7))/4 = 15

  2. If a system has a resource deadlock, is it possible that a process can be deadlocked yet not belong to a circular chain in the system’s resource allocation graph? Assume that the resource graph contains no resources with multiple instances. If no, explain why not. If yes, give an example showing how this could occur. (2 points)

    3. Answer: Yes, it is possible. Process A holds the resource R1 and needs the resource R2, process B holds the resource R2 and needs the resource R1. Thus, processes A and B create a circular chain. Process C needs resource R1. Process C is deadlocked because it is waiting on Process A to release the resource R1, but it will not happen because of deadlock (i.e., the circular chain between A and B).

  3. A system is deadlock-free if there is no sequence of events that can lead to a deadlock. Consider a system with four identical resources. In this system there are N processes and each process needs at most M of the resources. For the values of M and N given below, is the system deadlock-free? In each case, state why or why not. (4 points)

    1. Two processes, each needing at most three resources

      2. Answer: No. If each process holds two resources, there are no more available. Then each process could request the third resource and there would be a deadlock

    2. Three processes, each needing at most two resources

      3. Answer: Yes. Proof by contradiction. Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and therefore it can run to completion and return its resources when done.