Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1998-08-20
2001-08-21
Yoo, Do Hyun (Department: 2185)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S206000, C711S208000
Reexamination Certificate
active
06279094
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to memory management in a computer system and, specifically, to a memory management system for a computer system having multiple levels of virtual memory mapping tables.
Many types of general purpose computers and data processing systems contain memory that is organized using a “virtual memory” scheme. In general virtual memory allows applications and/or processes that are executing in the computer to behave as if they have an unlimited amount of memory at their disposal. In actuality, the amount of memory available to a particular application or process is limited by the amount of memory in the data processing system and further limited by the number of concurrently executing programs sharing that memory. In addition, a virtual memory scheme hides the actual physical address of memory from the application programs. Application programs access their memory space using a logical address, which is then converted to a physical address by the data processing system.
A virtual memory system organizes memory in units called “pages.” These pages are moved between a fast, primary memory and one or more larger and usually slower secondary, tertiary, etc. memories. The movement of pages (often called “swapping”) is transparent to the applications or processes that are executed in the data processing system, enabling the applications or processes to behave as if they each have an unlimited amount of memory.
Various conventional systems, however, are somewhat inefficient, either in how they swap pages or in how they manage various aspects of “clean-up” associated with swapping memory pages, especially under circumstances where two or more executing processes are allowed to share memory between themselves.
SUMMARY OF THE INVENTION
A preferred embodiment of the present invention operates within an object-oriented virtual memory management system. In the virtual memory management system, each page is referenced by traversing a series of mapping tables, which point to pages present in memory. Each mapping table is associated with one of a plurality of Partitioned Memory Objects (PMOs). Each PMO includes a plurality of Memory Object References (MORs). The lowest level PMOs point to NSKMPage data structures or BMOs (not shown). The NSKMPage data structures keep track of all pages in the physical memory. BMOs keep track of pages in the virtual memory that are not in physical memory. Both PMOs and NSKMPage data structures are collectively called “memory objects.”
Each MOR includes an “involved bit.” When a page is swapped into memory, the involved bits in all MORs relating to the page are set (except for the last MOR on a level). When a page is swapped out of memory, or when a memory reference is changed, such as when memory is shared or unmapped, the present invention allows the mapping tables corresponding to altered memory references to be invalidated in an efficient manner. Once a MOR having an involved bit cleared is detected during invalidation of the mapping tables, there is no requirement to invalidate additional mapping tables for the page.
In accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of invalidating an entry in a mapping table in a virtual memory, comprising the steps of: determining that a logical table entry in the virtual memory has changed; invalidating at least one mapping table entry, where the mapping table entry corresponds to a logical table entry that refers either directly or indirectly to the changed table entry, the invalidating step occurring if that logical table entry has its involved bit set; and stopping invalidating at least one mapping table entry, where the mapping table entry corresponds to a logical table entry that refers either directly or indirectly to the changed table entry, the stopping invalidating step occurring if that logical table has its involved bit clear.
In further accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of servicing a page fault caused by a null entry in a mapping table in a virtual memory system, comprising the steps of: filling in a path of mapping table values to point to the page that caused the page fault; and setting an involved bit in a current logical table in the path when the memory object to which the logical table points has a span greater than the span of an entry in a current mapping table.
REFERENCES:
patent: 4584639 (1986-04-01), Hardy
patent: 6075938 (2000-06-01), Bugnion et al.
Norman Hardy, “KeyKOS Architecture,” Operating Systems Review, vol. 19, n. 4, Oct. 1985, pp. 8-25.
Document entitled “A Programmer's Introduction to EROS,” URL:http://www.cis.upenn.edu/~eros/devel/intro/Progrmrlntro.html, 14 pages total. (publication date unknown).
Norman Hardy, “The KeyKOS Architecture,” Eighth Edition (Dec. 1990), Copyright © Key Logic, eight pages total.
Richard Rashid, Acadis Tevanian, Michael Young, David Golub, Robert Baron, David Black, William Bolosky and Jonathan Chew, “Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures,” Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, 2ndSymposium on Architectural Support for Programming Languages and Operating Systems, ACM Oct., 1987, eight pages total.
Compaq Computer Corporation
Encarnacion Yamir
Fenwick & West LLP
Yoo Do Hyun
LandOfFree
Method and apparatus for managing invalidation of virtual... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for managing invalidation of virtual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for managing invalidation of virtual... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2491513