Assignment 7 Solutions

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

  1. Background: On Friday Sept. 28, Octav Chipara gave a guest lecture on his work on sensor networks.

    a) What operating system was the central focus of his talk? (0.2 points)

    TinyOS

    b) What were the primary problems with that operating system? (0.3 points)

    There were two ways to read this question: One asks what problems TinyOS had to solve. These were extremely small memory resources, extreme limits on available power, and an eccentric CPU architecture that prevented multithreaded execution.

    The second reading asks what mistakes the designers of TinyOS made. Perhaps the greatest was in the selection of the eccentric CPU architecture that prevented multithreading.

  2. A problem: Consider the code distributed for MP4. The main program contains the event-processing loop of a discrete-event simulation. The code to process an EVENT_ARRIVE event schedules one or two new events. It always schedules the next EVENT_ARRIVE event, but it only sometimes schedules an EVENT_READY event.

    The notes for lecture 15, about 2/3 of the way down, contain code for a disk interrupt service routine and for a disk-read routine. The former corresponds, in a sense, to the EVENT_READY event, while the latter corresponds, in a similar sense, to the EVENT_ARRIVE event.

    a) Under what conditions does the simulation model schedule an EVENT_READY event. (0.4 points)

    When the disk was idle.

    b) What line of code in the disk-read routine performs an action that is simulated by the scheduling of an EVENT_READY event inside the code for an EVENT_ARRIVE event? (There is exactly one line of analogous code.) (0.4 points)

    When the disk is idle, the activity that causes the disk to wake-up is the code that enables the interrupt enable bit in the disk command register.

  3. Background: Consider two alternative implementions of the cyclic scan disk scheduling algorithm:

    a) Which of the above has a fairness problem when there is always a pending request for one particular cylinder? (0.4 points)

    As described, the array of FIFO queues has a fairness problem because if the queue for some cylinder is never emptied, the scan will never advance to the next cylinder.

    The tree solution does not have this problem because the new requests with disk addresses equal to the current request always go before it in the tree.

    b) In general, the time taken by an interrupt service routine should be strictly bounded. What limits the worst-case interrupt service time in each of the above? The number of cylinders? The number of requests? For each, when does the worst case occur? (0.4 points)

    In the array of queues, the worst-case service time is determined by the number of cylinders, since all of the queues in the array may need to be checked for empty in the case that there is no next request.

    In the tree, the worst case time is determined by the number of pending requests. The more requests, the more work is involved in finding the successor in the tree of the request just dequeued. The average case is O(log n), but the tree could be unbalanced leading to an O(n) dequeue.

  4. Consider a typical Unix-like file system, where directories connect names to i-node numbers, which are, in turn, indices into an i-table stored on disk. The i-table holds one i-node per file, where the i-node contains the disk addresses of the first few sectors of the file plus the address(es) of index sectors holding the addresses of the remaining sectors of the file (needed only for large files). The root of the file system directory is the file with i-number one.

    Ignore the possibility that frequently referenced disk sectors might be held in a cache in RAM. To open a file, the contents of that file's i-node must be read into the open-file data structure.

    a) How many disk accesses are required, at minimum, to open (but neither read nor write) /myfile (0.4 points)

    1. Read the i-node for / (the root of the file system).
    2. Read the first sector of the directory /, containing the entry named myfile.
    3. Read the i-node for /myfile.

    Note: If you are merely opening /myfile without either reading or writing it, there is no reason to read the first sector of the file.

    a) How many disk accesses are required, at minimum, to open and read the first sector of /tmp/myotherfile. (0.5 points)

    1. Read the i-node for / (the root of the file system).
    2. Read the first sector of the directory /, containing the entry named tmp.
    3. Read the i-node for /tmp.
    4. Read the first sector of the directory /tmp, containing the entry named myotherfile.
    5. Read the i-node for /tmp/myotherfile.
    6. Read first sector of /tmp/myotherfile.