10.11、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 Answer:

a. The FCFS schedule is 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130. The total seek distance is 7081.

b. The SSTF schedule is 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774. The total seek distance is 1745.

c. The SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 130, 86. The total seek distance is 9769.

d. The LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86. The total seek distance is 3319.

e. The C-SCAN schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 4999, 86, 130. The total seek distance is 9813.

f. (Bonus.) The C-LOOK schedule is 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130. The total seek distance is 3363. 12CHAPTER

Implementation Practice Exercises

12.1 Consider a ?le currently consisting of 100 blocks. Assume that the ?lecontrol 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 at the beginning but there is room to grow at the end. Also assume that the block information to be added is stored 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.

Answer: The results are:

Contiguous Linked Indexed a. 201 1 1 b. 101 52 1 c. 1 3 1 d. 198 1 0 e. 98 52 0 f. 0 100 0

12.2 What problems could occur if a system allowed a ?le system to be mounted simultaneously at more than one location? Answer:

4344 Chapter 12 Implementation

There would be multiple paths to the same ?le, which could confuse users or encourage mistakes (deleting a ?le with one path deletes the ?le in all the other paths).

12.3 Why must the bit map for ?le allocation be kept on mass storage, rather

than in main memory? Answer:

In case of system crash (memory failure) the free-space list would not be lost as it would be if the bit map had been stored in main memory.

12.4 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 ?le? Answer: ?

Contiguous—if ?le is usually accessed sequentially, if ?le is relatively small. ?

Linked—if ?le is large and usually accessed sequentially. ? Indexed—if ?le is large and usually accessed randomly.

12.5 One problem with contiguous allocation is that the user must preallocate enough space for each ?le. If the ?le grows to be larger than the

space allocated for it, special actions must be taken. One solution to this problem is to de?ne a ?le structure consisting of an initial contiguous area (of a speci?ed size). If this area is ?lled, the operating system automatically de?nes an over?ow area that is linked to the initial contiguous area. If the over?ow area is ?lled, another over?ow area is allocated. Compare this implementation of a ?le with the standard contiguous and linked implementations. Answer:

This method requires more overhead then the standard contiguous