File space allocation

linked list

The approach at the other end of the spectrum is a linked list. Each block in the file contains a pointer to the next block. The directory entry/inode contains just a pointer to the first block, and usually a pointer to the last block, to speed up append operations. The free blocks on the disk are kept on a 'free chain', which uses the same linkage mechanism as files. Remove blocks from free chain as they are needed.

This has very little overhead (just one pointer per block, say 4/1024 = <0.4%), very simple, quite effective when files are only being read and written serially. Completely negates the problem of external fragmentation. Also, files are relatively self-contained, so that if an error occurs on one part of the disk, individual files may still be recoverable.

Impractical generally, since random access is impossible (well, very, very slow)---this is the biggest problem. Also, blocks are now no longer a power of two (which is a nice attribute for blocks to have). And the free chain will tend to get fragmented, unless it is sorted by disk address (which is time-consuming).


last updated 3 April 1998