Browse Prior Art Database

Discrete Space Management on Asynchronous Disk Arrays Disclosure Number: IPCOM000111981D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 122K

Publishing Venue


Related People



Fig. 1. Space allocation on asynchronous disk arrays. Each rectangle is an extent.

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

Discrete Space Management on Asynchronous Disk Arrays

       Fig. 1.  Space allocation on asynchronous disk arrays.
Each rectangle is an extent.

      One important problem in designing asynchronous disk arrays is
how to manage storage space effectively.  Two major components of
space management are extent allocation and de-allocation.  On
conventional sequential storage systems, an extent is a contiguous
storage space.  On disk arrays, conventional wisdom is to model
extents as rectangles of arbitrary sizes and pack them disjointedly
on the two dimensional storage space.  Fig. 1 shows an example of
packing extents on an asynchronous disk array.  When an extent is
de-allocated, the corresponding rectangle is returned to the disk
array and becomes available for reuse.  However, packing and
unpacking rectangles on disk array space are functions of high
complexities and may also result in low disk space utilization.  In
this invention, we present a discrete space management approach which
simplifies the two-dimensional rectangle packing and unpacking
problem into a set of one-dimensional problems.  The approach can
also increase disk space utilization.

      Since disk spindles in asynchronous disk arrays are not
synchronized, accesses to disk string can be independent.  Hence it
is not necessary to allocate an extent on adjacent strings.  On each
string to be allocated, it is unnecessary to start at the same
location either.  Therefore, on asynchronous disk arrays, it is
unnecessary to directly pack rectangles on storage space.

      Let each extent Ei on an asynchronous disk array requests Li
blocks on each of Wi strings, where Li and Wi are integers.  The
request is modeled by a rectangle (Wi, Li), where Wi and Li are the
width and length of the rectangle, respectively.  In our invention,
these rectangles are not packed directly onto the disk array.
Instead, each rectangle (Wi, Li) is first partitioned horizontally
into Wi segments of length Li.  These segments are then independently
allocated on arbitrary Wi disk strings.  The Wi strings are not
necessary adjacent and segments allocated on different strings may
start at different locations.  For example, if the disk array has
eight disk strings numbered from 0 to 7 and Wi = 4, then it is
possible to allocate segment 1 starting at block 1 of string 1,
segment 2 at block 3 of string 6, segment 3 at block 2 of string 4,
and segment 4 at block 1 of string 7.  Multiple data sets are
allocated similarly one after another.  Fig. 2 shows an example...