The MRU strategy for dynamic storage allocation
91. R. P. Brent, The most-recently-used strategy for dynamic storage
allocation on a computer with virtual memory,
Australian Computer Science Communications 7 (1985), 17.1-17.8.
Paper: pdf (504K).
Abstract
We compare several dynamic storage strategies under the assumption that
they will be used on a computer with virtual memory.
We show that dynamic storage allocation
strategies which work well on computers without virtual memory may exhibit
poor paging behaviour in a virtual memory environment. We suggest a new
dynamic storage allocation strategy, the most recently used (MRU)
strategy, which is intended to minimize the number of page faults while
keeping the total (virtual) memory used within reasonable bounds.
Even in the simple case that all blocks allocated are of one fixed size,
the MRU strategy may be preferable to the widely used strategy of keeping
a singly-linked list of freeblocks and allocating then according to a
stack (i.e. last-in, first-out) discipline.
Comments
This is a shorter version of [90],
restricted to the MRU strategy.
Go to next publication
Return to Richard Brent's index page