Homework 6 Solutions

22C:116, Spring 2002

1. A Problem Consider the problem of printing files. One common approach is to spool the file to disk and then passing that file to a background process that does the actual printing. On a virtual memory system with one address space per process, one could equally well imagine storing the file to be printed in the virtual memory assigned the print process. Both of these methods could be used, for example, under UNIX, but only the former is used. Is there any technical reason to prefer one approach over the other, or is the common use of the former merely a historical accident.

   There is no reason to prefer one approach over the other! The standard model of spoolers used today dates back to the 1960's, when virtual memory was rare, so of course, spoolers explicitly copied the file that was to be printed to disk (see, for example, the UNIX print spoolers use the directory named /var/spool/lpd or /var/spool/lp/request/ for files awaiting printing, depending on the version of the print spooler that is being used).
   
   The number of disk accesses required to print a document in the first case is one access to write the print file and one to read the print file when it is printed, times the size of the document. In the second case, we would need at most one page fault to store the file in memory and one to read it from memory for printing, times the size of the document (and if we had enough ram, these would not be needed either).

2. Problems from the Text:
   Do problems 6 and 11 on page 374 in the text.
   
   Do problems 16, 19 and 22 on page 375 in the text.

   16) RAID level 2 allows hardware error correction using fast parallel hardware while the data is being read from disk. RAID level 3 requires that the total block be read and the CRC be computed for each sector read from each disk before any correction is done. Most likely, this would be done by firmware (software in the RAID controller) or by the operating system, while the error correction in RAID level 2 would generally be done completely in hardware (it takes only n-log-n xor gates to do this for an n-bit word).
   
   19) Interleaving is useful whenever the time taken by the disk hardware to finish one sector and start the next is shorter than the operating system's response to a transfer-complete interrupt. One thing that can make the transfer-complete interrupt time consuming is copying the data for a disk sector between main memory and the disk controller's interface buffer, but if the controller does this in real-time using DMA technology, the interrupt service routine must still dequeue the next disk request from the disk request queue, unblock the process waiting for the completion of the previous request and so on. These computations plus the basic overhead of interrupt response may take several hundred instructions, and if the intersector-gap on a track is shorter than this, interleaving will pay off!
   
   22) Doubling the linear recording density, with no other changes in the disk drive, will have no effect on seek time or rotational latency. Transfer times for reading and writing a sector will be halved. Because twice as many sectors fit in each cylinder, head position changes during long strings of sequential reads or writes will occur half as frequently. Because the intersector gap goes by twice as quickly, the new disk is more likely to require interleaving, and because sectors read twice as quickly, the new disk may require a different interleave factor and a different sector skew.

   
   Do problem 24 on page 375, but reverse the order of the requests given!

   a) First-come, first-served will serve the sectors in the order [(20) 10 22 20 2 40 6 38]; this requires moves of [ 10 12 2 18 38 34 32] cylinders, a total of 146 cylinders; at 6 msec per cylinder, this comes to .876 seconds.
   
   b) Closest cylinder next will serve the sectors in the order [(20) 20 22 10 6 2 38 40]; this requires moves of [ 0 2 12 4 4 36 2] cylinders, a total of 60 cylinders; at 6 msec per cylinder, this comes to .360 seconds.
   
   c) (Bidirectional) elevator, moving up at the start, will serve [(20) 20 22 38 40 10 6 2]; this requires moves of [0 2 16 2 30 4 4] cylinders, a total of 58 cylinders; at 6 msec per cylinder, this comes to .348 seconds.

   
   Do problems 26 and 32 on page 376 in the text.

   26) If we have use NVRAM to track which write operations is in progress in an implementation of stable storage, then, from the point of view of the stable storage implementation, the operation is in progress from the time we record 'start' in the NVRAM until the time we record 'stop'. Even if the operation has actually completed successfully, if the NVRAM holds an indication that it is in progress, we do not consider the write to have completed, and we treat it as if the operation had been interrupted by a failure. Since stable storage is designed to survive the failure of any write, this causes no problem! This failure mode has a very low probability, so it will lead to a very small degradation in the overall performance of the system.
   
   32) Scrolling a 5280 pixel window requires that 5280 pixels be copied, either from that window to new places on that window, or from the blank background color to the bottom line of the window. We need to know the number of pixels per byte, and we know that a character is 8x16 = 128 pixels and can be displayed in 5usec, or 39 nsec per pixel. Since it takes 50 nsec to copy a byte, we conclude that there are multiple pixels per byte -- furthermore, we know that there are other computations involved in putting a character on the screen other than copying the pixels.
   
   So, assume one bit per pixel, 8 pixels per byte, and we get a scroll time of 5280/8x50 = 33000 nsec = 33 usec.
   
   Displaying an 80 character line of text takes 80x50 = 4000 nsec = 40 usec, so we can display one 80 character line of text (with scrolling) every 40+33 = 73 usec (13699 lines per second). The average time per character, including scrolling overhead, is 73/80 = .9125 usec, and if we assume asynchronous communications (start+stop+8 = 10 bits per character) this is about 11 megabaud.
   
   The assumption of 8 pixels per byte was probably wrong -- the cost of copying the pixels to the display is probably comparable to the cost of the other operations involved in receiving a character, so let's try a different assumption, 4 bits per pixel. In this case, our scroll time is 5280/2x50 = 132000 nsec - 132 usec. The time to display and scroll one line is 40+132 = 172 usec (5184 lines per second). The average time per character, including scrolling, is 172/80 = 2.15 usec or about 4.6 megabaud.