A pruning-based disk scheduling algorithm for heterogeneous I/O workloads.
In heterogeneous I/O workload environments, disk scheduling algorithms should support different QoS (Quality-of-Service) for each I/O request. For example, the algorithm should meet the deadlines of real-time requests and at the same time provide reasonable response time for best-effort requests. This paper presents a novel disk scheduling algorithm called G-SCAN (Grouping-SCAN) for handling heterogeneous I/O workloads. To find a schedule that satisfies the deadline constraints and seek time minimization simultaneously, G-SCAN maintains a series of candidate schedules and expands the schedules whenever a new request arrives. Maintaining these candidate schedules requires excessive spatial and temporal overhead, but G-SCAN reduces the overhead to a manageable level via pruning the state space using two heuristics. One is grouping that clusters adjacent best-effort requests into a single scheduling unit and the other is the branch-and-bound strategy that cuts off inefficient or impractical schedules. Experiments with various synthetic and real-world I/O workloads show that G-SCAN outperforms existing disk scheduling algorithms significantly in terms of the average response time, throughput, and QoS-guarantees for heterogeneous I/O workloads. We also show that the overhead of G-SCAN is reasonable for on-line execution.
Department of Computer Engineering, Kwangwoon University, Seoul 139-701, Republic of Korea.
Taeseok
T
Kim
Department of Computer Science and Engineering, Ewha University, Seoul 120-750, Republic of Korea.
Hyokyung
H
Bahn
Division of Electrical and Computer Engineering, Hanyang University, Seoul 133-791, Republic of Korea.
Youjip
Y
Won
D000465:Algorithms; D001185:Artificial Intelligence; D006801:Humans; D016247:Information Storage and Retrieval / Q000379:methods*; D010561:Personnel Staffing and Scheduling; D015203:Reproducibility of Results; D012984:Software; D013997:Time Factors; D016526:Workload