Assignment 5, due Mar. 5

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday). The only exceptions to this rule will be by advance arrangement unless there is what insurance companies call "an act of God" - something outside your control. Homework must be turned in on paper and in class! Late work may be turned in to the teaching assistant's mailbox, but see the late work policy. Never push late work under someone's door!

1. Background: Consider a fictional disk drive with the following characteristics:
   • rotation rate: 5400 RPM
   • average seek time: 9 ms
   • surfaces: 4 (2 platters)
   • tracks per surface: 3,405
   • sectors per track: 185
   • data bytes per sector: 512

   Assume that seek time is linearly proportional to the number of tracks moved, and that the average stated is based on a move of 1/2 the number of tracks per surface.

   Note: The above is fairly typical of a reasonably modern drive, except for the following: Seek time is not a linear function of the number of tracks because of head acceleration and deceleration. As a result, real disk heads take a time proportional to the square root of the number of tracks moved, not linearly proportional. And, the number of sectors per track is typically not constant, but varies by a factor of two between the inner and outer tracks.

   a) What is the data capacity of this drive, in bytes? (0.3 points)

   b) Consider the latency time between requesting a disk transfer and the start of that transfer. This is the sum of seek latency and rotational latency. What is the worst case latency. Show your work. (0.3 points)

   c) what is the average case latency? Show your work. (0.3 points)

   d) what is the best case latency? (You may make simple approximations here.) (0.1 points)

2. A problem: Complete the following function for 0.5 points:

   struct diskaddress {
   	int surface;  /* 0 to 3 */
   	int cylinder; /* 0 to 3404 */
   	int sector;   /* 0 to 184 */
   };
   
   void inttoaddr( struct diskaddress * addr; int i )
   /* sets the fields of diskaddress to the linear sector number i
      where i is in the range 0 to the maximum capacity of the device */
   {
   	/* provide this code! */
   }
   

3. A problem: What aspect of the above code would you have to change to account for the oversimplification in the specification of this disk drive, when compared with real disk drives from the 21st century? (0.5 points)

4. Background: The Unix file system has a 2-level structure. Directories map file names to i-numbers, where the i-number is the index of an i-node in the i-table, and i-nodes describe where files are located on disk.

   A Problem Consider the problem of making a backup. Your backup program must traverse the entire directory tree, making exactly one copy of each data file, even though the Unix file system allows multiple links to each data file. Outline a reasonable way for the backup program to do this. (0.4 points)

5. Background Consider the problem of disk layout. Assume that the file system is old, after many allocations and deletions. When new disk space is allocated for a file, you might consider where the i-table is on disk, where any other sectors for that file are located, where the free space is located, and where the directory referencing that file is located.

   For examples of some bad ideas, you might elect to allocate the free sector nearest the i-table on disk, or you might elect to find the largest block of free disk sectors and allocate the new sector in the middle of that block.

   a) When a new file is created, where should the first sector be located? (0.3 points)

   b) When a file grows because of a write operation, where should the new sector be located? (0.3 points)