System and method for hard real-time garbage collection requiring a write barrier but no read barrier

• US 5,293,614 A
• Filed: 04/08/1991
• Issued: 03/08/1994
• Est. Priority Date: 04/08/1991
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Ferguson, Edward E., McEntee, Timothy J., Bartley, David H.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/682,806
• Time in Patent Office: 1,065 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 364/967, 364/967.4, 364/967.5, 364/246.11, 364/246.7, 364/281.1, 364/281.6, 395/425, 395/600, 395/650, 395/700, 395/725
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Generally, in one form of the invention, a computer system for executing application programs in hard real-time, comprises a central processing unit (CPU) for executing the application programs and system programs and a computer memory partitioned into a data memory and a code memory. A garbage collector, which executes on said CPU, places a write barrier over certain portions of memory. Furthermore, it transfers an object from a location in the memory to a second object at another location in the memory. In a critical section, which may not be interrupted, it allocates sufficient space for the second object so that the entire contents from the first object can be copied into the second object, and in an interruptable section, it copies the entire contents of the first object into the second object. A write routine is linked into the application programs for updating objects in the computer memory. The write routine is operable to update both the first object and the second object whenever the garbage collector is transferring the contents of the object into the second object. Both copies are thereby kept current.

Claims

1. A method for garbage collecting a memory concurrently with the execution of other processes, comprising the steps of:

allocating a required space in a surviving region of said memory to receive an object to be transported from a condemned region of memory during a non-interruptable phase of garbage collection, copying during an interruptable phase of garbage collection each word of said object to be transported from said condemned region to said allocated space; and

maintaining consistency between said object from said condemned space and said allocated space by writing to both said object and said allocated space whenever an application program updates said object and whenever an application program updates said allocated space.

2. A computer system for executing application programs in hard real-time, comprising:

a central processing unit (CPU) for executing said application programs and system programs;

a computer memory in which said application programs allocate objects as blocks of memory;

write means by means of which each said application programs store values in said memory in a store operation and through which each said store operation is monitored;

a garbage collector for executing concurrently with said application programs on said CPU to recover unused blocks of said memory, said garbage collector coupled to said write means for controlling the behavior of said write means based on phases of operation of said garbage collector, said garbage collector during at least one phase copies one original object from a first location of said memory to a second location of said memory; and

said write means responsive to said garbage collector in said one phase for storing values written by said application programs in both said original object at said first location and the copy at said second location.

3. The computer system of claim 2, wherein said write means is a logic circuit.

4. The computer system of claim 2 wherein said write means is a write routine.

5. The computer system of claim 4, further comprising a subroutine library for linking into said application programs and which comprises said write routine.

6. The computer system of claim 2, wherein said garbage collector further comprises code operable to change all references to said original object so that said references refer to said copy.