Page 234 - DCAP103_Principle of operating system

Unit 6: File Management

6.11 Free-Space Management Notes

Since disk space is limited, we need to reuse the space from deleted files for new files, if possible.
(Write-once optical disks only allow one write to any given sector, and thus such reuse is not
physically possible.) To keep track of free disk space, the system maintains a free-space list.
The free-space list records all free disk blocks—those not allocated to some file or directory. To
create a file, we search the free-space list for the required amount of space, and allocate that
space to the new file. This space is then removed from the free-space list. When a file is deleted,
its disk space is added to the free-space list. The free-space list, despite its name, might not be
implemented as a list, as we shall discuss.
6.11.1 Bit Vector

Frequently, the free-space list is implemented as a bit map or bit vector. Each block is represented
by 1 bit. If the block is free, the bit is 1; if the block is allocated, the bit is 0. For example, consider
a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, and 27 are free, and the rest of
the blocks are allocated. The free-space bit map would be
001111001111110001100000011100000 . . .
The main advantage of this approach is its relatively simplicity and efficiency in finding the
first free block, or n consecutive free blocks on the disk. Indeed, many computers supply bit-
manipulation instructions that can be used effectively for that purpose. For example, the Intel
family starting with the 80386 and the Motorola family starting with the 68020 (processors that
have powered PCs and Macintosh systems, respectively) have instructions that return the offset
in a word of the first bit with the value 1. In fact, the Apple Macintosh operating system uses
the bit-vector method to allocate disk space. To find the first free block, the Macintosh operating
system checks sequentially each word in the bit map to see whether that value is not 0, since
a 0-valued word has all 0 bits and represents a set of allocated blocks. The first non-0 word is
scanned for the first 1 bit, which is the location of the first free block. The calculation of the block
number is (number of bits per word) x (number of 0-value words) + offset of first 1 bit. Again,
we see hardware features driving software functionality. Unfortunately, bit vectors are inefficient
unless the entire vector is kept in main memory (and is written to disk occasionally for recovery
needs). Keeping it in main memory is possible for smaller disks, such as on microcomputers,
but not for larger ones. A 1.3-GB disk with 512-byte blocks would need a bit map of over
332 KB to track its free blocks. Clustering the blocks in groups of four reduces this number to
over 83 KB per disk.
6.11.2 Linked List

Another approach to free-space management is to link together all the free disk blocks, keeping
a pointer to the first free block in a special location on the disk and caching it in memory. This
first block contains a pointer to the next free disk block, and so on. we would keep a pointerto
block 2, as the first free block. Block 2 would contain a pointer to block. 3, which would point to
block 4, which would point to block 5, which would point to block 8, However, this scheme is
not efficient; to traverse the list, we must read each block, which requires substantial 1/0 time.
Fortunately, traversing the free list is not a frequent action. Usually, the operating system simply
needs a free block so that it can allocate that block to a file, so the first block in the free list is
used. The FAT method incorporates free-block accounting into the allocation data structure. No
separate method is needed.

LOVELY PROFESSIONAL UNIVERSITY 227