Real-time computer “garbage collector”

Details Real-time computer “garbage collector” Real-time computer “garbage collector”

1994-07-13

2002-01-22

Black, Thomas (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06341293

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the field of computer memory management, and in particular to the problem of efficiently performing computer garbage collection in real-time.
BACKGROUND
Computer programs typically make use of variables or similar labels to reference data “objects.” A portion of computer memory must be allocated during execution to each such object. Over time, as many such objects are created and used, the available, “free” memory that remains to be allocated in a particular system may begin to run short. As is well known in the art, a variety of methods and techniques have been proposed and implemented to reclaim as “free” and available those portions of computer memory that were originally allocated to program objects that are no longer in use by any running program. This task is generally known in the art as “garbage collection.” A great variety of different garbage collection techniques have been developed and used; for example, the reference paper
Uniprocessor Garbage Collection Techniques
by Paul R. Wilson (available through Internet via anonymous FTP from cs.utexas.edu as pub/garbage/bigsurv.ps) provides a broad survey of existing techniques, and explains commonly used terminology. That paper is incorporated herein in its entirety by this reference.
Prior art garbage collection systems have generally suffered to various degrees from the problem of excessive pause times. This problem arises when garbage collection is performed in real-time, i.e., concurrently with the execution of other live programs running on one or more processors. (In the field of garbage collection, the other live programs are typically referred to as “mutators,” because such programs potentially “mutate” or change the state of memory, from the point of view of the garbage collector or “GC.”)
For example, suppose that a system contains multiple mutator threads and a single GC thread. (A “thread” is an execution context within a shared address space, as discussed further below.) If the mutators are, for example, trying to present a movie at 30 frames per second, and they require a combined time of 23 ms to generate each frame, then problems will arise if the GC thread is run for more than 10 ms during any particular 33 ms interval. It would therefore be desirable in this scenario to guarantee that the garbage collector will run no more than 30 times per second (i.e., its frequency will be no greater than 30; equivalently, its period will be greater than or equal to 33 ms), and also that each time the garbage collector is run it will execute for a maximum duration of no more than 10 ms.
GC frequency and duration can of course be kept “limited” through brute force, in the sense that the execution time allotted to the GC program may be explicitly rationed under control of the operating system or some other scheduling manager. This does not solve the problem at hand, however, because garbage collectors generally perform certain non-deferable, atomic work that must not be interrupted by mutators, at the risk of causing potential memory corruption. For example, a well-known family of GC schemes known as “copying” collectors (described in the Wilson survey paper, for example) actually copy, to a new location in memory, each data object that is determined not to be garbage (i.e., the object may still be in use by a live program). Since each such data object can potentially be arbitrarily large, and because the copying operation is necessarily atomic, a copying garbage collector may enter a phase where it cannot be interrupted by any mutator for an arbitrarily long period of time. Such GC schemes are generally not satisfactory for real-time systems where a maximum GC duration is required.
While non-copying garbage collectors also exist in the prior art (e.g., Henry G. Baker Jr., The Treadmill: Real-Time Garbage Collection Without Motion Sickness, SIGPLAN Notices Vol. 27 No. 3 at pp. 66-70, March 1992, incorporated herein in its entirety by this reference), many current applications of interest—notably, in the realm of multimedia—require limits on the maximum frequency and duration of garbage collection that the prior art has so far failed to dependably satisfy, at least on general-purpose stock hardware. As a result, systems running multimedia applications and the like have so far been unable to use garbage collection, and have instead been forced to rely on inconvenient, manual storage management techniques.
SUMMARY OF THE INVENTION
The present invention disclosed herein provides a novel method and apparatus for real-time garbage collection that offers unprecedented low bounds on the worst-case for GC frequency and duration.
Briefly, the present invention is used with a plurality of objects and with one or more mutators. The mutators, and the garbage collector itself, run on one or more computer processors, as scheduled by a scheduler. Stock hardware may be used; i.e., special purpose hardware is not necessary. The mutators each have a corresponding thread with a corresponding thread state. In the present invention, execution of all mutators is temporarily restricted at the start of each new garbage collection cycle. However, unrestricted and concurrent execution of each mutator is resumed, as soon as that mutator's thread state is processed by the garbage collector.
In another feature of the present invention, the mutators are executed subject to a protective write barrier. However, the write barrier does not have to be applied to the modification of any mutator thread states, yielding valuable performance benefits.


REFERENCES:
patent: 4775932 (1988-10-01), Oxley et al.
patent: 4961137 (1990-10-01), Angesterijin et al.
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5321834 (1994-06-01), Weiser et al.
patent: 5355483 (1994-10-01), Surlet
N. Bagherzadeh et al, “A parallel asynchronous garbage collection algorithm for distributed systems”, Mar. 1991, IEEE Transactions, vol. 13, Iss 1, p. 100-7.*
Kuechlin et al., “On Multi-Threaded List Processing and Garbage Collection”, Ohio State University Technical Research Report, pp. 1-15, Mar. 22, 1991.

Affiliated with

Also associated with

Rating

Real-time computer “garbage collector” does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Real-time computer “garbage collector”, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time computer “garbage collector” will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2836129