Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1999-05-27
2002-06-04
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S220000, C711S219000, C711S203000, C711S200000
Reexamination Certificate
active
06401185
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems and more particularly to paged memory management for a run-time execution 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.
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 adapted 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 or pages for the part of the object that cannot fit on the first page.
When an object in a paged memory management system crosses a page boundary (referred herein to as a “paged object”), slot-access operations for the object need additional support from the run-time environment. A slot-access operation gets or sets a value of a “slot” in a object (i.e. a field or instance variable) at a known displacement from the virtual address of the beginning of the object. If the object is contiguous or fits on a single page, then the address of the slot can be determined simply by adding the displacement to the beginning of the object. For paged objects, on the other hand, this addition results in an invalid address when the displacement crosses one more page boundaries, because the page boundary may occur between any of the slots and vary from instance to instance.
Accordingly, a slot-access operation of a machine pointer to a paged object requires checking to see if adding the displacement crosses one or more page boundaries. When there is such an “excess displacement,” the logical page number and page offset for the displacement address is calculated, and the address of the beginning of the page is fetched from the page map and dereferenced with the page offset. This calculation is complicated when a certain amount of each page is reserved in a page header, for example, by the operating system or the run-time environment to store administrative information about the page. Conventionally, the page header is kept as small as practical because the page header represents overhead that is not available for storing objects of the program.
In accordance with one approach, the logical page number and the page offset are calculated by computing the integer quotient and remainder of the excess displacement with the effective size of the page. For example, if the page size is 4096 (2
12
) and the page header size is 120, then the effective page size is 4096−120=3976. For an excess displacement of 5000, the calculated integer quotient is 5000%3976=1, and the calculated remainder is 5000% 3976=1024. Thus, the address of the slot is 1024 bytes past the header of the first page after the next page.
Micro-benchmarks on the Pentium™ processor have determined that more than half of the time required to compute the slot address is spent performing the integer division and remainder calculations. Because slot-access calculations consume a significant portion of the run-time environment's time budget for all operations (e.g. about 5%), overall system performance of the run-time environment can be improved by improving the performance of the slot-access computation.
SUMMARY OF THE INVENTION
Therefore, there is a need for improving the performance of a run-time environment operating with a paged memory management system. More specifically, a need exists for a fast method of computing the slot address of a paged object, particularly when the logical displacement of the slot results in an address on another page. There exists a need for avoiding integer division and remainder operations by the processor in slot-access calculations.
These and other needs are addressed by the present invention, in which the integer division and remainder operations are replaced by a fast division technique that counts the number page boundaries crossed by the logical displacement and adding back into the remainder the size of the page header for each page boundary crossings. Accordingly, it is possible to employ arithmetical-logical operations of shifting and masking, which are faster than most hardware implementations of integer division and modulus, respectively. In another aspect, the use of these operations is facilitated by requiring the page size and the size of the page header to be a power of two.
Accordingly, one aspect of the invention pertains to a computer-implemented method and a computer-readable medium bearing instructions for accessing a slot of an object allocated on more than one page, when the slot is logically located at an excess displacement from an end of the first page upon which the object is allocated. Each page has the same page size and a page header of the same size. In accordance with this methodology, the number of page boundaries crossed by the excess displacement is calculated, e.g. by shifting, to identify which one of the pages the slot is located upon. A page offset for an address of the slot is calculated by adding a remainder of the excess displacement modulo the page size, e.g. by masking, and the number of crossed page boundaries in units of the common page header size. Thus, the slot is accessed at the page offset from the beginning of the identified page.
Another aspect of the invention relates to a computer-implemented and a computer-readable medium bearing instructions for managing memory in a paged memory system. In this system, 2
M
bytes of memory is allocated for each page, and 2
K
is allocated for each page header by padding where necessary. Consequently, a slot of an object, when the slot is located at an excess displacement from the end of the first page for the object, is accessed by calculating a quotient and remainder of the excess displacement modulo 2
M
−2
K
. The quotient indicates the page containing the slot and the remainder indicates the logical offset on the page for the slot.
In one embodiment, the quotient and remainder of the excess displacement modulo 2
M
−2
K
is calculated by shifting the excess displacement by K bits to produce a first partial quotient; masking the excess displacement to retain the K least significant bits thereof to produce a first partial remainder; calculating a second partial quotient and a second partial remainder of the first partial quotient by 2
M−K
−1; shifting the second partial remainder by K bits and adding a result thereof and the first partial remainder to produce the remainder; and establishing the second partial quotient as the quotient.
In another embodiment, the quotient and remainder of the excess displacement modulo 2
M
−2
K
is calculated by comparing the excess displacement and 2
M
−2
K
; if the excess displacement is less than 2
M
−2
K
, then establishing zero as the quotient
Sexton Harlan
Unietis David
Ditthavong & Carlson P.C.
Oracle Corp.
Peikari B. James
LandOfFree
Method and apparatus for accessing paged objects using a... 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 accessing paged objects using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for accessing paged objects using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2943421