A software implemented memory manager
John L. Callaghan · ACM SIGPLAN Notices · 1984
INTRODUC~ONThis paper describes the data structures and algorithms for the implementation of a Virtual Memory Manager written mainly in a high-level language without hardware assist mechanisms.BACKGROUND PLUS, an acronym for "Programming Language for Univac Systems", is a high-level language developed by Sperry for internal systems programming.As such, it is a Sperry proprietary language and compiler designed for implementing Sperry Software Products.It includes features, including those described within this paper, found in other languages which would give the Systems Programmer the advantages of greater productivity and machine-independent programs.Among the mechanisms provided by this language is one which provides for a virtual memory system through Areas.Areas represent a scheme in which each programs address space is split into a number of variabla-length blocks celled Areas and fixed--length blocks celled Pages such that each Area is paged through its own Page Table.This scheme is identical to the conventional idea of Segmentation and Paging.Area control statements and routines provide Area management functions.The PLUS statements ALLOCATE, FREE and EMPTY manage Areas while the paged Area has associated UPDATE, REFERENCE, HOLD and RELEASE routines to handle virtual addresses or Ioeators.UPDATE marks a page in memory as updated thus diffenng from the mass storage copy, REFERENCE converts a Iocetor to a pointer, HOLD marks a page as unmovable from primary storage and RE-LEASE performs the reverse function.The specific usage of the Storage Mechanisms described within this paper involves the Universal Compiling System (1). GENERAL DESCRIPTIONThe Memory Space (i.e., the set of real memory addresses) is expandable in n-word blocks maintained on a Free Space List. it is accessed through a set of contiguous addresses celled Iocatora constituting the Address Space.Locators are disassociated from real memory addresses thus allowing real memory requirements that are larger than available primary s~orage, Each locater contains three components.The first component is the Area designation which reflects logical program divisions such as data areas and program blocks and specifies a table entry which contains a Page Table Address.The second component specifies an index into a Page Table entry which contains a Page address.The third component contains a displacement into a Page.For such a three-component reference, three memory references are required.To prevent an intolerable delay, an acceleration mechanism consisting of the most recently referenced Iocator and memory address is maintained.Since memory references are observed to cluster, most page references result in the immediate return of a corresponding memory address.