Assignment 11: Chapter 11-13

Please make sure that you're using the same edition of the book. There is no guarantee that older editions use the same numbering for problems. Please submit a single tar file.

Note that problems may intentionally differ slightly from the ones shown in the book.

1. (11.3) Consider a system where free space is kept in a free-space list.
   1. Suppose that the pointer to the free-space list is lost. Can the system reconstruct the free-space list? Explain your answer.
   2. Consider a file system similar to the one used by UNIX with indexed allocation. How many disk I/O operations might be required to read the contents of a small local file at /a/b/c? Assume that none of the disk blocks is currently being cached.
   3. Suggest a scheme to ensure that the pointer is never lost as a result of memory failure.
2. (11.4) Some file systems allow disk storage to be allocated at different levels of granularity. For instance, a file system could allocate 4 KB of disk space as a single 4-KB block or as eight 512-byte blocks. How could we take advantage of this flexibility to improve performance? What modifications would have to be made to the free-space management scheme in order to support this feature?
3. (11.10) Explain why logging metadata updates ensures recovery of a file system after a file system crash.
4. (12.2) Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is 86, 913, 1470, 1509, 948, 1774, 1509, 1022, 130, 1750

   Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?

   1. FCFS
   2. SSTF
   3. SCAN
   4. LOOK
   5. C-SCAN
5. By consulting Internet and other resources, determine typical bit densities (areal density) for modern storage media: optical disks (DVDs and BluRay), magnetic tape (e.g., Ultrium) and magnetic disks. What are the respective read data rates? (Cite your sources)
6. (12.8) Requests are not usually uniformly distributed. For example, a cylinder containing the file system FAT or inodes can be expected to be accessed more frequently than a cylinder that contains only files. Suppose you know that 50 percent of the requests are for a small, fixed number of cylinders.
   1. Would any of the scheduling algorithms discussed in this chapter be particularly good for this case? Explain your answer.
   2. Propose a disk-scheduling algorithm that gives even better per- formance by taking advantage of this "hot spot" on the disk.
   3. File systems typically find data blocks via an indirection table, such as a FAT in DOS or inodes in UNIX. Describe one or more ways to take advantage of this indirection to improve the disk performance.
7. For each of the RAID schemes (RAID 1 through 6), compare
   1. the seek time;
   2. the read transfer rate;
   3. the write transfer rate;
   4. the time to restore a single bad drive.
   Label the seek time of a single disk by S (seconds), its capacity as C (bytes), the read transfer rate as R (bytes/second) and the write transfer rate as W (bytes/second).
8. (12.15) The reliability of a hard-disk drive is typically described in terms of a quantity called mean time between failures (MTBF). Although this quantity is called a "time," the MTBF actually is measured in drive-hours per failure.
   1. If a disk farm contains 1000 drives, each of which has a 750,000- hour MTBF, which of the following best describes how often a drive failure will occur in that disk farm: once per thousand years, once per century, once per decade, once per year, once per month, once per week, once per day, once per hour, once per minute, or once per second?
   2. Mortality statistics indicate that, on the average, a U.S. resident has about 1 chance in 1000 of dying between ages 20 and 21 years. Deduce the MTBF hours for 20 year olds. Convert this figure from hours to years. What does this MTBF tell you about the expected lifetime of a 20 year old?
   3. The manufacturer claims a 1-million hour MTBF for a certain model of disk drive. What can you say about the number of years that one of those drives can be expected to last?
9. Find a description of the PCI and PCI-X bus. How many address and data lines does it have? What is the data rate?
10. (13.4) In most multiprogrammed systems, user programs access memory through virtual addresses, while the operating system uses raw physical addresses to access memory. What are the implications of this design on the initiation of I/O operations by the user program and their execution by the operating system?