# 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

### FCFS

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

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

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

### SRTCF (i.e., preemptive)

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

### Non-preemptive priority scheduling

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

### Preemptive priority scheduling

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

### 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)

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).

### Two processes, each needing at most three resources

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

### Three processes, each needing at most two resources

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.