System and method for ensuring non-interfering garbage collection in a real time multi-threaded environment

[0001] This non-provisional patent application claims priority under 35 USC § 119(e) to U.S. provisional patent application Ser. No. 60/574,196, filed 24 May 2004, the disclosure of which is incorporated by reference.

[0002] The invention relates in general to multi-threaded operations and, in particular, to a system and method for ensuring non-interfering garbage collection in a real time multi-threaded environment.

[0003] Managed code platforms can present a machine-independent and architecture-neutral operating environment, such as provided by the Java operating environment, which is described in P. van der Linden, “Not Just Java,” Ch. 3, Sun Microsystems, Inc. (1997), the disclosure of which is incorporated by reference. Managed code environments are capable of providing real time execution, but ensuring such execution can be problematic due to the unpredictable latencies introduced by garbage collection mechanisms. Real time threads must be guaranteed to proceed within fixed timeliness constraints, yet other concurrent threads, particularly garbage collection threads, can potentially cause execution interference or memory corruption, absent appropriate programmatic safeguards.

[0004] Real time execution is supported in the Java operating environment, as specified in the Real-Time Specification for Java (RTSJ). Under the RTSJ, two classes of real time threads, real time (RT) threads and no-heap real time (NHRT) threads, are defined, in addition to the normal class of threads specified by the Java programming language. NHRT threads carry out execution in either immortal or scoped memory areas, which are both subject to storage reclamation that is controlled under well-defined rules not under garbage collection control. RT threads additionally carry out execution in heap storage and can assign references to heap-defined objects into objects allocated in the scoped memory area.

[0005] Garbage collection proceeds under mutual exclusion with all normal and RT threads, but is subject to preemption by NHRT threads. Storage objects allocated in a scoped memory area can only be reclaimed in the interval between inactive and active states, termed the dead zone, when the number of threads operating on the scoped memory area drops to zero.

[0006] Garbage collection preemption can create two particularized issues, where a linear garbage collection scan of a scoped memory area is temporarily interrupted. An unsynchronized read of the thread counter is sufficient to identify inactive scoped memory area, even if the counter value changes while being read by the garbage collector thread. If the thread counter value read is consistent, that is, no concurrent changes occurred, the garbage collector thread can safely proceed. However, if the thread counter value was changed during the read, two issues may arise. First, if a non-zero value was decreased to zero, the garbage collector thread will erroneously consider the scoped memory area active and perform a scan, even though performing such a scan is unnecessary and inefficient, as the scoped memory area has become inactive. Second, if a zero value was increased, the garbage collector thread will erroneously consider the scoped memory area inactive and not perform a scan. Although, strictly speaking, not problematic, updated references to heap objects relocated by the garbage collector thread will be written into the scoped memory area.

[0007] Two further problems could occur in a multiprocessing environment in which garbage collection executes on a processor distinct from one or more concurrently executing NHRT threads. Such actions could result in execution errors, memory corruption, or system crash. A similar set of problems could also occur in a uniprocessing environment. First, a scoped memory area could enter a dead zone during a garbage collection scan due to preemption. Ideally, garbage collection on that scoped memory area should stop because all stored objects are “dead” and further processing would be inefficient. Second, the NHRT threads could overrun the preempted garbage collector thread and allocate objects past the current position of the garbage collector thread. Once restarted, the garbage collector thread could incorrectly overwrite any scoped memory area locations previously interpreted as storing heap object references or could incorrectly interpret previously-read values at now-overwritten scoped memory area locations as class descriptor pointers or heap object references.

[0008] Therefore, there is a need for an approach to preventing program error and failures and memory corruption without introducing interferences to real time threads and, in particular, to NHRT threads, due to concurrent garbage collection activities.

[0009] A system and method for synchronizing non-interfering garbage collection in a real time capable operating environment is provided. Two groups of operations are defined to allow a garbage collector thread to read from and write to a scoped memory area without interfering with concurrently executing NHRT threads. A monotonically-increasing incarnation number is atomically incremented by executing NHRT and RT threads upon entry into the scoped memory area. To ensure a non-interfering read by a garbage collector thread, the incarnation number is read under a memory barrier and stored prior to the loading of a value from a selected location in the scoped memory area. The incarnation number is subsequently re-read under a memory barrier, and, if differing from the stored value, further processing of the scoped memory area is stopped. To ensure a non-interfering write by a garbage collector thread, instructions that implement a store operation by the garbage collector thread into a location in the scoped memory area are located in a buffer, known as a garbage collector write stub. The instructions are modified by an NHRT thread to interrupt scanning of the scoped memory area upon an attempt to write a value by the garbage collector thread. The modified instructions are reversed by an RT thread upon subsequently entering the scoped memory area. Thus, during execution of the garbage collector write stub, the garbage collector thread will either be interrupted from scanning further or will be allowed to write a value into a location in the scoped memory area without risk of corrupting the content.

[0010] One embodiment provides a system and method for ensuring non-interfering garbage collection in a real time multi-threaded environment. An incarnation counter is associated with a scoped memory area. The incarnation counter is atomically updated upon access by a no heap thread not interruptible by garbage collection operations. A write stub is identified and includes instructions to store data into storage locations of the scoped memory area. The instructions are dynamically modified to interrupt execution of a garbage collection thread. A garbage collection thread is executed over the scoped memory area. At least one of a read from the scoped memory area and a write to the scoped memory area are attempted. For the read attempt, an incarnation number is read from the incarnation counter of the scoped memory area and is locally stored. A value from a storage location in the scoped memory area is loaded and the incarnation number is reread. The reread incarnation number is compared with the locally stored incarnation number. The garbage collection thread is interrupted when the reread and locally stored incarnation numbers fail to match. For the write attempt, the instructions in the write stub are executed. The instructions include one of storing data into one such location in the scoped memory area and interrupting execution of the garbage collection thread.

[0011] Still other embodiments of the invention will become readily apparent to those skilled in the art from the following detailed description, wherein are described embodiments of the invention by way of illustrating the best mode contemplated for carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the spirit and the scope of the invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.

Real Time Multi-Threaded Environment

[0019] Managed code platforms, such as the Java operating environment, supra, can provide multi-threaded, real time execution, subject to timeliness constraints posited to ensure predictable program behavior. Although described herein with reference to an implementation in conformity with the RTSJ, other types of multi-threaded, real time operating environments are possible. Thus, FIG. 1 is a block diagram showing, by way of example, a multi-threaded, real time operating environment 10, in accordance with one embodiment. The multi-threaded environment 10 has three logically-defined layers 12, including operating system kernel 14, virtual machine 15, and threads 16-18. A computer system 11, operating under the control of the kernel 14, executes a virtual machine 15 to provide a managed code platform. Through the virtual machine 15, multiple process threads, including normal threads 16, real time (RT) threads 17, and no heap real time (NHRT) threads 18, execute.

[0020] The virtual machine 15 manages memory 13 for executing threads through logically-defined areas that can be used for the dynamic allocation of objects. The immortal memory area (IMA) 19 is used for objects that, once allocated, exist until the termination of the virtual machine 15. The scoped memory area (SMA) 20 is used for objects with lifetimes defined by scope. Finally, the heap 21 is used to manage objects with lifetimes defined by reachability. Other types of memory areas, including physical memory (not shown), are possible.

[0021] The NHRT threads 18 carry out execution in memory areas where storage reclamation is performed in accordance with well-defined rules not under garbage collection control to ensure predictable execution. In one embodiment, NHRT threads 18 are restricted to the immortal memory areas 19 and scoped memory areas 20. RT threads 17 carry out execution in the immortal memory areas 19, scoped memory areas 20, and heap 21. Both RT threads 17 and NHRT threads 18 can enter a scoped memory area 20 and allocate, read, or write objects. NHRT threads 18 may neither read nor write references to heap objects, as further described below with reference to FIG. 2. RT threads 17, however, can assign references to heap objects into objects defined in the scoped memory area 20, as further described below with reference to FIG. 3. In one embodiment, an attempt by an NHRT thread 18 to either allocate a heap object or to store a reference to a heap object will cause an exception to be thrown by the virtual machine 15.

[0022] Garbage collection activities are not allowed to interfere with execution of NHRT threads 18. Specifically, garbage collectors may not prevent an NHRT thread from making progress and any ongoing garbage collection activity can be preempted at any time by an NHRT thread 18. Nevertheless, absent programmatic safeguards as further described below beginning with reference to FIG. 5 et seq., interferences can potentially occur when the garbage collector thread reads a scoped memory area 20 to determine the liveness of referenced heap objects or to write content into the scoped memory area 20 to update relocated heap object references.

Real Time Threads

[0023] RT threads 17 can allocate, read, or write objects in immortal memory areas 19, scoped memory areas 20, and heap 21. FIG. 2 is a block diagram 40 showing RT threads 17 and memory areas 19, 20, 21 in the operating environment 10 of FIG. 1. For simplicity, only the scoped memory areas 20 and heap 21 will be discussed. Each instance 41a, 41b of an RT thread 17 can dynamically allocate memory for objects in storage locations 42a, 42b, 43a, 43b in scoped memory area 20 and 44a, 44b, 45a, 45b in the heap 21, respectively. Storage locations 42a, 42b in the scoped memory area 20 can store references 46 to storage locations 45a, 45b in the heap 21.

[0024] Storage objects allocated in the heap 21 can be reclaimed by a garbage collector thread (not shown). Storage objects allocated in the scoped memory area 20 can only be reclaimed when the scoped memory area 20 is in a dead zone. Preemption of garbage collection activities by NHRT threads 18 must be coordinated to avoid execution interference and memory corruption, as further described below with reference to FIGS. 4A-D. For instance, a garbage collector thread may need to read scoped memory area content to determine the liveness of referenced heap objects. Similarly, a garbage collector thread may need to write scoped memory area content to update references to heap objects that were reallocated or moved. Other types of garbage collection activities may also require coordination.

NHRT Threads

[0025] NHRT threads 18 are restricted to scoped memory areas 20 and immortal memory areas 19. FIG. 3 is a block diagram 50 showing NHRT threads 18 and memory areas 19, 20, 21 in the operating environment 10 of FIG. 1. For simplicity, only the scoped memory area 20 and heap 21 will be discussed. Each instance 51a, 51b, 51c of an NHRT thread 18 can dynamically allocate memory for objects in storage locations 52a, 52b in scoped memory area 20. However, references to heap objects may not be stored by an NHRT thread 18 in the SMA 20, nor may storage locations in the heap 21 be directly allocated by an NHRT thread 18.

[0026] Storage objects allocated in the scoped memory area 20 can only be reclaimed when the scoped memory area 20 is in an inactive state, known as a dead zone, which occurs when the number of threads operating on the scoped memory area 20 is zero. When the scoped memory area 20 enters a dead zone, all storage objects become reclaimable or dead. Any reclamation of storage objects in the scoped memory area 20 must be completed before the scoped memory area 20 leaves the dead zone. In one embodiment, storage objects in the scoped memory area 20 are allocated linearly by maintaining a cursor pointing to the last allocated byte. Upon each allocation, the cursor is incremented by the requested amount of bytes. Reclamation simply resets the cursor to point to the first byte of the scoped memory area 20.

Unsynchronized Garbage Collection

[0027] Garbage collection unsynchronized with NHRT threads 18 can potentially result in system failure or memory corruption. FIGS. 4A-D are timing diagrams 60-63 showing, by way of example, potential synchronization problems resulting from prior art unsynchronized garbage collection. As a scoped memory area 20 can include objects storing references to heap objects created by RT threads 17, a garbage collector thread may read storage locations from a scoped memory area 20 and interpret the read values as references to heap objects or references to class descriptions. Similarly, a garbage collector thread may write to storage locations in a scoped memory area 20 to store a new location of heap object that has been relocated or moved.

[0028] In one embodiment, garbage collection is performed based on several assumptions. All objects in an active scoped memory area 20 are assumed to be live. Garbage collection operates on each active scoped memory area 20 by scanning linearly from the address of the first allocated storage location to the address of the last allocated byte. References to heap objects are identified and processed, either by following the reference or modifying the reference, as necessary. The linear scan of each scoped memory area 20 is bounded by the value of the allocation cursor read at the time that garbage collection is started. Scanning can cease after the noted allocation cursor position since only NHRT threads 18 can enter a scoped memory area 20 concurrent to garbage collection. Consequently, the scoped memory area 20 will not contain any further references to heap objects. Each scoped memory area 20 that was inactive, that is, in a dead zone, at the time that garbage collection started can also be ignored, as only NHRT threads 18 can activate an inactive scoped memory area 20 concurrent to garbage collection. Nevertheless, conventional garbage collection activities which lack synchronization with NHRT threads 18 can lead to system failures or memory corruption.

[0029] Referring first to FIG. 4A, an NHRT thread T₁ and a garbage collector thread GC are executing concurrently on a multi-processor architecture with the garbage collector GC running on a distinct processor. Normal threads 16 and RT threads 17 are not allowed to run while a garbage collector thread is executing. Assuming that the NHRT thread T₁ began execution at time i and the garbage collector thread GC began execution subsequently at time j, the garbage collector thread GC will have identified any live heap object references 64 in the scoped memory area 20 that need to be updated to refer to new storage locations in the heap at time n.

[0030] Referring next to FIG. 4B, assume that the NHRT thread T₁ terminates at time j+m, while m>n, putting the scoped memory area 20 into an inactive state, that is, in a dead zone. By implication, the set of previously-identified references 64 will now be inactive or dead 65.

[0031] Referring next to FIG. 4C, the garbage collector thread GC continues scanning the scoped memory area 20 through time j+o, where o>m. However, as the scoped memory area 20 is in a dead zone, continuing to process the scoped memory area 20 is inefficient and unnecessarily wastes processor cycles.

[0032] Referring finally to FIG. 4D, a second NHRT thread T₂ also begins execution at time j+o. The execution of the second NHRT thread T₂ activates the scoped memory area 20, which causes the scoped memory area 20 to leave the dead zone, and the second NHRT thread T₂ then allocates one or more objects in the scoped memory area 20 up to and beyond the current cursor of the garbage collector thread GC. At a later time, such as time j+p, where p>o, the activation of the scoped memory area 20 by the second NHRT thread T₂ could create two problems. First, if the garbage collector thread GC reads a storage location in the scoped memory area 20 overwritten by the second NHRT thread T₂ and treats the value read from the storage location as holding a reference to a class description or to a heap object, a system error could occur. Second, if the garbage collector thread GC writes to a storage location in the scoped memory area 20 that the garbage collector thread GC assumes to contain a reference to a heap object that requires updating, the writing could corrupt the content of the object just allocated by the second NHRT thread T₂, thereby leading to memory corruption that in turn could cause a type safety violation or system crash.

Synchronized Garbage Collection

[0033] In one embodiment, the operations performed by garbage collector and NHRT threads, and, in a further embodiment, RT threads, are modified to synchronize garbage collection activities to scoped memory area state without locking NHRT thread progress, as further described below with reference to FIG. 5 et seq. The modifications allow a garbage collector thread to determine the liveness of an object stored in a scoped memory area 20 currently being scanned, but possibly having been modified in the interim by a concurrent preempting NHRT thread that has overtaken the garbage collector thread. The modifications can also interrupt the scanning when necessary to avoid the overwriting of a storage location in the scoped memory area 20 that has been modified by the NHRT thread.

[0034] The modifications have three components. First, public incarnation number counts the number of times that a scoped memory area 20 transitions from an inactive state to an active state. In one embodiment, the incarnation number is increased monotonically, although the incarnation number could also be decremented or otherwise updated to reflect changes in scoped memory area state. The incarnation number is initialized to zero upon creation of the scoped memory area 20 and is atomically increased whenever an RT or NHRT thread activates the scoped memory area. During a garbage collection, incarnation numbers can only be increased by NHRT threads. Second, an instruction buffer containing scoped memory area storing instructions is dynamically patched to prevent locations within the scoped memory area 20. Finally, in a further embodiment, cross-CPU interruption is introduced to force a garbage collection thread to accept instructions buffer modifications if still scanning when an NHRT thread enters the scoped memory area 20.

[0035] Garbage collection synchronization is provided for reading from and writing to storage locations in a scoped memory area 20. Garbage collector thread reads are protected through use of the incarnation number to ensure that values read from a scoped memory area are live and can safely be used as pointers to class descriptors or references to other objects, including live heap objects. Garbage collector writes are protected through dynamic instruction modification to interrupt the storing of content into a scoped memory area that has already been changed by NHRT thread.

[0036] Garbage Collection Thread Actions

[0037] Each garbage collector thread uses the incarnation number to ensure the safe reading of values from storage locations in a scoped memory area 20. FIG. 5 is a flow diagram 80 showing garbage collector thread actions 81, 82 for use in the operating environment 10 of FIG. 1. The garbage collector thread actions are loosely divided into two groups of actions 81, 82 that are respectively performed upon initially entering an inactive scoped memory area 20 and during the reading of a value from a storage location in a scoped memory area.

[0038] Initially, an inactive scoped memory area 20 is selected (block 83) and the incarnation number is read and stored into a local variable (block 84). A memory barrier is issued (block 85) to guarantee completion of the load before proceeding to reading values from the scoped memory area 20.

[0039] When reading a value from a storage location in the scoped memory area 20, the value is first loaded (block 86) and a memory barrier is issued (block 87) to guarantee completion of the load before any subsequent loads enter the instruction stream. The incarnation number is re-read (block 88). The value of the read incarnation number is compared to the value stored in the local variable (block 89). If the values differ (block 90), garbage collection processing of the scoped memory area 20 is stopped (block 91), as the scoped memory area 20 has entered a dead zone. Otherwise, if the values are the same (block 90), the loaded value can safely be used (block 92), as the value has not been modified by an preempting and overtaking NHRT thread 18 since started execution after garbage collection activities began.

[0040] Issuing memory barriers and reading the incarnation number each time a storage location is read can be computationally expensive. In a further embodiment, the cost can be amortized by using a temporary buffer to read one section of the scoped memory area 20 with each load, instead of loading just a single storage location. The temporary buffer is loaded with the current section of the scoped memory area 20 being processed, a memory barrier is issued, and the incarnation number is checked. If the incarnation number remains consistent, the values stored in the temporary buffer are correct and cannot be misinterpreted by the garbage collector thread. In a still further embodiment, values from only a specific location of interest in the scoped memory area 20 are read. For instance, the only header of an object and all object references might be loaded into the temporary buffer prior to checking for the incarnation number. Other forms of protected loads of values stored in a scoped memory area 20 are possible.

[0041] NHRT Thread Actions

[0042] Code containing instructions executed by a garbage collector thread to update the contents of storage locations in a scoped memory area is stored in a buffer, known as a garbage collector write stub, associated with the scoped memory area 20. The address of each garbage collector write stub is associated with the scoped memory area 20. The instructions can be modified and reverted respectively by NHRT threads 18 and RT threads 17. FIG. 6 is a flow diagram 110 showing NHRT thread actions 111 for use in the operating environment 10 of FIG. 1. Only a single group of actions 111 need be performed to modify garbage collector write stubs. Initially, a scoped memory area 20 is activated (block 112) upon entry into the scoped memory area 20 by an NHRT thread 18. The “store” instruction in the garbage collector write stub is modified by the NHRT thread 18 with a “branch” instruction that routes execution of the code to interrupt the scanning of the scoped memory area 20 (block 113). Additionally, if the scoped memory area was formerly inactive (block 114) the incarnation number is atomically increased (block 115). In one embodiment, the modified instructions do not interrupt the garbage collector thread itself, but only interrupt the scanning of the scoped memory area 20 associated with the garbage collector write stub. The interruption guarantees that the garbage collector thread will not overwrite any storage location once the scoped memory area 20 has entered a dead zone.

[0043] In a further embodiment, a cross-CPU interrupt may be required on multi-processor machines that are based on modern deeply pipelined processor architectures to guarantee that the change of instructions in the garbage collector write stub is made globally visible to all processors. For instance, the “store” instruction may already be in an instruction pipeline and is about to be performed.

[0044] Such cross-CPU interrupts may be expensive and, in a still further embodiment, each scoped memory area 20 can be augmented with an activity variable indicating whether a garbage collector thread is currently running over the scoped memory area 20. The activity variable is set to the garbage collector thread identifier prior to scanning, and is reset to zero when upon either normal termination or interrupt. An NHRT thread 18 activating a scoped memory area 20 consults the activity variable following activation, including patching of the “store” instruction, to determine whether a garbage collector thread is still scanning. If scanning is still in progress, a cross-CPU interrupt directed at the garbage collector thread is performed.

[0045] RT Thread Actions

[0046] RT threads 17 reverse the patching of a garbage collector write stub. Optimally, the garbage collector write stub patching only need be reversed when a heap object reference is written into a storage location in a scoped memory area 20, which can only be carried out by an RT thread 17 entering the scoped memory area 20. FIG. 7 is a flow diagram 130 showing RT thread actions 131,132 for use in the operating environment of FIG. 1. The RT thread actions are loosely divided into two groups of actions 131, 132 that are respectively performed for inactive and active scoped memory areas. Initially, the scoped memory area 20 is entered (block 133) and, if active (block 134), the current incarnation number is compared against a previously-stored incarnation number value (block 135). If the values differ (block 138), the “branch” instruction in the garbage collector write stub is modified to restore writing of values into the scoped memory area 20. Similarly, if the scoped memory area 20 is inactive (block 134), the “branch” instruction in the garbage collector write stub is also modified to restore writing (block 136). The incarnation number is then atomically increased (block 137).

[0047] Entry into a scoped memory area 20 is performed under mutual exclusion that covers determination of whether an entering thread activates the scoped memory area 20, increases of the incarnation number, replacement of “store” instructions in a garbage collector write stub, and determination of whether a thread must restore the “store” instruction. Other combinations of mutual exclusion are possible.

[0048] While the invention has been particularly shown and described as referenced to the embodiments thereof, those skilled in the art will understand that the foregoing and other changes in form and detail may be made therein without departing from the spirit and scope of the invention.