Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-08-11
2004-08-03
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06772153
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to digital data processing systems and methods and, in particular, relates to digital data processing systems having objects that can be locked and unlocked, and shared or not shared, by an executing thread.
BACKGROUND OF THE INVENTION
Computer programs with more than one active thread of execution must control access to shared resources to ensure correctness. In order to accomplish this many programming languages and libraries provide resource locks and monitors, such as software mechanisms that control concurrent access to critical sections of code.
Previous implementations of locks and monitors rely on atomic operations, such as read/modify/write operations, that are supported by the underlying hardware. In this case synchronization primitives are typically required to arbitrate between simultaneous attempts to lock an object. However, due to the required synchronization operations, it is expensive to support atomic operations, even in systems (such as those running the Java™ language) where many objects may not be shared or locked by multiple threads. As system clock speeds continue to increase, these synchronization operations will become relatively even more expensive.
OBJECTS AND ADVANTAGES OF THE INVENTION
It is a first object and advantage of this invention to provide an improved object locking mechanism that does not require the use of atomic operations for objects that are not shared.
It is another object and advantage of the teachings herein to enable a thread to acquire and release a lock without using atomic operations, wherein threads communicate using a message passing technique whereby a first thread sends a message to a second thread requesting permission to acquire a lock owned by the second thread, and where the second thread that owns the lock changes the state of the lock such that future lock/unlock operations use atomic operations that support object sharing.
SUMMARY OF THE INVENTION
The foregoing and other problems are overcome and the objects of the invention are realized by methods and apparatus in accordance with embodiments of this invention.
The teachings of this invention provide a simple and straightforward technique to identify a thread that is likely to be the only thread to lock an object, and to avoid synchronization operations on such objects until they are actually known to have been locked by more than one thread.
The teachings of this invention provide a technique to implement a locking mechanism for non-shared objects that does not require the use of atomic operations and related synchronization primitives. For programs where non-shared objects are common, the teachings of this invention serve to improve performance as compared to conventional resource locking mechanisms, wherein all objects, whether shared or non-shared, are locked using atomic operations.
In accordance with the teachings found herein, a lock is implemented by assigning the lock to the thread that creates the associated object. The “owning thread” can thereafter acquire and release the lock without requiring any atomic operations and/or the use of expensive synchronization primitives. If another thread attempts to acquire the lock, the non-owning thread sends a message to the owning thread, requesting permission to acquire the lock. At some point, the owning thread receives the message from the non-owning thread and changes the state of the lock such that future lock/unlock operations use atomic, system locking operations that support object sharing.
The use of this technique improves performance for programs where most objects are not shared, since for these objects, no atomic operations are necessary.
REFERENCES:
patent: 4104718 (1978-08-01), Poublan et al.
patent: 5907675 (1999-05-01), Aahlad
patent: 5918229 (1999-06-01), Davis et al.
patent: 5931919 (1999-08-01), Thomas et al.
patent: 5996032 (1999-11-01), Baker
patent: 6023700 (2000-02-01), Owens et al.
patent: 6314563 (2001-11-01), Agesen et al.
patent: 6389452 (2002-05-01), Glass
patent: 6415334 (2002-07-01), Kanamori
patent: 6473820 (2002-10-01), Zhang
Bacon et al.,Thin Locks: Featherweight Synchronization For Java, ACM Conference on Programming Language Design and Implementation (Montreal, Canada), SIGPLAN Notices vol. 33, No. 6, Jun. 1998.
Bacon David F.
Fink Stephen
August Casey P.
Dodds, Jr. Harold E.
International Business Machines - Corporation
Ohlandt Greeley Ruggiero & Perle L.L.P.
Robinson Greta
LandOfFree
Method and apparatus to provide concurrency control over... 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 to provide concurrency control over..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to provide concurrency control over... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3322638