Dynamic memory management algorithms in a paged memory environment

Abstract

Two algorithms are presented which dynamically cluster pages of a problem program based on past program behavior (i.e., reference string patterns) in a demand paged virtual memory environment. The objective of these algorithms is to minimize the number of page faults encountered by a program during execution, while at the same time to use memory page frames efficiently. Dynamic clusters of "time and reference" related pages are built during a program execution time. Whenever a page fault for the i-th instruction page occurs, in this time evolving environment, the pages of the cluster associated with the i-th page are compared to the pages currently in real (physical) memory. Thus during the page fault, the demand page, and any associated clustered pages not currently in physical memory are placed into memory. Page frames holding pages not in the current cluster are returned to the memory management system. Thus the physical amount of memory allocated to a processing program is dependent upon the size of the cluster associated with the instruction page at that time. When the current instruction page ceases to hold the next instruction, but the next sequential instruction page J is currently in real memory, pages not in instruction page J's domain (cluster) may be returned to the memory management system.