|Publication number||US7594091 B2|
|Application number||US 12/126,177|
|Publication date||Sep 22, 2009|
|Filing date||May 23, 2008|
|Priority date||Nov 26, 2003|
|Also published as||US7380073, US20050114609, US20080222331|
|Publication number||12126177, 126177, US 7594091 B2, US 7594091B2, US-B2-7594091, US7594091 B2, US7594091B2|
|Inventors||Charles S. Shorb|
|Original Assignee||Sas Institute Inc.|
|Export Citation||BiBTeX, EndNote, RefMan|
|Patent Citations (29), Non-Patent Citations (5), Referenced by (4), Classifications (7), Legal Events (1)|
|External Links: USPTO, USPTO Assignment, Espacenet|
This application is a continuation of U.S. application Ser. No. 10/722,761, filed on Nov. 26, 2003 now U.S. Pat. No. 7,380,073, the entirety of which is incorporated herein by reference.
The present invention relates generally to computer-implemented accessing of resources and more particularly to lock handling in the accessing of resources.
In multi-threaded environments, threads compete against each other for resources. The resources which the threads wish to access may include a file, an I/O device, data stored in memory, etc. Current approaches to handling the accessing of resources tend to exhibit performance inefficiencies. For example, one approach includes using a mutex (mutual exclusion) algorithm for synchronizing multiple threads read and write access to shared resources. Once a mutex has been locked by a thread, other threads attempting to lock it will be blocked. When the locking thread unlocks (releases) the mutex, one of the blocked threads will acquire it and proceed. (See Programming with POSIX Threads, David R. Butelihof, Addison Wesley Longman, Inc., Copyright 1997, pages 241-253).
Another example involves use of a native operating system lock to protect the underlying lock data structure elements (See Programming with POSIX Threads, David R. Butenhof, pages 253-269). This approach uses a read and write wait queue to block waiting requests until it is safe to service the requests. Obtaining exclusive access to the internal data structure of the shared lock by first obtaining an exclusive lock is computationally expensive and thus performance suffers.
In accordance with the disclosure provided herein, systems and methods are provided for handling access to one or more resources. Executable entities that are running substantially concurrently provide access requests to an operating system (OS). One or more traps of the OS are avoided through use of lock state information stored in a shared locking mechanism. The shared locking mechanism indicates the overall state of the locking process, such as the number of processes waiting to retrieve data from a resource and/or whether a writer process is waiting to access the resource.
The shared locking mechanism 40 details where in the locking process the system 30 is. For example, the shared locking mechanism 40 may indicate the number of executable entities waiting to retrieve data from a resource 32. The lock state information stored by the mechanism 40 may also include whether an executable entity 34 wishes to update data associated with a resource 32. The mechanism's lock state information indicates when it is proper to grant access to a resource 32 and, in some situations, what type of access is to be performed.
The locking state information stored in the shared locking mechanism 40 allows the opportunity for one or more traps 38 of the computer's operating system to be avoided when a resource is to be accessed. Avoided traps include those interrupts provided by the operating system's kernel that involve mutex algorithms or other costly locking approaches when accessing requested resources. The capability to avoid relatively intensive operating system (OS) kernel traps increases performance. It should be understood that the shared locking mechanism 40 may decide to utilize the OS traps 38, and may use in certain situations a mutually exclusive locking technique provided by the operating system in order to provide access 42 to a resource 32. Still further, the system 30 may be used so as to avoid all or substantially all OS calls when accessing resources through the shared locking mechanism 40.
There are many types of environments within which an execution entity 34 may use a shared locking mechanism 40 to request and access a resource 32. As an example, these include multi-processing, multi-tasking, and multi-threaded environments. An execution entity 34 can include processes, threads, daemons, applets, servlets, ActiveX components, stand-alone applications, code that runs at the request of another program, etc.
To assist a shared locking mechanism 40 in determining how to handle thread requests, the lock state information 56 may contain a wide variety of information. As an example,
The shared locking mechanism 40 could use the lock state information 56 in combination with a rules mechanism 60. The rules mechanism 60 provides guidance as to how access to the resources 32 should proceed based upon the lock state information 56. Additionally, the rules mechanism 60 may be formulated to enhance performance. As an illustration, obtaining exclusive access to the internal data structure of a shared lock by first obtaining an exclusive lock via OS traps 38 is typically computationally expensive. The rules mechanism 60 may offer an improvement in performance by providing the following locking guidelines when a request is being processed:
The lock state information 56 may be used to indicate when lock-related events are to be posted by one thread in order to notify another thread that its request can be serviced. For example, the lock state information 56 may contain status information as to whether a reader thread can post a lock release event to a writer thread. This prevents multiple reader threads from creating redundant posting of lock release events. It is noted that for a writer pending state a lock release event involves notification that a thread has completed its access of a resource. A lock ready event involves notification to a waiting writer thread that it can proceed.
At step 106, the lock to the requested resource is acquired. The lock state information may be updated at this step to indicate that a read or write lock has been acquired. At step 108, the resource request is accessed based upon the analyzed lock state information. Step 110 releases the lock, and the lock state information may be updated to indicate that a read or write lock has been released. Processing for this iteration ends at end block 112.
A lock status data store 200 may use as many bits as desired to capture the locking state of the system. For example,
In the example shown in
In the lock status data store 200, the writer active bit 222 is set to indicate that a writer thread is currently active. This provides protection against reader threads posting an OS event after the writer thread has been activated. It is noted that an OS event is a signaling mechanism to notify one or more threads of an occurrence of a particular event (e.g., notification that a lock has been released).
The wait event posted bit 224 is set to indicate that a write request waits on a wait event to be posted before proceeding. The last active read operation will clear this bit prior to posting an event to ensure that one and only one post will occur; this posting will occur if the writer active bit is not set.
The remaining low order bits 230 are used for an active reader count in a normal 2's complement fashion. By tracking the reader count, the system knows whether readers are present and when the last reader exits. Any number of bits may be used for the reader count. In a 32 bit atomic integer, 29-bits are available for read requests, which allow for up to 536,870,912 read lock requests. It should be understood that the order of the bits provided in
It is noted that many techniques may be used with the lock status data store 200, such as implementing shared access locks using basic OS primitives for those OS implementations not having native shared locks. For those that do, use of a lock status data store 200 can show increased performance over the native implementation by, among other things, using hardware atomic operations on a single status atomic integer in place of a slower OS mutex locking of a status data structure.
In this example, the shared lock may include the following elements encapsulated in a structure forming the basis of a shared lock: a native OS lock, a native OS event, and a host specific entity allowing for atomic integer operations which maintains the lock status. The host specific atomic entity may be an integer, or two integers where one serves as a barrier to modification of the other (to allow for machine level instruction spin-lock implementations).
The implementation may utilize host-level atomic routines for manipulation of the atomic entity, such as: an atomic get operation, which returns the current integer value of the atomic entity (on most hosts this may be the value integer portion of the atomic entity); an atomic set operation, which attempts to perform a compare/exchange operation on the atomic, and allows for indication of success or failure of the operation; an atomic add operation, which adds a value to the current atomic entity value and returns the new value; and an atomic sub operation which is typically an atomic add operation with the addend being the negative of the input to the atomic sub operation.
If there is a pending or active write request as determined by decision step 304, the read request unregisters its lock status that was made in step 302. In other words, the process backs out of the increment. This is done at step 306 by following the procedure described in reference to
However if the lock status was not set as determined by decision step 506, then this indicates that the read count is non-zero (i.e., readers are present), and the lock OS wait event is cleared at step 508 in preparation for a possible wait for an event that indicates that the writer can proceed. The OS event may be associated with the threads themselves instead of the lock data structure. However, there may be certain situations wherein an OS event may be associated with the lock status. It should be understood that based upon the situation at hand an OS event may be associated with the lock data structure.
The write pending (i.e., write requested) and not-posted bits are set at step 510, such as by using an atomic add operation. The lock status reader count is again checked at step 512, and if the reader count is zero, the write request is safe to honor, and step 518 marks the writer active bit of the lock status. After step 518 finishes, the write lock is deemed acquired as shown at indicator 520.
If decision step 512 determines that the lock status read count is not equal to zero, then read requests are still outstanding, and the write request waits at stop 514 for a lock OS event. It is noted that waiting on the lock OS event at step 514 (on
After step 514, the writer active and not-posted bits are set in the lock status at step 516. The not-posted bit is set as an indicator that the lock OS event should not be waited upon when the write lock release occurs. After step 516 finishes, the write lock is deemed acquired as shown at indicator 520.
It is noted that the flow charts discussed herein may have more or less steps than what are disclosed herein in order to suit the situation at hand. For example in
While a single resource is shown in
While examples have been used to disclose the invention, including the best mode, and also to enable any person skilled in the art to make and use the invention, the patentable scope of the invention is defined by the claims, and may include other examples that occur to those skilled in the art. As an illustration, although the flow charts of
As yet another example of the many applications and extensions of the system,
It is noted that processes and/or threads that wish to access the resources may enter any number of states while waiting to access a resource. They may enter a hibernation/sleep state or if allowed, may continue executing until the resource becomes available. Still further, they may execute a spin loop and continue to request access to the resource until it is released.
It is further noted that the systems and methods disclosed herein may be implemented on various types of computer architectures, such as for example on a single general purpose computer or workstation, or on a network (e.g., local area network, wide area network, or internet), or in a client-server configuration, or in an application service provider configuration. As an illustration, the requesting processes may all reside locally on the same computer as the shared locking mechanism, or may be distributed on remote computers, or may reside both on a local computer as well as on one or more remote computers. As another example of the wide scope, different OS atomic operations may be utilized with the systems and methods, and the OS atomic operations may dictate the implementation of the lock status data structure (e.g., for some hosts the atomic nature of tracking requests in the lock status data structure may be implemented by a load/clear approach; in a load/clear architecture, the tracking of read/write status may be handled by a separate locking integer protecting the actual status information. Note: This architecture would not require ‘backing out changes’ as was shown in
The systems' and methods' data may be stored as one or more data structures in computer memory depending upon the application at hand. The systems and methods may be provided on many different types of computer readable media including instructions being executable by a computer to perform the system and method operations described herein.
The computer components, software modules, functions and data structures described herein may be connected directly or indirectly to each other in order to allow the flow of data needed for their operations. It is also noted that a software module may include but is not limited to being implemented as one or more sub-modules which may be located on the same or different computer. A module may be a unit of code that performs a software operation, and can be implemented for example as a subroutine unit of code, or as a software function unit of code, or as an object (as in an object-oriented paradigm), or as an applet, or as another type of computer code.
It should be understood that as used in the description herein and throughout the claims that follow, the meaning of “a,” “an,” and “the” includes plural reference unless the context clearly dictates otherwise. Finally, as used in the description herein and throughout the claims that follow, the meanings of “and” and “or” include both the conjunctive and disjunctive and may be used interchangeably unless the context clearly dictates otherwise; the phrase “exclusive or” may be used to indicate situation where only the disjunctive meaning may apply.
|Cited Patent||Filing date||Publication date||Applicant||Title|
|US4604694||Dec 14, 1983||Aug 5, 1986||International Business Machines Corporation||Shared and exclusive access control|
|US5860159||Jul 1, 1996||Jan 12, 1999||Sun Microsystems, Inc.||Multiprocessing system including an apparatus for optimizing spin--lock operations|
|US5933825||Jul 21, 1997||Aug 3, 1999||Apple Computer, Inc.||Arbitrating concurrent access to file system objects|
|US6016490||Jan 30, 1998||Jan 18, 2000||Fuji Xerox Co., Ltd.||Database management system|
|US6029190 *||Sep 24, 1997||Feb 22, 2000||Sony Corporation||Read lock and write lock management system based upon mutex and semaphore availability|
|US6112222||Aug 25, 1998||Aug 29, 2000||International Business Machines Corporation||Method for resource lock/unlock capability in multithreaded computer environment|
|US6247025||Sep 22, 1997||Jun 12, 2001||International Business Machines Corporation||Locking and unlocking mechanism for controlling concurrent access to objects|
|US6343339||Oct 20, 2000||Jan 29, 2002||Sun Microsystems, Inc.||Method and apparatus that utilizes state locks to lock resources|
|US6480918||Dec 22, 1998||Nov 12, 2002||International Business Machines Corporation||Lingering locks with fairness control for multi-node computer systems|
|US6546443||Dec 15, 1999||Apr 8, 2003||Microsoft Corporation||Concurrency-safe reader-writer lock with time out support|
|US6598068||Jan 4, 1996||Jul 22, 2003||Sun Microsystems, Inc.||Method and apparatus for automatically managing concurrent access to a shared resource in a multi-threaded programming environment|
|US6691194||Nov 28, 2000||Feb 10, 2004||Emc Corporation||Selective association of lock override procedures with queued multimodal lock|
|US6718448||Nov 28, 2000||Apr 6, 2004||Emc Corporation||Queued locking of a shared resource using multimodal lock types|
|US6836887||Dec 21, 1998||Dec 28, 2004||Microsoft Corporation||Recyclable locking for multi-threaded computing environments|
|US6883026||Aug 20, 1999||Apr 19, 2005||International Business Machines Corporation||Method and apparatus for managing locks of objects and method and apparatus for unlocking objects|
|US7080375||Dec 30, 2000||Jul 18, 2006||Emc Corporation/Data General||Parallel dispatch wait signaling method, method for reducing contention of highly contended dispatcher lock, and related operating systems, multiprocessor computer systems and products|
|US7155588||Aug 12, 2002||Dec 26, 2006||Cisco Technology, Inc.||Memory fence with background lock release|
|US7376744||May 9, 2003||May 20, 2008||Oracle International Corporation||Using local locks for global synchronization in multi-node systems|
|US7380073 *||Nov 26, 2003||May 27, 2008||Sas Institute Inc.||Computer-implemented system and method for lock handling|
|US7444634||Oct 31, 2002||Oct 28, 2008||Sun Microsystems, Inc.||Method and apparatus for providing dynamic locks for global resources|
|US20030126187||Jun 25, 2002||Jul 3, 2003||Won Hee Sun||Apparatus and method for synchronization in a multi-thread system of JAVA virtual machine|
|US20030200398||Apr 17, 2002||Oct 23, 2003||International Business Machines Corporation||Method and apparatus for emulating shared memory in a storage controller|
|US20030233393||Jun 14, 2002||Dec 18, 2003||Xiao-Feng Li||Thread optimization for lock and unlock operations in a multi-thread environment|
|US20040059733||Sep 24, 2002||Mar 25, 2004||Xiaofeng Li||Methods and apparatus for locking objects in a multi-threaded environment|
|US20040117531||Dec 9, 2003||Jun 17, 2004||Mckenney Paul E.||Adaptive reader-writer lock|
|US20060130062||Dec 14, 2004||Jun 15, 2006||International Business Machines Corporation||Scheduling threads in a multi-threaded computer|
|US20070113233||Nov 10, 2005||May 17, 2007||Collard Jean-Francois C P||Program thread synchronization|
|US20070234326||Mar 31, 2006||Oct 4, 2007||Arun Kejariwal||Fast lock-free post-wait synchronization for exploiting parallelism on multi-core processors|
|US20070271450||May 17, 2006||Nov 22, 2007||Doshi Kshitij A||Method and system for enhanced thread synchronization and coordination|
|1||Butenhof, David R., "Programming with POSIX Threads", Addison-Wesley Professional Computing Series, Chapter 7, pp. 241-269 [Oct. 1997].|
|2||Deitel, Harvey M., "An Introduction to Operating Systems", Chapter 5, pp. 112-151 [Feb. 1990].|
|3||Glasser, Daniel, "Efficient Synchronization Techniques for Multithreaded Win32(R)-based Applications", Microsoft Systems Journal, vol. 10, No. 2, pp. 61-81 [Feb. 1995].|
|4||Schimmel, Curt, "UNIX(R) Systems for Modern Architectures:Symmetric Multiprocessing and Caching for Kernel Programmers", Addison-Wesley Publishing Company, pp. 154-169, Jun. 15, 1994.|
|5||Stallings, William Ph.D., "Operating Systems: Internals and Design Principles", 4th Edition, Prentice Hall, pp. 212-216, 2001.|
|Citing Patent||Filing date||Publication date||Applicant||Title|
|US8572617||Jul 21, 2009||Oct 29, 2013||Sas Institute Inc.||Processor-implemented systems and methods for event handling|
|US9213586||Mar 18, 2009||Dec 15, 2015||Sas Institute Inc.||Computer-implemented systems for resource level locking without resource level locks|
|US20100242043 *||Mar 18, 2009||Sep 23, 2010||Charles Scott Shorb||Computer-Implemented Systems For Resource Level Locking Without Resource Level Locks|
|US20110023032 *||Jul 21, 2009||Jan 27, 2011||Charles Scott Shorb||Processor-Implemented Systems And Methods For Event Handling|
|U.S. Classification||711/200, 711/152|
|International Classification||G06F12/00, G06F13/28, G06F13/00|