Methods and apparatus for performing a memory management technique

Mechanisms and techniques operate in a computerized device to perform a memory management technique such as garbage collection. The mechanisms and techniques operate to detect, within a storage structure associated with a thread, general memory references that reference storage locations in a general memory area such as a heap. The storage structure may be a stack utilized by the thread, which may be, for example, a Java thread, during operation of the thread in the computerized device. The system maintains a reference structure containing an association to the general memory area for each detected general memory reference within the storage structure. The system then operates a memory management technique on the general memory area for locations in the general memory area other than those for which an association to the general memory area is maintained in the reference structure, thus increasing the performance of the memory management technique.

FIELD OF THE INVENTION

The present invention generally relates to systems for performing memory management techniques within a computerized device, and more particularly, to systems, mechanisms and techniques that perform garbage collection of memory during operation of the computerized device.

BACKGROUND OF THE INVENTION

Conventional computerized devices include a processor (e.g., microprocessor, controller or central processing unit) that is capable of executing, interpreting, operating or otherwise performing computer program instructions (e.g., software code) associated with computer programs stored in a memory system within the computerized device. During execution of a computer program, instructions in the computer program may direct the processor to allocate various portions of memory in order to store data structures for use by the computer program. As an example, in the C programming language, a programmer can provide a malloc instruction for use with a data structure variable name as a parameter in order to cause the computerized device to reserve an area of memory equivalent in size to the data structure for use by the program containing the malloc instruction. Once the computer program is finished using the data structure, the programmer that created the computer program can include a free instruction that causes the processor to release the memory formerly allocated to the data structure for use by subsequent allocation requests within the computerized device.

Some conventional execution environments that operate within computerized devices automatically control the allocation and deallocation or release of memory on behalf of computer program processes. In such cases, the programmer does not need to provide specific instructions to allocate and deallocate memory. As an example, in the Java programming language (Java is a registered trademark of Sun Microsystems, Inc.), a programmer can create a program such as a Java applet and can create or define objects (i.e., data structures) in the Java applet as needed, without being concerned about the allocation or deallocation (i.e., release) of memory required to store and/or maintain the objects and associated data during operation of the Java applet. Instead, during runtime, the Java applet operates on a computerized device within an execution environment called a Java virtual machine or JVM. A conventional Java virtual machine interprets the Java computer program code within the Java applet and handles all processing operations associated with allocating or reserving memory on behalf of the Java applet for objects instantiated by that Java applet. In addition, a conventional Java virtual machine performs a periodic memory management technique called “garbage collection” in order to traverse memory and deallocate portions of memory which store object data that is no longer referenced by any objects in any Java processes or threads (e.g., by any applets). In this manner, the automatic memory allocation and deallocation mechanisms or garbage collection techniques operate as part of the Java virtual machine in order to handle allocation and deallocation of memory on behalf of Java processes or threads.

Continuing with the aforementioned example of a Java thread or process operating within a Java virtual machine, a conventional Java virtual machine provides a storage structure such as a stack to the Java thread. During operation of the Java thread, the Java virtual machine, on behalf of the Java thread or process, can place information onto (i.e., push) and off-of (i.e., pop) the stack on behalf of the Java thread associated with that stack. As a specific example, if a Java thread instantiates a series of objects A, B and C, the Java virtual machine allocates memory for each of these objects in a general memory area referred to as a heap. During operation of the Java thread, the Java virtual machine can reference the objects in a heap via pointers to those objects. The Java thread may perhaps call or otherwise transfer processing to another routine. In such cases, a conventional Java virtual machine may place references to the objects A, B and C associated with the Java thread onto a call-stack associated with the Java thread prior to the transfer of processing into the routine. The stack or call-stack thus contains such things as local variables, some of which may be references into the heap, and any intermediate but still live results saved from registers at a particular program counter location.

In other cases, an operating system might instruct the Java virtual machine to begin operation or execution (e.g., interpretation) of another Java thread. The first Java thread from which control was transferred may enter an idle or passive state or condition for an indefinite period of time. Perhaps the first Java thread becomes blocked while awaiting an event to occur. Information may be pushed onto the stack when a thread enters an idle condition. Within the Java execution environment, there may be many threads existing at any point in time. The stack associated with each of these Java threads may contain references to the general memory area or heap for objects associated with those threads.

As noted above, in a typical conventional Java virtual machine, each Java thread has a stack. The stack is composed of a set of frames, sometimes called activation records. Each frame consists of a set of cells or words. For the purposes of stack scanning, a word contains either a reference (root) to an object in the heap or a non-reference value. Example of non-reference values include integers, floating point values, return addresses, and the like. Frames are private to a thread and thus only a thread or the garbage collector may modify the cells contents of a frame. A frame is usually associated with a Java method (e.g., a routine or subroutine). When a thread is executing in a Java method, the corresponding frame is active. The active frame is always the topmost frame on the stack. A thread is not able to modify the contents of non-active frames.

As an example, suppose mA, mB, mC and mD are Java methods. Futher suppose mA calls into a mB, and mB calls into mC, and mC then calls into mD. Conceptually, the stack will then look like: {fA, fB, fC, fD)}, where fA is the frame associated with Java method mA, fB is the frame associated with Java method mB, and so forth. The frame fD (at the top of the stack) is the active frame while fA is the oldest frame. While fD is active the thread can't access the contents of frames fA, fB, fC. More specifically, the thread can't “name” the locations so it can't refer to them. When mD returns control into mC, we say the stack unwinds. At this point, the stack will have the following form: {fA, fB, fC} and the frame fC is the active frame.

As noted above, the Java virtual machine is responsible for deallocating memory on behalf of Java threads. To do so, the Java virtual machine typically performs a conventional garbage collection memory management technique for threads associated with the Java virtual machine. Such a conventional garbage collection memory management technique involves identifying or differentiating those portions of the heap or other general memory area that are no longer referenced by any Java threads as opposed to those portions of memory that are allocated to storing objects on behalf of thread. By identifying the used versus the unused areas of memory, some garbage collection technique can maintain a free list of the unused memory portions or areas for later use when an active or executing Java thread requires the instantiation of a new object in memory.

One technique used by conventional garbage collection memory management techniques to identify those areas of a heap that contain allocated memory (i.e., that contain object data in use by threads) operates by scanning the stacks associated with all threads in order to identify all references to objects in the heap. Those areas or portions of the heap that are not referenced within any of the stacks associated with the threads within that Java virtual machine are considered to be garbage. In other words, upon each operation of garbage collection, by scanning the stacks associated with the threads in a Java virtual machine, the garbage collection technique can identify all areas of the heap that are in use and thus those areas not identified are considered to be free memory and may be freely allocated upon the next request for heap memory.

Conventional stack scanning operations are transitive in that if a root reference (i.e., a reference to heap memory stored outside of the heap, such as in the stack) references a heap object (e.g., object A) which contains an intra-heap reference to another object (e.g., object B), the scan operation will note or otherwise detect that both objects A and B are reachable from the root. The scanning operation thus “traces” intra-object references to determine reachable heap memory portions.

During the process of garbage collection, some conventional garbage collection techniques, called “moving” or “copying” garbage collectors, go so far as to rearrange the general memory area (i.e., the heap) in order to coalesce or condense all areas of free memory (i.e., those areas not allocated to objects associated with threads) into a single contiguous area of free memory within the general memory area. This significantly overcomes a problem of memory fragmentation that occurs when there are many smaller non-contiguous portions of free memory. The garbage collection processing can thus move allocated portions of memory around (i.e., can mode data associated with objects) in order to group this allocated data into a single contiguous portion of allocated memory. The result is to thus collect many small unused but noncontiguous portions of free memory in order to make large portions of continuous free memory available should a need arise to allocate such memory. However, if a conventional garbage collection technique moves data within the heap that is allocated to an object associated with a thread (i.e., moves an existing object that is not garbage) in order to coalesce free memory, the conventional garbage collection technique must keep track of memory addresses before and after the move of the object data within the heap. Once the heap has been rearranged in order to group free memory into one or more large contiguous portions, the conventional garbage collection technique must return to the stacks of each thread in order to update the references (i.e., pointers or memory addresses) within those stacks to correctly point to or reference each object that was moved within the heap during the garbage collection process. In other words, if a conventional garbage collection process moves objects around within the heap, the garbage collection process must update the new locations of those objects within the stacks associated with the threads so that those threads can properly reference those objects. Conventional copying or moving garbage collectors can also adjust intra-heap (e.g., intra-object) references when object are moved during the garbage collection process.

SUMMARY OF THE INVENTION

Conventional techniques and mechanisms for performing memory management techniques such as garbage collection suffer from a variety of deficiencies. In particular, within an execution environment such as a Java virtual machine, upon each operation of a conventional garbage collection technique, the garbage collector (e.g., a routine, thread or process responsible for performing this operation) must scan the stacks of Java threads in order to detect references to objects or other information stored within the general memory area. This stack scanning process or operation requires significant processing resources. As noted above, situations may arise in which many threads become idle or blocked for extended periods of time in a computerized device. In such cases, each time the Java virtual machine performs the garbage collection technique, all stack information associated with each thread must be re-scanned in order to detect storage location references within the stacks associated with those threads to determine which portions of the general memory area are not considered garbage. When many threads are idle for extended periods of time, the processing resources required to scan the stacks of the idle threads can significantly degrade performance of the Java virtual machine each time the periodic process of garbage collection is performed.

It may be the case that certain threads become blocked or remain idle over a period of time during which the Java virtual machine performs multiple garbage collection cycles. Using conventional garbage collection techniques, each time garbage collection processing is performed, the garbage collector re-scans the stacks of all threads including those threads that may have been in an idle state since the last performance of garbage collection processing. This can take considerable time since a stack associated with a thread can contain other data or information besides the general memory references of concern to the garbage collection technique. When performing the scan of a stack to detect the general memory references, the conventional garbage collection technique must scan over or bypass this other data or information within the stack such as variable values pushed onto the stack, since this data does not represent a general memory reference. Accordingly, conventional garbage collection stack scanning techniques impose performance constraints on an execution environment such as a Java virtual machine due to the requirement of detecting all general memory references each time during the garbage collection stack scanning process. In other words, conventional stack scanning constitutes a performance penalty or cost even though a thread is passive or idle, and even in situations where idle threads remain idle for multiple iterations of garbage collection. A large number of idle threads can form a scalability barrier to peak performance of an execution environment such as a Java virtual machine.

Conventional garbage collection techniques also suffer a deficiency in that they re-scan stack information looking for references to the general memory area each time they perform, even though it may be the case that portions of the stack information for a particular thread that cycles between idle and non-idle (i.e., that is performed or operated for a period of time) does not change. That is, if a thread is idle, its stack content does not change during non-operation of the thread. However, when the thread is non-idle and is operating (e.g., an applet being interpreted by a Java virtual machine), content within its stack can change. However, the thread may return to an idle condition and it may be the case that a portion of the contents of the stack does not change from the state that it existed in since the last idle state of that thread. Conventional techniques for performing garbage collection do not recognize these facts and thus suffer from performance problems due to re-scanning the entire stack for each idle thread upon each operation of the garbage collection technique.

Embodiments of the invention are based, in part, on the observation that threads that remain continuously idle over the course of multiple garbage collection cycles have associated or corresponding stack information that does not change. In addition, some embodiments are also based in part on the observation that certain portions of the contents of a stack might not change, even if a thread moves or transitions from an idle condition to a non-idle or operational state and then transitions back to an idle condition. To significantly overcome the deficiencies of conventional memory management techniques such as garbage collection, embodiments of the invention provide a new structure called a “reference structure”. Embodiments of the invention can detect all references in stacks for idle threads to the general memory area and can place associations in the reference structure to these references and to the objects in memory that they reference. Then, upon operation of a memory management technique such as garbage collection, the garbage collection process can consult the reference structure instead of scanning all stacks of idle threads to determine what portions of memory are already allocated. This saves considerable processing time.

Embodiments of the invention thus provide mechanisms and techniques for performing a memory management technique such as garbage collection by creating a reference structure that stores or otherwise maintains references to the general memory area or heap on behalf of threads, processes, routines or other threads that have associated idle conditions. Embodiments of the invention thus avoid having to rescan stack information associated with idle thread during successive iterations of a memory management technique such as garbage collection. By “remembering” references to the general memory area associated within the idle threads (e.g., idle Java threads) for those threads that remain idle for multiple garbage collection cycles, stack scanning is reduced to a one time scan to initially detect such references. Thereafter, iterations of the garbage collection technique can maintain and utilize the reference structure containing only those references to the general memory area associated with the idle thread for future iterations (e.g., operations) of the memory management technique, without having to traverse or rescan the entire stack each time garbage collection is performed.

More specifically, embodiments of the invention operate within a computerized device and provide techniques and mechanisms for performing a memory management technique such as garbage collection. In one such embodiment, a method comprises the step of identifying an idle condition associated with a thread. The thread may be, for example, a thread such as a Java thread operating within a Java virtual machine execution environment. The method may identify the idle condition, for example, by detecting that the thread has not been operated in the computerized device for a predetermined period of time. Alternatively, the method may identify the idle condition for a particular thread by detecting that the thread has not been operated by the computerized device during performance(s) of the memory management technique (e.g., garbage collection) for at least one other thread. That is, the method may consider the idle condition to be present for a particular thread if the thread remains continuously idle for a number of iterations of the garbage collection process.

In response to identifying the idle condition associated with the thread, the method proceeds to detect, within a storage structure associated with a thread, general memory references that reference storage locations in a general memory area. The storage structure may be a stack, for example, that the thread utilizes during operation (i.e., during non-idle conditions) in the computerized device. The detected general memory references may be, for example, references within stack cells to objects stored within the general memory area, which may be a heap. In one embodiment, to detect the general memory references, the method traverses the stack associated with the thread to identify all stack cells in the stack that reference storage locations of objects in the general memory area. In this manner, comprehensive or complete stack scanning is not required.

The method maintains a reference structure containing an association to the general memory area for each detected general memory reference within the storage structure. In one embodiment, the method maintains the reference structure by creating an association to the general memory area in the reference structure for each storage location of an object in the general memory area that is referenced by at least one stack cell in the stack. Each entry or association maintained in the reference structure may be, for example, a copy of the contents of the stack cell containing the detected general memory reference or, alternatively, may be a pointer to the stack cell containing the detected general memory reference. In particular, in one embodiment, the reference structure is a root array reference structure and the association to the general memory area maintained for each detected general memory reference is a copy of the contents of the detected general memory reference from the storage structure. In another embodiment, the reference structure is a summary reference structure and the association to the general memory area maintained for each detected general memory reference is a pointer to at least one location in the storage structure that contains the detected general memory references. The reference structure thus contains a consolidated list of associations between general memory references to the general memory area (e.g., a heap) and their locations within the storage structure, such as a stack, associated within the idle thread such as a Java thread. In one embodiment, there may be a single association for multiple general memory references that reference the same object in the general memory area.

After creation of the reference structure, the method operates a memory management technique on the general memory area for locations in the general memory area other than those for which an association to the general memory area is maintained in the reference structure. In other words, the memory management technique locates areas that are not reachable from any roots. The memory management technique may be, for example, a garbage collection routine, thread, process or technique that modifies the general memory area to deallocate storage locations in the general memory area for use by threads. In other words, the memory management technique utilizes the reference structure to identify (i.e., either directly or transitively via intra-heap references) those portions of the general memory area that are in use (i.e., are allocated and are thus not garbage) by threads (e.g., idle threads) so that it can free unallocated areas of memory (i.e., so that it can collect garbage).

The memory management technique may modify portions of the general memory area during its operation. As an example, those portions of the general memory area not identified by associations contained within the reference structure may be consolidated in order to create contiguous portions of free memory. This may include moving objects referenced by the associations in the reference structure to different locations in the general memory area. In such cases, according to one embodiment of the invention, the method updates the reference structure to account for modifications, made to storage locations in the general memory area, during operation of the memory management technique. In this manner, this embodiment accurately maintains the associations within the reference structure (associations between stack cell references and the data in the general memory area) even though the memory management technique modifies the general memory area including portions of memory related to those associations.

After the memory management technique (e.g., garbage collection) completes its operation, certain threads may remain in an idle or blocked condition. This idle condition for one or more threads may continue until the next iteration of the memory management technique. Accordingly, in one embodiment of the invention, the step of operating a memory management technique is repeated during a continuous idle condition associated with the thread such that the repeated step of operating the memory management technique utilizes the reference structure associated with the thread without requiring performance of the step of detecting the general memory references within the storage structure for each repeated step of the memory management technique. In other words, in this embodiment of the invention, once the reference structure is created and maintained on behalf of an idle thread, and while this thread remains continuously idle, each successive iteration or operation of the memory management technique such as garbage collection utilizes the reference structure instead of performing the stack scanning operation. Since the reference structure contains the required information to identify those portions of the general memory area in use, or that are allocated to the idle thread (e.g., thread), performance of the memory management technique is significantly increased since there is no requirement to rescan the storage structure (e.g., the stack).

At some point, a thread may transition from its idle condition to a non-idle condition in order to operate within the execution environment. One embodiment of the invention is capable of detecting that the thread is to transition from an idle condition to the non-idle condition and in response, this embodiment of the invention updates each detected general memory reference in the storage structure associated with the thread based on any updates, made to the associations to the general memory area in the reference structure, that correspond to the detected general memory references. In this embodiment of the invention then, as the memory management technique performs during the idle condition associated with the thread, as noted in the aforementioned discussion, the memory management technique can reflect changes made to the general memory area within the reference structure. When this embodiment of the invention then detects that the thread is to again begin operation within the execution environment, this embodiment of the invention can cause any changes made to the reference structure to be reflected, updated or otherwise made to the storage structure (i.e., to the stack) associated with the thread before the thread again operates within the execution environment. Accordingly, any modifications to data within the general memory area such as movement of an object from one location to another during a garbage collection process become transparent to the idle thread once that thread again becomes active.

Other embodiments of the invention include a computerized device, workstation, handheld or laptop computer, or the like configured with software and/or circuitry (e.g., a processor as summarized above) to process any or all of the method operations disclosed herein as embodiments of the invention. In other words, a computerized device or a processor that is programmed or configured to operate as explained herein is considered an embodiment of the invention.

Other embodiments of the invention that are disclosed herein include software programs to perform the method embodiment steps and operations summarized above and disclosed in detail below. One such embodiment comprises a computer program product that has a computer-readable medium including computer program logic encoded thereon that, when performed in a computerized device having a coupling of a memory and a processor, programs the processor to perform the operations disclosed herein as embodiments of the invention. Such arrangements of the invention are typically provided as software, code and/or other data (e.g., data structures) arranged or encoded on a computer readable medium such as an optical medium (e.g., CD-ROM), floppy or hard disk or other a medium such as firmware or microcode in one or more ROM or RAM or PROM chips or as an Application Specific Integrated Circuit (ASIC). The software or firmware or other such configurations can be installed onto a computerized device to cause the computerized device to perform the techniques explained herein as embodiments of the invention. An example of such a software embodiment is a Java virtual Machine equipped with a memory management accelerator and/or a memory management process configured to operate as explained herein.

It is to be understood that the system of the invention can be embodied strictly as a software program, as software and hardware, or as hardware alone such as a processor. Example embodiments of the invention may be implemented within computer systems, processors, and computer program products and/or software applications manufactured by Sun Microsystems Inc. of Palo Alto, Calif., USA.

DETAILED DESCRIPTION OF EMBODIMENTS

Generally, embodiments of the invention provide mechanisms and techniques for performing a memory management technique such as, for example, garbage collection, by creating and maintaining a reference structure that stores or otherwise maintains references to a general memory area (e.g., a heap) on behalf of threads, processes, routines or other threads. Once a reference structure is created on behalf of one or more threads, the computerized device can operate or otherwise perform the memory management technique on a general memory area and can access the reference structure to determine what portions of the general memory area contain data already allocated or otherwise referenced by the threads. As an example, if the memory management technique is garbage collection, the garbage collector (e.g., a process or thread) can refer to the reference structure to identify those storage locations in the general memory area that are allocated on behalf of threads and can thus determine what portions of memory can be deallocated or freed for use by other threads. If the thread having an associated reference structure exists in an idle state or condition for a period of time that encompasses multiple iterations or operations of the memory management technique (e.g., multiple periodic operations of the garbage collector), performance of the memory management technique is increased by embodiments of the invention since the memory management technique can continue to utilize the reference structure created and maintained by embodiments of the invention instead of having to re-determine or re-scan the storage structure (e.g., a stack) to determine what general memory references exist on behalf of the idle thread to the general memory area.

As a specific example, embodiments of the invention do not require the garbage collector to re-scan the stack associated with an idle thread each time the garbage collector operates. By “remembering” references to the general memory area associated within the idle threads (e.g., idle Java threads) for those threads that remain idle for multiple garbage collection cycles, stack scanning is thus reduced to a one time or initial scan to initially detect such references. Thereafter, iterations of the garbage collection technique can maintain and utilize the reference structure containing only those associations to references in the general memory area associated with the idle thread, without having to traverse or re-scan the entire stack (containing other information in addition to the detected general memory references) each time garbage collection is performed.

FIG. 1illustrates an example of a computerized device100configured according to one example embodiment of the invention. The computerized device100includes an interconnection mechanism101such as a data bus or other circuitry that interconnects a processor102and a memory103. The processor102may be any type of central processing unit, controller, microprocessor, or other circuitry that is capable of executing, interpreting, operating, being configured with, or otherwise performing sets of logic instructions such as computer program code. The memory103maybe any type of computer readable medium such as electronic semiconductor memory (e.g., Random Access Memory or Read Only Memory) or another storage medium such magnetic or optical disk storage.

The processor102operates in execution environment105that in this example is a Java virtual machine. The execution environment105can operate one or more threads110-1through110-Y that in this example are Java threads. In addition, the execution environment105in the processor102operates a memory management accelerator120and a memory management process150, that in this example is a garbage collection process.

The memory103is encoded with various data structures that in this example include a reference structure130(labeled in this example as a summary table or root array, to be explained), a storage structure135(labeled in this example as a stack) and a general memory area140(labeled in this example as a heap).

The storage structure135in this example is a stack that can be utilized by the execution environment105during operation of a thread110as illustrated by access communications path137. Though not specifically illustrated, there may be a respective stack135for each respective thread110. During operation of a thread110, the operation environment105and/or the thread110may create, place, or put onto (as indicated at137) the storage structure135one or more general memory references160-1through160-N. In addition, the operation environment105and/or the thread110may utilize the storage structure135to store or push onto (and remove or pop-off) additional information164-1through164-P which can include, for example, procedure call information, register values, variable data or the like. Those skilled in the art understand that a stack storage structure135might be used to store a variety of different types of data or information in addition to the general memory references160during operation of the execution environment105when performing the thread110.

Within the storage structure135in this example, each general memory reference160references162(e.g., is a pointer to, or contains the address of) a respective corresponding general memory object170-1through170-N stored within the general memory area140(i.e., within the heap in this example). Each general memory reference160may contain, for example, an address that is a pointer to (i.e.,162) a storage location within the general memory area140at which the general memory object170exists. Also in this example, the general memory area140includes a general memory object170-X that represents an unused, unreferenced or garbage object within the general memory area140. That is, there is no general memory reference160within a storage structure135for the thread110(or for any other thread from any other storage structure) that presently references the general memory object170-X.

The memory management process150periodically generally operates as a garbage collection process or technique190or garbage collector as explained herein to periodically examine the general memory area140in order to deallocate or assign unused or unreferenced general memory objects170-X back to free memory for use by other threads110. During this technique190, the memory management process150may operate to coalesce or consolidate the general memory objects170-1through170-N into a contiguous area of allocated memory while at the same time coalescing or consolidating the unused or unallocated portions of memory172-1through172-M, along with any deallocated general memory object(s) (e.g.,170-X) in order to form larger contiguous portions of deallocated or free memory. In other words, and as will be explained in more detail, the memory management process150may perform the memory management technique190to remove memory fragmentation associated with the illustrated noncontiguous portions172of free memory. To assist in this memory management processing, embodiments of the invention provide the memory management accelerator120.

Generally, the memory management accelerator120creates and maintains the reference structure130, which in one embodiment is a table of references (i.e., associations188) to objects170in the heap. The memory management process150can utilize the reference structure to enhance performance of a memory management technique190as will be explained herein. The operation of the memory management accelerator120shown inFIG. 1, according to example embodiments of the invention, will now be discussed in conjunction with the processing steps illustrated in the flow chart of processing steps shown inFIGS. 2,3and4.

FIG. 2illustrates a flow chart of processing steps performed within a computerized device100configured according to one example embodiment of the invention to perform a memory management technique according to embodiments of the invention as explained herein.

In step200, the memory management accelerator120operates to identify an idle condition192associated with the thread110operating within the execution environment105. As noted above, in this example, the thread110may be a Java thread operating within a Java virtual machine execution environment105. In one embodiment of step200, the memory management accelerator120operates to identify an idle condition192associated with the thread110, for example, by detecting that a top frame of the storage structure (e.g., the stack135) indicates that the thread110has an associated known blocking call, such as a read, that indicates that the thread will remain idle for some time period.

Steps201and202illustrate two examples of processing steps that can be performed to identify an idle condition associated with the thread110(i.e., to perform step200).

In step201, the memory management accelerator120detects that the computerized device has not operated the thread110during a performance of the memory management technique. In other works, the thread has remained idle. The memory management accelerator120can monitor which threads110operating within the execution environment105are currently in an idle condition192and can compare115the idle states of these threads110with the periodic operation of the memory management process150. If the memory management process150performs multiple iterations while a particular thread110is continuously experiencing an idle condition192, then this embodiment considers that the thread has an associated idle condition192sufficient to perform the techniques explained herein to maintain the reference structure130in order to improve the performance of the memory management technique190.

Step202provides processing of an alternative embodiment in which the memory management accelerator120can identify an idle condition associated with the thread110by detecting an inactivity period of the thread110in the computerized device100that indicates the thread110has not been operated in the computerized device for a predetermined period of time. As an example, if the thread110is idle for a certain number of seconds, then the memory management accelerator120can consider that an idle condition192is associated with the thread110.

Next, in step203, the memory management accelerator120detects (as indicated at the arrows185-1through185-N), within a storage structure135(e.g., a stack) associated with the thread110(e.g., a Java thread), general memory references160(e.g., stack cell address references or pointers) that reference storage locations (e.g., general memory objects170) in a general memory area (e.g., a heap).

A more detailed example of the processing of step203is illustrated in step204in which the memory management accelerator120traverses the stack135associated with the thread to identify all stack cells160in the stack135that reference162storage locations of objects170in the general memory area140.

Next, in step205, the memory management accelerator120maintains (e.g., constructs or creates and subsequently maintains, as indicated at the arrows186-1through186-N) a reference structure130containing an association188-1through188-N to the general memory area140for each detected general memory reference160within the storage structure135.

An example of the processing of step205is illustrated in more detail in step206in which the memory management accelerator120creates or maintains an association188to the general memory area140in the reference structure130for each storage location170of an object in the general memory area140that is referenced by at least one stack cell160in the stack135. Note that in one embodiment, there may be a single association188for multiple general memory references160in the stack135that each reference the same storage location in the general memory area140(e.g., that each reference the same object170).

In one embodiment, the reference structure is a root array reference structure and each association to the general memory area maintained for each detected general memory reference is initially a copy of the contents of the detected general memory reference from the storage structure. In such an embodiment, the memory management accelerator120can replace stack cell general memory references160with pointers188(i.e., on type of association188) to entries186within the root array reference structure130. In other words, the general memory references160are copied to the reference structure130and replaced, in the stack135, with indirect references to the reference structure130.

In another embodiment, the reference structure is a summary reference structure and the association188to the general memory area maintained for each detected general memory reference is a pointer to at least one location in the storage structure that contains the detected general memory references. In this embodiment then, the entries186in the summary table reference structure130represent pointers188to the general memory references160within the storage structure135. Further details regarding the distinctions in processing between a root array reference structure and a summary table reference structure will be explained shortly.

Directing attention now briefly ahead toFIG. 5, the top of this figure illustrates an example of how the memory management accelerator120examines185the stack storage structure135during the existence of the idle condition192associated with thread110in order to create and maintain186the reference structure130containing in this example, associations188to general memory references160-1through160-N that reference or point to corresponding locations170-1through170-N within the general memory area140-1. In other words, the upper portion ofFIG. 5illustrates the operation of steps200through206as explained above with respect toFIG. 2in order to create and maintain the reference structure130. This example further illustrates the general memory references160being respectively labeled L1, L3and L5, which correspond to the general memory objects170-1through170-N stored at locations L1, L3and L5within the general memory area140-1.

Also inFIG. 5, the general memory area140-1illustrated inFIG. 5represents the arrangement of general memory objects170and unused portions of memory, or garbage locations,172-1through172-3, prior to the operation of the memory management process150. In other words, the general memory area140-1represents the arrangement of memory prior to garbage collection, whereas the general memory area140-2inFIG. 5represents the arrangement of the general memory area after performance of the garbage collection memory management technique190by the memory management process150according to one embodiment of the invention which will be explained shortly.

Returning attention now back to the flow chart and specifically to step207at the top ofFIG. 3, in step207, the memory management accelerator120triggers115(FIG. 1) the memory management process150to operate a memory management technique190such as garbage collection on the general memory area140for locations (i.e., unused object170-X and garbage locations172-1through172-M inFIG. 1) in the general memory area140other than those for which an association188to the general memory area140is maintained in the reference structure130. That is, in one embodiment of the invention, the memory management technique190performs, in step203, garbage collection on the general memory area140for storage locations170-X and172.

Briefly returning attention again to the example illustration inFIG. 5, this figure illustrates an example of how the processing of step207fromFIG. 3causes the memory management process150to operate the memory management technique190in order to include the garbage locations or portions172-1through172-3of the general memory area140-1(that indicates how this area appears before garbage collection) in a free list of memory as shown in the general memory area140-2(that indicates how memory appears after garbage collection). In other words, one embodiment of the invention causes the memory management process150to read the associations188(as shown at location178inFIG. 5) contained within the reference structure130to identify the general memory objects locations170contained within the general memory area140-1. Based on the associations160, the memory management process150can identify other locations within the general memory area such as garbage locations172that can be deallocated or assigned to a free memory list in order to be allocated to other threads110should this garbage memory be needed. Accordingly, as shown inFIG. 5, the general memory area140-2illustrates that the garbage portions of memory172have now been placed or converted into free memory portions174-1through174-3(i.e., are on a free list maintained by the execution environment105). Note that in this example embodiment, the memory management technique does not otherwise modify the general memory area140. That is, no movement is made to the general memory objects170in this example embodiment.

Returning attention now back to the flow chart of processing steps illustrated inFIG. 3, certain embodiments of the invention can provide a memory management technique190which modifies locations of objects170within the general memory area140, for example, to overcome memory fragmentation issues. Processing steps related to the an example operation of the memory management technique190that modifies the general memory area140according to one example embodiment of the invention are illustrated in steps208and209.

As indicated in step208, operation of the memory management technique (step207) can include modifying the general memory area140to deallocate memory locations (i.e.,172and170-X inFIG. 1) other than those locations corresponding to associations188maintained in the reference structure130. That is, in step208, the memory management process150can free those portions of the heap140for which there are no general memory reference associations maintained within the reference structure130. In example illustrated inFIG. 1, these locations include the fragmented memory areas172as well as the general memory object170-X, for which there are no longer any general memory reference associations188which point to or otherwise reference this general memory object170-X. When deallocating memory portions172and170-X in this manner, the garbage collection process150can reference178the reference structure130to identify those areas of the general memory area140that are presently allocated for use by the idle thread(s)110. The memory management technique190may thus move the general memory objects170around within the general memory area140in order to coalesce or developed larger contiguous portion of free memory172into a single portion. This may include, for example, moving the general memory objects170-1through170-N into a single contiguous portion of allocated memory, thus leaving the remainder of the heap140free for allocation to data structures required by other threads110.

Directing attention briefly ahead to the illustration inFIG. 6, this figure is similar to that ofFIG. 5but illustrates how changes made by the memory management process150to the general memory area140during operation of the memory management technique190can be updated or otherwise reflected within the reference structure130, and then subsequently, as will be explained, into the storage structure135associated with the thread (when that thread attempts to operate again by becoming non-idle). That is, this Figure also illustrates an example of how these changes can be further reflected in the storage structure135associated with a thread110as the thread transitions from an idle condition to a non-idle condition.

At the top ofFIG. 6, the storage structure135-1represents the contents of the stack associated with a thread110before an operation of the memory management technique190. As previously discussed, the memory management accelerator120examines the storage structure135-1according to the techniques explained with respect to the processing steps in FIG.2and maintains or otherwise produces the reference structure130-1which contains a list or other set of associations188between the locations of the general memory references160-1through160-N detected within the storage structure135-1and corresponding general memory objects170-1through170-N within the general memory area140-1.

After creation of the reference structure130-1, the memory management accelerator120triggers (as indicated at location178inFIG. 6) the memory management process150to read the associations188from the reference structure130-1in order to perform the memory management technique190upon the general memory area140-1. This allows the memory management technique190to identify current portions of memory that are “in use.” As in the aforementioned example fromFIG. 5, the “before” general memory area140-1inFIG. 6illustrates an example of object placement170and garbage memory locations172as a series of locations L1through L6as they exist prior to the operation of the garbage collection memory management technique190. In this example operation of the memory management technique190, the memory management process150performs the processing of steps208and209discussed above with respect toFIG. 3in order to modify the general memory area140-1to be arranged as the general memory area140-2(i.e., after garbage collection has taken place). In this example then, the memory management process150performs garbage collection upon garbage locations172-1through172-3and consolidates the arrangement of general memory objects170-1through170-N from their original respective locations L1, L3and L5to their new locations L1, L2and L3within the general memory area140-2. The memory management technique190thus coalesces or consolidates the general memory objects170into a contiguous portion of the heap140-2. In doing so, the memory management technique190also deallocates the remaining portion174of the general memory area which comprises memory locations L4through L6and assigns this area174as free memory.

However, in performing this memory management technique to rearrange the locations of the objects170within the general memory area140, this embodiment of the memory management process150also performs step209as discussed above with respect toFIG. 3in order to update the reference structure130to account for modifications made to storage locations170in the general memory area140that were made during performance of the memory management technique190and that relate to the associations188to the general memory area maintained in the reference structure130. In other words, after rearranging the locations of the general memory objects170within the general memory area according to the memory management technique190, the memory management process150updates the associations188(as indicated at location179inFIG. 6) in order to cause the memory management accelerator120to properly maintain the reference structure130-2according to any new locations of objects170within the memory140. The reference structure130-2thus reflects the contents of the reference structure130after performance of the memory management technique.

In the specific example illustrated inFIG. 6, notice that the associations188-1through188-N to general memory references160in the reference structure130-1reference respective memory storage locations L1, L3and L5in the general memory area140-1(i.e., reference locations to objects170at their locations within the heap prior to the performance of the memory management technique). Then, after the memory management process150performs the memory management technique190according to steps208and209(FIG.3), the memory management process150operates in conjunction with the memory management accelerator120to update the reference structure130-1to appear as shown in130-2. Specifically, after performance of the memory management technique190, the associations188-1through188-N to general memory references in the reference structure130-2now reference respective locations L1, L2and L3(as opposed to L1, L3and L5) in the general memory area140-2(i.e., reference locations to objects170at their new locations within the heap after the performance of the memory management technique).

Note that in this example embodiment, multiple iterations of the memory management process150may be performed, for example, in a periodic manner by a Java virtual machine, and each time general memory objects170are rearranged within the general memory area140in order to perform garbage collection, the memory management process150can operate in conjunction with the memory management accelerator120in order to properly update or maintain the associations188in the reference structure130. Also note that in this example embodiment, the storage structure135does not necessarily have to be updated each time the reference structure130changes based on operation of the memory management technique. Instead, as will be explained shortly, in this embodiment of the invention, updates can be made to the reference structure130during successive iterations of the memory management technique190and then, upon the detection of the transition of the thread110from an idle condition to a non-idle condition (step210, to be explained), the memory management accelerator120can perform a proper update of the general memory references160within the storage structure135prior to the thread110operating again within the computerized device100. Returning attention back to step207inFIG. 3, this is illustrated by the logic of step210.

As note above, after performance of the operation of the memory management technique190in step207for one iteration of garbage collection, processing proceeds to step210.

In step210, the memory management accelerator120determines if the thread is to transition from its current idle condition to a non-idle condition. In other words, the memory management accelerator120can determine or otherwise detect when the thread is about to begin performance within the execution environment105(FIG.1). In step210, if the thread remains in an idle condition, processing can return to step207in order to repeat performance of the periodic memory management technique using the current state of the reference structure135for this particular thread110. In other words, as long as the thread110remains in an idle condition, each successive periodic operation of the memory management technique190can utilize the current reference structure130for that thread110to increase performance of the memory management technique as explained herein. As discussed above with respect to the example illustrated inFIG. 6, upon another successive operation of the memory management process150, the memory management process150, upon a second iteration, utilizes the reference structure130-2containing associations160to general memory references reflecting the current locations L1, L2and L3of the general memory objects170within the general memory area140-2to identify currently allocated portions of the general memory area (i.e., the heap)140.

Accordingly, the processing of steps207through210can continue to return to step207during the continuous idle condition of the thread110. In step210, once the memory management accelerator120detects a change in the idle condition192of the thread110(i.e., that the thread110is about to execute or operate again), processing proceeds to step211.

In step211, the memory management accelerator120updates each detected general memory reference160in the storage structure135associated with the thread110based on any modifications or updates made, during operation of the memory management technique190, to the associations188to the general memory area140in the reference structure130that correspond to the detected general memory references160in the storage structure135. In other words, prior to the transition of the thread from the idle condition to the non-idle condition, the memory management accelerator120causes any changes made during one or more iterations of the memory management technique to the reference structure130to be reflected within the general memory reference locations160in the storage structure135that correspond to the associations188in the reference structure130. This is illustrated inFIG. 6by the contents of storage structure135-2as it appears after completion of the memory management technique190and just prior to operation of the thread110(i.e., as the thread transitions from the idle condition to the non-idle condition).

There are a number of events embodiments of the invention can use as a trigger to restore stack roots from the reference structure. In one configuration, roots are restored in the stack when the thread transitions from idle to active. In another embodiment of the invention as a thread unwinds (e.g., transition from idle to non-idle), the system of the invention can restore the roots in the next underlying frame (or group of frames), such as by restoring one frame or multiple frames at a time. In yet configuration, embodiments of the invention can wait until the thread exits the idle state and begins operation and can use a “poison” reference. In such cases, when a thread accesses an object via such a poison reference, the Java virtual machine can restore the reference at that time (e.g., can restore one cell at a time, on-demand for that cell by the active thread).

InFIG. 6, note the differences between the storage structure135-1before operation of the memory management technique (i.e., when the thread110initially enters the idle condition192) as opposed to the contents of the storage structure135-2after operation of the memory management technique for one or more iterations (i.e., when the thread110transitions from the idle condition to a non-idle condition). Specifically, notice that embodiments of the invention properly update the new locations L1, L2and L3of the general memory objects170-1through170-N from the reference structure130-2to storage structure135-2as the thread transitions from the idle condition to a non-idle condition (i.e., just prior to performance of the thread110within the execution environment105).

Returning attention back to step211inFIG. 3, after the storage structure135is updated, processing proceeds to step212shown at the top of the flow chart of processing steps in FIG.4.

In step212inFIG. 4, the memory management accelerator120stores the reference structure130during operation of the thread110in the computerized device100. In other words, in this example embodiment of the invention, when the thread transitions from the idle condition to the non-idle condition and again begins execution, interpretation, or other performance within the execution environment105(FIG.1), the memory management accelerator120saves or preserves the current state of the reference structure130. This is done in this example because the reference structure130represents an initial effort on the part of the memory management accelerator120to gather or collect the associations188from each general memory reference160in a thread's stack135to the corresponding location of the objects170within the general memory area140. Accordingly, when the thread110operates in execution environment in the non-idle condition, it may be the case that certain of the stack locations, and hence their corresponding associations188in the reference structure130, may not be disturbed or modified during execution or operation of the thread110. Accordingly, in this embodiment of the invention and as will be explained shortly, by storing the reference structure130, if the thread110again enters an idle condition192, this embodiment of the invention can determine what portions of the reference structure contain associations188that are still valid or, in other words, still accurately associate general memory references160to locations of objects170in the heap. To do so, processing proceeds to perform step213through216in order to recover, for reuse, those portions of the reference structure130which were not disturbed during operation of the thread110.

Specifically, in step213, the memory management accelerator120detects a second idle condition192associated with the thread110. In other words, the memory management accelerator120detects that the thread110is again idle, blocked or otherwise non-operational within the execution environment105.

In step214, the memory management accelerator identifies at least a portion of the stored reference structure130that contains associations188to the general memory area140that have not changed during the operation of the thread110in the computerized device100. Steps215and216illustrate one example embodiment of the invention that allows the memory management accelerator120to determine which portions of the reference structure130are still valid, usable, or in other words, that have not changed since the former idle condition of the thread110.

In step215, the memory management accelerator120examines the storage structure135(i.e., examines the stack) associated with the thread110to detect a predetermined storage locations160in the storage structure135that identify portions of the storage structure135that have not changed during operation of the thread110. In other words, in step215, the memory management accelerator120can examine the stack135to detect predetermined or known stack cell contents within specific stack sells in the stack135. In one embodiment of the invention, the memory management accelerator120, during initial detection of general memory references160in step203(FIG. 2) can keep track of the stack locations of these general memory references160for future use in step215. Alternatively, during startup of a thread after transition from the idle condition to the non-idle condition, the memory management accelerator120can keep track of certain known marker values in the stack at various locations. When the thread thus goes idle again, by starting at the top of the stack and examining consecutive stack frames, the memory management accelerator120in step217can attempt to find storage locations within the stack135that contain the same contents as they did prior to operation of the thread (i.e., since the last idle condition). As an example, the marker locations or values can be detected. Once a location in the stack135has been identified in step215, embodiments of the memory management accelerator120can thus infer that the remaining contents of the stack below this location have not changed during operation of the thread110. In other words, even though the thread110was operated in the execution environment105, there is likely to be a location in the stack below which no changes were made. By identifying such a location, the memory management accelerator120can identify that the remaining portions of the stack below this location have not been modified during operation of the thread110. Accordingly, processing proceeds to step216.

In step216, the memory management accelerator120maintains, for use within the reference structure130, those associations188from the stored reference structure130that correspond to the locations in the storage structure135(i.e., in the stack) that have not changed during operation of the thread110. In other words, by detecting which portions of the stack135have not changed during operation of the thread in step215, all locations in the stack135below the unchanged locations are assumed not to have changed as well (i.e., due to the last in first out or LIFO nature of stack operation). Accordingly, those associations188in the stored reference structure130that correspond to these unchanged stack locations are assumed in step216to still be valid or, in other words, are assumed to point to or otherwise reference proper locations170of general memory objects in the general memory area140that have not been deallocated or moved during operation of the thread110.

Accordingly, after completion of step216, the memory management accelerator120has identified which portions of the reference structure130(i.e., which associations188) can be reused during another iteration of embodiments of the invention as previously explained. By reusing these portions of the reference structure130, the performance of the operation of detecting general memory references160(i.e., step203and204inFIG. 2) and maintaining the reference structure (i.e., steps205and206inFIG. 2) are increased. That is, when the thread110reenters an idle condition, by reusing portions of the reference structure130, the memory management accelerator120only needs to examine those portions of the storage structure135(i.e., the stack) that have changed since the last idle condition of the thread110(i.e., only needs to examine those portions of the stack that have changed during operation of the thread). Thus a complete stack scan may not be required, even after a thread110operates for a period of time.

Accordingly, in step217inFIG. 4, the memory management accelerator repeats the step of detecting (i.e., repeats the general processing of steps203and204), within the storage structure135associated with the thread110, to detect general memory references160that reference storage locations (i.e., objects170) in the general memory area140for portions of the storage structure135that have changed during the operation of the thread110in the computerized device100. In other words, in step217, the memory management accelerator only needs to examine those portions of the stack135that were modified during operation of the thread110since the last idle condition of the thread110that cost creation of the reference structure130. After processing step217, processing proceeds to step218.

In step218, the memory management accelerator120repeats the step of maintaining the reference structure130(i.e., repeats the general processing of steps205and206inFIG. 2) for each detected general memory reference160within the storage structure135, for those portions of the storage structure135that have changed during the operation of the thread110in the computerized device100, such that (new) associations188corresponding to the general memory references160detected in the repeated step of maintaining are added to the reference structure130. In other words, in steps217and218, the memory management accelerator120examines only the changed or new portions of the stack135in order to detect any new general memory references160to object locations170in the general memory area140and adds new associations188into the reference structure130for any of these newly detected general memory references160.

In this manner, the embodiment of the invention illustrated by the processing from steps212through218provides the ability to reuse portions of the reference structure130and thus take advantage of former processing performed to create, develop and maintain the reference structure during its initial creation (i.e., produced a result of the initial detection of the idle condition associated with the thread110).

It is to be understood that the aforementioned processing steps illustrate examples of processing performed according to embodiments of the invention. It is to be understood that there can be many variations made to the embodiments explained above while still achieving the same objective of those embodiments and the invention in general. For example, alterations to these processing steps may be made by those skilled in the art without changing overall effects achieved, such as, for example, providing an increase in the performance of the memory management techniques such as garbage collection within the computerized device100. Accordingly, such modifications, eliminations or rearrangement of certain processing steps are intended to be covered within the scope of embodiments of the invention.

As an example, the processing illustrated inFIG. 4in order to store the reference structure130for future use in the event to the thread again enters an idle condition110is optional and need not be included in all embodiments of the invention. Accordingly, an embodiment of the invention that operates to re-create a new reference structure130each time the thread110enters an idle condition is considered to be embodiment of the invention.

In another embodiment, the reference structure can be utilized by the memory management technique to better organize the heap or general memory area. As an example, the set of memory objects referenced by associations in the reference structure for threads that remain idle for long periods are not likely to be referenced for extended periods of time. As such, a garbage collection memory management technique can use this information to “promote” these object in the heap earlier in time in order to more efficiently manage or organize memory. That is, embodiments can mark or otherwise uniquely designate reference associations in the references structure that are associated with threads know to remain idle for long periods of time. When such a thread goes idle, the garbage collection mechanism can use the associations to that thread's objects from the reference structure to move or “sequester” the objects for that thread to an area in general memory that can be used to maintain long-lived objects, thus quickly freeing up the original locations for use by more active threads.

In another alternative embodiment of the invention, the processing operations of detecting general memory references (step203), maintaining the reference structure130(step205) and operating a memory management technique (step207) are performed for a plurality of threads110-1through110-Y (not specifically shown) that each have an associated idle condition. In such an embodiment, a single reference structure130can be used to maintain all associations188between general memory references160and storage locations170within the general memory area140. There may be separate individual storage structures135for each different thread110. In such an embodiment, the single reference structure contains associations to the general memory area for detected general memory references from the plurality of threads.

FIG. 7illustrates an example of a multi-dimensional reference structure130configured in accordance with one example embodiment of the invention. That is, in another embodiment of the invention, the reference structure is a multi-dimensional reference structure130including indexed association storage areas402-1through402-4. Each index association storage area402identifies a list or other set of associations188indexed, in this example, based on addresses of the general memory references160that reference objects170within the general memory area140. In other words, in embodiments of the invention that utilize a single reference structure130to track associations188of general memory references160to objects170in the general memory area on behalf of multiple storage structures135(i.e., multiple stacks) used by multiple threads110that are idle, the single reference structure130inFIG. 7can be arranged for efficient placement of the associations188to increase performance of accessing and updating associations188within the multidimensional reference structure130.

In the illustrated example, each indexed association storage area402-01through402-4represents a range of storage location memory addresses L0through L99of the general memory area140. As a specific example, upon detection of the general memory reference160-19in the stack135that references memory location L74in the general memory area140, the memory management accelerator120creates an association188-9that associated the general memory reference160-19to the general memory storage location L74. To place this in the multidimensional reference structure130, memory management accelerator120uses the address L74to determine which indexed associated storage area402-3, covering the address range L75through L75and adds this association188-9below this indexed associated storage area402-3. This allows quick access to the associations188based on their corresponding memory addresses L0through L99, in this simple example.

In one embodiment of the invention then, the step of maintaining the reference structure (step205and206) can include the step of identifying an indexed association storage area402in which to store an association to the general memory area based on an address of the object170in the general memory area140that is referenced by at least one stack cell160in the stack135, as explained in the above example. The memory management accelerator120then stores the association188to the general memory area140at the indexed association storage area402-1through402-4identified in the step of identifying.

Also as illustrated inFIG. 7, a hash function410or similar technique can be used upon each detected general memory reference160in order to quickly determine which particular indexed association storage area402is to contain the association188. In other words, embodiments of the invention can utilize the address of the object in the general memory area to access a proper indexed association storage area in the reference structure without having to search, within the reference structure, indexed association storage areas unrelated to the address of the object. A hash function, for example, which looks at or uses a certain number of, for example, low ordered bits of the memory address can be used to determine which indexed association storage area402in which to place the association188.

In one embodiment, the heap or general memory area140is constructed or arranged in such a way that generations of objects (i.e., objects created in the same section of code or method in a thread or at the same time) are grouped by address. In such arrangements, the hash function410can extract the high-order bits of an objects heap offset (i.e. location170) to properly place associations188into the reference structure130, such that associations to common generations of objects170are located in a common portion of the reference structure130. In such cases, the memory management process150, during garbage collection of a single generation in the heap140, only needs to scan the corresponding subsection in the hash table-based reference structure130to perform updates of association entries188.

In another embodiment of the invention, at least one association188in the reference structure130is associated with an object in the general memory area on behalf of at least two stack cells160(i.e., at least two general memory references) in the stack135. That is, in this embodiment of the invention, a single association188can represent the contents of two stack cells. Accordingly, if there are two general memory references160within a storage structure135associated with the thread110, and each general memory reference160references the same object storage locations170in the general memory area140, in this embodiment of the invention only maintains a single association188to this object170and to each of these general memory references160. During the process of updating the storage structure135based on the reference structure130as explained above during transition of the thread from an idle condition to a non-idle condition, this embodiment of the invention modifies or updates both general memory references160based on the single association188.

It is to be understood that the example reference structure inFIG. 7is shown by way of example only. The reference structure130could take on other forms as well in various other embodiments of the invention. In particular, as discussed herein, the reference structure can be a summary table or summary reference structure130containing a list of stack cells (e.g., cell addresses) as each association188. In such embodiments, each idle thread would have its own private summary table130.

In other embodiments, the reference structure130can be a root array reference structure130containing entries188that contain pointers to objects in the general memory area140.

In such embodiments, if the memory management technique implements a moving or copying garbage collection technique, then as a thread transitions from idle to a non-idle state, the memory management accelerator120can operate a Java virtual machine stack walker process to replace reference stack cells in the storage structure135with pointers to the root array entry. Thus, each root array entry in the reference structure130contains a reference. In such a configuration, each idle thread typically has its own private root array and each “live” stack cell in the storage structure135has its own corresponding root array entry.

In another alternate configuration of the root array reference structure130, multiple stack cells160could point to same root array reference structure entry188. In such an embodiment, at the idle to non-idle (i.e., active) transition of a thread110, the memory management accelerator120can operate a Java virtual machine stack walker process to find all stack reference cells and, using the associated root array reference structure entry188(in this embodiment, recall that for an idle thread each stack reference cell160holds a pointer to a root array entry188) the memory management accelerator120operating in the Java virtual machine stores the “fresh” reference value into the stack cell160.

In yet another alternative arrangement of the root array reference structure130that can be used if the memory management technique implements a moving or copying garbage collection technique, at the idle to active transition of a thread, the memory management accelerator120can operate a stack walker process that leaves the stack cells160unchanged in the storage structure135, but copies memory references into the root array130. Thus, the root array entry contains a reference and a cell-identifier pair such as {reference, cell-identifier}. This is hybrid form, as it shares some characteristics with the summary table form. In such a configuration, each idle thread has its own private root array. At the idle to non-idle transition of a thread, the memory management accelerator120uses the cell-identifiers as addresses to restore the fresh reference values into the thread's110stack135. This technique accelerates the idle to non-idle transition.

In still a further alternative arrangement of the root array reference structure130that can be used if the memory management technique implements a moving or copying garbage collection technique, at the idle to active transition of a thread, at the active or non-idle to idle thread transition, a stack walker within the memory management accelerator120copies references160into the root array reference structure135, and then uses the vacated stack cells to form a linked list of cells that refer to the same object. Each root array entry188contains a reference and a point to the next reference in the root array list, such as {reference160to memory address170, CellListHead}. When the thread remains idle, each vacated stack cell160holds a pointer to the_next vacated stack cell that refers to the same object. The last cell in the list contains a distinguished end-of-list value (perhaps 0). In other words, the CellListHead is head of a linked list of cells that refer to the same object. In a typical stack135, multiple cells160may refer to the same object170, so this form is useful to conserve storage space and reduce the size of the storage structure135. In such embodiments, each idle thread has its own private root array and this technique can accelerate the processing required at the idle to no-idle active transition of a thread.

In still a further alternative arrangement of the root array reference structure130that can be used if the memory management technique implements a moving or copying garbage collection technique, at the active or non-idle to idle transition of a thread, a stack walker within the memory management accelerator120copies references160from the storage structure135into the root array reference structure130and replaces each stack cell160with a pointer to a root array entry188. The root array thus contains entries188-1through188-N that appear as {reference, Reference-Count}. The Reference-Count field indicates how many stack cells160-1through160-N point to this root array entry188. The entries188can also contain a “next” link, pointing to the next root array entry188in a hash equivalence class. During idle to non-idle transition of a thread, as the memory management technique replaces stack cell entries160with their new values (i.e., the new locations170of objects that they formerly referenced), the Reference-Count is decremented. When the value of Reference-Count reaches 0, the root array entry188could be reused or released. In embodiments where the root array entries are one-to-one with stack cells, the reference count field would be 1 for entries188that are in-use. In embodiments that use a single root array reference structure association entry188to maintain an association to multiple stack cells160, the Reference-Count reflects the number of stack cells160referenced by this single association entry188. Thus, embodiments of the invention can free portions (i.e., association entires188) in the reference structure130by using reference counts to indicate when threads are referencing the information in a single entry188.

For embodiments that use non-copying or non-moving garbage collector techniques, as a thread transitions from idle to a non-idle state, the stack-walker process of the memory management accelerator120copies references160from the root array references structure130to the stack135.

It is also to be understood that in certain embodiments of the invention, there are a plurality of threads and each thread is a Java thread associated with a Java execution environment such as a Java virtual machine. In such an embodiment, the storage structure associated with each thread is a stack structure and the general memory area is a heap structure used by the Java execution environment to maintain objects on behalf of each Java thread. Also in such an embodiment, the detected general memory references are object references from the stack structure to the heap structure for objects referenced by the Java thread. Furthermore, in such an embodiment, the memory management technique is a garbage collection technique that uses the reference structure to identify objects in the heap that are in use by threads so as not to deallocate areas of the heap related to those identified objects.

According to another embodiment of the invention, the existence of a passivated thread (i.e., one for which entries exist in the reference structure130) can be used to direct other processes in the Java virtual machine to operate accordingly. As an example, when a thread is stopped for garbage collection, the garbage collection process performs a stack scan to deflate idle monitors. However, in embodiments of the invention, threads that are idle and for which a reference structure is created (or for which a shared reference structure130contains entries from the stack of the idle thread to the reference structure), no deflation scan is required. Thus, embodiments of the invention can create a “passivated idle thread” state and when a thread is in such a state, garbage collection does not need to perform deflation scanning.

Embodiments of the invention can thus operate the memory management technique to perform garbage collection without requiring access to the storage structure associated with the thread during rearrangement of the general memory area. It is to be understood that the memory management process150and/or the memory management accelerator may be integral parts of the execution environment105or may be separate processes or programs.

Such variations are intended to be covered by the scope of this invention. As such, the foregoing description of embodiments of the invention are not intended to be the limiting. Rather, any limitations to the invention are presented in the following claims.