Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1998-11-09
2001-08-21
Nguyen, Hiep T. (Department: 2185)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S206000, C711S209000, C711S147000
Reexamination Certificate
active
06279095
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to a method and apparatus for memory management and more specifically, to a method and apparatus for ensuring that memory pages will always be present and mapped in the memory of a data processing system.
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.
A page fault occurs when an application program requests a particular page of memory, but that page is not present in memory, or when a particular page is present but not yet mapped into the program's address space (i.e., when the page is not “mapped”). Operating systems usually respond to a page fault by bringing the missing page into memory and mapping it. Bringing the page into memory and/or mapping it, however, can be too time-consuming for certain application programs.
Therefore, many data processing systems allow application programs (or users) to “lock” memory. Locking memory means that the memory is guaranteed to be present in the memory of the data processing system and that it will not be swapped out. Locking some or all of the memory avoids “page faults” for the locked memory because the locked pages are guaranteed to be present. Locking some or all of memory may not, however, guarantee that the memory is mapped.
While some conventional systems implement a virtual paging scheme that allows applications and/or processes executing on the system to share memory, these data processing systems generally do not guarantee that shared memory will be mapped.
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.”
A preferred embodiment of the present invention guarantees that a page of memory is physically mapped in all addressing paths in which it appears via a scheme called “omnibus wiring.” Omnibus wiring is used, for example, when a page needs to be “locked.” If a page is omnibus wired, it is guaranteed that the page is present in memory and the mapping tables pointing to the page's location are present and filled in for all possible address references to the page. Because the system is which the present invention is implemented allows memory sharing between processes, there can be several virtual addresses that address a single page. Some of these references may include “uplevel references,” which are references to a portion of a larger address space than can be addressed by the MOR.
Omnibus wiring can be invoked in two ways: 1) when a request is received that a page should be omnibus wired (see FIG.
9
(
a
)) and 2) when a new mapping is created that leads to a page that is already omnibus wired (e.g., when two processes share memory) (see FIG.
9
(
b
)).
In a preferred embodiment of the present invention, omnibus wiring is performed in two phases. A first phase, called the “dry run” creates any necessary mapping tables but does not make any logical changes to existing mapping tables. The dry run allows the data processing system to back out of its promise to do omnibus wiring if some failure occurs during the dry run. The second phase involves making changes to logical tables by recursing up and down through the logical tables making necessary changes to the logical tables. Omnibus wiring can also be performed in a single stage, where the two phases are combined.
Each PMO contains an Omnibus wiring (OW) flag, which indicates that some downstream memory objects are already omnibus wired, i.e., that all mapping tables needed to map the omnibus wired objects are actually filled in and that the corresponding pages are present in memory.
The “span” of a PMO is the size of memory that can be referenced by the PMO. The span of an entry in a PMO is the span of the next smaller PMO (or, if this is the smallest PMO, the size of a page). The span of a mapping table is the size of the memory that can be referenced by the mapping table. The span of an entry in a mapping table is the span of the next smaller mapping table (or if this is the smallest mapping table, the size of a page). Each PMO also has an associated “Mapping Table Reference span” (called an “MTR span”). An MTR span is a span of the entries in a smallest mapping table that can be associated with the PMO. (As described above, the span of these entries is the span of the next smaller mapping table).
Each PMO also contains a “cached min Span Code Referrer Mapping Table Reference” (cached MSCR) field. The cached MSCR field of a PMO usually indicates the smallest mapping table reference (MTR) of any PMO that references that PMO directly or indirectly. Thus, it is known that, for a particular PMO, there are no upstream mapping tables having entries with a smaller span than the cached MSCR value of the PMO.
The cached MSCR field is used to determine whether it is necessary to continue recursing upwards when omnibus wiring a MOR, since there is a special case associated with “uplevel references” and omnibus wiring, as described below in more detail.
In accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method, performed by a data processing system having a virtual memory system, to omnibus wire a page in memory, comprising: following a first group of pointers that refer to the omnibus wired page upwards in the virtual memory system to ensure that all elements referenced by the first group of pointers are also omnibus wired, where omnibus wiring the page guarantees that the page is present in memory, that all mapping tables referencing the omnibus wired page are also present in memory, and that the omnibus wired page can be referenced via the mapping tables; and following a second group of pointers that also refer to the omnibus wired page, where the second group of pointers are part of an uplevel reference, upwards in the virtual memory system to ensure that all memory elements referenced by the second group of pointers are also omnibus wired.
The invention further comprises the act of checking a cached MSCR field in a first memory element in the second group and, if the cached MSCR field is greater than or equal to a span of a memory element in the second group, stopping the upwards recursion.
REFERENCES:
patent: 4277826 (1981-07-01), Collins et al.
patent: 4
Compaq Computer Corporation
Encarnacion Yamir
Fenwick & West LLP
Nguyen Hiep T.
LandOfFree
Method and apparatus for omnibus wiring of virtual mapping... 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 omnibus wiring of virtual mapping..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for omnibus wiring of virtual mapping... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546535