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

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

We claim:

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.

Description

NOTICE

(C) Copyright Texas Instruments Incorporated 1991. A portion of the disclosure of this patent document contains material which is subject to copyright. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention generally relates to real-time systems, in particular it relates to garbage collectors for memory reclamation in systems with hard deadlines.

2. Description of the Related Art

Run-time support systems for most modern programming languages provide a memory management package with which the user can dynamically allocate and deallocate storage for objects. Some memory management packages are automatic in the sense that they reclaim the storage associated with an object when the package can determine that the application can no longer use that object. The component that performs this service is commonly called the garbage collector.

Automatic memory management is a valuable tool for complex applications. It can simplify the task of an application programmer since he can use complex dynamic data structures without having to explicitly determine constituent lifetimes. This freedom can result in more robust applications since subtle errors involving premature or missed deallocation are not possible. Automatic memory management is a fundamental or desirable feature of many programming languages.

Many garbage collectors have been described that are real-time in the sense that they can be guaranteed to reclaim memory faster than the application can allocate it. This macro-level property is not sufficient for a hard real-time system since it is still possible for deadlines to be missed due to micro-level side effects of executing the collector. It is desirable to have a garbage collector that is compatible with hard real-time execution.

A first problem in implementing a real-time garbage collector is providing adequate computational resources to reclaim storage. The time required to reclaim memory is typically much longer than the execution times and deadlines of the hard real-time tasks because reclamation must access a significant fraction of system memory. For the system to be responsive to external events while reclamation is occurring, a procedure may be used for memory reclamation whose execution is interleaved with application tasks.

Another problem is minimizing the impact of the collector on the schedulability of application tasks. Methods for memory reclamation typically involve scanning objects, relocating pointers, and copying objects. These operations cannot be safely interrupted by application tasks that use the automatic memory management abstraction and thus become critical sections during which execution of the application is blocked. It is essential that the duration of such atomic operations be tightly bounded so the reclamation process's interference with the application tasks can be assessed and held to practical values For example, a procedure that must copy an object atomically is undesirable if worst-case behavior must be handled; any task has the potential to be delayed for the time required to copy the largest allocated object.

Another problem is maintaining predictable execution times for application tasks. The choice of reclamation method can affect the execution time of an application task due to the overhead associated with invoking the memory management abstraction. For example, some designs have the property that any access to an object may require that the object be copied from one area of storage to another. It is important to design a procedure that has a uniform and tightly bound overhead so it is possible to automatically or manually determine the execution time of application tasks.

One category of garbage collectors is "copying" collectors. In these, live objects are separated from dead (garbage) objects by copying the live objects to a new area and discarding the dead objects and the original instances of the live objects. This type of collector has the advantage that it compacts the live objects together. However, it has the disadvantage that references to old objects must be adjusted to point to the new copies. Typical implementations use "barriers" on read, write, and object identity tests that occur in application programs. The barriers ensure that consistency is maintained while objects are being transported. Because read operations tend to be more frequent than write and identity tests, it is more efficient to not require a read barrier; accordingly, it is desirable to require the special handling, required by a "barrier," only on write and identity test operations.

Accordingly, improvements which overcome any or all of the problems are presently desirable.

SUMMARY

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 the CPU, places a write barrier over certain portions of memory. Furthermore, it transfers an object from a location in said 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 said 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 consistent.

An advantage of the invention is that the garbage collector may execute as a separately schedulable task. A further advantage of the invention is that it uses no read barrier. A third advantage of the invention is that the critical section, during which the garbage collector may not be interrupted, is of a fixed predictable duration.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a vehicle which uses an embedded system to collect sensory data and to control the vehicle;

FIGS. 2(a) and 2(b) show both hardware and software used to control a vehicle;

FIG. 3 shows the software modules linked together to form one application program;

FIG. 4 shows a view of the various regions which make up the data memory of a computer;

FIG. 5 shows an example data memory during phase one of a garbage collector according to the present invention;

FIGS. 6(a), 6(b), 6(c) and 6(d) together show an example of a condemned region during phase two of a garbage collector according to a preferred embodiment;

FIGS. 7(a) and 7(b) show an example of memory being processed by phase three of the garbage collector according to the present invention;

FIGS. 8(a) and 8(b) show an example of memory being processed by phase four of a garbage collector according to the present invention;

Corresponding numerals and symbols in the different figures refer to corresponding parts unless otherwise indicated.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

In FIG. 1, an airborne vehicle 700 has a computer system 600 connected to sensors 50, 52, 54, and 56. Computer system 600 obtains data, concerning airborne vehicle 700, such as altitude, air speed, direction, and radar information. Computer software (not shown) resident in computer system 600 analyzes this data and advises the pilot of the vehicle. In an alternative embodiment, computer system 600, by way of software, controls the flight of the vehicle. In this case, computer system 600 has access to control mechanisms, for example elevators 60A and 60B, a rudder 64 and the throttle control for an engine 66.

In both cases computer system 600 operates in hard real-time, meaning that computer programs executing on computer system 600 have hard deadlines, which is to say that it is not only desirable to meet the deadlines, but that failing to do so can have fatal consequences.

FIG. 2(a) shows as an example a preferred embodiment of the computer hardware and software of computer system 600. Computer system 600 is connected to sensors 50 through 56 and device controllers 60 and 64. Computer system 600 includes a central processing unit (CPU) 10 connected to a computer memory 20, which stores programs 22 through 32 which CPU 10 executes. Some of these programs are system programs, such as a job scheduler 22 and a garbage collector (GC) 32. Others programs, 24A, 24B, 24C, and 24D, are application programs which may be used to control specific devices, for example control surfaces 60 and 64, and application programs used to analyze data obtained from sensors 50 through 56. Computer memory 20 also contains a data memory 34, in which programs 22 and 24 store data. GC 32 does memory reclamation in data memory 34. FIG. 2(b) shows an alternative embodiment of computer system 600, in which two processors 10A and 10B both access memory 20. The garbage collector 32 executes on processor 10B, while application programs 24 execute on processor 10A.

The above described computer systems are used for illustrative purposes and should not be construed as limitations. In particular, there is neither a limitation on the number of application programs nor is there a limitation to flight system applications. A person skilled in the art will realize that there are many other environments wherein garbage collector 32 is a useful improvement. Furthermore, garbage collector 32 may be implemented either in software or in hardware, as a logic circuit or in firmware.

FIG. 3 is a diagram of an application program 24. An application program consists of some application code 42, an allocator 44, a write routine 46, and an object identity test 48. The allocator 44, the write routine 46, and the object identity test 48 may be parts of subroutine libraries, and they are linked with the application code 42 to form one executable unit 24. In alternative embodiments the allocator 44, the write routine 46, and the object identity test 48, are implemented in hardware, as a logic circuit, or in firmware. In which case, rather than being linked into application program 24, those elements are invoked directly through the execution of the corresponding instructions.

The allocator 44 is responsible for memory allocation, and the write routine 46 manages the necessary overhead with which the application code 42 must contend in order to have real-time garbage collection. The logic which comprises this overhead is described in greater detail below, in conjunction with Phases 1, 2, 3, and 4.

FIG. 4 is a schematic of data memory 34. Data memory 34 is divided into permanent fragments of memory regions 340-356. The regions may be, but do not necessarily have to be, contiguous. Furthermore, the regions may vary in size.

Each region is a spatial division. The number of regions will vary depending on the system. Objects are allocated at allocation pointer 340, which points to the next available memory word for allocation. Only one allocation pointer exists. After an object is allocated, allocation pointer 340 is advanced to the next word following the new object. Memory 34 is treated as if it were circular. When the highest memory address has been allocated, allocation pointer 340 is set to the lowest memory location where objects can be allocated. While the regions themselves are contiguous blocks of memory, the regions do not need to be contiguous with respect to each other. Logically, the regions are arranged in a queue. However, in physical memory there is no restriction on their arrangement.

The portion of memory 20 under consideration does not include a fixed area of memory 20 outside of garbage collector 32's domain which may be desirable in a system implementation; e.g. in FIG. 2, an area 36 of memory 20 contains all code block objects, which might be required to be non-relocatable. The code block objects will not contain any external pointers; therefore, they will not need to be scanned during garbage collection. However, it is possible to store code block objects in data memory 34.

An object cannot cross a region's boundary. If the number of available words left in the region which contains allocation pointer 340 (from allocation pointer 340 to the region's end) is less than the size of the object to be allocated or transported, the object is placed at the first word of the successive region. If an application requires objects of greater size than the region, it is expected such objects will be allocated in an area of memory outside the confines of the garbage collector described here.

A single region, condemned region 352, is garbage collected at a time. Specifically, and viewing memory 34 circularly, it is the first allocated region; i.e., a region containing allocated objects, following allocation pointer 340. Garbage collector 32 adds to the pool of available memory from the "bottom" while the allocator keeps using it from the "top." During garbage collection objects are moved from condemned region 352 into one of the surviving regions, for example the current allocation region 344.

Allocation pointer 340 may not advance into condemned region 352. If it does, the computer has run out of available memory.

FIG. 6 shows an example of condemned region 352. Each object 1-5, at its allocation, will include a mark word 1000, a word of memory used exclusively by garbage collector 32. Each mark word 1000 is initialized to the value `UNMARKED` at the time of the object's allocation. Other values which can exist in a mark word 1000, depending on the garbage collection phase, are `MARK,` an integer used as a pointer to another object, and `NIL` to indicate that the object is the end of a linked list.

A write barrier 370, shown in FIGS. 5, 7, and 8, enables interleaving of garbage collection processing with application processing. A viable implementation of the write barrier is to place the two boundaries of the write barrier in dedicated registers. In the case where the regions are allowed to be arranged in a non-contiguous fashion within the physical memory, write barrier 370 is slightly more complicated in that two registers would be insufficient. One solution is to associate a set of write barrier registers with each region of memory. The write barrier 370 may also be implemented in the memory hardware.

Write barrier 370 surrounds a subset of contiguous memory locations, and the action of the barrier comes into play when a value is written to a word of memory 34. During certain phases of a reclamation, special handling occurs when a reference to an object within the barrier is being written. During other phases, special handling occurs when any value is written into a word in an object residing within the write barrier.

The "special handling" is extra code for the application processes which is required to enable interleaving of garbage collection processing and application processing. This code is part of the write routine 46, shown in Table 1. The garbage collection phases, described below, are not application code overhead, since garbage collection is a separately schedulable task.

The garbage collector 32 operates in five phases, each of which is described below.

The pseudocode listing of Table 1 below shows the details of the operation of the write routine 46:

                  TABLE 1
    ______________________________________
    800  Write routine (ADDRESS, VALUE)
    802  Which phase is GC 32 in?
    804  Phase 1:
    806     IF VALUE is a pointer whose referent is
              in Condemned region 352 and ADDRESS is a
              location outside of condemned region 352,
              THEN,
    808         Mark the referent object
    810  Phase 2:
    811     IF VALUE is a pointer whose referent is in
              condemned region 352 and the mark word 1000
              of the referent object is UNMARKED, THEN,
    812         Add the referent object to the list
                pointed to by register TO-SCAN
    813  Phase 3 and Phase 4:
    814     IF ADDRESS is within the write barrier AND
              the mark word 1000 of the object to which
              ADDRESS belongs points to another object,
              THEN,
    816         Write VALUE into both objects
    818  Phase 4:
    820     IF VALUE is a pointer whose value is
              within the write boundary, THEN,
    822         Modify the value to point to
                the transported copy
    824  Phase 5: (No Special Handling)
    ______________________________________

                  TABLE 2
    ______________________________________
    101  Set write Barrier boundaries beginning
         and end of condemned region.
    103  Save copy of allocation pointer.
    105  Scan boxed memory locations in allocated
         regions for references to objects in the
         condemned region:
    107     Scan all words beginning with the first
            word in condemned region to the copied
            allocation pointer:
    109       If the word being scanned is a
              reference to an object in the
              condemned region then
    111         mark that object by
                writing "MARK" in the
                object's mark word.
    ______________________________________

                  TABLE 3
    ______________________________________
    201  Place the write barrier to cover condemned region
    203  Initialize a list's origin, register TO-SCAN, to NIL
    205  Scan condemned region, to link all objects whose
         mark word contains "MARK":
    207     IF the word of the object being scanned
            has the value "MARK" then
    209       add the object to the beginning of
              the list
    211  Until TO-SCAN is empty do
    213     Remove the first address from the list
    215     Scan the words in the object at that
            address
    217     IF the object refers to an unmarked
            object in the condemned region,
    219       add the referent object to the list
    221     Replace the contents of the mark
            word of the object just scanned with
            a pointer to itself.
    ______________________________________

                  TABLE 4
    ______________________________________
    301  Set write barrier boundaries to the current
         allocation pointer and the beginning of the
         condemned region, as shown in FIG. 7a.
    303  For each object in the condemned region do
    305     If the mark word of the object is not UNMARKED
            then:
    307       Transport the object:
                  begin critical section 308
    309         The mark word of the object is given
                the value of the allocation pointer
    311         The location pointed to by the
                allocation pointer is given the
                value, as an integer, of the
                object's mark word address
    313         The object's size in words is added
                to the allocation pointer
    315         The write barrier's end boundary is
                extended to the location of the last
                word of the object that is being
                transported.
                  end of critical section
                  begin interruptable section 316
    317         Transport each word of the object to
                the newly created copy.
                  end interruptable section
    ______________________________________

                  TABLE 5
    ______________________________________
    401  Save a copy of the allocation pointer
    403  Scan all boxed memory locations in allocated
         regions, beginning with the memory word following
         the condemned region and ending with the saved
         allocation pointer
    405     If the word is a reference to an object
            within the condemned region
    407     update the word to reference the
            object's transported copy.
    ______________________________________

                  TABLE 6
    ______________________________________
    501  Make the write barrier inoperative
    503  Visit each object in the area of memory
         where the transported objects are placed
    507     Reset the object's mark word to
            UNMARKED
    ______________________________________

• Inventors
  Ferguson, Edward E.; Bartley, David H.; McEntee, Timothy J.;
• Assignee
  Texas Instruments Incorporated (Dallas, TX)
• Published
  Mar-8-1994
• Current US Classes:
  707/201
  707/206
  711/170
• Application #
  682806
• International Classes
  G06F 012/12; G06F 012/16
• Field of Search
  364/DIG. 395/425 395/600 395/650 395/700 395/725
• Examiner
  Kulik; Paul V.
• Agent
  Troike; Robert L., Heiting; Leo N., Donaldson; Richard L.
• US Patent References:
  4797810
  4807120
  4907151
  4989134
  5088036
  5136706