Grouped sweeping scheduling for DASD-based multimedia storage management

Abstract

This paper presents a new formulation of DASD (direct access storage device) disk arm scheduling schemes for multimedia storage management. The formulation, referred to as grouped sweeping scheduling (GSS), provides a framework for minimizing the buffer space required in the retrieval of multimedia streams. In GSS, the set of n media streams that are to be served concurrently is divided into g groups. Groups are served in fixed order and streams within each group are served in an elevator-like SCAN scheme. Hence, the fixed order (FIFO) and SCAN schemes are special cases of GSS when g=n and g=1, respectively. In this paper an optimization problem is formulated in which the buffer requirement is minimized with respect to the two design parameters:g and the size of the service unit, i.e. the number of blocks accessed in each service cycle. This formulation initially assumes that all media streams have the same playout requirements. A procedure of complexity O(1) is developed in computing the optimum solution to this problem. The proof of optimality and comparisons between the optimized GSS scheme and FIFO and SCAN are also presented. The paper also discusses the effect of disk arrays in the GSS formulation and issues related to operating GSS in a dynamic setting where streams arrive and depart in random order. Finally, the GSS scheme is extended to support heterogeneous media streams where each stream may have its own playout requirement. © 1993 Springer-Verlag.