Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-08-22
2002-02-05
Maung, Zarni (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06345313
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to techniques for synchronizing objects with threads of execution, in particular, to techniques used to manage the dynamic associations between objects and data structures used to synchronize the objects.
BACKGROUND OF THE INVENTION
Multithreading environments allow different parts of a process, known as threads, to execute concurrently. Multithreading processes may be carefully designed so that multiple threads can execute concurrently without interfering with each other unnecessarily.
In multiprocessor computer systems, threads may run in parallel on the processors that form the multiprocessor computer system. Moreover, if a program can be broken down into constituent threads, such computer systems can run the program more quickly since concurrently running threads of the same program may execute in parallel. Single processor, multitasking computer systems can also execute multiple threads of execution virtually simultaneously through the use of various resource scheduling mechanisms well known to those skilled in the art.
When multithreading programs are object-oriented, each thread of a program may independently invoke methods of objects. However, because of software constraints in the program or hardware constraints in the computer system, only a predefined number of threads may be allowed to invoke the methods of any given object at one time.
For example, an object may contain a method that accesses a shared computer resource, such as an I/O device, that can only handle one access at a time. Since concurrently running threads may concurrently seek to invoke that method of the object, access to that method of the object must be restricted to one thread at a time. When execution of a method is restricted in this manner, the object of which this method is a member is said to be “synchronized” with the thread that currently has access to the method.
In the past, various approaches have been used to synchronize an object with a thread. These include the use of synchronization constructs like mutexes, monitors, and semaphores. One approach for the management of synchronization constructs, the dynamic-association approach, is described in U.S. patent application Ser. No. 08/569,805, entitled “OBJECT SYNCHRONIZATION MODULE AND METHOD WITH REDUCED MEMORY REQUIREMENTS”, filed by Timothy G. Lindholm and Jonathan Payne on Dec. 8, 1995.
In the dynamic-association approach, synchronization constructs are associated with and disassociated with objects as needed. For example, during run-time, a thread may invoke a method of an object that requires synchronization. A synchronization construct is associated with the object if a synchronization construct is not already associated with the object. When the thread exits the method that required synchronization of the thread with the object, and there are no other threads currently requiring synchronization with the object, the synchronization construct is disassociated with the object.
Synchronization constructs are stored in a data structure referred to as synchronization construct cache. Managing the association of these synchronization constructs with objects involves the use of other data structures which are also part of, or associated with, the synchronization construct cache. A hash table links an object to its associated synchronization construct. A free list contains entries identifying the synchronization constructs that are not currently associated with any object.
Associating a synchronization construct with an object entails operations which update the synchronization construct and the synchronization construct cache. These operations include, for example, updating the synchronization construct with information linking the synchronization construct to the object, creating an entry in the hash table linking the object to the synchronization construct, and removing the synchronization construct from the free list. Likewise, terminating the association of a synchronization construct with an object includes operations such as removing an entry in the hash table linking the object to the synchronization construct, and adding the synchronization construct to the free list.
It is very common in multitasking computer systems for one or more threads to repeatedly invoke a method of the same object. When a repeatedly invoked method of an object requires synchronization, the operations involved in the association and disassociation of the synchronization construct with the object are likewise repeated. The repeated performance of the operations involved in associating and terminating the association of a synchronization construct with an object can create an undesirable amount of overhead that adversely impacts overall computer system performance.
The operations involved in associating and terminating the association of synclronization constructs perform updates to data structures (i.e. the hash table, synchronization construct, and free list) in the synchronization construct cache. Because the synchronization construct cache is shared by all threads, the data structure representing the synchronization construct cache is a global data structure. A reference or an update to a data structure in the synchronization construct cache may require a lock of the global data structure representing the synchronization construct cache to prevent interference to and from other concurrently executing threads that may also desire to update the data structure. A lock of a global data structure is herein referred to as a global lock. Because the synchronization construct cache is a global data structure, it may be referred to as the global synchronization construct cache.
A thread contending for a data structure globally locked by another thread is delayed until the other thread releases its global lock. Delays such as this one, which are caused by one thread contending for a data structure locked by another thread, are herein referred to as contention delays.
As threads executing in a computer system increase the number of operations performing updates on global data structures, or the number of threads increases, contention delays can often increase to undesirable levels. Thus frequently repeated associations and termination of associations of synchronization constructs, which involve operations performing updates on data structures in the global synchronization construct cache, can cause contention delays to reach undesirable levels.
Based on the foregoing, it clearly desirable to reduce the amount of overhead caused by frequently repeated associations and termination of associations of synchronization constructs. It is further desirable to reduce contention delays caused by frequently repeated associations and termination of associations of synchronization constructs with objects.
SUMMARY OF THE INVENTION
A method and apparatus for managing the association of objects with synchronization constructs used to synchronize those objects is provided. According to one aspect of the invention, a cache of synchronization constructs is provided. Synchronization constructs are used to synchronize objects with threads. When a thread requests synchronization with an object, a determination is made of whether a synchronization construct is already associated with the object. If a synchronization construct is already associated with the object, then that synchronization construct is used to synchronize the object with the thread. After association of a synchronization construct with an object, the association is maintained even when the synchronization construct meets criteria for terminating the association with object.
According to another aspect of the invention, a determination is made of whether a collection enabling condition exists. If a collection enabling condition exists, the association between objects and synchronization constructs is terminated for synchronization constructs meeting criteria for terminating the association between a synchronization construct and an object.
According to anoth
Maung Zarni
McDermott & Will & Emery
Sun Microsystems Inc.
LandOfFree
Recovery of synchronization constructs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Recovery of synchronization constructs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recovery of synchronization constructs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2968229