Dynamic storage allocation on a computer with virtual memory
90. R. P. Brent,
Dynamic storage allocation on a computer with virtual memory,
Report CMA-R37-84, CMA, ANU, September 1984;
Report TR-CS-84-06, DCS, ANU, October 1984, 42 pp.
Abstract:
dvi (3K),
pdf (72K),
ps (25K).
Report: pdf (2019K).
Abstract
We compare several dynamic storage strategies under the assumption that
they will be used on a computer with virtual memory. On such a computer
the total (virtual) memory referenced by a process may exceed the actual
amount of random-access memory available to the process, and it is usually
more important to minimize the number of page faults than the virtual
memory required by the process. 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 some new
dynamic storage allocation strategies which are intended to mininize the
number of page faults while keeping the total (virtual) memory used within
reasonable bounds. The new strategies can be implemented efficiently and
are preferable to well-known strategies such as the first-fit strategy
if the blocks being allocated are appreciably smaller than the page size.
Even in the simple case that all blocks are of one fixed size, the new
strategies may be preferable to the widely used strategy of keeping a
singly-linked list of free blocks and allocating them according to a
stack (i.e. last-in, first-out) discipline.
Errata
[Page numbers start from zero.]
Page 3, line -8: "othan" should be "than".
Page 14, line -4: "1757" should be "1595".
Corrections made in the online version.
Comments
A shorter version (restricted to the MRU strategy) appeared as
[91].
The first-fit strategy is described in [89].
Go to next publication
Return to Richard Brent's index page