Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1999-02-11
2002-08-13
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S209000
Reexamination Certificate
active
06434685
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems and more particularly to managing memory for a run-time environment.
BACKGROUND OF THE INVENTION
A dynamic run-time environment for a language such as JAVA™ is responsible for managing memory for objects that are created and destroyed during the execution of a program. An object may be defined as a logically contiguous atomic unit of typed state of the program. Objects thus encapsulate data in particular regions of memory that are allocated and deallocated for the program by the dynamic run-time environment.
The state of the program, or “program state,” is the set of the objects and the references between the objects that exist at a specific point in time during the execution of the program. A “reference” is an entity used to identify and ultimately access the region of memory for storing the data of the object. Typically, references between objects in a run-time environment are encoded using machine pointers, which contain the memory address of the referenced objects. Since machine pointers are closely coupled to the underlying hardware and firmware of a computer system, machine pointers provide a fast means of accessing objects and, hence, are a popular implementation for references.
A program state containing machine pointers is so machine-dependent that it is sometimes disadvantageous. For example, it may be desirable to store the program state on disk and restore the stored program state to main memory, even between different types of machines. For instance, some run-time environments provide load-balancing and crash recovery functions by transferring the execution of a program from one machine to another.
Differences between server environments make machine independence very difficult to achieve for portable run-time environments. For example, some operating systems, in practice if not by design, limit the guaranteed size of contiguous virtual memory to a “page,” typically about two or four kilobytes in size, and prior paged memory systems simply failed when sufficient large blocks of virtual memory was not available. This page-size limitation is particularly common for allocating objects in shared memory for access by different processes.
If the run-time environment is modified to allow objects to be allocated in a plurality of non-contiguous pages, however, then the overhead in calculating which parts of an object belong to which pages becomes a significant factor in system performance. For example, one way to determine which pages belong to an object is to maintain an ancillary data structure called a page map that lists a set of pages in a logical order. If a part of object at a given displacement cannot fit on a page based on the location of the beginning of the object in the page and the displacement into the object, the page map is consulted to determine the next logical page. Furthermore, it may be desirable to different page maps for different groups of objects, for example, read-only objects in a shared memory space and updateable objects in a private memory space.
Therefore, managing memory for objects that can be broken up into pages requires calculating the offset of the beginning of an object within a page, determining the logical page number of the object, and identifying the appropriate page map. One approach is save all this information near the beginning of each object in a preheader, but this is wasteful of memory since the page number and page map is identical for every object on the same page. Another approach is to store the page number and a reference to the page map in a page header at the beginning of the page and store the page offset in the object header. Although memory consumption is somewhat reduced, at least one word of memory for the page offset is still required. System performance is adversely affected, because the extra memory fetch is required to reach the object header.
SUMMARY OF THE INVENTION
There exists a need for a memory management system that is portable to, and capable of working with, operating systems that imposes a page-size limitation to contiguous memory. A need exists for an efficient mechanism for calculating which parts of an object belong to which pages. More specifically, there is need to avoid storing page management information in a preheader, which consumes memory and adds to run-time overhead in performance.
These and other needs are addressed the present invention, in which pages are aligned on a predetermined boundary at least as large as the largest page size, for example, on a 4K boundary. A machine pointer to the beginning of an object is masked according to the alignment restriction to determine the starting address of the page and the page header, including the logical page number and, in some embodiment, a reference to the associated page map. Consequently, it is not necessary to load and store the offset of the object in a preheader of the object, thereby saving memory and improving the performance of page-associated memory management operations.
One aspect of the invention relates to a computer-implemented method and a computer-readable medium bearing instructions for managing a paged memory system, in which objects are stored in pages identified by page numbers. The methodology includes allocating a page of memory aligned at an alignment boundary at least as large as a size of the page. A pointer to one of the objects according to the alignment boundary is masked to produce a page address indicative of a beginning of the page, in which at least a portion of the object is stored on the page. The page number is determined for the page based on the page address.
Another aspect of the invention involves a computer-implemented method and computer-readable medium bearing instructions for converting a machine pointer to an object into a page-offset numeric reference. A page-offset numeric reference indicates an offset within a page of memory to the beginning of the object and a page number of the page. The methodology includes masking a pointer to one of the objects according to a predetermined alignment boundary to produce a page address indicative of a beginning of the page; determining the page number based on the page address; and determining the offset based on the page address.
Yet another aspect of the invention pertains to a computer-implemented method and a computer-readable medium bearing instructions for dereferencing a page-offset numeric reference contained in a referencing object and referring to a referenced object. The methodology includes masking a pointer to the referencing object according to a predetermined alignment boundary to produce a page address indicative of a beginning of a referencing page; determining a reference to a page map based on the page address; and determining a machine pointer to the referenced object based on the reference to the page map, the page number, and offset.
Still other objects and advantages of the present invention will become readily apparent from the following detailed description, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.
REFERENCES:
patent: 5426747 (1995-06-01), Weinreb et al.
patent: 5794256 (1998-08-01), Bennett et al.
patent: 5805896 (1998-09-01), Burgess
patent: 5845331 (1998-12-01), Carter et al.
patent: 6009266 (1999-12-01), Brownell et al.
patent: 6105041 (2000-08-01), Bennett et al.
patent: 6128621 (2000-10-01), Weisz
patent: 6154823 (2000-11-01), Benayon et al.
patent: 6178519 (2001-01-01), Tucker
patent: 6199141 (2001-03-01), Weinreb et al.
patent: 6298401 (2001-10-01), Anderson
patent: 0 700 000 (1996-03-01), None
patent: 0 874 309 (1998-10-01), None
patent: 0967546 (1999-12-01), None
patent: 2 239 335 (1990-
Jungerman Mark
Meyer Scott
Sexton Harlan
Unietis David
Ditthavong & Carlson P.C.
Oracle Corp.
Verbrugge Kevin
LandOfFree
Paged memory management system within a run-time environment does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Paged memory management system within a run-time environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Paged memory management system within a run-time environment will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2915527