Hybrid: achieving deterministic fairness and high throughput in disk scheduling

Many computer applications require moving data from/to disk devices. Since the throughput of disk devices is extremely sensitive to the locality of accesses, the disk schedulers proposed in the literature typically assume the knowledge of the disks' physical parameters (e.g. seek and rotational latency) to meet the different Quality of Service requirements. Unfortunately, the unavoidable discrepancies between the estimated and actual values of such parameters affect the service guarantees, both in terms of response time and disk bandwidth distribution. In this paper we present Hybrid, a Proportional Share disk scheduling algorithm that distributes disk bandwidth among applications with a bounded lag over an ideally fair distribution. This lag is independent from the actual values of the disk's parameters - in fact, Hybrid is defined without using the disk's physical parameters. Furthermore, it can be easily configured to achieve the desired tradeoff between short-term fairness and throughput. Finally, we present an implementation of Hybrid in the FreeBSD operating system, and provide experimental results to demonstrate its effectiveness in achieving high throughput, and in meeting the requirements of file transfer, interactive, and soft real time applications.