Browse Prior Art Database

Grouped Sweeping Scheme for Disk Scheduling to Support Multi-Media Applications

IP.com Disclosure Number: IPCOM000116362D
Original Publication Date: 1995-Sep-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 105K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+3]

Abstract

Disclosed is an efficient Grouped Sweeping Scheme (GSS) for disk scheduling to support multi-media applications minimizing the buffer requirement.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Grouped Sweeping Scheme for Disk Scheduling to Support Multi-Media
Applications

      Disclosed is an efficient Grouped Sweeping Scheme (GSS) for
disk scheduling to support multi-media applications minimizing the
buffer requirement.

      In a multi-media file system, the unique requirement is to
support continuous storage and retrieval of media, and maintain
synchronization between multiple media streams.  To meet this
continuous synchronization requirement, a large amount of buffer is
often needed to handle the non-uniform arrival patterns of the blocks
for each media stream from disks.  Developed here is an efficient GSS
for disk scheduling to support multi-media applications to minimize
the buffer requirement.  To serve multiple media streams, previous
works generally use a fixed order round-robin service scheme.  In
this approach, a request from each stream is served in a fixed order
in each cycle of service where a fixed number of blocks is read from
disk for each stream.  Since the blocks from different streams are
inter-mixed on the disk, this can result in a significant amount of
seek (or disk arm movement) delays and degrade the performance.  To
alleviate this problem, an elevator-type service scheme can be
adopted, where the disk arm scans through the tracks from one end of
the disk to the other end and picks up the requested blocks from each
stream in a service cycle.  Since the first stream served in the
previous cycle may be the last stream served in the current cycle,
the buffering requirement has to be able to accommodate two cycles of
delay.  This is in contrast to the fixed order scheme where the
buffering requirement only needs to accommodate one cycle of delay,
albeit the delay of each cycle tends to be longer.  Also, there is a
longer initial delay of a full service cycle time before the media
stream can be started for the elevator-type service scheme.

      The purpose is to reduce the amount of seek delay, but minimize
the worst case bound on the times between two consecutive services to
the same request stream.  The basic idea is to strike a balance
between these two conflicting requirements.  It is desirable to serve
multiple request streams during each scan, but the number served must
be controlled to prevent the worst case bound on inter-service times
from deteriorating significantly.  The proposed GSS for  disk
scheduling addresses the above problems, by dividing the number of
media streams, n, needed to be served into g groups.  The g value is
determined below to optimize the buffer requirement.  The assignment
of streams to groups is arbitrary.  In each cycle of service, scan g
times through the disk tracks from one-end to the other.  In each
scan, one group of <n over g> streams is served.

      To simplify the notation, we assume that a track is the unit
of allocation on the disk.  Each track can contain b blocks of a
medium
stream.  In each service cycle, k blocks are rea...