Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1998-03-23
2001-04-17
Cabeca, John W. (Department: 2752)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S161000, C711S006000, C711S165000
Reexamination Certificate
active
06219770
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.
Certain conventional systems occasionally need to copy portions of memory. This copy can either be user-initiated or initiated by the operating system. Conventional systems often use a “lazy” copy method in which the memory to be copied is assigned a status of read-only, but the actual copy is deferred until later. If an attempt is made to write into either the original or the copy, the memory is then copied at that time and both the original and the copy are given an I/O status of read-write. In this way, it appears that a copy was made immediately, but the actual copying is deferred until the last possible time. If no write is performed, no copying ever occurs. For this reason, this method is called “copy on write” or “virtual copy.” This method is used, for example to implement the Unix and Posix “fork” operation, which copy the entire private memory of a process. Unix and Posix do not allow two processes to share memory that is subject to copy on write.
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.”
When a memory object is duplicated (also called a “copy on write” or a “virtual copy”), the actual copy of the duplicated memory is deferred until a write to the original or copy of the memory object actually occurs. Each MOR has a VCState field, which can have values of VCOriginal, VCDuplicate, VCSubdupFull, or VCSubdupPart.
During a copy on write operation, a VCState of a MOR (in a PMO) that refers to the duplicated memory object is set to “VCDuplicate.” The MOR is set to point to the memory object that is being copied. The VCState of lower level MORs referring to memory within the copied memory are set to “subduplicate” (which can be either VCSubdupFull or VCSubdupPart). The I/O status of the chain of memory objects is set to ROVC (Read Only Virtual Copy), which indicates that a virtual copy of the memory has been performed. In a preferred embodiment, ROVC is indicated when a NumDupRefs field is zero.
The virtual memory management system allows “uplevel references,” in which a memory object defining a first area of memory opens a “window” on a memory object having a second, larger area of memory. Such uplevel references receive special treatment during the copy on write operation. Only the subset of MORs in the second memory object's tree of memory objects that defines the window that is copied is marked subduplicate. Specifically, if all the memory defined by a MOR is in the window, the MOR is marked as VCSubdupFull. If only part of the memory defined by a MOR is in the window, the MOR is marked as VCSubdupPart.
The use of VCStates of VCSubdupPart and VCSubdupFull (which are collectively called “Subduplicate”) improves the efficiency of the copy on write operation. If, after a first copy on write operation, a second copy on write operation occurs for a portion of memory that overlaps the already-copied memory, it is not necessary to traverse subtrees of MORs having a VCState of VCSubdupFull or VCDuplicate, since these have already been marked during the first copy on write operation. Skipping tree traversals makes it faster to mark the VCState of MORs during a copy on write operation. But, because the nature of uplevel references makes it undesirable to skip marking VCStates for uplevel references, subtrees with a VCState of VCSubdupPart are still traversed and marked during subsequent copy on write operations.
In accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of implementing a copy on write operation, performed by a data processing system, comprising the steps of: receiving an instruction to implement a copy on write for a portion of memory, where the location of the portion of memory is described by a chain of memory objects having an initial memory object and at least one subsequent memory object; creating a copy of a Memory Object Reference (MOR) in the initial memory object; creating a pointer in the copy of the MOR to the memory being copied; marking the copy of the MOR as duplicated, while deferring the actual copying of the memory; and marking at least one MOR in the subsequent memory objects as a subduplicate.
REFERENCES:
patent: 4918653 (1990-04-01), Johri et al.
patent: 5202994 (1993-04-01), Begur et al.
patent: 5465365 (1995-11-01), Winterbottom
patent: 5473777 (1995-12-01), Moeller et al.
patent: 5619696 (1997-04-01), Nakagawa
patent: 5666514 (1997-09-01), Cheriton
patent: 5729710 (1998-03-01), Magee et al.
patent: 5843226 (1998-11-01), Barton et al.
patent: 5893117 (1999-04-01), Wang
patent: 5893155 (1999-04-01), Cheriton
Park et al., Torjan: A High-Performance Simulator for Shared Memory Architectures, 1996, pp. 44-53.*
Branstad et al., Assurance for the Trusted Mach Operating System, 1989, pp. 103-108.*
Costa, COWL: Copy-On-Write for Logic Programs, 1999, pp. 720-727.*
Brustoloni et al., Copy Emulation in Checksummed, Multiple-Packet Communication, 1997, pp. 1122-1130.*
Banahan et al., The Unix Book, 1983, pp. 108-111.*
Goodheart et al., The Magic Garden Explained, 1994, pp. 91, 93, 105-107, 115-117, 177,252, 253.*
Norman Hardy, “KayKOS 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/Progrmrintro.html, 14 pages total. (publication date unknown).
Norman Hardy, “The KeyKOS Architecture,” Eighth Edition (Dec. 1990), Copyright © Key Logic, eight pages total.
Richard Rashid, Avadis 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 page
Cabeca John W.
Compaq Computer Corporation
Fenwick & West
Peugh Brian R.
LandOfFree
Method and apparatus for managing copy on write operations... 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 copy on write operations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for managing copy on write operations... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2515502