Reader-writer lock

• US 9,934,077 B2
• Filed: 02/11/2016
• Issued: 04/03/2018
• Est. Priority Date: 01/22/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Steinmacher-Burow, Burkhard
• Primary Examiner(s): Bertram, Ryan
• Application Number:
  US15/041,115
• Publication Number:
  US 20160162341A1
• Time in Patent Office: 782 Days
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method and system for implementing a reader-writer lock having a write lock requested by a thread is disclosed. The reader-writer lock is structured to have counters and a flag. The counters use an atomic process to count read locks held or outstanding read lock requests. The flag identifies a counter and is configured to distinguish between counters. A read lock is prepared, acquired, and released. The atomic process is used and the flag or flagged counter is polled. A write lock is prepared, acquired, and released.

Claims

1. A computer-implemented method for processing a set of access requests of a resource shared by a set of threads, the method comprising:

creating a set of pools for storing the set of access requests of the resource, the set of pools including a first pool configured to be active and a second pool configured to be inactive;

processing a first request of a first type of the set of access requests of the first pool, wherein processing a first request of a first type further comprises;

counting with a first counter, using an atomic process to increment the first counter in response to a first bit of the first counter being enabled, a number of read locks held in the first pool, wherein the first bit is initially set to be enabled;

counting with a second counter, using the atomic process to increment the second counter in response to a second bit of the second counter being enabled, a number of outstanding read lock requests in the first pool, wherein the second bit is initially set to be disabled; and

indicating with a flag either the first counter or the second counter but not both, configured to discern the first counter from the second counter, wherein the flag is initially set to identify the first counter; and

switching, in response to processing a second request of a second type of the set of access requests of the first pool, the first pool to be the second pool configured to be inactive and the second pool to be the first pool configured to be active.

2. The method of claim 1, wherein the first request of the first type uses a first quantity of processing resources and the second request of the second type uses a second quantity of processing resources, the first quantity different from the second quantity.

3. The method of claim 1, wherein the processing is atomically processing in an order defined by a processing strategy configured to initiate storing of the first request to the first pool in response to the first request and existence, at an address related to the resource, of a first logical value associated with the set of pools.

4. The method of claim 3, wherein the processing strategy is further configured to initiate storing of the first request to the second pool in response to the first request and existence, at the address related to the resource, of a second logical value associated with the set of pools.

5. The method of claim 1, wherein switching, in response to processing a second request of a second type of the set of access requests of the first pool, the first pool to be the second pool configured to be inactive and the second pool to be the first pool configured to be active further includes performing the switch in response to reaching a threshold count of a count of requests of the set of access requests initiated to be stored in the first pool.

6. The method of claim 1, wherein processing the second request of the second type of the set of access requests of the first pool in response to processing a third request of a third type of the set of access requests initiated for storage in the first pool subsequent to the second request being initiated for storage in the first pool.

7. The method of claim 6, wherein processing the second request of the second type of the set of access requests of the first pool in response to processing a fourth request of a fourth type of the set of access requests initiated for storage in the first pool subsequent to the second request being initiated for storage in the first pool, and wherein processing the first request in response to processing the second request in response to reaching a temporal threshold for processing the second request.

8. The method of claim 1, further comprising:

converting the first request of the first type to the second type; and

processing the second request in response to processing the converted first request.

16. The method of claim 8, wherein the first type is a read-type request, wherein the second type is a write-type request, wherein converting the first request of the first type to the second type further comprises:

determining if there are intervening write-type requests;

converting the first request of the first type to the second type in response to determining that there are no intervening write-type requests;

refreshing the resource in response to determining that there are intervening write-type requests; and

converting the first request of the first type to the second type in response to refreshing the resource.

17. The method of claim 1, wherein processing a first request of a first type further comprises:

preparing, using the atomic process in association with at least one counter of the first and second counters, a read lock associated with a flagged counter of the first and second counters;

acquiring, by polling the flag to identify the flagged counter of the first and second counters, the read lock; and

releasing, using the flagged counter to decrement a value of the flagged counter, the read lock.

18. The method of claim 17, wherein processing a second request of a second type further comprises:

preparing, by disabling the flagged counter and enabling an unflagged counter of the first and second counters, a write lock;

acquiring, by polling the flagged counter until the value of the flagged counter reaches zero, the write lock; and

releasing, using the flag to unflag the flagged counter and flag the unflagged counter, the write lock.

9. A system processing a set of access requests of a resource shared by a set of threads, the system comprising:

a reader-writer lock configured to;

provide a set of pools for storing data access requests;

assign a first pool of the set of pools to a first pool position;

assign a second pool of the set of pools to a second pool position;

wait for data access requests to access data by performing the following steps;

storing received read requests to the pool in the first position until a write request acquires a first ticket of a ticket lock and spins until a first turn associated with the pool in the first position, and

subsequently storing received read requests to the pool in the second position until a write request acquires a second ticket of the ticket lock and spins until a second turn associated with the pool in the second position,

atomically process the stored data access requests in the pool in the first pool position; and

exchange the first and second pool positions of the pools in response to processing each respective read request and each respective write request of the pool in the first pool position;

wherein the reader-writer lock comprises;

a first counter configured to count, using an atomic process to increment the first counter in response to a first bit of the first counter being enabled, a number of read locks held, wherein the first bit is initially set to be enabled;

a second counter configured to count, using the atomic process to increment the second counter in response to a second bit of the second counter being enabled, a number of outstanding read lock requests, wherein the second bit is initially set to be disabled; and

a flag, identifying either the first counter or the second counter but not both, configured to discern the first counter from the second counter, wherein the flag is initially set to identify the first counter.

10. The system of claim 9, further configured to wait for data access requests to access data in parallel with atomically processing the stored data access requests in the pool in the first pool position.

11. The system of claim 9, further configured to atomically process the stored data access requests in the pool in the first pool position in an order defined by a certain processing strategy.

12. The system of claim 11, wherein the certain processing strategy admits a read request to a particular pool only if the particular pool is admitting data access requests.

13. The system of claim 9, wherein to atomically process the stored data access requests the reader-writer lock is further configured to:

convert one or more read requests into write requests.

14. The system of claim 13, wherein to convert one or more read requests into write requests the reader-writer lock is further configured to:

determine if there are intervening write requests in the pool in the first pool position;

convert the read request to a write request in response to determining there are no intervening write requests in the pool in the first pool position;

refresh the resource in response to determining there are one or more intervening write requests in the pool in the first pool position; and

convert, in response to refreshing the resource, the read request to a write request.

15. The system of claim 9, wherein the reader-writer lock configured to atomically process the stored data access requests is further configured to:

prepare, using the atomic process in association with at least one counter of the first and second counters, a read lock associated with a flagged counter of the first and second counters;

acquire, by polling the flag to identify the flagged counter of the first and second counters, the read lock;

release, using the flagged counter to decrement a value of the flagged counter, the read lock;

prepare, by disabling the flagged counter and enabling an unflagged counter of the first and second counters, a write lock;

acquire, by polling the flagged counter until the value of the flagged counter reaches zero, the write lock; and

release, using the flag to unflag the flagged counter and flag the unflagged counter, the write lock.