Reentrant read-write lock algorithm

• US 9,672,077 B2
• Filed: 05/05/2016
• Issued: 06/06/2017
• Est. Priority Date: 07/28/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Greco, Marco
• Primary Examiner(s): DORAIS, CRAIG C
• Application Number:
  US15/146,918
• Publication Number:
  US 20170031731A1
• Time in Patent Office: 397 Days
• Field of Search: None
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

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.

Claims

1. 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.

2. The computer-implemented method of claim 1, wherein said lock state descriptor comprises an indication of the current relationship between said lock and said one of said concurrently executing threads.

3. The computer-implemented method of claim 1, wherein 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.

4. The computer-implemented method of claim 1, wherein 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.

5. The computer-implemented method of claim 1, wherein:

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.

6. The computer-implemented method of claim 1, wherein 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.

7. The computer-implemented method of claim 1, wherein higher lock levels do not acquire or release said lock if the shareable resource being managed by said lock has not been published.