Access to a shareable resource between threads is controlled by a lock having shared, optimistic and exclusive modes and maintaining a list of threads requesting ownership of said lock. A shared optimistic mode is provided. A lock state descriptor is provided for each desired change of mode comprising a current mode in which a thread has already acquired the lock. When a thread acquires the lock in shared optimistic mode, other threads are allowed to acquire the lock in shared or optimistic mode. When a thread which acquired the lock in shared optimistic mode wants to acquire the lock in exclusive mode, other threads which have acquired the lock in shared or optimistic mode are prevented from acquiring the lock in exclusive mode until the thread which acquired the lock in shared optimistic mode and requested to acquire the lock in exclusive mode releases the lock.

BACKGROUND

The present invention relates to read-write lock algorithms, and more specifically to optimizing usage of such locks.

Within the class of passive locking algorithms there is a set known as recursive locks, otherwise known as reentrant or relockable locks. Recursive, reentrant and relockable locks are slightly different in the type of problem they try to address, but the most used implementation, relockable mutexes, addresses all three types of scenarios.

Non-reentrant locks can only be acquired once, meaning that if a process or thread tries to acquire a lock it already owns, it will stall waiting on itself. However, recursive locks can be acquired multiple times by the owner, the lock being relinquished when the owner releases the lock the same number of times it had previously acquired it. The usual implementation of recursive locks adds a lock counter (and a lock owner) to the lock structure, with the lock being available if the counter is zero, and busy otherwise.

Proponents of recursive locks highlight flexibility as their best feature. By just switching to recursive locks, an algorithm dealing with recursive structures or, for Object Oriented languages, derived classes, can easily be switched to being multithreaded without any other change. Asynchronous routines that deal with a shared structure can be executed without fear of deadlock due to the interrupted thread already owning the lock controlling the resources, and software functions manipulating a specific resource can be implemented to be called both in the case where the lock is already owned by the caller and the case where it is not, which greatly helps in terms of code reuse and maintainability. Conversely, opponents of recursive locks highlight a substantial performance penalty compared to non recursive locks and obfuscating interaction between participant threads, possibly hiding unintended or unforeseen behavior.

Read-write locks are a class of locks which allow multiple threads to access a controlled structure in read mode concurrently. Modification of the structure entails acquiring the lock in an exclusive mode. Read-write locks offer clear concurrency advantages over non-shared types of locks in environments where structures are modified seldom but accessed very frequently.

Relockable mutexes have a lock count and a mutex owner in order to be able to track the number of times the owner has acquired the lock and avoid self stalls. In a similar way, read-write locks have a reader count, so that a prospective exclusive locker has to wait for the reader count to revert to zero before it is allowed to acquire the lock. In order to promote fairness, while there are waiters in the lock queue, new readers will be made to wait even if readers are already accessing the controlled resource, so that writers have a chance to modify the shared resource in a timely manner.

Since, for performance and space reasons, readers are only tracked in number and not in identity, the logical step of first acquiring the read-write lock in shared mode and then recursively promote it to exclusive, rather than having the intended effect, will in fact produce a self stall.

Prior art relockable read-write mutexes offer no advantage over plain read-write locks mutexes in this respect. Keeping track of the number of exclusive locks by the same thread plus keeping track of the number of shared lockers, means that relockable mutexes will self stall when recursively mixing shared and exclusive lock attempts, in whatever order they happen.

Consider now the following scenario: a large concurrent application uses a complex shareable resource which exists as a single entity, but can be divided into subcomponents or portions, each of which can be modified individually, but cannot exist on its own. A real world scenario is a dictionary cache for a server. Industrial strength SQL servers, for instance, comprise, among others, a dictionary cache of tables, so that information about individual tables does not have to be accessed from disk every time a statement is parsed.

Individual cache entries comprise several parts, such as table name and owner, columns and types, indexes, check constraints and referential constraints. Some of the parts will make references to other entries, or entries in different dictionary caches, for example, referential constraints will point to dependent tables, or, in extensible SQL engines, column types may point to a user defined types dictionary cache. In terms of code reusability, it makes sense to have individual functions each dealing with individual parts, for instance one function to load table information, one for columns, one for indexes, one for constraints and the like.

When loading information about a table previously missing from the cache, since the entry information has no meaning until all the individual parts are available, a wrapper function would call in turn all the functions dealing with each individual parts and once successful push the new entry into the cache.

When new indexes are created, or dropped, only the function dealing with indexes needs to be called, but this time with the whole cache entry locked (the information still has no meaning until the new index information is updated).

When preparing a new statement, information about tables referenced by foreign key constraints needs to be checked, because the primary key table might have changed, its dictionary cache entry might be stale and referential constraints information would then need to be reloaded. This activity does not require an exclusive lock. It is only necessary to make sure that the current entry does not change when performing the check, which can be done with a shared lock, an exclusive lock only being needed if the constraint information is found to be stale and needs to be reloaded. Since during normal operation no changes would be expected in any table cache entry, being unable to perform such checks in parallel can constitute a serious performance bottleneck, depending on engine load and the popularity among statements of the table itself.

With current locking technology, there are several options. With plain locks, either code is duplicated, such as to handle a new table entry, and individual parts, when they are individually modified, or infrastructure is needed to pass the lock state in between wrapper and inner functions. Since the entry lock can only be acquired in exclusive mode, only one thread can check each individual entry for stale referential constraints information. This means that parsing statements using the same table is serialized.

With recursive locks, code reutilization is fine, albeit with a (possibly small) performance penalty. As the complexity of the code grows, the interaction between nested locks might become obfuscated, making code maintenance more complex. In time, having a single code line might become more complex than maintaining two specialized copies of the same code. Referential constraint information checking is still serialized.

With read-write locks, the same code reutilization problem exists as with plain locks. Contrary to expectations, a referential constraint checking operation in this example cannot be easily parallelized. Assume for a moment that the checking itself is done using shared locks. When the referenced table dictionary entry is found to be stale, meaning that the referential constraint needs to be reloaded, the lock will then have to be promoted to exclusive by releasing it and reacquiring it in exclusive mode. However once the lock has been promoted, there is no guarantee that the structure being checked has not changed, since other threads could have acquired the lock in exclusive mode and modified the structure during our wait for the lock promotion.

This means that after having promoted the lock, the shared resource must be checked again for changes and restart possibly from the beginning of the outer wrapper function. This may not seem like a major drawback, but when many threads are checking the structure concurrently and all find it out of date, all will have to promote the lock and recheck the structure with the lock held in exclusive mode, which means that any change detected by more than one thread at the same time will result in many serialized rechecks, leading to a substantial bottleneck on the lock. Given the complexity of this operation, many times an easier choice is to just acquire the lock in exclusive mode from the beginning, again giving up on parallelism.

The most desirable option would, of course, be a lock that allows both code reutilization and parallel operation during structure validation.

Java class “ReentrantReadWriteLock”, the details of which can be found at http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/.

ReentrantReadWriteLock.html discloses a simple implementation of a read write lock that can be locked multiple times and that can be promoted from read to write. It does not allow multiple readers to check a structure in parallel, and on detecting a change, avoid a thundering herd of lock promoters all trying to amend the structure in the same way and at the same time. A reader of the lock can only upgrade the lock to write mode if it is the only reader around, which can lead to stalls.

BRIEF SUMMARY

According to an embodiment of the invention, a computer-implemented method for managing access to a shareable resource between a plurality of concurrently executing threads, access to the shareable resource being controlled by a lock, the lock being adapted to be accessed by one or more of the plurality of concurrently executing threads in at least a shared mode, an optimistic mode and an exclusive mode and the lock maintaining a list of threads requesting ownership of the lock, the method comprises: providing a shared optimistic mode for the lock, the lock being acquirable in the shared optimistic mode by one or more of the plurality of concurrently executing threads; providing, for each change of mode desired by one of the concurrently executing threads, a lock state descriptor, the lock state descriptor comprising an indication of the current mode, if any, in which the one of the concurrently executing threads has already acquired the lock; responsive to the one or more of the concurrently executing threads acquiring the lock in the shared optimistic mode, allowing others of the one or more concurrent threads to acquire the lock in the shared mode or the optimistic mode; and responsive to the one or more of the concurrently executing threads which has acquired the lock in the shared optimistic mode requesting to acquire the lock in the exclusive mode, preventing others of the one or more of the concurrently executing threads which have acquired the lock in the shared mode or the optimistic mode from acquiring the lock in the exclusive mode until the one or more of the concurrently executing threads which has acquired the lock in the shared optimistic mode requesting to acquire the lock in the exclusive mode releases the lock.

This embodiment provides the advantage of having threads flag a possible intent of modifying a portion of a shareable resource before checking it and when the portion is found to be needing a refresh, rather than switching a plurality of readers to a trickle of writers, repeatedly updating the portion one at a time, only a first thread promotes the lock to exclusive and modifies the portion. At this point, all other threads that found the portion to be wanting check again, in parallel, that the refresh done by the exclusive locker is up to date, thus avoiding both subsequent needless modifications to the portion and a substantial bottleneck on the lock caused by all the other threads acquiring the lock in an exclusive modes for a fairly long period of time.

In an embodiment, the lock state descriptor comprises an indication of the current relationship between the lock and the one of the concurrently executing threads.

In an embodiment, each request for a change of mode to the optimistic mode comprises an identifier identifying a portion of the shareable resource that the requestor making the request wishes to access. This embodiment has the advantage that the current lock owner, on releasing the lock, wakes up only those requesters who that use the same identifier, rather than waking up the optimistic lock promoters. This releases just threads waiting on the portion of the shareable resource, but not threads waiting on other portions, thereby avoiding further contention.

In an embodiment, each lock state descriptor further comprises a count of the number of attempts to access the lock in the shared optimistic mode, the one of the concurrently executing threads attempting to access the lock in the shared optimistic mode having its attempt to access the lock terminated when the count reaches a predetermined value. This embodiment has the advantage of avoiding infinite loops of a thread being asked to retry checking in optimistic mode.

In an embodiment, responsive to the one or more of the concurrently executing threads releasing the lock from the exclusive mode; updating a current mode or a requested mode in the lock state descriptor as being “amended” in order to indicate that a lock promoter from the optimistic mode to the exclusive mode was successful in altering the shareable resource being controlled by the lock; updating the current mode or the requested mode in the lock state descriptor as being “preserved” in order to indicate that the lock promoter from the optimistic mode to the exclusive mode did not make a change to the structure or the requested mode; and updating the current mode or the requested mode in the lock state descriptor as being “failed” in order to indicate that the lock promoter from the optimistic mode to the exclusive mode was unsuccessful in altering the shareable resource being controlled by the lock.

In an embodiment, the lock state descriptor further comprises an indication as to whether, on resuming a lower lock state from a higher lock state, the lock state should be reset to that of the lower lock state so as to preserve the previous lower lock state or the lock state should be propagated from the higher lock level to the lower lock level. This embodiment provides the advantage that keeping the exclusive lock until the shareable resource has been checked and amended and releasing all the optimistic lock requestors at the end of the modifications. It also has the advantage that when no other portion of the shareable resource needs modifying, reverting as quickly as possible to a read lock boosts concurrency.

In an embodiment, higher lock levels do not acquire or release the lock if the shareable resource being managed by the lock has not been published.

Embodiments of the invention provide a system for managing access to a shareable resource between a plurality of concurrently executing threads, the system comprising: a lock for controlling access to the shareable resource, the lock being adapted to be accessed by one or more of the plurality of concurrently executing threads in at least a shared mode, an optimistic mode and an exclusive mode and the lock maintaining a list of threads requesting ownership of the lock, the lock comprising: a shared optimistic mode for the lock, the lock being acquirable in the shared optimistic mode by the one or more of the concurrently executing threads; a lock state descriptor for each change of mode desired by one of the concurrently executing threads, the lock state descriptor comprising an indication of the current mode, if any, in which the one of the concurrently executing threads has already acquired the lock; and wherein: responsive to the one or more of the concurrently executing threads acquiring the lock in the shared optimistic mode, allowing others of the one or more concurrent threads to acquire the lock in the shared mode or the optimistic mode; and responsive to the one or more of the concurrently executing threads which has acquired the lock in the shared optimistic mode requesting to acquire the lock in the exclusive mode, preventing others of the one or more of the concurrently executing threads which have acquired the lock in the shared mode or the optimistic mode from acquiring the lock in the exclusive mode until the one or more of the concurrently executing threads which has acquired the lock in the shared optimistic mode requesting to acquire the lock in the exclusive mode releases the lock.

Embodiments of the invention also provide a computer program product for managing access to a shareable resource between a plurality of concurrently executing threads, access to the shareable resource being controlled by a lock, the lock being adapted to be accessed by one or more of the plurality of concurrently executing threads in at least a shared mode, an optimistic mode and an exclusive mode and the lock maintaining a list of threads requesting ownership of the lock, the computer program product comprising: a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to: provide a shared optimistic mode for the lock, the lock being acquirable in the shared optimistic mode by one or more of the plurality of concurrently executing threads; provide, for each change of mode desired by one of the concurrently executing threads, a lock state descriptor, the lock state descriptor comprising an indication of the current mode, if any, in which the one of the concurrently executing threads has already acquired the lock; responsive to the one or more of the concurrently executing threads acquiring the lock in the shared optimistic mode, allow others of the one or more concurrent threads to acquire the lock in the shared mode or the optimistic mode; responsive to the one or more of the concurrently executing threads which has acquired the lock in the shared optimistic mode requesting to acquire the lock in the exclusive mode, prevent others of the one or more of the concurrently executing threads which have acquired the lock in the shared mode or the optimistic mode from acquiring the lock in the exclusive mode until the one or more of the concurrently executing threads which has acquired the lock in the shared optimistic mode requesting to acquire the lock in the exclusive mode releases the lock.

DETAILED DESCRIPTION

Embodiments of the invention provide a shared lock so as to take advantage of parallelism in operations such as check-reloads, independently of any code reutilization issues being addressed. These embodiments provide a reentrant lock infrastructure that allows code to be reutilized while maintaining lock states consistent with the operation being performed.

Embodiments of the invention provide a new lock that adds a fourth state to read-write locks, referred to hereinafter as a Shared Optimistic state. The behavior of such a lock is as described below.

When the lock is in the unlocked state, any thread can acquire it in any of the other modes.

When the lock has been acquired in shared mode by one or more threads, other threads can still acquire the lock in shared or optimistic mode, providing parallel read operations. Threads wishing to acquire the lock in exclusive mode will have to wait for the current readers (in either shared or optimistic mode) to release the lock before they can proceed. When a particular thread wants to switch from shared to exclusive mode, there is no guarantee that by the time it acquires the lock in exclusive mode, other writers haven't changed the structure protected by the lock.

When the lock has been acquired in a shared optimistic mode, according to embodiments of the present invention, by one or more threads, one or more of the other concurrently executing threads can still acquire it in shared or optimistic mode, providing parallel read operations. Threads wishing to acquire the lock in exclusive mode have to wait for the current readers (in either shared or optimistic mode) to release the lock before they can proceed. When a particular thread wants to switch from shared optimistic to exclusive mode, it has to wait for the other current readers to release the lock, but other threads wishing to acquire the lock in exclusive mode are prevented from acquiring the lock until the thread promoting the lock from optimistic to exclusive has released the lock, thus providing a partial guarantee that writers have not changed the structure protected by the lock. This means that when the lock is in a transient state whereby there are no reader lock owners (the last one having just released the lock), but an optimistic reader wanting to promote the lock to exclusive has not yet made it to a running state, any new thread wanting to acquire the lock in whichever mode will be placed in lock wait queue even if the lock is currently (and temporarily) in unlocked state.

When the lock is acquired in exclusive mode, every other thread has to wait for the lock to be released. The important change in behavior compared to read-write locks occurs when the current exclusive lock owner releases the lock. If the lock owner had promoted the lock from optimistic and the initial set of waiters in the queue are other optimistic readers also wanting to promote the lock to exclusive, the lock owner would proceed to wake up all the would be promoters (and readers) it finds at the head of the wait queue, but the promoters would acquire the lock in optimistic mode a second time and would be instructed to perform again whatever operation they were doing.

The advantage of embodiments of the present invention is that, in scenarios as detailed earlier, by having threads flag the possible intent of modifying a substructure before checking it, when the structure is found to be needing a refresh, rather than switching a multitude of readers to a trickle of writers, it is now possible to have only the first thread promote the lock to exclusive and modify the substructure. The trickle of writers would be needlessly repeatedly updating, one at a time (and while readers of other parts of the structure are prevented from operating) the substructure in question. Once the first thread has promoted the lock to exclusive and modified the substructure, at the end of which operation all other threads that found the substructure to be wanting can then check again, in parallel, that the refresh done by the only exclusive locker is up to date, thus avoiding both subsequent needless substructure modifications (which would have to occur with a normal read-write lock) and a substantial bottleneck on the lock itself caused by all other threads acquiring the lock in exclusive mode for a fairly long period of time.

FIG. 1is a block diagram of a system in which embodiments of the present invention may be implemented. Lock470controls access to a shareable resource440between a plurality of concurrently executing threads450-456. Resource440comprises a plurality of subsections, or parts442,444. Access to the shareable resource440, or to one of the plurality of subsections, or parts442,444, by one or more of the plurality of concurrently executing threads450-456is in one or more modes. The lock470is adapted to be accessed by one or more of the plurality of concurrently executing threads450-456in at least a shared mode, an optimistic mode and an exclusive mode as well as a shared optimistic mode. The lock470maintains a list of threads450-456requesting ownership of the lock470, implemented as a lock wait queue460. Lock470comprises a lock structure100, which will be described below with reference toFIG. 2. Each thread450-456comprises lock state descriptors200,220-260, there being one lock state descriptor200,220-260for each request by each thread450-456to access the lock470. Lock state descriptor200,220-260will be described below with reference toFIG. 3. The use of a lock state descriptor200,220-260within a thread450-456has the advantage that the thread450-456does not need to inspect a lock470to find out if the thread450-456already owns the lock470. Lock state descriptors200,220-260are associated with threads450-456, and not locks470, because in different nested functions a thread450-456may have performed lock470switches, and the lock state descriptor200,220-260tells the thread450-456which state change it needs to perform on the lock470to get it to the state in which the caller thread450-456expects the lock470to be.

FIG. 2is a block diagram of a lock structure100according to embodiments of the present invention. Lock structure100comprises busy_lock_t102which is a pointer to a busylock structure, such as a test and set, ticket lock or atomic deli counter lock. Readers104is a count of the number of concurrently executing threads which are accessing the lock in a read mode. Optimistic106is a count of the number of concurrently executing threads which are accessing the lock in an optimistic mode. Owner108is an indicator containing an identifier associated with the owner of the lock. Thread_t110is a pointer to one of the concurrently executing threads which is waiting to access the lock.

FIG. 3is a block diagram of a lock state descriptor structure200according to embodiments of the present invention. As mentioned above, there is one lock state descriptor200,220-260for each request by each thread450-456to access the lock470. If there is a plurality of concurrently executing threads450-456, each making one or more requests to access the lock470, then there is a lock state descriptor200,220-260associated with each of the requests. Current_mode202is an indicator of the current mode, if any, in which the lock470is being accessed by the thread450-456. Requested_mode204is an indicator of the desired mode in which the lock470is desired to be accessed by the thread450-456. Previous_mode206is an indicator of the previous mode in which the lock470was previously accessed by the thread450-456. Optimistic_ID208is an indicator of a subsection, or part442,444, of the resource440, access to which is being controlled by the lock470. The subsection, or part442,444, of the resource is that subsection, or part442,444, of the resource440that is being amended by the thread450-456that has successfully promoted the lock from optimistic408state to exclusive406state. Options210is a set of indications including whether the lock470is to be restored (see description below with reference toFIG. 7A) or whether the lock is PRIVATE (see description below with reference toFIG. 8A). Lock_t212is a pointer to the lock structure100itself. State_t214is a pointer to a previous one of the lock state descriptors200,220-260. State_t216is a pointer to a next one of the lock state descriptors200,220-260.

In a computer-implemented method, the lock state descriptor200,220-260comprises an indication of the current relationship between the lock470and the one of the concurrently executing threads200,220-260.

FIG. 4is a block diagram of a thread structure110of the lock structure100ofFIG. 1according to embodiments of the present invention. Thread_ID302is an identifier associated with the particular thread structure110. Lock_mode304is an indicator of the mode in which the particular thread currently has access to the lock470. Optimistic ID306is an identifier of a subsection, or part442,444, of the resource440, access to which is being controlled by the lock470. Optimistic_ID306in the lock structure100is a counterpart of the Optimistic ID208in the thread450-456. Thread_t308is pointer to a next one of the thread structures110.

FIG. 5is a block diagram of lock states of a shared lock470. Lock470is initially in a released402or unlocked state. One or more of the concurrently executing threads450-456may access the lock470concurrently in a shared404mode and may release the lock470from the shared404mode to a released402mode. One of the concurrently executing threads450-456may access the lock470in exclusive406or unshared mode and may release the lock470from the exclusive406mode to a released402mode. One or more of the concurrently executing threads450-456may access the lock470concurrently in a shared optimistic408mode and may release the lock470from the shared optimistic408mode to a released402mode. Additionally, one of the concurrently executing threads450-456may transition to access the lock470in an exclusive406or unshared mode from a shared optimistic408mode and may then either release the lock470or may return to the shared406optimistic mode.

Embodiments of the present invention differ from relational intent locks in that an intent lock on an object flags the presence of a lock on a lower object. For example, an intent lock on a table flags a lock on a row. This prevents other threads from acquiring locks on the table itself. Intent locks do not allow lock promotion on the same object, nor do they allow multiple lock requesters to obtain at the same time as others a lower lock than they had actually requested.

Prior art read-write locks do not keep track of individual read lock owners. This means that promoting a lock470from shared optimistic408mode to exclusive406mode cannot be achieved using a prior art read-write lock. This is because the lock structure100does not report whether the requesting thread already owns a shared lock470and the lock algorithm cannot determine whether it should proceed with a lock promotion or a lock acquisition.

Embodiments of the present invention add a Lock State Descriptor200,220-260, which reports the ownership state (if any) of an individual thread450-456on an individual lock470. Using the information contained in the Lock State Descriptor200,220-260together with the state of the lock structure, embodiments of the present invention allow the lock470to transition correctly from one lock state402-408to another402-408.

Embodiments of the invention provide a reentrant lock infrastructure by linking, in a list, lock state descriptors200,220-260for the same lock470and thread450-456. Since each lock state descriptor200,220-260holds the current relationship between the lock470and the thread450-456, the lock470does not need to be acquired multiple times. Acquiring the lock470once is enough, thereby eliminating performance problems inherent with relockable mutexes.

In an embodiment of the invention, the lock state descriptor200,220-260lists are implemented by explicitly passing a state pointer from the calling function to the called one, which allows the implementation of recursive locks and reusable code, but does not allow reentrant locks.

In another embodiment of the invention, the lock descriptor lists200,220-260are implemented by having a per thread stack of descriptors.

In another embodiment, the lock descriptor lists200,220-260are implemented by having a per thread linked list.

In another embodiment, the lock descriptor lists200,220-260are implemented by having a per system linked list.

Advantages of the embodiments above include speed for frame based states, the ability to debug a locking scheme and the ability to detect deadlocks.

In an embodiment of the invention, the switch from one lock state402-408, or “lock level”, to the next state402-408is implicit. At each new lock request, if a lock state descriptor200,220-260for the same lock470already exists, a new lock state descriptor200,220-260is created. At each release operation, the current state is destroyed, mimicking the behavior of relockable mutexes.

In another embodiment of the invention, the switch from one lock state402-408to the next state402-408is explicit. In this embodiment, the programmer needs to explicitly declare in which sections of code a further lock470attempt is expected on that particular lock470. The advantage of this embodiment is that a locking scheme has to be explicitly defined and enforced.

In most circumstances programmers use locks470in a non reentrant manner and for the shortest amount of time, as per usual multithreading programming tradition. Programmers explicitly turn to a reentrant lock infrastructure for a specific lock470, only in places where the reentrant use of the lock470is completely understood, thereby eliminating the biggest criticism to relockable mutexes.

FIGS. 6A and 6Bare a flow chart of a process to initialize the lock state descriptor200structure ofFIG. 3according to embodiments of the present invention. The exemplary embodiment ofFIGS. 6A and 6Bare just one of many possible embodiments of the invention as defined by the claims of the invention. The process ofFIGS. 6A and 6B, called lockstate_mark, marks a new lock470state level. The lock470can be acquired by the owner multiple times (or levels) in the same way as known recursive/relockable mutexes do. Unlike in known recursive/relockable mutexes, there is an explicit switch between levels, described later with reference toFIGS. 8A to 8I.

FIGS. 6A and 6Bwill now be described in more detail by means of the pseudocode below. In an exemplary usage, the lockstate_mark process initiates a first lock level, where the thread450-456does not own the lock470. In the pseudocode examples below, references in <angle brackets>are references to the Figures of the drawings, numbers at the start of each line are references to the corresponding reference numerals in the drawings and references in angle brackets to connectors are references to inter-page connectors in the drawings.

<FIG. 6A>504—allocate new lock state descriptor structure506—initialize lock structure508—search previous descriptor for the same lock510—if found link

<corresponding else is through connector B at line518inFIG. 6B>512—set new descriptor→previous_level to previous descriptor

<connector B fromFIG. 6A>518—set new descriptor→previous_level to NULL520—set new descriptor→current_mode to RELEASED522—set new descriptor→previous_mode to RELEASED524—set new descriptor→requested_mode to RELEASED526—append new descriptor to thread descriptor list

FIGS. 7A and 7Bare a flow chart of a process to restore the lock state descriptor structure200,220-260ofFIG. 3. The exemplary embodiment ofFIGS. 7A and 7Bare just one of many possible embodiments of the invention as defined by the claims of the invention. The process ofFIGS. 7A and 7B, called lockstate_restore, terminates the current lock level and sets the lock470back as the previous lock level expects it to be. If this process is carried out on the first lock level, then the lock is released.

FIGS. 7A and 7Bwill now be described in more detail by means of the pseudocode below.

<corresponding else is at line610>606—if the lock is in use<if not line618(through connector C toFIG. 7B)>608—lockstate_lower(RELEASED, lockstate→current_mode, lockstate→lock)

<connector C fromFIG. 7A>618—remove lock state from thread lock list620—free lock state descriptor structure

FIGS. 8A to 8Iare a flow chart of a process to switch between the modes402-408ofFIG. 2in the structure of the lock470ofFIG. 1. The exemplary embodiment ofFIGS. 8A to 8Iare just one of many possible embodiments of the invention as defined by the claims of the invention. The process ofFIGS. 8A to 8I, called lockstate_switch, causes the lock470to transition from one state402-408to another402-408as needed, for example, from RELEASED to EXCLUSIVE terminates the current lock level and sets the lock470back as the previous lock level expects it to be. If this process is carried out on the first lock level, then the lock470is released.

FIGS. 8A to 8Iwill now be described in more detail by means of the pseudocode below. In an exemplary usage, lockswitch_switch is used to acquire a lock470which the thread does not already own, in an EXCLUSIVE mode.

<corresponding else is at line 9 (through connector G toFIG. 8B)>

—else716—acquire lockstate→lock→busylock717—if mode is EXCLUSIVE

<corresponding else is at line746inFIG. 8H(through connector H)>718—if lockstate→lock→current_mode is set to OPTIMISTIC

<connector J toFIG. 8D>722—else if lockstate→lock→current_mode is set to SHARED

<corresponding else is at line725(through connector L toFIG. 8D)>

728—do729—if thread→optimistic_id is not set to NOPROMOTE

(that is, this is a lock promotion)<corresponding else is at line732>730—scan lockstate→lock→waiting from the head731—append thread to lockstate→lock→waiting before any thread that is not doing a lock promotion

thread→optimistic_id is not set to NOPROMOTE

(that is, this is a lock promotion)

<corresponding else is at line50>744—return SUCCESS

FIGS. 9A to 9Hare a flow chart of a process to lower the mode of the structure100of the lock470ofFIG. 1. The exemplary embodiment ofFIGS. 9A to 9Hare just one of many possible embodiments of the invention as defined by the claims of the invention. The process ofFIGS. 9A to 9H, called lockstate_lower, is a helper function, used only by the lockstate_switch( ) and lockstate_restore( ) processes to cause the lock470to transition from a state402-408to a lower state402-408.

FIGS. 9A to 9Hwill now be described in more detail by means of the pseudocode below.

<corresponding else is between line839and840(through connector AA toFIG. 9G)>804—set lock→owner to NOBODY805—if to_mode is RELEASED or AMENDED and thread→optimistic_id is not NOPROMOTE

<corresponding else is at line819>806—scan lock→waiting

<connector BB fromFIG. 9A>807—while first waiter→lock_mode is EXCLUSIVE and waiter→optimistic_id not NOPROMOTE and

<connector FF fromFIG. 9B>813—if no waiter removed from lock→waiting and first waiter→lock_mode is EXCLUSIVE814—remove from lock→waiting815—release lock→busylock816—wake up waiters817—set thread→optimistic_id to NOPROMOTE818—exit

<FIG. 9A>819—else if to_mode is not OPTIMISTIC or SHARED

<corresponding else is at line836(through connector CC toFIG. 9F)>820—scan lock→waiting821—if first waiter→lock_mode is EXCLUSIVE

<corresponding else is at line829(through connector DD toFIG. 9E)>

/* enforce optimistic lock promotion after a PRESERVE */823—if waiter→optimistic_id is not NOPROMOTE and

—else829—while first waiter→lock_mode is SHARED or OPTIMISTIC830—remove from lock→waiting831—if any found <if not line836(through connector CC toFIG. 9F)>832—release lock→busylock833—wake up all waiters834—set thread→optimistic_id to NOPROMOTE835—exit

/* EXCLUSIVE to OPTIMISTIC should be avoided

as this means that any subsequent optimistic promoter will not retry

<corresponding else is at line852>848—remove from lock→waiting849—release lock→busylock850—wake up waiter851—exit

—else852—while first waiter is SHARED or OPTIMISTIC853—remove from waiting list854—if any found855—release lock→busylock856—wake up all waiters857—exit858—release lock→busylock859—exit

In a computer-implemented method for managing access to a shareable resource between a plurality of concurrently executing threads, access to said shareable resource being controlled by a lock, said lock being adapted to be accessed by one or more of said plurality of concurrently executing threads in at least a shared mode, an optimistic mode and an exclusive mode and said lock maintaining a list of threads requesting ownership of said lock, the method comprising: providing a shared optimistic mode for said lock, said lock being acquirable in said shared optimistic mode by one or more of said plurality of concurrently executing threads; providing, for each change of mode desired by one of said concurrently executing threads, a lock state descriptor, said lock state descriptor comprising an indication of the current_mode, if any, in which said one of said concurrently executing threads has already acquired said lock; responsive to said one or more of the concurrently executing threads acquiring said lock in said shared optimistic mode, allowing others of said one or more concurrent threads to acquire said lock in said shared mode or said optimistic mode; and responsive to said one or more of the concurrently executing threads which has acquired said lock in said shared optimistic mode requesting to acquire said lock in said exclusive mode, preventing others of said one or more of the concurrently executing threads which have acquired said lock in said shared mode or said optimistic mode from acquiring said lock in said exclusive mode until said one or more of the concurrently executing threads which has acquired said lock in said shared optimistic mode requesting to acquire said lock in said exclusive mode releases said lock.

In a specific embodiment of the invention, an identifier is associated to an optimistic lock request. Using the identifier, rather than waking up all of the optimistic lock promoters, upon releasing the lock, the current lock owner can wake up only requesters that have used the same identifier as the lock owner. All such lock requesters would be going through the same section of code. This allows the release of just threads waiting on the particular substructure that has just been amended, but not threads waiting on other substructures, which are still outdated, thereby avoiding further contention.

In a computer-implemented method, each request for a change of mode to said optimistic mode comprises an identifier identifying a portion of said shareable resource that the requestor making said request wishes to access.

In another specific embodiment, shared optimistic lock requests have a counter associated with them, whereby an individual thread is not asked to retry checking in optimistic mode more than a set number of times, to avoid infinite loops. When the retry count is exhausted, a thread may be made to wait to obtain the lock in exclusive mode or abort, even if an optimistic retry could be done again.

In a computer-implemented method, each lock state descriptor further comprises a count of the number of attempts to access said lock in said shared optimistic mode, said one of the concurrently executing threads attempting to access said lock in said shared optimistic mode having its attempt to access said lock terminated when said count reaches a predetermined value.

In another specific embodiment, locks may be released from exclusive mode in either “amended” or “preserved” mode, to mark that a lock promoter from optimistic to exclusive mode has been successful/unsuccessful in altering the controlled structure. The “amended” mode or “preserved” mode is indicated in the CURRENT_MODE202or REQUESTED_MODE204of the lock state descriptor structure200. Amended mode results in all optimistic to exclusive promotion waiters being released in optimistic mode, while preserved mode results in the next optimistic to exclusive promoter being released having gained exclusive access to the lock. In this embodiment, since the current thread, for whatever reason, could not successfully amend the substructure, the next thread should try to amend it, since it is still invalid and in need of modifications.

In a computer-implemented method, responsive to said one or more of the concurrently executing threads releasing said lock from said exclusive mode; updating a current mode or a requested mode in said lock state descriptor as being “amended” in order to indicate that a lock promoter from said optimistic mode to said exclusive mode was successful in altering said shareable resource being controlled by said lock; updating said current mode or said requested mode in said lock state descriptor as being “preserved” in order to indicate that said lock promoter from said optimistic mode to said exclusive mode did not make a change to the structure or said requested mode; and updating said current mode or said requested mode in said lock state descriptor as being “failed” in order to indicate that said lock promoter from said optimistic mode to said exclusive mode was unsuccessful in altering said shareable resource being controlled by said lock.

In another specific embodiment, a request to mark a new lock state may have options associated with it. A first example of the options is a “preserve lock state” or “propagate lock state”, whereby once a higher lock level has completed and the current lock level is resumed, the lock can be reset to the state set in the current level or the state set by the higher level can be propagated to the current level. Once a thread has obtained a lock in exclusive mode because modification to a substructure is needed, it may be advantageous to keep the exclusive lock until all the parts of the complex structure are checked and amended, and release all optimistic lock requester at the end of all of the modifications, if it is expected that other subparts might need modifications. This avoids all other threads repeatedly stopping and waiting on the same lock for each other subpart that it has been found to be needing a refresh, thereby causing a bottleneck. On the contrary when no other subpart is expected to be needing modifications, reverting as quickly as possible to a read lock boosts concurrency.

In a computer-implemented method, said lock state descriptor further comprises an indication as to whether, on resuming a lower lock state from a higher lock state, the lock state should be reset to that of said lower lock state so as to preserve the previous lower lock state or the lock state should be propagated from said higher lock level to said lower lock level.

A second example of the options is “private”, whereby higher lock levels may not acquire/release the lock on the ground that the structure being manipulated has not been published yet and therefore, being not visible to other threads, requires no locking. This may initially appear to be a step in the direction of obfuscating the locking scheme in that the function dictates that the structure should be protected, but the underlying setting is such that the lock is ignored. However, it is yet another setting that has to be explicitly chosen. The programmer has to understand the chosen locking scheme in order to be able to determine that a “private” state would be acceptable at higher levels in the chosen section of code.

In a computer-implemented method, higher lock levels do not acquire or release said lock if the shareable resource being managed by said lock has not been published.

Embodiments of the invention described above may provide the advantage of improved ability to debug the locking scheme. Prior art mutex implementations allow the use of debugable mutexes. Whilst it is possible to use a tool which, through use of code instrumentation or otherwise, is able to build a graph of lock requests and identify deadlocks, lock state descriptors200,220-260according to the present invention allow a much greater range of problems to be detected.

An example of an error that can already be detected by prior art mutex implementations is a thread is attempting to lock a mutex that it already owns, such as, for example POSIX threads.

An example of a potential problem that cannot be detected by prior art implementations is a thread using a mutex in a recursive manner in places where it would not be expected. Recursive POSIX mutexes are reentrant at all times and cannot distinguish between the two uses. The use of lock state descriptors200,220-260according to embodiments of the present invention allows the detection, and rejection, of threads450-456trying to use a lock470directly, that is, outside of the lock reentrant infrastructure, when previously the same lock470had been explicitly marked for recursive use, and the recursive use has not been terminated. The use of lock state descriptors200,220-260according to embodiments of the present invention allows the detection of an attempted reentrant lock request when the lock470had already been acquired directly, that is, use of reentrant locks where reentrancy was not expected.

As a further example of a debugging facility, during the development phase, the underlying locking infrastructure may be set to detect when an individual thread450-456has acquired more than a threshold number of locks470as this might affect concurrency or induce deadlocks. Embodiments of the invention allow limits to be set individually for both recursive and non recursive lock requests.

In a similar way, embodiments of the invention allow a limit to be set on the number of levels402-408individual locks470can get to, so as to be able to detect combinations of stacked lock470requests that the programmer had not envisaged.

Detecting an optimistic lock request, whether with a specific ID or not, following a previous optimistic lock request with a different specific ID should indicate to a programmer that there is a problem.

In summary, embodiments of the present invention provide an extra lock state408coupled with the ability of releasing exclusive lock waiters in read mode404instead and a (stack or graph of effective or implied) lock state change. These provide the advantage of the ability to process, in parallel, a wider array of scenarios coupled with the ability to use reentrant code without any of the disadvantages of relockable mutexes.

The following example in pseudo C shows how an embodiment of the invention may be used. The following example does not describe aspects of embodiments of the invention, but instead describes solely how embodiments of the invention may be used.

In the pseudo C code below lock_init( ) lock_switch( ) and lock_free( ) are hypothetical functions that initialize, manipulate and dispose of passive wait read-write mutexes in the customary way.

The pseudo code below instantiates a complex structure:

/* this part of the code must be done with an exclusive lock

if one hadn't been acquired already and the structure

has already been published

/* release the lock and signal if the structure has been modified */

/* allocate and initialize new structure */

if (!(in=malloc(sizeof(structdesc))))

/* allocate lock and mark lock state to be private */

<and again for other structure parts>

/* append structure to list with lock acquired */

<insert structure in list>

The pseudo C code below manipulates part of a complex structure:

The pseudo C code below checks and possibly amends a complex structure:

/* prevent writers from modifying the superstructure but

allow parallel checks of individual substructures

/* promote the lock to exclusive to perform the modifications

if the lock cannot be promoted—somebody has already done

the required modifications—check again, again in parallel

if (result==ERROR)

/* the lock has successfully been promoted, proceed to refresh the substructure

The pseudo C code below disposes of a complex structure:

if (<structure has references>)

Referring now toFIG. 10, a schematic of an example of computing system is shown. Computing system912is only one example of a suitable computing system and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the invention described herein. Regardless, computing system912is capable of being implemented and/or performing any of the functionality set forth hereinabove.

As shown inFIG. 10, computer system/server912is shown in the form of a general-purpose computing device. The components of computer system/server912may include, but are not limited to, one or more processors or processing units916, a system memory928, and a bus918that couples various system components including system memory928to processor916.

Computer system/server912typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server912, and it includes both volatile and non-volatile media, removable and non-removable media.

Program/utility940, having a set (at least one) of program modules942, may be stored in memory928by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules942generally carry out the functions and/or methodologies of embodiments of the invention as described herein.

Computer system/server912may also communicate with one or more external devices914such as a keyboard, a pointing device, a display924, etc.; one or more devices that enable a user to interact with computer system/server912; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server912to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces922. Still yet, computer system/server912can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter920. As depicted, network adapter920communicates with the other components of computer system/server912via bus918. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server912. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.