Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Digital systems, linear algebra, introduction to formal proof / 3 / c / Solution

This is linked file allocation. A file header holds the first and last disk block numbers, and the successor field in each block extends the chain. The header therefore does not impose a fixed small maximum number of blocks per file.

To state a numerical bound, suppose a physical block has $B$ bytes, the successor-or-final-count field occupies $h$ bytes, and $N$ distinct data blocks are both addressable and available. A full block then holds $C=B-h$ payload bytes. If the final count can represent every value up to $C$,A smaller computer file can use an arbitrary number of full payload blocks followed by a partial block, so allocation need not be contiguous. With a $p$-bit disk block number, $N\le 2^p$, reduced by reserved addresses and blocks consumed by other data and metadata. This gives the address-width bound as well as the actual device-space bound.

There is no positive minimum payload size: an empty computer file can be represented by an empty-chain convention or a zero-count terminal block. The question does not specify which representation is used or the relevant field widths, so it does not determine an absolute byte limit or a particular empty-file encoding. Its description presupposes a convention that distinguishes a successor value from a terminal byte count.