<
Problem 2.
Suppose that we are scheduling I/O requests for the new Megatron 747 disk
Recall that the average seek, latency and transfer times are 6.5, 7.8, and 0.5 milliseconds.
Initially the head is at cylinder 4000, and then the following requests come in:
time = 0; request for block on cylinder 4000 arrives
time = 2; request for block on cylinder 6000 arrives
time = 12; request for block on cylinder 1000 arrives
time = 17; request for block on cylinder 7000 arrives
time = 26; request for block on cylinder 3000 arrives
Solution:
a. If we use the elevator scheduling algorithm, at what time is each request serviced completely?
avg. latency + transfer time = 7.8 + 0.5 = 8.3 ms
seek time = 1 + n/500 where n = #tracks to travel
Request 1: Cylinder 4000
access time = 8.3ms
since the disk head is already on cylinder 4000
no seek is needed.
completion time = 8.3 ms
——
Request 2: Cylinder 6000
access time = seek time + 8.3
= 1 + 2000/500 + 8.3
= 13.3 ms
Completion time = 8.3 + 13.3 = 21.6 ms
——-
At this time, Request 4(Cylinder 7000) and Request 3(Cylinder 1000) are pending. The disk header will continue outward to serve Request 4(Cylinder 7000) and defer serving Request 3(Cylinder 1000) till the reverse pass.
Request 4: Cylinder 7000
access time = seek time + 8.3
= 1 + 1000/500 + 8.3
= 11.3 ms
completion time = 21.6 + 11.3 = 32.9 ms
——-
Request 5: Cylinder 3000
access time = seek time + 8.3
= 1 + 4000/500 + 8.3 = 17.3 ms
completion time = 32.9 + 17.3 = 50.2 ms
——-
Request 3: Cylinder 1000
access time = seek time + 8.3
= 1 + 2000/500 + 8.3 = 13.3ms
completion time = 50.2 + 13.3 = 63.5ms
——
b. If we use the first-come-first-served scheduler, at what time is each request serviced fully?
Request 1: Cylinder 4000
access time = 8.3ms
since the disk head is already on cylinder 4000
no seek is needed.
completion time = 8.3 ms
——
Request 2: Cylinder 6000
access time = seek time + 8.3
= 1 + 2000/500 + 8.3
= 13.3 ms
Completion time = 8.3 + 13.3 = 21.6 ms
——-
Request 3: Cylinder 1000
access time = seek time + 8.3
= 1 + 5000/500 + 8.3 = 19.3ms
completion time = 21.6 + 19.3 = 40.9 ms
Request 4: Cylinder 7000
access time = seek time + 8.3
= 1 + 6000/500 + 8.3
= 21.3 ms
completion time = 40.9 + 21.3 = 62.2 ms
——-
Request 5: Cylinder 3000
access time = seek time + 8.3
= 1 + 4000/500 + 8.3 = 17.3 ms
completion time = 62.2 + 17.3 = 79.5ms