Assignment 6, due Sept. 28

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: First, use man strcmp to read the relevant documentation. Assume that x and y are C string variables (pointers to the first character of a string or almost equivalently arrays of characters) and consider the following two lines of code:

   if (a == b) thing1();
   if (!strcmp(a, b)) thing2();
   

   a) Under what circumstances does the first if statement execute thing1()? (0.4 points)

   b) Under what circumstances does the second if statement execute thing2()? (0.4 points)

2. A problem: Write a shell script that exercises each feature you are required to add to the MUSH shell in MP3. Your goal here is to make your test script as brief as possible, testing each new feature (aside from the required comments) just once. Aside from the new built-in commands you should be able to do this by launching /bin/echo and perhaps also /bin/tcsh -c "echo $arg". The latter can be used to test if environment variables are correctly passed to applicationsthe shell; try man tcsh for help. Please document the expected output of your test script in comments in the script. (0.7 points)

3. Background: A linearized disk address is one where the sectors of a disk are numbered consecutively from 0 up to the number of sectors on the disk. Consider a disk with 2 sectors per track, 2 surfaces, and 2 cylinders (just big enough to illustrate the alternatives). This has 8 sectors, total, and we could linearize them as follows:
   0. surface 0, cylinder 0, sector 0
   1. surface 1, cylinder 0, sector 0
   2. surface 0, cylinder 1, sector 0
   3. surface 1, cylinder 1, sector 0
   4. surface 0, cylinder 0, sector 1
   5. surface 1, cylinder 0, sector 1
   6. surface 0, cylinder 1, sector 1
   7. surface 1, cylinder 1, sector 1

   a) The above linear ordering is stupid. What is the most sensible order? (0.4 points)

   Hint: If the sectors are read in a sensible order, the latency (sum of rotational and head positioning latency) should be near-minimal. The sensible order should also remain sensible if you enlarged the disk to have a realistic and useful number of sectors per track, tracks per cylinder, and cylinders. Please ignore any restrictions on reading consecutive sectors on one track, or alternatively and equivalently, assume that interleaving, if required, is done in the hardware.

   b) Given the constants SURFACES, CYLINDERS, and SECTORS (per track, for the latter), write a C function linearize(surface,track,cylinder) that produces a linear disk address from the indicated surface, track and cylinder numbers. (0.3 points)

   c) Given the constants SURFACES, CYLINDERS, and SECTORS (as in the previous part), write expressions to convert the linear disk address linear to the three variables that make up a disk address, surface, cylinder, and sector. (0.3 points)

4. Background: Suppose your disk scheduler uses the cyclic-scan disk scheduling policy (as documented for the notes for Lecture 15). The disk-request queue is maintained as a binary search tree, sorted in order of ascending linearized disk addresses (in the order you determined in the previous problem), and the cyclic scan is accomplished by traversing the tree using an in-order traversal (these terms are all to be found in Wikipedia, if your data structures course didn't cover them). After each disk request is completed, its successor (in ascending order, usually) is located and then the completed request is deleted from the tree.

   There are two possible insertion rules: Given a request for disk address a, it is inserted just before the lowest item already in the queue that has an address greater than or equal to a, or it is inserted just after the highest item in the queue that has an address less than or equal to a.

   A question: Which of the above is correct, and what could go wrong with the other alternative. (0.5 points)