Abstract
Towards Optimal I/O Scheduling for MEMS-based Storage
by: Hailing Yu, Divyakant Agrawal, and Amr El Abbadi
Abstract:
In recent years, disk I/O performance has become an significantbottleneck in processor-to-disk performance. MEMS-based storage devicesare being developed as a solution to conventional disk devices. This paperfocuses on developing a two-dimensional scheduling algorithm for MEMS-basedstorage devices according to their characteristics. First, we establishthat finding the optimal solution for scheduling algorithms is NP-Hard.Second, off-line and on-line scheduling algorithms are developed. Thenwe analyze these algorithms and conclude that they are guaranteed to perform within twice the optimal time for any workload.
Keywords:
MEMS-based storage, I/O Scheduling, Minimum Spanning Tree
Date:
July 2002
Document: 2002-22
