Read-write spinlock

• US 8,799,591 B2
• Filed: 01/30/2007
• Issued: 08/05/2014
• Est. Priority Date: 01/30/2007
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Larson, Douglas V., McConnell, Marcia E.
• Primary Examiner(s): Faal, Baboucarr
• Application Number:
  US11/700,747
• Publication Number:
  US 20080183979A1
• Time in Patent Office: 2,744 Days
• Field of Search: None
• US Class Current: 711/152
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

An embodiment of the invention provides an apparatus and method for controlling access by a read-write spinlock with no mutual exclusion among readers. The apparatus and method perform the steps of using values in a data structure in the read-write spinlock to control read access to a shared object and using values in the data structure and a guard lock to control write access to the shared object.

Claims

1. A method comprising:

using values in a data structure in a read-write spinlock but no guard lock to control read access to a shared object; and

using values in the data structure and a guard lock to control write access to the shared object.

2. The method of claim 1, wherein the read-write spinlock permits multiple read accesses to the shared object at a same time.

3. The method of claim 1, wherein the guard lock prevents multiple write accesses to the shared object at a same time.

4. The method of claim 1, wherein a reader can start a read access if no writer has blocked read access by setting a read_flow field at a first value.

5. The method of claim 1, wherein a reader is prevented to start a read access if a writer sets a read_flow field to a second value that prevents read access and wherein the second value does not prevent a reader that is already reading to finish reading.

6. The method of claim 1, further comprising:

placing a reader in a spin and wait state if read access is not permitted to the shared object.

7. The method of claim 6, further comprising:

permitting a reader in the spin and wait state to obtain a read-lock and read to the shared object when read access is permitted to the shared object.

8. The method of claim 1, wherein write access is permitted after blocking new readers and there no readers executing in the shared object.

9. The method of claim 1, wherein write access is prevented if there are readers that are executing in the shared object.

10. The method of claim 1, further comprising:

placing a writer in a spin and wait state if write access is prevented.

11. The method of claim 1, wherein a reader reads and modifies the data structure by a fetch-and-add instruction.

12. The method of claim 11, wherein the fetch-and-add instruction increments counts and simultaneously reads the other fields in the data structure.

13. The method of claim 1, wherein a reader reads and modifies the data structure by a compare-and-swap instruction.

14. An apparatus comprising:

non transitory media encoded with a read-write spinlock including a data structure;

with values to control read access to a shared object without using a guard lock, and with values in the data structure and a guard lock to control write access to the shared object.

15. The apparatus of claim 14, wherein the read-write spinlock permits multiple read accesses to the shared object at a same time.

16. The apparatus of claim 14, wherein the guard lock prevents multiple write accesses to the shared object at a same time.

17. The apparatus of claim 14, wherein a reader can start a read access if no writer has blocked read access by setting a read_flow field at a first value.

18. The apparatus of claim 14, wherein a reader is prevented from starting a read access if a writer sets a read_flow field to a second value that prevents read access and wherein the second value does not prevent a reader that is already reading to finish reading.

19. The apparatus of claim 14, wherein a reader is placed in a spin and wait state if read access is not permitted to the shared object.

20. The apparatus of claim 19, wherein the reader in the spin and wait state is permitted to obtain a read-lock and to read to the shared object when read access is permitted to the shared object.

21. The apparatus of claim 14, wherein write access is permitted after blocking new readers and there no readers executing in the shared object.

22. The apparatus of claim 14, where write access is prevented if there are readers that are executing in the shared object.

23. The apparatus of claim 14, wherein a writer is placed in a spin and wait state if write access is prevented.

24. The apparatus of claim 14, wherein a reader reads and modifies the data structure by a fetch-and-add instruction.

25. The apparatus of claim 24, wherein the fetch-and-add instruction increments counts and simultaneously reads the other fields in the data structure.

26. The apparatus of claim 14, wherein a reader reads and modifies the data structure by a compare-and-swap instruction.

27. An apparatus for controlling access by a read-write spinlock with no mutual exclusion among readers, the apparatus comprising:

means for using values in a data structure in the read-write spinlock to control read access to a shared object; and

means for using values in the data structure and a guard lock to control write access to the shared object.

28. An article of manufacture comprising a non-transitory machine-readable storage medium having stored thereon instructions to:

use values in a data structure in the read-write spinlock to control read access to a shared object without using a guard lock; and

use values in the data structure and a guard lock to control write access to the shared object.

29. A method comprising:

using a spinlock data structure to control read access and to control write access to a data object as a function of values stored in said data structure;

using a guard lock to prevent a processor requesting write access to said data object other than a processor controlling said guard lock from writing to said spinlock data structure; and

using atomic read-then-write instructions to prevent a processor requesting read access to said data object from writing to said spinlock structure while another processor is writing to said spinlock structure.

30. A method as recited in claim 29 wherein said read-then-write instructions include fetch-and-add instructions or compare-and-swap instructions.

31. A method as recited in claim 29 wherein said spinlock data structure includes a read-flow field for storing a read-flow value indicating whether or not read access is permitted to said data object, a read-waiters field for storing a read-waiters value indicating a number of processors waiting for read access to said data object, and a read-count field for storing a read-count value indicating a number of processors currently having read access to said data object.

32. A method as recited in claim 31 wherein a processor uses said read-then-write instructions to:

increment said read-waiter value while waiting for read access to said data object;

decrement said read-waiter value when provided read access to said data object while said read-waiter value is non-zero;

increment said read-count value when provided read access to said data object; and

decrement said read-count value upon completion of a read access of said data object.

33. A method as recited in claim 32 wherein said read-flow value indicates whether or not read access to said data object is enabled.

34. A method as recited in claim 33 wherein a processor requesting read access:

i) determines from said read-flow value whether read access is enabled, and

ii) if not, increments said read-waiter count and spins until said read access is provided.

35. A method as recited in claim 34 wherein, when said processor determines read access is currently provided to said data object, said processor:

i) decrements said read-waiter value if it is non zero;

ii) increments said read-count value;

iii) reads from said data object; and

iv) decrements said read-count value once said read access is complete.

36. A method as recited in claim 33 wherein a processor requesting write access to said data object:

determines whether or not said guard lock is available; and

if not, spins until said guard lock is available.

37. A method as recited in claim 36 wherein said processor:

if said guard lock is available, acquires said guard lock so that it is unavailable to other processors requesting write access to said data object;

if or once said read-waiter value is zero, sets said read-flow value to disable read access to said data object;

if or once said read-count value is zero, exercises write access to said data object;

once said write access is complete, resets said read-flow value to enable read access to said data object; and

relinquishes said guard lock.