Incremental Fragmentation Reduction
Original Publication Date: 1978-Aug-01
Included in the Prior Art Database: 2005-Feb-21
Proposed herein is an algorithm for reorganizing the contents of disk storage to reduce the level of fragmentation (the condition which exists when free space is available in small, discontinuous intervals). Loosely speaking, those intervals are selected where fragmentation is most severe. Data contained in these intervals is then moved elsewhere in the pack. The decrease in fragmentation is obtained by the combination of (a) clearing the intervals selected and (b) using the contents of these intervals to fill small "holes" on free spaces elsewhere in the pack. The result is a substantial reduction of fragmentation at the cost of moving only a fraction of the pack contents.