
%         Registration              Enhancements to Linux I/O Scheduling      
%  [2]Register/Submit Proposal Seetharami R Seelam (seelam@cs.utep.edu)       

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 \textit{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, \textit{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.             


