A Comparison of FFS Disk Allocation Policies
Keith A. Smith, Margo Seltzer · 1996
A new disk allocation algorithm, added to a recent version of the UNIX Fast File System, attempts to improve file layout by exploiting the clusters of free space that are available in the file system. In this paper I study the effectiveness of this algorithm at reducing file system fragmentation. To do this, I have created a program that artificially ages a file system by replaying a workload similar to that experienced by a real file system. To evaluate the effectiveness of the new disk allocation algorithm, I use this program to replay four months of activity on two file systems that differ only in the disk allocation algorithms that they use. At the end of the four month simulation, the file system that used the new allocation algorithm had 3 % more file data blocks that were contiguously laid out. 1