Chainmail: A Model of First-fit Memory Allocation
C. M. Reeves · The Computer Journal · 1987
First-fit memory allocation is most simply modelled as a Markov chain but with an unmanageably large state space. By exploiting the localisation of the effects upon the store of block reservation and release, a tractable model is derived for the stochastic equilibrium of memory configuration. The interactions between positions and sizes of blocks constitute a two-dimensional structure of equations giving rise to the name Chainmail. The greater analytical complexity of these equations is compensated for by a reduction in the computational complexity of their solution. The model is validated by comparison with a number of simulation experiments using both left and right placement strategies.