Real-Time Parallel IO Stream Scheduling

We introduce a framework for real-time I/O scheduling for multiple-disk parallel I/O systems. The framework is used to model a video server delivering continuous media VBR video data with real- time requirements. The video streams are assumed to be stored in CDL format and distributed across multiple disks. Within a server-network-client model, our framework translates the requirements imposed by video and resource availability into constraints on prefetching in the real-time domain. We present a novel algorithm RT-OPT for optimally prefetching blocks into the server buffer. We show that if the schedule created by RT-OPT fails to meet the deadline of any block, then no feasible schedule is possible for the same buffer size, data placement and single-disk scheduling policy. Sim- ulations with MPEG traces show that RT-OPT achieves high scalability by dynamically multiplexing the buffer among different clients and disks optimally. The number of clients supported was shown to be uniformly superior to intuitive but suboptimal algorithms like GREED-EDF that aggressively keep the disks busy fetching in order of deadlines.