Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-09-16
2003-07-15
Banankhah, Majid (Department: 2127)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C711S145000
Reexamination Certificate
active
06594683
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of locking data structures in a multi-threaded computing environment. Specifically, this invention is a method, apparatus, and computer program product for locking interrelated groups of data structures in a multi-threaded computing environment.
2. Background
Data structures contain organized information in a computer's memory. Each of these data structures can be independent or interrelated to other data structures. Access to the data structures is simple when the access occurs in a computing environment that has a single flow of execution (thread-of-execution) because the data in the interrelated data structures is always consistent during the execution of the single thread. However, if an asynchronous operation occurs (such as an interrupt, process context switch or similar operation that allows for concurrent access to the data structure) the contents of the data structure may be made inconsistent if an asynchronous operation changes the data structure while another operation is accessing the data structure. Modern computing systems often use threads-of-execution to parallelize computer operations.
A thread-of-execution (a thread) is a sequence of control within a programmed-process. A traditional single-threaded programmed-process follows a single sequence-of-control while executing. A multithreaded programmed-process has several sequences of control, and is capable of several independent actions. A particular implementation of a multi-threaded computing environment is discussed in
SunOS Multi
-
thread Architecture,
by Powell, Kleiman, Barton, Shah, Stein and Weeks, USENIX, Winter 1991, page 65. Posix® threads are described in
Programming with POSIX Threads,
by David R. Butenhof, © 1997 by Addison Wesley Longman, Inc., ISBN 0-201-63392-2, pages 35-95.
The subsequently disclosed invention is described within the context of an object-oriented programming (OOP) paradigm. The OOP paradigm uses objects. Objects associate an object's data with OOP methods for operating on that object's data. Usually, OOP objects are instantiated in a heap memory area and are based on classes that reference the programmed methods for the OOP object. Instantiated OOP objects are accessed through pointers and contain data (in instance variables) specific to that particular instantiated OOP object. Conceptually, an OOP object contains object-related information (such as the number of instance variables in the object), data structures for storing the object's instance variables, and addresses of called-routines (OOP methods) that access and/or manipulate the contents of the instance variables in the object. However, because objects often share called-routines and object-related information, this shared information is usually extracted into a class. Thus, the instantiated object simply contains its instance variables and a pointer to its class. Further information about OOP concepts may be found in
Not Just Java
by Peter van der Linden, Sun Microsystems Press/Prentice Hall PTR Corp., Upper Saddle River, N.J., (1997), ISBN 0-13-864638-4, pages 136-149.
Data structures also can be treated as objects within the OOP paradigm. Such data structure objects include the instantiated data that make up the data structure, programmed methods to access this data and potentially links to other data structure objects.
A useful data structure for image processing purposes (and many other purposes) is a modified directed acyclic graph (DAG) that represents images and the operations applied to these images. The DAG elements can be represented as objects. One or more DAGs can be constructed by an imaging library as the library captures a series of imaging operations directed to one or more source images. The resulting DAGs are contained within an object collection. The object collection generally contains both independent and interrelated DAG objects. Independent objects are those that do not depend on other objects. Interrelated objects access each other to perform their operation. An independent object can be locked by a thread to assure exclusive access to the thread. However, to lock an interrelated object, each interrelated object must also be locked to assure that the information in the object is not changed by a second thread while a first thread is processing
One prior art approach to locking objects uses a mutex to serialize thread access to the object collection. The difficulty with this approach is that while one thread processes objects in the object collection other threads cannot. Thus, independent operations, controlled by threads, that need to access an object in the object collection cannot make the access until the locking thread releases the object collection. This approach limits the advantages of a multi-threaded computing environment by making the object collection a blocking resource.
Another prior art approach assigns a mutex (generally within a control object) to serialize access to each group of objects that may be interrelated in the object collection. Thus, the object collection may have multiple control-objects each controlling access to an independent group of the object collection where each group contains objects that may be interdependent. The difficulty with this prior art approach is that the control-object is used to control access to a group of objects that are believed to be interrelated but often are not actually interrelated. This means that the control-objects are over inclusive and lock more than the required objects. This results in increased thread blocking and thus reduced performance.
It would be advantageous to monitor which objects in the object collection are actually interrelated and thus use each control object to limit access to the minimal group of the interrelated objects.
SUMMARY OF THE INVENTION
The present invention improves the performance of a multi-threaded computer application that uses groups of interrelated data structures containing values that must be exclusively accessed by a thread. The invention monitors interrelationships between the data structures and provides mechanisms to lock the minimal set of data structures needed for the exclusive thread access. The invention only locks interrelated data structures comprising a group while leaving independent data structures or unrelated groups of data structures unlocked and available to other threads. Because the group contains a minimal set of interrelated data structures, when the group is locked other threads are less likely to be blocked by the lock. Thus, these other threads are more likely to be able to simultaneously process data structures in other groups.
One aspect of the invention is a computer controlled method for locking an object-of-interest in an object collection without keeping a non-interrelated object locked. The object collection is accessed by one or more threads in a multi-threaded computing environment. A group lock controls thread access to a respective group of interrelated objects containing the object-of-interest. The method includes the step of associating a reference lock with the object collection to control thread access to a plurality of group lock linkages used by the group lock. The method also includes the step of modifying the plurality of group lock linkages responsive to a change of relationship between a first object within the respective group of interrelated objects with a second object. An additional method step is of locking the respective group of interrelated objects, containing the object-of-interest. Thus, this step locks the object-of-interest and its interrelated objects.
Another aspect of the invention is an apparatus, having a central processing unit (CPU) and a memory coupled to said CPU, for locking an object-of-interest in an object collection without keeping a non-interrelated object locked. The object collection is accessed by one or more threads in a multi-threaded computing environment. A group lock controls thread access to a respect
Furlani John L.
Ohlson Alexander R.
Banankhah Majid
Sun Microsystems Inc.
LandOfFree
Method, apparatus and computer program product for locking... 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, apparatus and computer program product for locking..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus and computer program product for locking... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3078934