Analysis of Disc Fragmentation Using Markov Chains

The fragmented storage map is represented by a Markov model which incorporates correlation between locations not necessarily adjacent to one another. Formulae for the average access distance for contiguous and non-contiguous allocations are given. For large storage requirements, the performance penalty of the former can be substantially higher than that of the latter: they are shown to be O(k**n) and O(n), respectively, where n is the storage requirement and k greater than 1. The Markov model is also able to achieve close agreement with published measurements.