Enhancements to Linux I/O Scheduling

The Linux 2.6 release provides four I/O schedulers: deadline, anticipatory, noop, and completely fair queuing (CFQ), along with an option to select one of these four at boot time. The selection is based on a priori knowledge of the workload, hardware configuration of the system, and the file system, among other factors. The anticipatory scheduler (AS) is the default. Although the AS performs well under many situations, we have identified cases, under certain combinations of workloads, where the AS leads to starvation of processes. To mitigate this problem, we implemented an extension to the AS (called Cooperative AS or CAS) and compared its performance with the other four schedulers. This paper briefly describes the AS and the related deadline scheduler, highlighting their shortcomings; in addition, it gives a detailed description of the CAS. We report performance of all five schedulers on a set of workloads, which represent a wide range of I/O behavior. The study shows that (1) the CAS has an order of magnitude improvement in performance in cases where the AS leads to starvation and (2) in several cases the CAS has performance comparable to that of the other schedulers. But, as the literature and this study reports, no one scheduler can provide the best possible performance for all workloads; accordingly, Linux provides four from which to select. Even when dealing with just four I/O schedulers, in systems that service concurrent workloads with different I/O behaviors, a priori selection of the scheduler with the best possible performance can be an intricate task. Dynamic selection based on workload needs, system configuration, and other parameters can address this challenge. Accordingly, we are developing metrics and heuristics that can be used for this purpose. The paper concludes with a description of our efforts in this direction, in particular, we present a characterization function based on metrics related to system behavior and I/O requests that can be used to measure and compare scheduling algorithm performance. This characterization function can be used to dynamically select an appropriate scheduler based on observed system behavior.