Towards dynamic adaptation of I /O scheduling in commodity operating systems

Disk scheduling algorithms in operating systems often are designed to satisfy a primary application data delivery requirement. Multiple concurrent and conflicting requirements need to be satisfied to support concurrently executing applications. Accordingly, a disk scheduling algorithm that is designed to concurrently satisfy multiple data delivery requirements is crucial to the support of diverse architectures, disk systems, and workloads. To concurrently satisfy multiple data delivery requirements, we implement and evaluate a mechanism that dynamically switches between two policies in order to enforce two performance requirements. This two-policy adaptation strives to provide latency guarantees for requests at all times and, when all requests meet their latency requirements, it strives to simultaneously provide fairness in terms of number of requests. This dissertation presents a description of the two-policy adaptation and demonstrates why, in some cases, it cannot simultaneously satisfy both performance requirements. Also, the fairness of the number of requests metric is disputed. Accordingly, we next leverage a fair queuing discipline and implement a fair scheduling algorithm that can be extended to satisfy multiple data delivery requirements concurrently. Our new scheduling strategy uses compensated disk-time as the resource-sharing metric and achieves fairness and predictable application performance. To the best of our knowledge, ours is the only I/O scheduling algorithm that provides predictability in application performance, one of the most important system requirements. In addition, this algorithm and the underlying queuing system is flexible enough to implement the enforcement of a number of other performance requirements such as request latencies, anticipation of requests, and service level objectives, while concurrently providing fairness. In this dissertation we describes the impact of different resource-sharing metrics of conventional fair scheduling on application performance predictability. We present the fairness properties, analytical and experimental evaluations of various fair scheduling algorithms