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. Th...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/940850 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552160608387072 |
|---|---|
| author | Taeseok Kim Hyokyung Bahn Youjip Won |
| author_facet | Taeseok Kim Hyokyung Bahn Youjip Won |
| author_sort | Taeseok Kim |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-5dc771dadd9f443299e637a6a7fe403f |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-5dc771dadd9f443299e637a6a7fe403f2025-02-03T05:59:27ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/940850940850A Pruning-Based Disk Scheduling Algorithm for Heterogeneous I/O WorkloadsTaeseok Kim0Hyokyung Bahn1Youjip Won2Department of Computer Engineering, Kwangwoon University, Seoul 139-701, Republic of KoreaDepartment of Computer Science and Engineering, Ewha University, Seoul 120-750, Republic of KoreaDivision of Electrical and Computer Engineering, Hanyang University, Seoul 133-791, Republic of KoreaIn 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.http://dx.doi.org/10.1155/2014/940850 |
| spellingShingle | Taeseok Kim Hyokyung Bahn Youjip Won A Pruning-Based Disk Scheduling Algorithm for Heterogeneous I/O Workloads The Scientific World Journal |
| title | A Pruning-Based Disk Scheduling Algorithm for Heterogeneous I/O Workloads |
| title_full | A Pruning-Based Disk Scheduling Algorithm for Heterogeneous I/O Workloads |
| title_fullStr | A Pruning-Based Disk Scheduling Algorithm for Heterogeneous I/O Workloads |
| title_full_unstemmed | A Pruning-Based Disk Scheduling Algorithm for Heterogeneous I/O Workloads |
| title_short | A Pruning-Based Disk Scheduling Algorithm for Heterogeneous I/O Workloads |
| title_sort | pruning based disk scheduling algorithm for heterogeneous i o workloads |
| url | http://dx.doi.org/10.1155/2014/940850 |
| work_keys_str_mv | AT taeseokkim apruningbaseddiskschedulingalgorithmforheterogeneousioworkloads AT hyokyungbahn apruningbaseddiskschedulingalgorithmforheterogeneousioworkloads AT youjipwon apruningbaseddiskschedulingalgorithmforheterogeneousioworkloads AT taeseokkim pruningbaseddiskschedulingalgorithmforheterogeneousioworkloads AT hyokyungbahn pruningbaseddiskschedulingalgorithmforheterogeneousioworkloads AT youjipwon pruningbaseddiskschedulingalgorithmforheterogeneousioworkloads |