Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-02-08
2004-12-07
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S170000, C707S793000
Reexamination Certificate
active
06829686
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and apparatus for bag-to-set, buffering remembered set.
Sun, Sun Microsystems, the Sun logo, Solaris and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
2. Background Art
A “remembered set” is a set of objects that are represented in computer software. Normally the objects in the remembered set are objects that have been updated during a given time interval. Write barriers often are used to determine which objects belong in the remembered set. Before further discussing write barriers and their application to remembered sets, an overview of objects and object oriented programming is helpful.
Object-Oriented Programming
Object-oriented programming is a method of creating computer programs by combining certain fundamental building blocks, and creating relationships among and between the building blocks. The building blocks in object-oriented programming systems are called “objects.” An object is a programming unit that groups together a data structure (one or more instance variables) and the operations (methods) that can use or affect that data. Thus, an object consists of data and one or more operations or procedures that can be performed on that data. The joining of data and operations into a unitary building block is called “encapsulation.”
An object can be instructed to perform one of its methods when it receives a “message.” A message is a command or instruction sent to the object to execute a certain method. A message consists of a method selection (e.g., method name) and a plurality of arguments. A message tells the receiving object what operations to perform.
One advantage of object-oriented programming is the way in which methods are invoked. When a message is sent to an object, it is not necessary for the message to instruct the object how to perform a certain method. It is only necessary to request that the object execute the method. This greatly simplifies program development.
Object-oriented programming languages are predominantly based on a “class” scheme. The class-based object-oriented programming scheme is generally described in Lieberman, “Using Prototypical Objects to Implement Shared Behavior in Object-Oriented Systems,” OOPSLA 86 Proceedings, September 1986, pp. 214-223.
A class defines a type of object that typically includes both variables and methods for the class. An object class is used to create a particular instance of an object. An instance of an object class includes the variables and methods defined for the class. Multiple instances of the same class can be created from an object class. Each instance that is created from the object class is the to be of the same type or class.
To illustrate, an employee object class can include “name” and “salary” instance variables and a “set.sub.-salary” method. Instances of the employee object class can be created, or instantiated for each employee in an organization. Each object instance is the to be of type “employee.” Each employee object instance includes “name” and “salary” instance variables and the “set.sub.-salary” method. The values associated with the “name” and “salary” variables in each employee object instance contain the name and salary of an employee in the organization. A message can be sent to an employee's employee object instance to invoke the “set.sub.-salary” method to modify the employee's salary (i.e., the value associated with the “salary” variable in the employee's employee object).
A hierarchy of classes can be defined such that an object class definition has one or more subclasses. A subclass inherits its parent's (and grandparent's etc.) definition. The parent class is also referred to as a “superclass.” Each subclass in the hierarchy may add to or modify the behavior specified by its parent class. Some object-oriented programming languages support multiple inheritance where a subclass may inherit a class definition from more than one parent class. Other programming languages, such as the Java programming language, support only single inheritance, where a subclass is limited to inheriting the class definition of only one parent class. The Java programming language also provides a mechanism known as an “interface” which comprises a set of constant and abstract method declarations. An object class can implement the abstract methods defined in an interface.
An object is a generic term that is used in the object-oriented programming environment to refer to a module that contains related code and variables. A software application can be written using an object-oriented programming language whereby the program's functionality is implemented using objects. As previously discussed, the encapsulation provided by objects in an object-oriented programming environment may be extended to the notion of components under a component model definition.
Write Barriers
Write barriers are inserted into computer programs so that the program can keep track of and/or trigger reactions when data items of interest are modified. Pages, objects, records, arrays, fields, array elements, documents, and paragraphs provide a few examples of data items that may be of interest when implementing a write barrier.
One application of a write barrier is for the tracking of inter-generational pointers in a garbage collector. A pointer is a memory address that indicates where data can be found. Garbage collection is a part of a language's runtime system, or an add-on library, perhaps assisted by the compiler, the hardware, the operating system, or any combination of the three, that automatically determines what memory a program is no longer using, and recycles it for other use.
Often it is advantageous in garbage collection to know which pointers point from one generation to another (i.e., inter-generational pointers), or which pointers point from one area of memory to another area of memory. To find such pointers, one current scheme determines which pointers are already inter-generational. Then, when an object is updated, the garbage collector will only look at the inter-generational pointers to determine if they have been changed rather than looking at every pointer.
Another use of a write barrier is in the tracking of cache-resident objects in persistent object caching. In general, caches are implemented under the assumption that it is very likely that some object or piece of data will be repeatedly accessed. Access delays are minimized by keeping popular data close to the entity which needs it. Persistent objects are forms of data that continue to exist, even after the process that created them has stopped executing. When an executing process is using a persistent object there is a benefit to caching such an object, namely, the object can be accessed in memory rather than on disk and a memory access is quicker than a disk access.
In a garbage collector or a persistent object cache, all updates are recorded in the remembered set. Remembered sets are typically implemented using either a “store buffer” technique or a “card marking” technique.
Store Buffers
A store buffer is a stack of pointers to one or more updated entities. A store buffer can be a “bag” or a “set”. Updated entities are added to a bag immediately and every time an object is updated. Hence, a store buffer in the form of a bag may contain a plurality of duplicate entries for the same object as it is updated over time.
To be more efficient, some current schemes represent the remembered set with no duplicate entries. Using this approach, the remembered set is a true set and not a bag. To implement a store buffer in the form of a true set, objects are given a “dirty mark” when added to the set. Then, if the
Knippel Ross C.
Mathiske Bernd J. W.
Bragdon Reginald G.
Osha & May L.L.P.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for bag-to-set, buffering remembered set does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for bag-to-set, buffering remembered set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for bag-to-set, buffering remembered set will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310110