Scheduling Multiple Flows on Parallel Disk Systems

Abstract. We examine the problem of scheduling concurrent independent flows on multiple-disk I/O storage systems. Two models are considered: in the shared buffer model the memory buffer is shared among all the disks, while in the partitioned buffer model each flow has a private buffer. For the parallel disk model with d> 1 disks it is shown that the problem of minimizing the schedule length of n> 2 concurrent flows is NP-complete for both buffer models. A randomized scheduling algorithm for the partitioned buffer model is analyzed and probabilistic bounds on the schedule length are presented. Finally a heuristic based on static buffer allocation for the shared buffer model is discussed.