1. 

Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4,999. The drive is currently serving a request at cylinder 2,150, and the previous request was at cylinder 1,805. The queue of pending requests, in FIFO order, is:

2,069,  1,212,  2,296,  2,800,  544,  1,618,  356,  1,523,  4,965,  3681

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. C-SCAN

First-come-first-served (FCFS)

2150, 2,069, 1,212, 2,296, 2,800, 544, 1,618, 356, 1,523, 4,965, 3,681   

81+857+1084+504+2256+1074+1262+1167+3442+1284=13011 cylinder

Shortest-seek-time first (STSF)

2150,2069,2296,1618,1523,1212,544,356,2800,3681,4965

81+227+678+95+311+668+188+2444+881+1284=6857 cylinder.

Selects the request with the least seek time from the current head position. 

In other words, SSTF chooses the pending request closest to the current head position.

C-SCAN 

Moves the head from one end of the disk to the other, servicing requests along the way. When the head reaches the other end, however, it immediately returns to the beginning of the disk without servicing any requests on the return trip.

146+504+881+1284+34+4999+356+188+688+311+95+451=9937cylinder.

Both SCAN and C-SCAN move the disk arm across the full width of the disk.

2.

Elementary physics states that when an object is subjected to a constant acceleration a, the relationship between distance d and time t is given by 

Suppose that, during a seek, the disk 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 5,000 cylinders in 18 milliseconds.

a. The distance of a seek is the number of cylinders over which the head moves. Explain why the seek time is related 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:

where t is the time in milliseconds and L is the seek distance in cylinders

c. Suppose that the disk rotates at 7200RPM. What is the average rotational latency of this disk drive? What seek distance can be covered during the time of average rotational latency?

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 2at2. Suppose that, during a seek, the disk in Exercise 12.17 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 √L, where t is the time in milli seconds and L is the seek distance in cylinders. c. Calculate the total seek time for each of the schedules in Exercise 12.17. 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?

Answer: a. Solving d = 1 2at2 for t gives t = p(2d/a). b. Solve the simultaneous equations t = x + y √L that result from(t = 1, L = 1) and (t = 18, L = 4999) to obtain t = 0.7561+0.2439√L. c. The total seek times are: FCFS 65.20; SSTF 31.52; SCAN 62.02; LOOK 40.29; C-SCAN 62.10 (and C-LOOK 40.42). Thus, SSTF is fastest here. d. (65.20 − 31.52)/65.20 = 0.52. The percentage speedup of SSTF over FCFS is 52%, with respect to the seek time. If we include the overhead of rotational latency and data transfer, the percentage speedup will be less.下载本文