Assignment 7, due Oct. 11

On all assignments, your name must be legible as it appears on your University ID card! 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: Consider a disk with 17 sectors per track, 255 tracks per surface, and 3 surfaces used for data storage (the actual device has 4 surfaces, but in many disk systems, one surface is used for formatting -- the logic for both radial head motion and locating the sectors of each track uses that surface.)

   There are 17 times 255 times 3 (that is 13005) sectors on this disk. Disk addresses on this device have 3 components: cyl -- cylinder, surf -- surface and sect -- sector. Which is the most significant component, which is the middle

   a) Which is the most significant component of the disk address, which is the middle (in significance) and which is the least significant? (0.4 points)

   Least significant: sector number
   Middle: surface number
   Most significant: cylinder number

   b) A linearized disk address on this disk will be a sector number between 0 to 13004. Give the expressions to extract sect, cyl and surf from a linearized sector number num. (0.6 points)

   sect = num mod 17
   surf = (num / 17) mod 3
   cyl = num / (17 * 3)

2. Background: On Unix and Linux systems, the basic file interface on read(fd,buf,len) and write(fd,buf,len) where fd designates an open file, buf is the address of a buffer in the user's memory, and len gives the size of the buffer. By default, a call to read or write on an open disk file blocks the calling process until the operation is complete and exactly len bytes have been transferred (except when reading past the end of file). The disk address is taken from the file position, which may be set arbitrarily by lseek() and is incremented by len after each read() or write().

   A Question: When can the system safely copy data directly between the user's buffer and the disk without using any intermediate system buffers? Consider expressing your answer in terms of constraints on the file position, sector size, buffer address, buffer length, etc. (0.5 points)

   When the file position is a multiple of the sector size and the buffer length is equal to the sector size.

3. Background: Consider a disk input/output driver where the disk interrupt service routine dequeues requests from the disk request queue, where each request indicates the disk address (sector, cylinder, surface), the memory address of a buffer, and the transfer direction. The enqueue routine is part of the driver.

   a) Suppose a disk request is already in the queue to write disk address a, and the user asks the driver to enqueue a new write to disk address a. For maximum performance, what should be done? (0.5 points)

   The new write request should replace the request already in the queue.

   b) Suppose a disk request is already in the queue to write disk address a, and the user asks the driver to enqueue a new read from disk address a. For maximum performance, what should be done? (0.5 points)

   The data from the buffer of the pending write request can be copied directly into the buffer for the read request. There is no need to enqueue the read request.

   c) The computation needed to determin if a request is already in the queue is simplified if the disk request queue is sorted by disk address instead of being a simple FIFO queue. Aside from supporting the optimizations hinted at above, what is the primary reason a disk driver might keep the queue sorted.

   The sorted queue can be used as the basis for a disk scheduler using something like the elevator algorithm.

   Added note, not part of the homework solution: The optimization suggested above has a dangerous side effect. If some process keeps enqueueing write requests for some sector it could potentially prevent that sector from ever being written to disk. In the event of something like a power failure, this could be catastrophic. Care needs to be taken to assure that regardless of any replacement of disk requests, this will not happen.