Assignment 5, due Feb. 24

On every assignment, write your name legibly as it appears on your University ID and on the class list! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the instructor's mailbox. Never push late work under someone's door!

1. Background: Some archaic operating systems offered a disk interface where I/O requests were explicitly enqueued by users. I/O request blocks were allocated by users (sometimes statically, sometimes as local variables, depending on the user context). To perform I/O, a user would:
   1. Fill the request block with a disk address, buffer address and transfer direction.
   2. Enqueue the request block.
   3. Optionally do other work, possibly enqueue other request blocks.
   4. Wait for this request to be done.

   The routine to enqueue a disk request used reserved linkage fields in the disk request record also enables the disk interrupt, just in case it was disabled because the disk queue had been empty. The identity of the device register and the mask for setting the device-specific interrupt enable bit are stored in the queue control block. Here is a version of enqueue appropriate for simple FIFO disk request queues:

           enqueue( request * b; diskqueue * q ) {
               request->next = NULL;
               if (q->tail == NULL) { /* empty queue detected */
                   q->head = request;
               } else { /* non-empty queue */
                   q->tail->next = request;
               }
               q->tail = request;
   	    out(q->controlreg, in(q->controlreg) | q->iebit )
           }
   

   Note: The above code is modified. The original version of the assignment contained a serious programming error.

   a) Write the corresponding dequeue that can be called from within the disk interrupt service routine. Assume it is called with interrupts disabled globally. In the event that dequeue is applied to an empty queue, it should: i - return NULL and ii - disable the device specific interrupt. Otherwise, it leaves interrupts alone and returns a pointer to the dequeued disk request block. (0.8 points)

   b) Given that the disk interrupt service routine does the dequeue operations from the disk request queue, there are critical sections in the enqueue code that must be protected by turning off the CPU's main interrupt enable bit. Add them in properly using ei() and di() as primitives to enable and disable interrupts. Note that the sequence ei();di() makes sense when there are two consecutive critical sections involving unrelated subjects. (0.7 points)

   c) To support a simple FIFO queue, there is a pair of pointers in each queue control block, q->head and q->tail. What change would you make to the queue control block data structure if you wanted to use the elevator algorithm for disk scheduling? (0.8 points)

2. Background: Suppose you had a mature operating system that worked well with rotating magnetic disk memory, and you wanted to replace the disk with flash memory technology. Explain why it might or might not make sense to continue using interrupt driven I/O in this context, and if interrupts are still useful, whether there is any reason to do disk scheduling. (0.7 points)