soln12-14.txt

operating system concepts sixth edition windows XP updat 操作系统课后答案

UFPR - Bacharelado em Ci阯cia da Computa玢o
CI215 - Sistemas Operacionais
Oitava Lista de Exerc韈ios [17nov04]       Exerc韈ios Caps 12-14 de SGG-osc

12.1 Consider a file currently consisting of 100 blocks. Assume that the
file control block (and the index block, in the case of indexed
allocation) is already in memory.  Calculate how many disk I/O operations
are required for contiguous, linked, and indexed (single-level) allocation
strategies, if, for one block, the following conditions hold. In the
contiguous- allocation case, assume that there is no room to grow in the
beginning, but there is room to grow in the end. Assume that the block
information to be added is store d in memory.
a. The block is added at the beginning.  b. The block is added in the middle.
c. The block is added at the end. d. The block is removed from the beginning.
e. The block is removed from the middle. f.The block is removed from the end.

12.2 Consider a system where free space is kept in a free-space list.  (a)
Suppose that the pointer to the free-space list is lost. Can the system
reconstruct the free-space list? Explain your answer.  (b) Suggest a scheme
to ensure that the pointer is never lost as a result of memory failure.

12.4 Why must the bit map for file allocation be kept on mass storage,
rather than in main memory?

12.5 Consider a system that supports the strategies of contiguous, linked,
and indexed allocation. What criteria should be used in deciding which
strategy is best utilized for a particular file?

12.6 Consider a file system on a disk that has both logical and physical
block sizes of 512 bytes.  Assume that the information about each file is
already in memory.  For each of the three allocation strategies
(contiguous, linked, and indexed), answer these questions: (a) How is the
logical-to-physical address mapping accomplished in this system? [for the
indexed allocation, assume that a file is always less than 512 blocks
long]  (b) If we are currently at logical block 10 (the last block
accessed was block 10) and want to access logical block 4, how many
physical blocks must be read from the disk?

12.7 One problem with contiguous allocation is that the user must
preallocate enough space for each file.  If the file grows to be larger
than the space allocated for it, special actions must be taken.  One
solution to this problem is to define a file structure consisting of an
initial contiguous area (of a specified size).  If this area is filled, the
operating system automatically defines an overflow area that is linked to
the initial contiguous area.  If the overflow area is filled, another
overflow area is allocated. Compare this implementation of a file with the
standard contiguous and linked implementations.

12.8 Fragmentation on a storage device could be eliminated by recompaction
of the information.  Typical disk devices do not have relocation or base
registers (such as are used when memory is to be compacted), so how can we
relocate files?  Give three reasons why recompacting and relocation of
files often are avoided.

12.9 How do caches help improve performance?  Why do systems not use more
or larger caches if they are so useful?

12.12 Explain why logging metadata updates ensures recovery of a file
system after a file system crash.

12.13 Explain how the VFS layer allows an operating system easily to
support multiple types of file systems.


13.1 State three advantages of placing functionality in a device
controller, rather than in the kernel. State three disadvantages.

13.2 Consider the following I/O scenarios on a single-user PC.  (a) A mouse
used with a graphical user interface; (b) A tape drive on a multitasking
operating system (assume no device pre-allocation is available); (c) A disk
drive containing user files; (d) A graphics card with direct bus
connection, accessible through memory-mapped I/O.  For each of these I/O
scenarios, would you design the operating system to use buffering,
spooling, caching, or a combination?  Would you use polled I/O, or
interrupt-driven I/O?  Give reasons for your choices.

13.3 The example of handshaking in Section 13.2 used 2 bits: a busy bit and
a command ready bit. Is it possible to implement this handshaking with
only 1 bit? If it is, describe the protocol. If it is not, explain why 1
bit is insufficient.

13.4 Describe three circumstances under which blocking I/O should be
used. Describe three circumstances under which nonblocking I/O should be
used. Why not just implement nonblocking I/O and have processes busy-wait
until their device is ready?

13.5 Why might a system use interrupt-driven I/O to manage a single serial
port, but polling I/O to manage a front-end processor, such as a terminal
concentrator?

13.6 Polling for an I/O completion can waste a large number of CPU cycles
if the processor iterates a busy-waiting loop many times before the I/O
completes.  But if the I/O device is ready for service, polling can be much
more efficient than is catching and dispatching an interrupt. Describe a
hybrid strategy that combines polling, sleeping, and interrupts for I/O
device service. For each of these three strategies (pure polling, pure
interrupts, hybrid), describe a computing environment in which that
strategy is more e fficient than is either of the others.

13.7 UNIX coordinates the activities of the kernel I/O components by
manipulating shared in-kernel data structures, whereas Windows NT uses
object-oriented message passing between kernel I/O components. Discuss
three pros and three cons of each approach.

13.8 How does DMA increase system concurrency? How does it complicate
hardware design?

13.9 Write (in pseudocode) an implementation of virtual clocks, including
the queuing and management of timer requests for the kernel and
applications. Assume that the hardware provides three timer channels.

13.10 Why is it important to scale up system bus and device speeds as the
CPU speed increases?


14.1 None of the disk-scheduling disciplines, except FCFS, is truly fair
(starvation may occur).  (a) Explain why this assertion is true; (b)
Describe a way to modify algorithms such as SCAN to ensure fairness; (c)
Explain why fairness is an important goal in a time-sharing system; (d)
Give three or more examples of circumstances in which it is important that
the operating system be unfair in serving I/O requests.

14.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, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
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?
(a) FCFS (b) SSTF (c) SCAN (d) LOOK (e) C-SCAN

14.3 From elementary physics, we know that when an object is subjected to a
constant acceleration a, the relationship between distance D and time T is
given by D = 1/2*A*T**2. Suppose that, during a seek, the disk in Exercise
14.2 accelerates the disk arm at a constant rate for the first half of the
seek, then decelerates the disk arm at the same rate for the second half of
the seek.  Assume that the disk can perform a seek to an adjacent cylinder
in 1 millisecond and a full-stroke seek over all 5000 cylinders in 18
milliseconds.  (a) The distance of a seek is the number of cylinders that
the head moves.  Explain why the seek time is proportional to the square
root of the seek distance.  (b) Write an equation for the seek time as a
function of the seek distance. This equation should be of the form T =
X+Y*sqrt(L), where T is the time in milliseconds and L is the seek distance
in cylinders. (c) Calculate the total seek time for each of the schedules
in Exercise 14.2 and then determine which schedule is the fastest (has the
smallest total seek time).  (d) The percentage speedup is the time saved
divided by the original time.  What is the percentage speedup of the
fastest schedule over FCFS?

14.4 Suppose that the disk in Exercise 14.3 rotates at 7200 RPM.  (a) What
is the average rotational latency of this disk drive? (b) What seek
distance can be covered in the time that you found for part (a)?

14.5 The accelerating seek described in Exercise 14.3 is typical of
hard-disk drives. By contrast, floppy disks (and many hard disks
manufactured before the mid-1980s) typically seek at a fixed rate. Suppose
that the disk in Exercise 14.3 has a constant-rate seek rather than a
constant-acceleration seek, so the seek time is of the form T = X+Y*L,
where T is the time in milliseconds and L is the seek distance. Suppose
that the time to seek o an adjacent cylinder is 1 millisecond, as before,
and is 0.5 milliseconds for each additional cylinder.  (a) Write an
equation for this seek time as a function of the seek distance; (b) using
the seek-time function from part (a), calculate the total seek time for
each of the schedules in Exercise 14.2. Is your answer the same as it was
for Exercise 14.3.c? (c) What is the percentage speedup of the fastest
schedule over FCFS in this case?

14.8 Is disk scheduling, other than FCFS scheduling, useful in a
single-user environment? Explain your answer.

14.9 Explain why SSTF scheduling tends to favor middle cylinders over the
innermost and outermost cylinders.

14.10 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 only contains files. Suppose
you know that 50 percent of the requests are for a small, fixed number of
cylinders. (a) Would any of the scheduling algorithms discussed in this
chapter be particularly good for this case? Explain your answer.  (b)
Propose a disk-scheduling algorithm that gives even better performance by
taking advantage of this "hot spot" on the disk; (c) 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.

14.11 Why is rotational latency usually not considered in disk scheduling?
How would you modify SSTF, SCAN, and C-SCAN to include latency
optimization?

14.12 How would use of a RAM disk affect your selection of a
disk-scheduling algorithm? What factors would you need to consider? Do the
same considerations apply to hard-disk scheduling, given that the file
system stores recently used blocks in a buffer cache in main memory?

14.13 Why is it important to balance file system I/O among the disks and
controllers on a system in a multitasking environment?

14.14 What are the tradeoffs involved in rereading code pages from the file
system versus using swap space to store them?

14.15 Is there any way to implement truly stable storage? Explain your answer.

14.16 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.  (a) 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?  (b)
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?  (c)
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?