1. A computing system runs at most n process at a time, and each process needs at most two tape drives. What is the minimum number of tape drives required by the computing system to avoid deadlock? Explain.

   ---

   n + 1 tape drives. With n' <= n tape drives, n' process could each request one tape drive, which they would receive, and then request the other tape drive, which would deadlock all n' processes. With n + 1 tape drives, there would always be a tape drive available to satisfy the second request for at least one process, which avoids deadlock.

   ---

2. Suppose a terminal controller has neither DMA hardware nor interrupt-generating hardware. Describe how a terminal driver would implement a write operation using such a controller.

   Assume the controller presents an register-based terminal interface similar to that in the project simulator. You may use pseudo-code to present the general idea; don't go into details.

   ---

   The driver would use polling:

   while string != end-of-string
     tty-data-register = *string++
     tty-control-register = write
     while true 
       sleep(10)
       if tty-status-register == done
         break
   

   ---

3. Let R be a sequence of disk I-O requests. Let A_FCFS be the average disk arm motion when servicing R using first come, first serve (FCFS) scheduling. Let A_E be the average disk-arm motion when servicing R using elevator scheduling. Is it ever possible that A_FCFS < A_E? Explain.

   You may assume that the disk arm starts at cylinder 0 and that any two I-O requests in R involve different cylinders.

   ---

   The average disk-arm motion is the sum of the individual disk arm motions divided by the number of requests (the size of R). Because both scheduling algorithms service the same number of requests, the question reduces to: can the sum of individual disk-arm motions produced by elevator scheduling ever be larger than the sum of individual disk-arm motions produced by FCFS scheduling?

   The easiest way to solve this problem is to draw a picture (see Figures 3-20 and 3-21 in the text). The elevator algorithm orders the requests in R by increasing cylinder order, so the total arm motion for the elevator algorithm is C, the highest cylinder number requested in R.

   Because the disk arm starts at cylinder 0 and must service cylinder C, the total disk-arm motion for FCFS must also be at least C. If R is ordered by increasing cylinders, then the total disk-arm motions for the two schedulers are the same. However, if R has some other order, than the FCFS scheduler must move the disk arm backwards (that is, away from C) at least once, which increases the total disk-arm motion.

   The total disk-arm motion for FCFS can never be less than the total disk-arm motion for elevator scheduling, so it will never be possible to have A_FCFS < A_E.

   ---

4. The resource-trajectory graph assumed a uniprocessor system. Explain how the resource-trajectory graph may change for a dual-processor system.

   ---

   On a uniprocessor, only one process may execute at a time, so any step in the trajectory will be parallel to the axis associated with the executing process. Two processes may run on a dual-processor system, so a single step in the trajectory may parallel two axes simultaneously, resulting in a diagonal line.

   ---

This page last modified on 7 November 2000.