Object space manager method and circuit

• US 5,692,185 A
• Filed: 01/29/1996
• Issued: 11/25/1997
• Est. Priority Date: 12/21/1992
• Status: Expired due to Term

• Current Assignee: Aonix
• Original Assignee: Iowa State University Research Foundation Incorporated (Iowa State University)
• Inventors: Schmidt, William, Nilsen, Kelvin D.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/592,956
• Time in Patent Office: 666 Days
• Field of Search: 395/600, 395/401, 395/427
• US Class Current: 707/814
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence

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.

Claims

1. An object space manager circuit for locating headers of objects in an associated memory containing L₁ memory cells, the individual memory cells being represented by the integers from 0 to L₁ -1, L₁ having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to L₁, an object being allocated memory cells from S₁ to S₂, S₁ 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₁ to S₂, S₁ and S₂ being inputs to said coding circuit, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), INT( ) being the integer portion of the quantity in parentheses, said code being outputted to said memory for storage.

2. The object space manager circuit of claim 1 wherein said code memory is divided into sections numbered from 1 to G, the second element of said object locator code together with a flag bit equal to 1 being stored in section M(S) at memory cell address INT(S/N_M(S)-1), N₀ being equal to 1, the flag bit being set equal to 0 at memory cell addresses INT(S/N_M-1) in section M, M taking on all values between 1 and G not equal to M(S).

3. The object space manager circuit of claim 2 further comprising:

an object locator circuit which accepts an associated memory cell number S allocated to an object as input, retrieves the second element of the object locator code from the section of memory for which said flag bit equals 1 thereby identifying M(S), and produces said S₁ as output, S₁ being equal to N_M(S) +(S₁ modulo N_M(S)).

4. The object space manager circuit of claim 1 further comprising:

an object locator circuit which accepts an associated memory cell number S allocated to an object as input, retrieves the code from said code memory, and produces said S₁ as output, S₁ being equal to N_M(S) +(S₁ modulo N_M(S)).

5. The object space manager circuit of claim 4 wherein said associated memory includes memory cells with numbers in the range from -L₂ to -1, said coding circuit generating an object locator code if S₁ is less than 0 and S is equal to or greater than 0, said coding circuit being inoperative if S is less than 0, the S₁ produced by said object locator circuit being the second element of said code if the first element is equal to 0 and S is equal to or greater than 0, said object locator circuit being inoperative if S is less than 0.

6. The object space manager circuit of claim 1 wherein the code memory comprises G random access memories (RAM'"'"'s) identified by the integers from 1 to G, said code memory having log₂ F address lines and G sets of data lines, log₂ F being an integer, one set of data lines being associated with each of said RAM'"'"'s, said code memory address lines being numbered from 1 to log₂ F in order of address bit significance, address line 1 corresponding to the most significant bit, the address lines for RAM H being address lines 1 to log₂ (F/N_H-1), H being any integer from 1 to G, log₂ N_H being an integer less than or equal to log₂ F, N_G being equal to F, N₀ being equal to 1.

7. The object space manager circuit of claim 6 wherein RAM H has at least (log₂ N_H) data lines.

8. The object space manager circuit of claim 7 wherein RAM H has at least (log₂ (N_H /N_H-1)) data lines.

9. An object space manager circuit for locating headers of objects in an associated memory containing L₁ memory cells, the individual memory cells being represented by the integers from 0 to L₁ -1, L1 having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to a submultiple F of L₁, an object being allocated memory cells from S₁ to S₂, 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₁ /F-1, said object space manager circuit comprising:

a code memory;

a coding circuit which accepts as inputs the two integers S₁ and S₂, 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₁ modulo N_H respectively for the smallest value of H for which INT(S₁ /N_H)-INT(S/N_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₁ /F)-INT(S/F) and S₁ modulo F respectively if INT(S₁ /F) does not equal INT(S/F), the "valid" integer for all other level-H codes for S being set equal to 0.

10. The object space manager circuit of claim 9 wherein said code memory is a random access memory assembly (RAMA) comprising G random access memories (RAM'"'"'s) identified by the integers from 1 to G, said level-H code being stored in RAM H, H taking on the integer values from 1 to G, said RAMA having log₂ F address lines and G sets of data lines, log₂ F being an integer, one set of data lines being associated with each of said RAM'"'"'s, said RAMA address lines being numbered from 1 to log₂ F in order of address bit significance, address line 1 corresponding to the most significant bit, the address lines for RAM H being address lines 1 to log₂ (F/N_H-1), log₂ N_H being an integer less than or equal to log₂ F, N_G being equal to F, N₀ being equal to 1.

11. The object space manager circuit of claim 9 further comprising:

an object location retrieving circuit which accepts as input a value for said S, retrieves from said code memory the level-H "valid" integer and the "offset" integer for the value of H for which the "valid" integer is not equal to 0 and produces said S₁ as output, said S₁ being equal to QF plus N_H plus the "offset" integer if the "valid" integer equals 1, said S₁ being equal to F plus the "offset" integer if the "valid" integer is less than 0.

12. A process for locating the first memory cell occupied by an object in a memory containing L₁ memory cells, the addresses of the individual memory cells being represented by the integers from 0 to L₁ -1, L₁ having a plurality of submultiples N₁, N₂, . . . N_G, the largest submultiple N_G being equal to L₁, an object being allocated memory cells from S₁ to S₂, S₁ being the first memory cell, said process comprising the steps:

generating a code for each memory address S in the range S₁ to S₂, M(S) being the subscript of the smallest of said submultiples for which INT(S/N_M(S)) equals INT(S₁ /N_M(S)), INT( ) being the integer portion of the quantity in parentheses;

saving said codes.

13. The process of claim 12 comprising the additional steps:

inputting to said process an address S associated with a memory cell in said memory allocated to said object;

retrieving the code;

producing said S₁ as output, S₁ being equal to N_M(S) +(S₁ modulo N_M(S)).

14. The process of claim 13 wherein said first memory includes memory cells with addresses in the range from -L₂ to -1 and said generating step results in a code if S₁ is less than 0 and S is equal to or greater than 0, said process being inoperative if S is less than 0, the S₁ resulting from said producing step being the second element of said code if S₁ is less than 0 and S is equal to or greater than 0, said process being inoperative if S is less than 0.

15. An electronic circuit to practice the process of claim 14.

16. 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₁ -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₁, N₂, . . . N_G, the largest submultiple N_G being equal to a submultiple F of L₁, an object being allocated memory cells from S₁ to S₂, 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₁ /F-1, said process comprising the steps:

accepting as inputs the two integers S₁ and S₂ ;

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₁ modulo N_H respectively for the smallest value of H for which INT(S₁ /N_H)-INT(S/N_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₁ /F)-INT(S/F) and S₁ modulo F respectively if INT(S₁ /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.

17. The process of claim 16 comprising the additional step:

accepting as input a value for S;

retrieving the level-H "valid" integer and the "offset" integer for the value of H for which the "valid" integer is not equal to 0;

producing said S₁ as output, said S₁ being equal to QF plus N_H plus the "offset" integer if the "valid" integer equals 1, said S₁ being equal to ("valid" integer plus Q)F plus the "offset" integer if the "valid" integer is less than 0.

18. An electronic circuit to practice the process of claim 17.