``Free bandwidth'' is different from bandwidth available during idle periods--the disk head may pass over locations that are of interest to some background operations even as it is ``busy'' serving foreground requests. Inserting some of these background requests into the foreground request stream should impose little penalty on foreground activities. Example applications that can benefit from free bandwidth are background activities such as data mining and storage reorganization [17].
Our next group of eager-writing scheduling algorithms are inspired by the approach of exploiting free bandwidth. Under this approach, we first schedule the reads using a known disk scheduling algorithm. Based on this schedule, we calculate a ``deadline'' by which the disk head must arrive at a target cylinder for each read operation so that the read operation can complete in time. Once the schedule and the deadlines of the reads are determined, we attempt to insert eager-writes into gaps among the reads if suitable free blocks can be located and the insertion of these eager-writes does not cause the disk head to miss the deadlines prescribed by the read schedule. In this case, the disk head also moves in one direction until it can move no further and has to reverse its direction.
The above description is not sufficient for fully specifying the scheduling order--to complete the description, we must determine what scheduling algorithm to use to schedule the reads. We shall explore two possibilities: shortest access time first (SATF) as described above, and SCAN, which orders the read requests solely based on their seek distance. We call the resulting overall algorithms FreeBW-SATF and FreeBW-SCAN respectively.
These scheduling algorithms inspired by the exploitation of free bandwidth are a different way of balancing the scheduling of reads and eager-writes. When there are many read requests, however, these algorithms will tend to favor scheduling reads first; this happens because a large number of reads tend to reduce the gap among them and there is less room left for eager writes. In the extreme case, it may degenerate to the read-first algorithm which, as we have explained in Section 4.1, may have its shortcomings.