A Note On Bit-Mapped Free Sector Management

Introduction

The most common methods for maintain a list of free sectors on disk are to use either a linked list or a bit map.

Using a linked list has the advantage that is requires no extra storage since the links are stored in the free sectors. It also provides quick allocation and deallocation, requiring only that a free sector be removed from the head of the list, or a freed sector be added to the head of the list, respectively.

The main disadvantage of a linked list is that over time the list tends towards random. That is, unless the list is sorted, sectors are placed on the list in no particular order. The result is poor locality during file access, significantly impacting performance by increasing the average seek time.

By using a bit map, adjacent free sectors will always appear adjacent in the bit map. There is a small cost in terms of storage; that is, the bit map will contain one eighth as many bytes as there are sectors on the disk. There is a potentially more important concern: the average number of bits that must be scanned in order to find a free sector. Since this technique was first used, the size of disks has increased by approximately four orders of magnitude. If the number of bits to be scanned on average increased even a small fraction of this amount, the technique would need to be abandoned.

This question came up in our undergraduate operating systems course. Our initial speculation was that bit maps would be inappropriate for the large disks that are becoming available.

As the following analysis will show, the bit map technique remains viable for large disks, and as we shall see it is, in a sense, independent of the size of the disk.