DYNAMIC STORAGE ALLOCATION ON A COMPUTER WITH VIRTUAL MEMORY

RICHARD P. BRENT

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.

Comments

Only the Abstract is given here. The full report appeared as [1], and a shorter version appeared as [2].

References

1. R. P. Brent, “Dynamic storage allocation on a computer with virtual memory”, Report CMA-R37-84, CMA, ANU, September 1984; and Report TR-CS-84-06, DCS, ANU, October 1984, 42 pp. rpb090.

2. R. P. Brent, “The most-recently-used strategy for dynamic storage allocation on a computer with virtual memory”, Proc. Eighth Australian Computer Science Conference, special issue of Australian Computer Science Communications 7 (1985), 17.1–17.8. rpb091.

Department of Computer Science and Centre for Mathematical Analysis, Australian National University, Canberra

1991 Mathematics Subject Classification. Primary 68M20; Secondary 68M07, 68N15, 68P05, 68P20.

Key words and phrases. Algorithms, performance, dynamic storage allocation, dynamic memory management, paging, virtual memory, list processing, linked lists, stacks, first-fit strategy, least-free strategy, most-free strategy, most-recently-used strategy, new, dispose, Pascal.

CR Categories. D.3.4, D.4.2, D.4.8, E.2.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1984, 1993, R. P. Brent. rpb090a typeset using AMS-L^{A}TEX