1. A colleague of yours finds the banker's algorithm too complicated and has created a simpler variant: when a process asks for an resource allocation, the modified banker's algorithm ignores the process's requested resource amount and returns the process's specified maximum resource allocation. Does the modified banker's algorithm avoid deadlock? If so, explain why; if not, give a counter-example.

   You may assume the standard resource-allocation model.

   ---

   The modified banker's algorithm avoids deadlock. The modified banker's algorithm can satisfy at least one maximum request, so the first process to make a request gets its resources and can continue execution. That process will eventually return its resources, which can then be allocated to some other process. The modified banker's algorithm may delay processes unnecessarily, but it won't deadlock them.

   ---

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. Use resource-trajectory graphs to determine if processes managed by sequential batch scheduler might suffer from deadlock.

   ---

   A sequential batch scheduler executes one program after another, waiting until the currently executing process ends before starting the next process; that is, a sequential batch scheduler implements mono-programming.

   Because each process ends before the next begins, the trajectory of each process parallels the axis associated with the process, depending on which process runs first. These trajectories avoid all possible forbidden regions, and sequential batch scheduling avoids deadlock.

   ---

This page last modified on 7 November 2000.