Linked list file system; block size impact

File system using a linked list

In linked-list allocation each file is a chain of disk blocks. One word of each block holds a pointer (the number of the next block); the rest is data. The directory entry stores the file name and the address of the first block.

 dir: A -> 4
 block 4 : [data..|-> 7]
 block 7 : [data..|-> 2]
 block 2 : [data..|-> end]

• Any free block can be used, so there is no external fragmentation.
• Sequential reading is easy; the file can grow by taking any free block.
• Random access is slow (to reach block n read n blocks) and a block's data size becomes (block size - pointer size).
• Variation: a FAT keeps all next-pointers in a table in memory, which fixes random access speed.

Impact of block size

Block (cluster) size is a trade-off between data rate and space utilization.

• Data rate: time to read a block = seek + rotational delay + transfer time. Seek and rotation are fixed per access, so large blocks give a higher data rate.
• Disk space utilization: most files are small. If the block is larger than the file, space is wasted in the last block (internal fragmentation).

Illustration (Tanenbaum): average seek 5 ms, rotational delay 4.17 ms, transfer rate 100 MB/s, median file size 2 KB:

 data rate   ^            .---- rises with block size
             |        .-'
             |    .-'
             | .-'
 utilization |'-._
             |    '-._.__ falls with block size
             +----------------> block size

So a small block wastes less space but gives poor speed, and a large block is fast but wastes space. A compromise of 4 KB (or 2 to 8 KB) is common.