Dynamic Memory Allocation-a Markovian Analysis
Georg Ch. Pflug · The Computer Journal · 1984
A new, approximate Markovian approach for the analysis of the behaviour of dynamic memory allocation algorithms is presented in this paper. The most famous result in this area, Knuth's 50% rule, is given a new sense. The distribution of the number of free blocks is calculated explicitly for low storage utilization. Thus, simulation results published by earlier authors can be explained by the analysis. However, the method is an approximate one. The exact form of the stationary distribution of the storage configuration is still unknown and its determination seems–owing to the complexity of the system–to be a very hard problem.