US 5,692,185 A · Object space manager method and circuit

Abstract

The garbage-collecting memory module (GCMM) functions much like traditional memory in a computer system, thereby permitting the invention to be utilized with a wide variety of computers. It differs from traditional memory in that it automatically cleanses itself of garbage while functioning as traditional memory without causing excessive delays in the execution of application programs by an associated computer. The GCMM can be designed to interface with a computer system via a traditional memory bus and to communicate with the central processing unit (CPU) of the computer using standard communication protocols. The GCMM is comprised of a memory, a means for communicating with the CPU, and a garbage-collecting control unit. The garbage-collecting control unit gives top priority to satisfying the computer's requests for memory services. The collection of garbage takes place during the intervals between memory service requests. Garbage collection is accomplished by copying live objects that are stored in one region of memory to a second region thereby leaving dead objects behind in the first region. When the copying process has been completed, the dead objects are disposed of, and the garbage-collecting process continues with the copying of live objects in the second region back to the first. An up-to-date list of live objects is maintained by the CPU and forwarded to the GCMM at the start of each garbage-collection cycle.

Claims18

Dependent claims

An object space manager circuit for locating headers of objects in an associated memory containing L.sub.1 memory cells, the individual memory cells being represented by the integers from 0 to L.sub.1 -1, L.sub.1 having a plurality of submultiples N.sub.1, N.sub.2, . . . N.sub.G, the largest submultiple N.sub.G being equal to L.sub.1, an object being allocated memory cells from S.sub.1 to S.sub.2, S.sub.1 containing the header of said object, said object space manager circuit comprising:

a code memory;
a coding circuit which generates an object locator code, for each associated memory cell S in the range S.sub.1 to S.sub.2, S.sub.1 and S.sub.2 being inputs to said coding circuit, M(S) being the subscript of the smallest of said submultiples for which INT(S/N.sub.M(S)) equals INT(S.sub.1 /N.sub.M(S)), INT( ) being the integer portion of the quantity in parentheses, said code being outputted to said memory for storage.

An object space manager circuit for locating headers of objects in an associated memory containing L.sub.1 memory cells, the individual memory cells being represented by the integers from 0 to L.sub.1 -1, L1 having a plurality of submultiples N.sub.1, N.sub.2, . . . N.sub.G, the largest submultiple N.sub.G being equal to a submultiple F of L.sub.1, an object being allocated memory cells from S.sub.1 to S.sub.2, at least one of said memory cells being in the range from QF to (Q+1)F-1, Q being an integer between 0 and L.sub.1 /F-1, said object space manager circuit comprising:

a code memory;
a coding circuit which accepts as inputs the two integers S.sub.1 and S.sub.2, generates an object locator code for each of said allocated memory cells S in the range QF to (Q+1)F-1 comprising a plurality of level-H codes, H taking on integer values between 1 and G, and stores said object locator code in said code memory, each of said level-H codes consisting of a "valid" integer and an "offset" integer, the "valid" integer of all of said codes being initially set equal to 0, the "valid" integer and the "offset" integer of the level-H code for S being set equal to 1 and S.sub.1 modulo N.sub.H respectively for the smallest value of H for which INT(S.sub.1 /N.sub.H)-INT(S/N.sub.H) is equal to 0, INT( ) being the integer portion of the quantity in parentheses, the "valid" integer and the "offset" integer of the level-G code for S being set equal to INT(S.sub.1 /F)-INT(S/F) and S.sub.1 modulo F respectively if INT(S.sub.1 /F) does not equal INT(S/F), the "valid" integer for all other level-H codes for S being set equal to 0.

A process for identifying the first memory cell in a first sequence of memory cells given the number of any first-sequence memory cell, said first sequence being a portion of a second sequence of memory cells represented by the integers from 0 to L.sub.1 -1, the first memory cell of said first sequence being the memory cell with the lowest second-sequence number, L1 having a plurality of submultiples N.sub.1, N.sub.2, . . . N.sub.G, the largest submultiple N.sub.G being equal to a submultiple F of L.sub.1, an object being allocated memory cells from S.sub.1 to S.sub.2, at least one of said memory cells being in the range from QF to (Q+1)F-1, Q being an integer between 0 and L.sub.1 /F-1, said process comprising the steps:

accepting as inputs the two integers S.sub.1 and S.sub.2 ;
generating an object locator code for each member S of said first sequence in the range QF to (Q+1)F-1 comprising a plurality of level-H codes, H taking on integer values between 1 and G, each of said level-H codes consisting of a "valid" integer and an "offset" integer, the "valid" integer of all of said codes being initially set equal to 0, the "valid" integer and the "offset" integer of the level-H code for S being set equal to 1 and S.sub.1 modulo N.sub.H respectively for the smallest value of H for which INT(S.sub.1 /N.sub.H)-INT(S/N.sub.H) is equal to 0, INT( ) being the integer portion of the quantity in parentheses, the "valid" integer and the "offset" integer of the level-G code for S being set equal to INT(S.sub.1 /F)-INT(S/F) and S.sub.1 modulo F respectively if INT(S.sub.1 /F) does not equal INT(S/F), the "valid" integer for all other level-H codes for S being set equal to 0;
saving said object locator codes.

Dependencies are inferred from the claim text.

Object space manager method and circuit

Life of this patent

Object space manager method and circuit

Life of this patent

Abstract

Claims18