Assignment 6, due Feb. 23
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!
In a uniform interleaving, you use every i'th sector where the interval between successive sector numbers is a constant. The interleaving 0-2-4-6-1-3-5-7 is non-uniform because, while i=2 in most cases, the jump from 6 to 1 uses i=3 and the jump from 7 back to 0 uses i=1.
The sequence given by i=1 is usually described as non-interleaved, but technically, it is the simplest uniform interleaving.
a) List all of the uniform interleavings on 8 sectors, and for each, state the value of i. (0.5 points)
0-1-2-3-4-5-6-7, i = 1
0-3-6-1-4-7-2-5, i = 3
0-5-2-7-4-1-6-3, i = 5
0-7-6-5-4-3-2-1, i = 7
Note that i = 5 is equivalent to i = –3 and i = 7 is equivalent to i = –1, but these alternative expressions do not help you arrive at an answer to part b.
b) Give a general rule. If the disk has s sectors per track, what values of i give distinct uniform interleavings. (There is a formally correct mathematical description of the required relationship between s and i.) (0.5 points)
i is a nonzero integer less than s where s and i have no common factors other than 1.
a) Which use of the extra RAM allowed both floppy disks to be used for user data once the system was up and running? (0.3 points)
With the RAM disk, you can eject the system disk and use the former system disk drive to hold a user disk once the system is running.
In contrast, with disk cache, the system disk must remain mounted in one drive at any time that access to that disk is expected.
b) Which use of the extra RAM accelerated access to user files as well as system programs. (0.3 points)
Disk cache accelerates access to frequently used files on any disks that use it.
In contrast, RAM disks only help for the disk that was copied into RAM.
c) Which use of the extra RAM required extra effort when a floppy disk was ejected from its drive? Explain the problem. (0.4 points)
With a disk cache, if you eject a disk, you'd better also invalidate all of the cache entries that refer to that disk. Otherwise, if you mount a new disk on the same drive, the software might think those old cache entries held data that was on the new disk.
In contrast, with a RAM disk, once the copy from disk to RAM is made, the job is done.
a) Where does the disk scheduler go? Specifically, is there any need for a disk scheduler for the mounted disk image? Briefly, why or why not? (0.5 points)
The disk scheduler is only applicable to access to a physical disk. The virtual disk that is a disk image is just a collection of sectors of some real disk file, so when a disk image is accessed, sector numbers are translated to the locations where real disk sectors are located, and then scheduling becomes relevant.
b) What if the natural block size (the sector size) of my real disk differs from the natural block size of my mounted disk image file. Would this be easier to deal with using the Unix read() and write() kernel calls as a disk interface, or using the linearized sector number scheme outlined in the notes for Feb. 21? Briefly explain your answer. (0.5 points)
It would be easier with the Unix read() and write() kernel calls because those hide any information about the sector size from the user.
In contrast, if the sector size of the real and virtual disks differ and you use linearized sector numbers for random-access addressing within files, your application software becomes responsible for translating single-sector reads and writes on the virtual disk into multiple operations using the other sector size.
Note that this does not change the number of physical I/O operations you end up doing. It only changes who is responsible for figuring out how single operations on one sector size are done using multiple operations on a different sector size.