|
(1) Do this exam on your own. On the first page of your paper, include the honor pledge and sign it: "I have neither given nor received aid on this exam." Any evidence of copying or other forms of collusion will be grounds for failure of this exam. (2) Be brief in your responses. But justify your answers. Without justification I cannot see what you have in mind and I cannot award partial credit. (3) Prepare your responses with a word processing program. (4) These resources may be helpful:
|
Consider again the effects of different schedulers on response time for jobs using a single CPU. For this question, assume that there are 10 jobs to be processed and their service times are 1,2,...,10 respectively. The completion time of a job is the time the job leaves the system (after waiting in the queue and then receiving its service). The response time is the sum of the completion times divided by the number of jobs. The schedule completion time is the completion time of the last job.
Let us add a new distinction. A schedule is preemptive if a job can be interrupted partway through and some other job allowed to use the CPU. The full state of the preempted job is saved so that the job can resume execution later. The effect of preemption is to break a job's execution time into a series of pieces. The Round Robin (RR) scheduler is preemptive, while shortest job first (SJF) and longest job first (LJF) are non-preemptive. For this problem, assume that the switching time of a preemption is zero.
|
(a) What are the response times of SJF, LJF, and RR (for the initial queue 1,2,...,10 and time quantum 1 sec)? (b) Prove that LJF gives the longest response time among non-preemptive schedules. (c) What is the worst case (longest response time) among preemptive schedules? Can it be worse than LJF? Why? (d) Is it possible for a preemptive schedule to give a shorter response time than SJF? Why? (e) Does the response time of RR (with 1 sec time quantum) depend on the initial order of the queue? If so, what initial order gives the worst possible response time? (f) Processor sharing (PS) is a scheduler that acts like RR with time slice approaching 0. At any moment when n jobs are in the queue, all jobs proceed in parallel at 1/n the processor speed. What is the response time of the PS schedule for the given jobs? Does the initial order of the jobs affect response time of PS? (g) Many systems use a multilevel queue (MLQ). Consider a simple case where Level k has time quantum 2**k. Level k has priority over Level k+1. Jobs start in level 0, each receiving time quantum 1; jobs not finishing are preempted and put at Level 1. This is repeated. A job at Level k gets a time quantum 2**k and if it is not finished it is placed at Level k+1. For the initial ordering 1,2,...,10 what is the response time of this MLQ? (h) What conclusions can you draw about the relative merits of preemption versus non-preemption, and about the different scheduling strategies? (i) Schedulers are used in dynamic situations where new jobs of different (and unknown) service times arrive at random. The response time is measured between job arrival and job completion. The simplest scheduler is first in first out (FIFO). What is the benefit of RR over FIFO scheduling in this case? (Hint: consider what happens after a very long job arrives.) (j) What is the benefit of MLQ scheduling when jobs arrive at random? How does MLQ response time compare with RR for very short jobs? Long jobs? Why? |
One way to lock a critical section is with the test-and-set-lock instruction of a CPU. A variable x is used as the lock: x=0 means unlocked and x=1 means locked. The instruction (TSL x) returns the value of x and sets x=1 in one memory cycle. The protocol for locking a critical section is:
A: while (TSL lock) do { }
CRITICAL SECTION
lock=0
Consider a simulation of this protocol on a CPU that has no TSL instruction:
B: if lock=0 then lock=1 else goto B
CRITICAL SECTION
lock=0
Consider also this protocol:
C: if mutex=0 then mutex=1 else goto C
while lock=1 do{ }
lock=1
mutex=0
CRITICAL SECTION
lock=0
A protocol is safe if it allows only one process at a time into the critical section. It is live if a process waiting for entry is guaranteed to eventually gain entry.
|
(a) Show that the protocol A is safe and live. (b) The protocol B permits a race condition that makes it unsafe. Show details of how the bug can cause a failure. (c) Does protocol C repair the bug in B? If so, prove it is safe and live. If not, exhibit a bug. (d) What would happen if a clock interrupt occurred while a process is in the protocol A? Is it still safe? Live? Explain carefully. (d) What would happen if all interrupts were on while a process is in protocol A? Is it still safe? Live? Explain carefully. (e) What would happen if all interrupts were off in protocol A? Is it still safe? Live? Explain carefully. |
One way to implement the interaction between a user process (virtual machine) and an I/O device is outlined by the protocol below based on private semaphores. This is a pseudo-code representation of a protocol for I/O synchronization with private semaphores found in the lecture slides on synchronization.
P[pid]:
do tasks
insert request (pid,a,b,rw,sz) into disk work queue
signal(wq)
wait(pid)
repeat
DiskDaemon:
wait(wq)
(i,a,b,rw,sz) = remove request from disk work queue
STARTIO(a,b,rw,sz)
wait(DiskDaemon)
signal(i)
repeat
Disk:
wait for STARTIO
perform task indicated by parameters
generate DiskComplete interrupt dci
repeat
IH[dci]:
signal(DiskDaemon)
return
In this protocol, P is a process, pid is a process id, work queue holds all requests for disk I/O in a first-in-first-out list, DiskDaemon is a permanent process that manages the interface to the disk, Disk is a hardware device treated like a process, IH is an interrupt handler, wq is a semaphore counting requests in the work queue (initially 0), and STARTIO is the hardware instruction for initiating I/O. The semaphore with index pid is the private semaphore of process pid. A process's private semaphore has initial count 0.
|
(a) Identify all the critical sections of this protocol and say how you would protect them. (b) Construct a timing diagram with one time axis for each process above, showing how a single disk I/O request flows through the system and the delays it may encounter. Use arrows in the diagram to represent messages and signals traveling between processes. Identify all the delays experienced by a request. (c) Is the system as specified free from deadock? If not, how would you repair the protocol? Explain carefully. (d) Speculate: what would be involved in eliminating the DiskDaemon process and simply using a disk device driver program? (e) Some systems attempt a form of SJF scheduling for the disk. The next job chosen from the work queue is the one with the shortest seek time (SSTF). This implies that the DiskDaemon can read the current disk position so that it can calculate the seek time of each request. Outline the modifications to the protocol to accommodate SSTF scheduling. |