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.
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)
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
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.
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).
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)
- Two processes, each needing at most three
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
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.