File allocation methods; free space management

File allocation methods

The file allocation method decides which disk blocks belong to a file. The main methods are:

1. Contiguous allocation - each file occupies a set of consecutive blocks. The directory stores the start block and length.

 file A: blocks 0-3   file B: blocks 4-6   free 7-...
 [A][A][A][A][B][B][B][ ][ ]

• Advantages: simple; very fast sequential and direct access (only one seek); only start and length are stored.
• Disadvantages: external fragmentation (needs compaction); file size must be known in advance; file growth is difficult.

2. Linked-list allocation - each block contains a pointer to the next block; the directory stores the first block.

 [blk 9 |->2] [blk 2 |->14] [blk 14 |->nil]

• Advantages: no external fragmentation; files can grow easily; no need to know size.
• Disadvantages: random access is very slow (must follow the chain); the pointer takes space in each block (so the data size is no longer a power of 2); one lost pointer breaks the file (poor reliability).

3. Linked list with a table in memory (FAT) - the pointers are moved out of the data blocks into a File Allocation Table in memory; entry i gives the block after block i.

• Advantages: full block available for data; random access is faster (chain followed in memory).
• Disadvantages: the whole table must be in memory (a 1 TB disk with 1 KB blocks needs 10⁹ entries), so it does not scale.

4. Indexed allocation (i-node) - each file has an index block (i-node) that lists the addresses of all its blocks (UNIX adds indirect blocks for large files).

 i-node: [b1][b2][b3]...[single indirect]-->[b..][b..]

• Advantages: supports direct access, no external fragmentation, only the i-nodes of open files need to be in memory.
• Disadvantages: index block overhead (even for a small file); very large files need multiple levels of indirection.

Free disk space management

The OS must keep track of which disk blocks are free. Common methods:

1. Bit map (bit vector) - one bit per block: 1 = free, 0 = allocated (or the reverse). Example: for a disk of 16 blocks where blocks 2, 3, 5, 8, 9 are free:

 block: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
 bit  : 0 0 1 1 0 1 0 0 1 1  0  0  0  0  0  0

Simple and easy to find n consecutive free blocks. Size = number of blocks / 8 bytes: a 16 GB disk with 1 KB blocks has 16 M blocks, so the map needs 16 Mbit = 2 MB.

2. Linked list of free blocks - each free block holds the address of the next free block; the OS keeps only the head. No extra space is used, but traversing the list is slow.

 head -> [2 |->3] -> [3 |->5] -> [5 |->8] -> [8 |->9] -> nil

3. Grouping - the first free block stores the addresses of n free blocks; the last of those holds the addresses of the next n. Many free blocks can be found quickly.

4. Counting - store the address of the first free block and the number of contiguous free blocks following it, e.g. (2,2), (5,1), (8,2). Short list when free space is contiguous.

5. Free list in blocks (pointer blocks) - Tanenbaum: a block holds as many free block numbers as fit (e.g. 255 in a 1 KB block with 4-byte numbers); when it empties, the next list block is read.

Bit map needs more memory than the list on a nearly full disk, but is better on a nearly empty disk.