Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2001-10-09
2004-11-30
Lane, Jack (Department: 2188)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S156000, C711S159000
Reexamination Certificate
active
06826671
ABSTRACT:
TECHNICAL FIELD
The present invention relates to methods and devices for controlling access to physical memory in computer systems using virtual memory techniques.
BACKGROUND ART
To allow many processes to share a limited amount of physical memory in a computer system, modern operating systems (such as Sun Microsystem's Solaris™ operating system (“OS”)) implement virtual memory, which provides a mapping between a process's virtual address space and physical addresses. The operation of virtual memory in a computer system is described in John L. Hennessey and David A. Patterson, Computer Architecture: A Quantitative Approach, pp. 427-472 (2d ed. 1995), which is incorporated herein by reference.
Since more than one process may map its virtual addresses to the same physical location, tagging is necessary to identify which process is currently attempting to access memory. These tags are referred to as contexts. When a process attempts to access a (virtual) address, the process presents this address and the context to a memory management unit (“MMU”). The MMU then consults appropriate data structures that store either all or some subset of virtual-to-physical translations used by the system. These data structures may, for example, be organized as a table, a hierarchy of tables or a linked list. These data structures will be referred to hereafter as “mapping structures.” Such address translations are often cached in a special mapping structure called a translation lookaside buffer (“TLB”), which may have hardware support for speed of accessing translation entries.
The operating system may need to invalidate (demap) the address space of a particular process. Demapping may occur, for example, when a process exits and the OS decides to reuse the context for another process. If the mapping structure resides in memory, rather than in special purpose hardware that supports associative searching, demapping a context may require scanning the whole mapping structure. For very large mapping structures, scanning the structure can present a performance problem. For example, the OS needs to be certain that a context demapping operation has completed before the OS can proceed. Otherwise, another mapping for the same context and virtual address can be created, and, if two mappings exist, incorrect translations can occur. The scanning process to demap a process may take a long time to complete, degrading system performance. If the memory that stores the mapping structure is also used for other data, attempting to complete the demapping process as soon as possible will consume a substantial portion of the memory bandwidth, delaying satisfaction of requests from other clients trying to access non-mapping-structure data.
SUMMARY OF THE INVENTION
In accordance with an embodiment of the present invention, a method is presented for controlling virtual memory in a computer system with a plurality of process contexts. The system contains an address translation mapping structure with a plurality of address translation entries. Each translation entry includes a validity flag and a mapping indicator. A mapping indicator and a cleanup indicator are also maintained for each process context in a context table. When each translation entry is initialized, the entry's validity flag is set and the mapping indicator is set equal to the mapping indicator for the associated context. A process context is demapped by changing the mapping indicator for the context and the cleanup indicator for the context. Memory accesses using a translation entry associated with the demapped context are invalidated since the mapping indicator for the entry does not match the mapping indicator for the context. This embodiment advantageously invalidates all the mapping structure entries associated with a demapped context by changing a single indicator.
In a further embodiment of the invention, a background process scans the cleanup indicator for each context. When the cleanup indicator for any context indicates that the context has been demapped, the process scans the mapping structure. The validity flag for an entry is cleared if the mapping indicator for the entry does not match the context mapping indicator for its associated context. All of the cleanup indicators that indicated that the associated context had been demapped at the start of the scan of the mapping structure are changed to indicate the background process was run, when the scan is completed.
In a memory management device embodiment of the present invention for a computer system, a mapping structure with a plurality of translation entries is included. Each translation entry includes a validity flag and a mapping indicator. A context mapping indicator and a cleanup indicator are provided for each of a plurality of process contexts in a context table. Logic is included that loads each translation entry by setting the entry's validity flag and setting the mapping indicator for the entry equal to the mapping indicator for the associated context. Logic is included that demaps a process context by changing the mapping indicator for the context and the cleanup indicator for the context. Logic is further included that invalidates memory accesses that require translation entries associated with the demapped context, by checking that the mapping indicator for the entry does not match the mapping indicator for the context.
REFERENCES:
patent: 5293597 (1994-03-01), Jensen et al.
patent: 5630087 (1997-05-01), Talluri et al.
patent: 5696925 (1997-12-01), Koh
patent: 5890189 (1999-03-01), Nozue et al.
patent: 5978594 (1999-11-01), Bonnell et al.
patent: 6233667 (2001-05-01), Shaylor et al.
Cassiday Daniel R.
Feehrer John R.
Hill Mark Donald
Jackson Christopher J.
Ostrovsky Boris
Kivlin B. Noäl
Lane Jack
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
LandOfFree
Method and device for a context-based memory management system 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 device for a context-based memory management system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for a context-based memory management system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3338389