Comparison of Eager-writing Scheduling Algorithms

*Figure* 4: Throughput comparison of different eager-writing scheduling algorithms as we vary the number of queued requests.
$\begin{figure} \centerline {\psfig{figure=figs/sched_queuelen.eps,width=3.2in,clip=}}\end{figure}$

Figure 4 compares the throughput of different eager-writing algorithms as we vary the queue length. This simple simulated workload has a 50% write ratio and it runs on a disk with a dilution factor of 2.

SATF-EW works well for all queue lengths. In contrast, although it is known that SATF generally outperforms SCAN in a traditional storage system [16,23], interestingly enough, FreeBW-SATF performs worse than FreeBW-SCAN, especially when the queue is large. This occurs because the aggressive scheduling of reads by SATF under high load leaves little ``free bandwidth'' for scheduling the eager-writes; consequently, FreeBW-SATF becomes similar to the read-first algorithm and unnecessarily penalizes writes. In contrast, by using SCAN to schedule the reads, FreeBW-SCAN causes the reads to be spaced further apart so more ``free bandwidth'' becomes available for eager-writes; consequently, the scheduling of reads and writes are better balanced and the overall performance of FreeBW-SCAN is better.

When there are a large number of reads but few writes, however, the performance of FreeBW-SCAN is not the best due to its failure to take rotational delay of reads into consideration. To address this shortcoming, we augment FreeBW-SCAN with a simple heuristics: when there is no write request in the queue, we replace SCAN with SATF. We call the modified algorithm FreeBW-Hybrid. Figure 4 shows that this hybrid algorithm performs the best for this workload--it even slightly outperforms SATF-EW due to its successful masking the eager-writes in the gaps of reads.

*Figure* 5: Throughput comparison of different eager-writing scheduling algorithms as we vary the fraction of queued operations that are reads.
$\begin{figure} \centerline {\psfig{figure=figs/sched_readratio.eps,width=3.2in,clip=}}\end{figure}$

Figure 5 compares the throughput of these algorithms as we vary the ratio of reads. The queue length is 64 and the disk dilution factor is 2.

SATF-EW works well for all read ratios. When the read ratio is high, the disadvantage of FreeBW-SCAN is most apparent. In contrast, all other algorithms approach the performance of SATF when the read ratio approaches 100%. Interestingly, when the number of reads is small (but nonzero), the free bandwidth-based approaches also perform worse than SATF-EW. This is because the seek time among those small number of reads dominates and there is little rotational time left for scheduling the eager-writes. When there are a modest number of reads, due to both of its ability of successfully exploiting free bandwidth and its intelligent scheduling of reads, FreeBW-Hybrid is the best.