Information Technology Reference
In-Depth Information
SPTF/SSTF. An initially appealing option is to use a greedy scheduler that,
given the current position of the disk head and platter, always services the
pending request that can be serviced in the minimum amount of time. This
approach is called shortest positioning time first (SPTF) (or shortest seek time
Definition: shortest
positioning time first
first (SSTF) if rotational positioning is not considered.)
Definition: shortest seek
time first
SPTF and SSTF have two significant limitations. First, because moving
the disk arm and waiting for some rotation time affects the cost of serving
subsequent requests, these greedy approaches are not guaranteed to optimize
disk performance. Second, these greedy approaches can cause starvation when,
for example, a continuous stream of requests to inner tracks prevents requests
to outer tracks from ever being serviced.
Example: SPTF is not optimal.
Question: Suppose a disk's head is just inside the middle track of a disk so
that seeking to the inside track would cost 9.9 ms while seeking
to the outside track would cost 10.1 ms. Assume that for the
disk in question, seeking between the outer and inner track costs
15 ms and that a rotation takes 10ms.
Also suppose that the disk has two sets of pending requests. The
first set is 1000 requests to read each of the 1000 sectors on the
inner track of the disk; the second set is 2000 requests to read
each of the 2000 sectors on the outer track of the disk.
Compare the average response time per request for the SPTF
schedule (first read the “nearby” inner track and then read the
outer track) and the alternative of reading the outer track first
and then the inner track.
Answer: To service either the outer set of requests, the disk must seek
to the appropriate track and then wait for one full rotation while
all of the track's data sweeps under the arm. For either set, the
average response time for a request in that set will be the delay
until the seek completes plus one half the disk's rotation time.
Notice that the set is handled second must wait until the first one
is completely done before it can start, adding to the response
time observed for requests in that set.
Inner first (SPTF):
(1000(9:9 + 5) + 2000(9:9 + 10 + 15 + 5))=3000
= 31:6 ms
Outer first:
(2000(10:1 + 5) + 1000(10:1 + 10 + 15 + 5))=3000
= 23:3 ms
