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).


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.


This is a shorter version of [90], restricted to the MRU strategy.

Go to next publication

Return to Richard Brent's index page