FILE-SYSTEM MANAGEMENT AND OPTIMIZATION
Keeping Track of Free Blocks
Once a block size has been chosen, the next issue is how to keep track of free
blocks. Two methods are widely used, as shown in Fig. 4-22. The first one con-
sists of using a linked list of disk blocks, with each block holding as many free
disk block numbers as will fit. With a 1-KB block and a 32-bit disk block number,
each block on the free list holds the numbers of 255 free blocks.
(One slot is re-
quired for the pointer to the next block.)
Consider a 1-TB disk, which has about 1
billion disk blocks.
To store all these addresses at 255 per block requires about 4
Generally, free blocks are used to hold the free list, so the storage
is essentially free.
Free disk blocks: 16, 17, 18
A 1-KB disk block can hold 256
32-bit disk block numbers
(a) Storing the free list on a linked list. (b) A bitmap.
The other free-space management technique is the bitmap.
A disk with
blocks requires a bitmap with
bits. Free blocks are represented by 1s in the map,
allocated blocks by 0s (or vice versa). For our example 1-TB disk, we need 1 bil-
lion bits for the map, which requires around 130,000 1-KB blocks to store.
not surprising that the bitmap requires less space, since it uses 1 bit per block, vs.
32 bits in the linked-list model. Only if the disk is nearly full (i.e., has few free
blocks) will the linked-list scheme require fewer blocks than the bitmap.
If free blocks tend to come in long runs of consecutive blocks, the free-list sys-
tem can be modified to keep track of runs of blocks rather than single blocks.
8-, 16-, or 32-bit count could be associated with each block giving the number of
consecutive free blocks.
In the best case, a basically empty disk could be repres-
ented by two numbers: the address of the first free block followed by the count of
On the other hand, if the disk becomes severely fragmented, keeping
track of runs is less efficient than keeping track of individual blocks because not
only must the address be stored, but also the count.
This issue illustrates a problem operating system designers often have. There
are multiple data structures and algorithms that can be used to solve a problem, but
choosing the best one requires data that the designers do not have and will not have
until the system is deployed and heavily used. And even then, the data may not be
available. For example, our own measurements of file sizes at the VU in 1984 and
1995, the Website data, and the Cornell data are only four samples. While a lot bet-
ter than nothing, we have little idea if they are also representative of home com-
puters, corporate computers, government computers, and others. With some effort
we might have been able to get a couple of samples from other kinds of computers,
but even then it would be foolish to extrapolate to all computers of the kind meas-
Getting back to the free list method for a moment, only one block of pointers
need be kept in main memory. When a file is created, the needed blocks are taken
from the block of pointers.
When it runs out, a new block of pointers is read in
from the disk. Similarly, when a file is deleted, its blocks are freed and added to
the block of pointers in main memory. When this block fills up, it is written to
Under certain circumstances, this method leads to unnecessary disk I/O.
sider the situation of Fig. 4-23(a), in which the block of pointers in memory has
room for only two more entries.
If a three-block file is freed, the pointer block
overflows and has to be written to disk, leading to the situation of Fig. 4-23(b). If
a three-block file is now written, the full block of pointers has to be read in again,
taking us back to Fig. 4-23(a). If the three-block file just written was a temporary
file, when it is freed, another disk write is needed to write the full block of pointers
back to the disk.
In short, when the block of pointers is almost empty, a series of
short-lived temporary files can cause a lot of disk I/O.
An alternative approach that avoids most of this disk I/O is to split the full
block of pointers. Thus instead of going from Fig. 4-23(a) to Fig. 4-23(b), we go
from Fig. 4-23(a) to Fig. 4-23(c) when three blocks are freed. Now the system can
handle a series of temporary files without doing any disk I/O.
If the block in mem-
ory fills up, it is written to the disk, and the half-full block from the disk is read in.
The idea here is to keep most of the pointer blocks on disk full (to minimize disk
usage), but keep the one in memory about half full, so it can handle both file crea-
tion and file removal without disk I/O on the free list.
With a bitmap, it is also possible to keep just one block in memory, going to
disk for another only when it becomes completely full or empty.
benefit of this approach is that by doing all the allocation from a single block of the
bitmap, the disk blocks will be close together, thus minimizing disk-arm motion.