Reader-writer lock for multiprocessor systems

• US 6,823,511 B1
• Filed: 01/10/2000
• Issued: 11/23/2004
• Est. Priority Date: 01/10/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kingsbury, Brent, McKenney, Paul E.
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): ALI, SYED J
• Application Number:
  US09/480,082
• Time in Patent Office: 1,779 Days
• Field of Search: 709/100, 709/102, 709/104, 709/106, 709/107, 709/312, 710/200-244, 711/147, 711/148, 711/150, 711/152
• US Class Current: 718/102
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A reader-writer lock minimizes writer and reader overhead by employing lock structures that are shared among groups of processors that have lower latencies. In the illustrated multiprocessor system having a non-uniform memory access (NUMA) architecture, each processor node has a lock structure comprised of a shared counter and associated flag for each CPU group. During a read, the counter can be changed only by processors within a CPU group performing a read. This reduces the reader overhead that otherwise would exist if all processors in the system shared a single counter. During a write, the shared flag can be changed by a process running on any processor in the system. The processors in a CPU group are notified of the write through the shared flag. This reduces the writer overhead that otherwise would exist if each processor in the system had a separate flag. The number of CPUs per group can be varied to optimize performance of the lock in different multiprocessor systems.

Claims

1. A reader-writer lock for a multiprocessor system comprising:

a first counter shared by a first group of two or more processors, the counter adapted to indicate whether a process running on a processor in the first processor group has read-acquired the lock;

a first flag associated with the first counter, the flag adapted to indicate whether a process running on a processor in the multiprocessor system has write-acquired the lock;

a second counter shared by a second group of one or more processors, the second counter adapted to indicate whether a process running on a processor in the second processor group has read-acquired the lock; and

a second flag associated with the second counter, the second flag adapted to indicate whether a process running on a processor in the multiprocessor system has write-acquired the lock.

2. The reader-writer lock of claim 1, wherein the multiprocessor system includes interconnected processor nodes, a first node including the first processor group and local memory storing the first counter and first flag, and a second node including the second processor group and local memory storing the second counter and the second flag.

3. The reader-writer lock of claim 2, wherein a line of local memory on a node is sized to contain counters and associated flags that are parts of multiple reader-writer locks for the processor group on the node.

4. The reader-writer lock of claim 2, further comprising at least two groups of processors on each node, each processor group sharing a separate counter and associated flag.

5. The reader-writer lock of claim 4, wherein the counter and associated flag for a first processor group on the node are stored in a first line of memory and the counter and associated flag for a second processor group on the node are stored in a second line of memory.

6. The reader-writer lock of claim 1, further comprising an identifier adapted to indicate the processor group that contains the processor on which a process was running at the time the process acquired the lock.

7. The reader-writer lock of claim 1, further comprising a mutual exclusion lock adapted to indicate to other processes desiring to acquire the reader-writer lock that a process has write-acquired the reader-writer lock.

8. The reader-writer lock of claim 1, further comprising a mutual exclusion lock adapted to indicate to other processes desiring to acquire the reader-writer lock that a process is write-acquiring the reader-writer lock.

9. The reader-writer lock of claim 1, further comprising an indicator adapted to indicate to a first writing process before it releases the lock that a second writing process desires to acquire the lock,

thereby avoiding a need to clear said flags to indicate that the first writing process has released the lock.

10. The reader-writer lock of claim 1, further comprising an indicator adapted to indicate to a second writing process before it acquires the lock that a first writing process has most recently held the lock,

thereby avoiding a need to set said flags to indicate that the second writing process has write-acquired the lock.

11. The reader-writer lock of claim 1, further comprising a termination flag adapted to indicate whether the each process acquiring the lock is active.

12. The reader-writer lock of claim 1, further comprising including an identifier adapted to identify whether the lock is held by an exclusive-reading process.

13. The reader-writer lock of claim 1, wherein the first counter and first flag are combined in a word.

14. The reader-writer lock of claim 1, wherein the multiprocessor system includes interconnected processor nodes, wherein a quantity of processors per node is variable.

15. A reader-writer lock for a multiprocessor system comprising:

a lock structure shared by a group of one or more processors, the structure adapted to indicate whether a process running on a processor in the processor group has read-acquired the lock;

a flag associated with the lock structure, the flag adapted to indicate whether a process running on a processor in the multiprocessor system has write-acquired the lock; and

an indicator adapted to indicate to a first writing process before it releases the lock that a second writing process desires to acquire the lock,

thereby avoiding a need to clear the flag to indicate that the first writing process has released the lock.

16. The reader-writer lock of claim 15, further comprising an indicator adapted to indicate to a second writing process before it acquires the lock that a first writing process has most recently held the lock,

thereby avoiding a need to set the flag to indicate that the second writing process has write-acquired the lock.

17. The reader-writer lock of claim 15, wherein the lock structure comprises a counter and an associated flag.

18. A reader-writer lock for a multiprocessor system comprising:

a first counter shared by a first group of one or more processors, the counter adapted to indicate whether a process running on a processor in the first processor group has read-acquired the lock;

a first flag associated with the first counter, the flag adapted to indicate whether a process running on a processor in the multiprocessor system has write-acquired the lock;

a second counter shared by a second group of one or more processors, the second counter adapted to indicate whether a process running on a processor in the second processor group has read-acquired the lock;

a second flag associated with the second counter, the second flag adapted to indicate whether a process running on a processor in the multiprocessor system has write-acquired the lock; and

an identifier adapted to indicate the processor group that contains the processor On which a process was running at the time the process acquired the lock.

19. The reader-writer lock of claim 18, wherein a process running on a processor in the first processor group read-acquires the lock by changing the first counter.

20. The reader-writer lock of claim 18, wherein a process running on a processor in the first processor group write-acquires the lock by changing the first and second flags associated with the first and second counters.

21. A method of write-acquiring a reader-writer lock in a multiprocessor comprising:

providing a first counter shared by a first group of two or more processors and a second counter shared by a second group of two or more processors;

indicating through a count of waiting writers to a first writing process before it releases the lock that a second writing process desires to acquire the lock;

maintaining the status of an indicator to indicate that a process has write-acquired the lock; and

releasing the lock to the second writing process,

thereby avoiding a need to clear the flag indicator to indicate that the first writing process has released the lock.

22. The method of claim 21, further comprising

avoiding setting of a flat to indicate that the second writing process has write-acquired the lock by indicating to the second writing process before it acquires the lock that a first writing process has most recently held the lock;

wherein said flag is associated with the counter and is adapted to indicate whether a process running on a processor in the multiprocessor system has write acquired the lock.

23. A method of upgrading an exclusive-reading process to a writing process, comprising:

providing a first counter shared by a first group of one or more processors, the counter adapted to indicate whether a process running on a processor in the first processor group has read-acquired the lock;

providing a first flag associated with the first counter, the flag adapted to indicate whether a process running on a processor in the multiprocessor system has write-acquired the lock;

providing a second counter shared by a second group of one or more processors, the second counter adapted to indicate whether a process running on a processor in the second processor group has read-acquired the lock;

providing a second flag associated with the second counter, the second flag adapted to indicate whether a process running on a processor in the multiprocessor system has write acquired the lock;

exclusive-read acquiring a lock; and

write-acquiring the lock.