Assignment 6, Solutions

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

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)

When the pointers a and b are equal -- that is, when they point to the same place.

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

When the strings pointed to by a and b are equal -- that is, when they contain identical text
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)
```
# comment should be simply ignored
/bin/echo a "b   c" 'd  e' # comment
# output: a b   c d   e
setenv gribble "- #"
/bin/echo $gribble
# output: - #
/bin/tcsh -c "echo $gribble"
# output: - #
exit
```
Note that the above does not test any of the error conditions, nor does it test how you deal with areas where the assignment was ambiguous.
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:
1. surface 0, cylinder 0, sector 0
2. surface 1, cylinder 0, sector 0
3. surface 0, cylinder 1, sector 0
4. surface 1, cylinder 1, sector 0
5. surface 0, cylinder 0, sector 1
6. surface 1, cylinder 0, sector 1
7. surface 0, cylinder 1, sector 1
8. surface 1, cylinder 1, sector 1
a) The above linear ordering is stupid. What is the most sensible order? (0.4 points)
1. surface 0, cylinder 0, sector 0
2. surface 0, cylinder 0, sector 1
3. surface 1, cylinder 0, sector 0
4. surface 1, cylinder 0, sector 1
5. surface 0, cylinder 1, sector 0
6. surface 0, cylinder 1, sector 1
7. surface 1, cylinder 1, sector 0
8. surface 1, cylinder 1, sector 1
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)
There was a bug in the problem specification (strangely, nobody asked about it!). The sector number obviously matters, and track is both ambiguous and redundant in each reading of the ambiguity.
```
int linearize(int surface, int cylinder, int sector){
	return sector + surface * SECTORS + cylinder * (SECTORS + SURFACES);
}
```
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)
As above, there was the same bug in the problem specification.
```
sector = linear % SECTORS;
surface = (linear / SECTORS) % SURFACES;
cylinder = linear / (SECTORS * SURFACES);
```
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)

The key question is, if the disk is currently working on a sector with linearized address a while another request for a arrives in the request queue, is that second request going to be processed immediately when the current request is completed, or will it be put off until all other pending requests have been served.
The former option leads to the potential that some ill-behaved customer (or a group of customers) could prevent any other user from getting service by repeated requests for access to one particular sector. The latter option guarantees fairness.
Therefore, a request for address a must be "inserted just before the lowest item already in the queue that has an address greater than or equal to a."