Sun Microsystems, Inc.

Oracle America, Inc.

Y Srinivas Ramakrishna

David L Detlefs

Antonios Printezis

Alexander T Garthwaite

Ole Agesen

Ross Charles Knippel

Derek R White

Alex Garthwaite

The present disclosure describes garbage collection that provides prompt reclamation of large objects. A heap space is divided into Young regions, Old regions, and Humongous regions. A remembered set is created and maintained, during the execution of one or more programs, for each region that specifies where there are references from outside the region to inside the region. A garbage collection list is generated specifying regions to perform garbage collection on. All Young regions and at least one Humongous region are included in the garbage collection list. If it is determined to include Old regions, the Old regions are selected and included in the garbage collection list. Then, a garbage collection is performed on the regions specified in the garbage collection list. During the garbage collection, the indication for each region is utilized to determine reachable objects in the region, ensuring that reachable objects are not deallocated.

Prompt large object reclamation

A garbage collector divides the garbage-collected heap into 'cards.' It maintains a table containing a card-object table entry for each card. A card's entry contains information from which the collector can determine where any references in the card are located and thereby identify objects that may be reachable. The encoding of a card's table entry is not restricted to values that indicate the location of the object in which the card begins. Instead, its possible values additionally include ones that indicate that the card begins with a certain number of references or that an object begins at a given location in the middle of the card. The collector thereby avoids consulting object's class information unnecessarily.

Method and mechanism for finding references in a card in time linear in the size of the card in a garbage-collected heap

An object structure's header (,) allocates a two-bit synchronization-state field (,) solely to monitor data for implementing synchronization on that object. When the object is locked by a particular execution thread, or when one or more execution threads are waiting for a lock or notification on that object, its header contains a pointer to monitor resources in the form of a linked list of lock records (,) associated with the threads involved. The synchronization-state field (,) ordinarily contains an indication of whether such a linked list exists and, if so, whether its first member is associated with a thread that has a lock on the object. When a thread attempts to gain access to that linked list, it employs an atomic swap operation to place a special busy value in that lock-state field (,) and write its execution-environment pointer into the object's header (,). If the previous value of that field was not the special busy value, the thread uses the header's previous contents to perform its intended synchronization operation. Otherwise, it obtains that information through its own execution environment (,, or,) or that of the thread whose identifier the object header previously contained. When the thread completes its synchronization operation, it employs an atomic compare-and-swap operation to write the results into the object's header if that header still contains the thread identifier that the thread originally wrote there. Otherwise, it communicates that information to its successor thread if the thread identifier is different and thereby indicates that at least one successor is contending for access to the linked list.

Busy-wait-free synchronization

Growing community of inventors

Union City, CA, United States of America

Y Srinivas Ramakrishna