Assignment 6, Solutions

Part of the homework for 22C:112, Spring 2012
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  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 ) {
                b->next = NULL;
                if (q->tail == NULL) { /* empty queue detected */
                    q->head = b;
                } else { /* non-empty queue */
                    q->tail->next = b;
                }
                q->tail = b;
    	    out(q->controlreg, in(q->controlreg) | q->iebit )
            }
    

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

    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)

    request * dequeue( diskqueue * q ) {
        /* this assumes that the caller will
           never dequeue from an empty queue. */
        request * i = q->head;
        q->head = i->next;
        if (q->head == NULL) q->TAIL = NULL;
    }
    

    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)

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

    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)

    For example, the queue control block could hold an array of queues, one per cylinder of the disk. Requests would be enqueued in the request queue for the cylinder named in the request, and the disk interrupt service routine would scan the array based on the current cylinder number. To support the elevator algorithm, you also need a current cylinder number (an integer) to tell the interrupt service routine which queue it is currently working on.

  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.

    Problem: 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)

    If the flash memory data transfer is over a potentially slow serial link like USB, it would make sense to use a DMA controller to do the data transfer. If the flash memory is significantly slower than RAM, even if it would be possible to use the CPU to read and write individual words or bytes of the memory, it would make sense to use DMA to move the data so that the CPU can do useful work at RAM speed. If a DMA controller is used to move the data, then an interrupt is the natural way to signal the CPU that a transfer is done.