Assignment 11: Chapter 11-13
This assignment is to be completed individually, not as a group.
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.
- (11.3) Consider a system where free space is kept in a free-space
- Suppose that the pointer to the free-space list is lost. Can the
system reconstruct the free-space list? Explain your answer.
- 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.
- Suggest a scheme to ensure that the pointer is never lost as a
result of memory failure.
- (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?
- (11.10) Explain why logging metadata updates ensures recovery of a
file system after a file system crash.
- (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?
- 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)
- (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.
- Would any of the scheduling algorithms discussed in this chapter
be particularly good for this case? Explain your answer.
- Propose a disk-scheduling algorithm that gives even better per-
formance by taking advantage of this "hot spot" on the disk.
- 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
- For each of the RAID schemes (RAID 1 through 6), compare
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).
- the seek time;
- the read transfer rate;
- the write transfer rate;
- the time to restore a single bad drive.
- (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.
- 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?
- 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?
- 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?
- Find a description of the PCI and PCI-X bus. How many address and
data lines does it have? What is the data rate?
- (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?
by Henning Schulzrinne