Subject: Operating Systems

Topic: File Management

Difficulty: Hard

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.

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 relative simplicity and its 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.

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. In our earlier example, we would keep a pointer to 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, and so on (Figure 11.10). However; this scheme is not efficient; to traverse the list, we must read each block, which requires substantial I/O time.

3. Grouping

A modification of the free-list approach is to store the addresses of n free blocks in the first free block. The first n—1 of these blocks are actually free. The last block contains the addresses of another n free blocks, and so on.

The addresses of a large number of free blocks can now be found quickly, unlike the situation when the standard linked-list approach is used.

4. Counting

Another approach is to take advantage of the fact that, generally, several contiguous blocks may be allocated or freed simultaneously, particularly when space is allocated with the contiguous-allocation algorithm or through clustering.

Thus, rather than keeping a list of n free disk addresses, we can keep the address of the first free block and the number n of free contiguous blocks that follow the first block. Each entry in the free-space list then consists of a disk address and a count.

Although each entry requires more space than would a simple disk address, the overall list will be shorter, as long as the count is generally greater than 1.