Check out the new USENIX Web site. next up previous
Next: Eager-writing-based Free Bandwidth Scheduling Up: Scheduling on an EW-Array Previous: Naive Scheduling Algorithms


Eager-writing-based Shortest Access Time First Scheduling

The traditional shortest access time first (SATF) algorithm greedily schedules the request that is closest to the current disk head position [16,23]. It takes both seek and rotational latency into consideration. We now extend this algorithm for eager-writing, and we call this extension the SATF-EW algorithm. The SATF-EW algorithm examines the queue and compares the location of the closest read request against the location of the closest free block. If the former is closer, we schedule the read request, else we schedule a write request into the closest free block. To avoid trapping the disk head in a small region and exhausting the free blocks, we always force the disk head to move in one seek direction until it can move no further and has to switch direction.

Unlike the naive algorithms described earlier, SATF-EW generally strikes a sound balance in scheduling read and write requests. When there are a large fraction of free blocks and there are many write requests, however, SATF-EW will tend to favor scheduling writes first; in the extreme case, it may degenerate to the write-first algorithm which, as we have explained earlier, may have its shortcomings.


next up previous
Next: Eager-writing-based Free Bandwidth Scheduling Up: Scheduling on an EW-Array Previous: Naive Scheduling Algorithms
Chi Zhang
2001-11-16