Browse Prior Art Database

Object-Based Selective Defragmentation Algorithm for Magneto Optic Media

IP.com Disclosure Number: IPCOM000105582D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 125K

Publishing Venue

IBM

Related People

Dewey, DW: AUTHOR [+2]

Abstract

This article presents an iterative file system defragmentation algorithm that instead of attempting to reorganize an entire file system selects individual files or objects to be moved. The utility is intended for use with a file system tailored to magneto optic media. The increased capacity and slower access speeds of magneto optic media make complete file system reorganization prohibitively slow. An existing selective defrag algorithm was used as a starting point but that algorithm ignores object fragmentation and focuses on free space fragmentation only. Defragmentation of files was also desired to increase read performance. The current algorithm attempts to accomplish the most gain with the least amount of work and may be ran over multiple controlled periods in background time.

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

Object-Based Selective Defragmentation Algorithm for Magneto Optic Media

      This article presents an iterative file system defragmentation
algorithm that instead of attempting to reorganize an entire file
system selects individual files or objects to be moved.  The utility
is intended for use with a file system tailored to magneto optic
media.  The increased capacity and slower access speeds of magneto
optic media make complete file system reorganization prohibitively
slow.  An existing selective defrag algorithm was used as a starting
point but that algorithm ignores object fragmentation and focuses on
free space fragmentation only.  Defragmentation of files was also
desired to increase read performance.  The current algorithm attempts
to accomplish the most gain with the least amount of work and may be
ran over multiple controlled periods in background time.  A
serendipitous result is a utility that allows one to defrag primarily
for write performance or primarily for read performance.

      The common practice for selective defragging in place is to
identify a range or ranges to be cleared and then moving all extents
in that range.  The selection of these ranges is usually based on a
gain/cost ratio where the gain for clearing a range is calculated as:

     Let:     L = Length of the range

              With n free extents in the range:
              For i = 1 to n     fi = Length of free extent i in
range

              With m allocated extents in the range:
              For i = 1 to m     ai = Length of allocated extent i in
                                      range

              Sum1 = Sum of (fi * fi)  for i = 1 to n

              Sum2 = Sum of (ai * ai)  for i = 1 to m

     Then:

              Gain =    (L*L - Sum1 - Sum2) /L

     Cost is measured by the number of sectors to move and the value
Gain/Cost becomes dimensionless.

      The application of this standard range clearing to the file
system being used is difficult since the algorithm implies a mapping
from extents.  A defrag operation doing range clearing would need to
build the new mapping.  The increased capacity of the MO media makes
this prohibitive since often there would not be enough memory or disk
space to store this new mapping.

      Further, standard range clearing does not take into account the
fragmentation of individual objects.  By selecting individual objects
to be moved or coalesced our approach does.

      The algorithm is based on evaluating the gain of moving an
individual object instead of clearing a range.  The evaluation of
gain for moving an object can take into account both the
fragmentation of the object and the effect moving it will have on
free space fragmentation.  Various selection criteria can be chosen
to give a preference towards object or free space...