Assignment 7, due Oct. 12

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 lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

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)

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

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)

   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)

3. Background: Consider two alternative implementions of the cyclic scan disk scheduling algorithm:
   • The disk request queue is organized as an array of FIFO queues, one per cylinder. Requests are enqueued in the queue selected by the cylinder number in the request. Requests are dequeued from the queue for the current cylinder until it is empty, and then the move is made to the next non-empty cylinder in increasing order.
   • The disk request queue is organized as a lexicographically sorted binary tree. New requests are sorted into the tree just before the item already in the tree with a greater-or-equal linear disk address, and requests are deleted from the tree after they are processed, before moving to the next request in in-order traversal order.

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

   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)

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)

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

Machine Problem IV

Due October 22

Consider the discrete-event simulation model distributed here:
-- http://homepage.cs.uiowa.edu/~dwjones/opsys/hw/mp4.txt

This simulation program models the performance of a disk drive with a random distribution of disk requests for randomly selected disk sectors. Neither the arrival distribution nor the disk disk address distribution are uniform, although neither is particularly realistic.

The simulation, as distributed, uses a FIFO queue for the disk request queue. This is not a good choice. Your goal is to replace the FIFO queue with a decent disk scheduling algorithm such as some variant of the circular scan algorithm. This can (and should) be done by making changes to the section of the program entitled "disk queue" along with any required changes to the queueable fields fo the disk request structure (declared in the code section just before the disk queue section).

You can evaluate the effectiveness of your disk scheduler by observing its impact on the statistics gathered by the disk simulator. A decrease in the average time requests spend in the queue is good, as is a decrease in the worst-case wait and the worst-case queue length.

Your code, in a file called mp4.c should be submitted as usual.

Warning: This is a data-structure intensive programming problem. You will need to, at the very minimum, think seriously in terms of multiple linked lists, and you may need to build binary trees. Plan to spend some time, and plan for serious debugging.