A Comparison of FFS Disk Allocation Policies
Keith A. Smith and Margo Seltzer
Harvard University
Abstract
The 4.4BSD file system includes a new algorithm for allocating disk
blocks to files. The goal of this algorithm is to improve file
clustering, increasing the amount of sequential I/O when reading or
writing files, thereby improving file system performance. In this
paper we study the effectiveness of this algorithm at reducing file
system fragmentation. We have created a program that artificially
ages a file system by replaying a workload similar to that experienced
by a real file system. We used this program to evaluate the
effectiveness of the new disk allocation algorithm by replaying ten
months of activity on two file systems that differed only in the disk
allocation algorithms that they used. At the end of the ten month
simulation, the file system using the new allocation algorithm had
approximately half the fragmentation of a similarly aged file system
that used the traditional disk allocation algorithm. Measuring the
performance difference between the two file systems by reading and
writing the same set of files on the two systems showed that this
decrease in fragmentation improved file write throughput by 20% and
read throughput by 32%. In certain test cases, the new allocation
algorithm provided a performance improvement of greater than 50%.
Download the full text of this paper in PDF,
ASCII (46,394 bytes) and
POSTSCRIPT (198,245 bytes) form.
To Become a USENIX Member, please see our
Membership Information.