Free Space Management

Free Space Management

• Space that is allocated to files must be managed and space which is not allocated to any file must be managed. To keep track of free disk space, the system maintains a free space list. File allocation table and disk allocation both are required to manage free space properly.

• When a file is deleted, its disk space is added to the free-space list.

• Following are the techniques used for free space management:

1. Bit tables or bit vector

2. Chained free portions or linked list

3. Indexing or grouping

4. Free block list or counting

1. Bit tables or bit vector old

• Each block on the disk is represented by bit. It uses vector chain for blocks. Free block is represented by o and used block represented by 1.

• For example, consider a disk where blocks 3, 4, 5, 7, 9, 14, 15, 19, 30, 31, 32, 35, 36, 37, 38 are free blocks and rest of the blocks are allocated. The free space is shown below:

111000101011110011101111111111000110000

• The memory required for a block bitmap = Disk size / 8 × (block size of file system)

• Bit map requires extra space. For example:

• When bit table is stored into the memory, then exhaustive search of the table can ano slow file system performance. Most of the file system use auxiliary data structure al for bit table. File system also maintain summary table. Summary table contains sub-range, number of free blocks and maximum sized contiguous number of free blocks.

• Summary table is used to store information about contiguous free blocks. Whenever file system needs a number of contiguous blocks, it can scan the summary table to find an appropriate sub-range and then search that sub-range. This method is used in Apple Macintosh.

Advantage :

a. Easy to find a free blocks

b. It is as small as possible.

Disadvantage :

It may not be feasible to keep the bitmap in memory for large disks.

2. Link list

• In this method, all free space disk blocks are linked, keeping a pointer to the first free block. All file allocation methods used link list free space techniques.

• There is small space overhead because there is no need for a disk allocation table. In the above example, free blocks are 3, 4, 5, 7, 9, 14, 15, 19, 30, 31, 32, 35, 36, 37, 38. Here free block pointer is on block number 3. Block 3 contains pointer to block 4, block 4 contains pointer to block 5 and block 5 contains pointer to block 7 and so on.

• This method is not efficient because to reach free block 9, we have to traverse 973 block 3, 4, 5 and 7 then we will reach to block 9.

• Disk will become quite fragmented after some use. Many portions will be a single block long.

3. Grouping

• First free block contains the addresses of n free blocks. The first n-1 of these blocks is actually free. The last block also contains the address of another n free block.

• Consider the free blocks: 3, 4, 5, 7, 9, 14, 15, 19, 30, 31, 32, 35, 36, 37, 38

• When all the blocks in the group have been allocated, then use the block that held the pointer.

• Because of grouping method, address of a large number of free blocks can be found quickly.

4. Counting

• It keeps 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.