Object space manager method and circuit
First Claim
1. An object space manager circuit for locating headers of objects in an associated memory containing L1 memory cells, the individual memory cells being represented by the integers from 0 to L1 -1, L1 having a plurality of submultiples N1, N2, . . . NG, the largest submultiple NG being equal to L1, an object being allocated memory cells from S1 to S2, S1 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 S1 to S2, S1 and S2 being inputs to said coding circuit, M(S) being the subscript of the smallest of said submultiples for which INT(S/NM(S)) equals INT(S1 /NM(S)), INT( ) being the integer portion of the quantity in parentheses, said code being outputted to said memory for storage.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
18 Claims
-
1. An object space manager circuit for locating headers of objects in an associated memory containing L1 memory cells, the individual memory cells being represented by the integers from 0 to L1 -1, L1 having a plurality of submultiples N1, N2, . . . NG, the largest submultiple NG being equal to L1, an object being allocated memory cells from S1 to S2, S1 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 S1 to S2, S1 and S2 being inputs to said coding circuit, M(S) being the subscript of the smallest of said submultiples for which INT(S/NM(S)) equals INT(S1 /NM(S)), INT( ) being the integer portion of the quantity in parentheses, said code being outputted to said memory for storage. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An object space manager circuit for locating headers of objects in an associated memory containing L1 memory cells, the individual memory cells being represented by the integers from 0 to L1 -1, L1 having a plurality of submultiples N1, N2, . . . NG, the largest submultiple NG being equal to a submultiple F of L1, an object being allocated memory cells from S1 to S2, 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 L1 /F-1, said object space manager circuit comprising:
-
a code memory; a coding circuit which accepts as inputs the two integers S1 and S2, 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 S1 modulo NH respectively for the smallest value of H for which INT(S1 /NH)-INT(S/NH) 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(S1 /F)-INT(S/F) and S1 modulo F respectively if INT(S1 /F) does not equal INT(S/F), the "valid" integer for all other level-H codes for S being set equal to 0. - View Dependent Claims (10, 11)
-
-
12. A process for locating the first memory cell occupied by an object in a memory containing L1 memory cells, the addresses of the individual memory cells being represented by the integers from 0 to L1 -1, L1 having a plurality of submultiples N1, N2, . . . NG, the largest submultiple NG being equal to L1, an object being allocated memory cells from S1 to S2, S1 being the first memory cell, said process comprising the steps:
-
generating a code for each memory address S in the range S1 to S2, M(S) being the subscript of the smallest of said submultiples for which INT(S/NM(S)) equals INT(S1 /NM(S)), INT( ) being the integer portion of the quantity in parentheses; saving said codes. - View Dependent Claims (13, 14, 15)
-
-
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 L1 -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 N1, N2, . . . NG, the largest submultiple NG being equal to a submultiple F of L1, an object being allocated memory cells from S1 to S2, 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 L1 /F-1, said process comprising the steps:
-
accepting as inputs the two integers S1 and S2 ; 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 S1 modulo NH respectively for the smallest value of H for which INT(S1 /NH)-INT(S/NH) 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(S1 /F)-INT(S/F) and S1 modulo F respectively if INT(S1 /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. - View Dependent Claims (17, 18)
-
Specification