Scalable and lock-free first-in-first-out queue implementation

• US 7,836,228 B1
• Filed: 10/15/2004
• Issued: 11/16/2010
• Est. Priority Date: 06/18/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Shalev, Ori, Shavit, Nir, Moir, Mark
• Primary Examiner(s): Hafiz; Tariq
• Assistant Examiner(s): Vidwan; Jasjit S
• Application Number:
  US10/966,465
• Time in Patent Office: 2,223 Days
• Field of Search: 719/311, 719/312, 719/313, 719/314, 711/147, 710/20, 710/21, 710/29, 710/33, 710/35, 710/36, 710/52
• US Class Current: 710/52
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

A scalable first-in-first-out queue implementation adjusts to load on a host system. The scalable FIFO queue implementation is lock-free and linearizable, and scales to large numbers of threads. The FIFO queue implementation includes a central queue and an elimination structure for eliminating enqueue-dequeue operation pairs. The elimination mechanism tracks enqueue operations and/or dequeue operations and eliminates without synchronizing on the FIFO queue implementation.

Claims

1. A method, comprising:

using a computer to perform;

providing a shared first-in-first-out (FIFO) queue that includes a central queue and an elimination data structure, wherein the elimination data structure comprises one or more entries each indicating an enqueue or dequeue operation to attempt to eliminate as part of an enqueue-dequeue operation pair;

receiving a request for an enqueue operation that would add an element to the FIFO queue or a dequeue operation that would remove an element from the FIFO queue;

in response to said receiving, dynamically determining whether to allow access to the central queue to add an element to or remove an element from the central queue as specified by the request, or to attempt elimination of an enqueue-dequeue operation pair comprising the requested enqueue or dequeue operation, wherein attempting elimination comprises;

updating one or more entries of the elimination data structure; and

examining one or more entries of the elimination data structure in an attempt to locate a corresponding enqueue or dequeue operation with which to form the enqueue-dequeue operation pair;

 

wherein said determining comprises determining whether the elimination would result in invalid behavior for the FIFO queue; and

allowing access to the central queue or attempting elimination without accessing the central queue, dependent on results of said determining.

2. The method of claim 1, wherein said determining is dependent on a heuristic for adaptation to load on the system.

3. The method of claim 2, wherein the heuristic is inexpensive to evaluate and limits write access to a common location of the FIFO queue by concurrently executing operations.

4. The method of claim 2, wherein the heuristic eventually attempts to complete the requested enqueue or dequeue operation on the shared FIFO queue and ensures lock-freedom.

5. The method of claim 4, wherein the heuristic avoids frequent attempts to complete the requested enqueue or dequeue operation on the central queue when the load is high on the system.

6. The method of claim 2, wherein the heuristic causes elimination to be attempted in response to failure of an attempted access of the central queue.

7. The method of claim 6, further comprising using the computer to perform repeating said attempting elimination if the elimination does not succeed.

8. The method of claim 1, wherein said attempting elimination comprises:

attempting to synchronize an enqueue operation and a dequeue operation indicated by entries of the elimination data structure to form an enqueue-dequeue operation pair for elimination.

9. The method of claim 8, wherein said forming an enqueue-dequeue operation pair comprises determining whether sufficient operations have been performed to allow elimination without violating behavior for the FIFO queue.

10. The method of claim 9, wherein said determining whether sufficient operations have been performed comprises comparing an enqueue order value of a head of the central queue with an enqueue order value of a previously observed tail of the central queue.

11. The method of claim 1, wherein said attempting elimination comprises:

an enqueue operation indicating in a tracking data structure entry a first value to be enqueued and an enqueue order value for the first value with respect to a tail of the central queue; and

a dequeue operation, which corresponds to the enqueue operation, selecting the tracking data structure entry and comparing the enqueue order value of the first value against an enqueue order value of a first element of the central queue to determine whether to allow elimination of the enqueue operation and the dequeue operation based, at least in part, on the comparison.

12. The method of claim 11, wherein the tracking data structure includes a collision array.

13. The method of claim 11, wherein the first element includes either a head of the central queue, or an element adjacent to the head of the central queue, the head element being a dummy element.

14. The method of claim 1, wherein said attempting elimination comprises:

a dequeue operation installing an entry in the elimination data structure; and

an enqueue operation selecting the entry installed by the dequeue operation and examining the installed entry to determine whether elimination of the dequeue operation and the enqueued operation is allowed.

15. The method of claim 1 further comprising:

using the computer to perform determining whether the central queue is empty; and

wherein said attempting elimination is performed in response to determining that the central queue is empty.

16. A computer-readable storage medium storing program instructions computer-executable to:

instantiate a lock-free linearizable shared first-in-first-out (FIFO) queue in a shared memory, wherein the FIFO queue includes;

a central queue; and

an elimination data structure, wherein the elimination data structure comprises one or more entries each indicating an enqueue operation that would add an element to the FIFO queue or a dequeue operation that would remove an element from the FIFO queue; and

form enqueue-dequeue operation pairs that can be eliminated without enqueueing or dequeueing elements from the central queue, wherein each pair comprises at least one entry of the elimination data structure.

17. The computer-readable storage medium of claim 16, wherein a first formed enqueue-dequeue operation pair does not modify variables modified by a second formed enqueue-dequeue operation pair in at least some circumstances.

18. The computer-readable storage medium of claim 17, wherein the at least some circumstances include the central queue being empty.

19. The computer-readable storage medium of claim 16, wherein each element of the central queue indicates a value that has been added to the central queue and an enqueue order value, wherein the enqueue order value corresponds to a tail element of the central queue.

20. The computer-readable storage medium of claim 16, wherein the program instructions are further computer-executable to implement, in response to receiving a request to enqueue or dequeue an element of the FIFO queue, dynamically determining whether to allow access to the central queue to add an element to or remove an element from the central queue as specified by the request, or to attempt elimination of an enqueue-dequeue operation pair.

21. The computer-readable storage medium of claim 20, wherein said dynamically determining comprises applying a heuristic that is dependent on load on a system that hosts the FIFO queue implementation.

22. The computer-readable storage medium of claim 20, wherein elimination is attempted only if the elimination does not cause the FIFO queue to behave invalidly.

23. A method, comprising:

using a computer to perform;

mediating concurrent access to a shared first-in-first-out (FIFO) queue, said mediating comprising;

in response to receiving a request for an enqueue operation that would add an element to the FIFO queue or a dequeue operation that would remove an element from the FIFO queue, determining whether sufficient operations exist for the shared FIFO queue to allow elimination of an enqueue-dequeue operation pair comprising the requested enqueue or dequeue operation; and

eliminating the enqueue-dequeue operation pair if the sufficient operations have been performed;

wherein said determining is dependent on contents of an elimination data structure that is included in the FIFO queue and that comprises one or more entries each indicating an enqueue or dequeue operation on the FIFO queue to attempt to eliminate as part of an enqueue-dequeue operation pair.

24. The method of claim 23, wherein said determining whether sufficient operations have been performed comprises:

a requested dequeue operation determining whether the corresponding enqueue operation is pending; and

the requested dequeue operation determining whether elimination of the enqueue-dequeue operation pair is consistent with expected behavior of the FIFO queue.

25. The method of claim 23, wherein said determining whether sufficient operations have been performed comprises:

a requested enqueue operation determining whether the corresponding dequeue operation is pending; and

the requested enqueue operation determining whether elimination of the enqueue-dequeue operation pair is consistent with expected behavior of the FIFO queue.

26. The method of claim 23, wherein the FIFO queue further includes:

a central queue for values to be enqueued therein and dequeued therefrom.

27. The method of claim 26, wherein elimination is allowed if the central queue is empty.

28. The method of claim 26, wherein each element of the central queue indicates a value that has been added to the central queue and an associated FIFO enqueue order value.

29. The method of claim 28, wherein the enqueue order value is relative to a tail of the central queue.

30. A method comprising:

using a computer to perform;

tracking enqueue and dequeue operations attempting to access a central queue of a shared first-in-first-out (FIFO) queue, wherein the FIFO queue also includes an elimination data structure, wherein the elimination data structure comprises one or more entries, and wherein each entry indicates an enqueue or dequeue operation to attempt to eliminate as part of an enqueue-dequeue operation pair;

determining whether elimination of an enqueue-dequeue operation pair comprising an enqueue operation attempting to add a given value to the FIFO queue and a dequeue operation attempting to remove the given value from the FIFO queue is allowable, wherein the elimination data structure comprises at least one operation of the enqueue-dequeue operation pair, and wherein said determining is dependent on the tracking; and

in response to determining that elimination is allowable, attempting elimination of the enqueue-dequeue operation pair, wherein said attempting elimination comprises updating one or more entries of the elimination data structure.

31. The method of claim 30, wherein the tracking comprises associating an enqueue order value with the given value that the enqueue operation is attempting to add to the FIFO queue.

32. The method of claim 30, wherein said determining comprises:

determining whether the enqueue operation and the dequeue operation are pending; and

determining if elimination of the enqueue-dequeue operation pair would be consistent with expected behavior of the FIFO queue.

33. The method of claim 32, wherein said determining if the elimination would be consistent with expected behavior of the FIFO queue comprises comparing the enqueue order value of a tail of the central queue that was previously observed by the enqueue operation with an enqueue order value of a first element of the central queue.

34. The method of claim 30, wherein access of the FIFO queue is linearizable.

35. The method of claim 30, wherein the FIFO queue is lock-free.

36. The method of claim 30, wherein the central queue of the FIFO queue is configured such that values are enqueued therein and dequeued therefrom.

37. The method of claim 36, further comprising:

using the computer to perform determining whether to access the central queue or to attempt to eliminate the enqueue-dequeue operation pair;

wherein said determining whether elimination is allowable is performed in response to determining that elimination should be attempted.

38. The method of claim 37, wherein said determining whether to access the central queue or to attempt to eliminate the enqueue-dequeue operation pair is dependent on a heuristic.

39. The method of claim 38, wherein the heuristic is dependent on a load on a system that hosts the FIFO queue.

40. The method of claim 30, further comprising using the computer to perform preventing ABA hazards using at least one of:

bounded timestamps, value recycling, or version numbers.

41. A computer program product encoded on one or more machine-readable media, the computer program product comprising:

a first functional sequence executable to determine, in response to receiving a request for an enqueue operation that would add an element to a shared first-in-first-out (FIFO) or a dequeue operation that would remove an element from the FIFO queue, whether to access a central queue of the FIFO queue to add an element to or remove an element from the central queue as specified by the request, or to attempt elimination of an enqueue-dequeue operation pair comprising the requested enqueue or dequeue operation;

a second functional sequence executable to associate a first value with a second value, wherein the first value comprises a value to be enqueued, and wherein the second value is usable in determining whether elimination of the enqueue-dequeue operation pair is allowable; and

a third functional sequence executable to attempt elimination of the enqueue-dequeue operation pair in accordance with the determination by the first functional sequence;

wherein said determining is dependent on contents of an elimination data structure comprising one or more entries;

wherein each entry indicates an enqueue or dequeue operation on the FIFO queue to attempt to eliminate as part of an enqueue-dequeue operation pair; and

wherein attempting elimination comprises updating one or more entries of the elimination data structure.

42. The computer program product of claim 41, wherein the second functional sequence is executable to attempt to enqueue the first value in the central queue.

43. The computer program product of claim 42, wherein the third functional sequence is executed in response to the first functional sequence determining that elimination should be attempted elimination or the second functional sequence failing to enqueue the first value.

44. The computer program product of claim 41, wherein the first functional sequence determines whether to access the central queue dependent on a heuristic that corresponds to system load.

45. The computer program product of claim 41, wherein to attempt elimination of the enqueue-dequeue operation pair, the third functional sequence is executable to select an entry in the elimination data structure and to attempt to indicate the first and second values in the selected elimination data structure entry.

46. The computer program product of claim 45, wherein the attempt to indicate the first and second values fails if the selected entry is not empty.

47. The computer program product of claim 46, wherein an entry in the elimination data structure is indicated as empty if it contains a non-pointer special value.

48. The computer program product of claim 46, wherein indicating the first and second values comprises the third functional sequence storing, in the selected entry, a reference to a node that indicates the first and second values.

49. The computer program product of claim 41, further comprising a fourth functional sequence executable to attempt to dequeue the first value from the central queue.

50. The computer program product of claim 49, further comprising a fifth functional sequence executable to execute the first functional sequence, and to execute the fourth functional sequence if the first functional sequence determines that the FIFO queue should be accessed.

51. The computer program product of claim 50, further comprising a sixth functional sequence executable to attempt to eliminate the enqueue-dequeue operation pair if the first functional sequence determines that elimination should be attempted.

52. The computer program product of claim 51, wherein to attempt to eliminate the enqueue-dequeue operation pair, the sixth functional sequence is executable to determine whether sufficient operations have been performed to allow elimination.

53. The computer program product of claim 52, wherein said determining whether sufficient operations have been performed comprises:

determining whether the second value is less than a third value associated with a head of the central queue; and

if so, eliminating the attempted enqueue and dequeue of the first value.

54. The computer program product of claim 53, wherein the head of the central queue hosts the third value.

55. A system, comprising:

a computer-readable storage medium storing a set of one or more store elements operable to host a scalable lock-free first-in-first-out (FIFO) queue, wherein the FIFO queue includes a central queue and an elimination data structure, and wherein the elimination data structure comprises one or more entries each indicating an enqueue or dequeue operation to attempt to eliminate as part of an enqueue-dequeue operation pair; and

means for controlling access to the FIFO queue by linearizable enqueue operations that would add an element to the FIFO queue and dequeue operations that would remove an element from the FIFO queue dependent on load on the system, wherein said controlling access comprises determining whether to attempt to eliminate the linearizable operations in enqueue-dequeue operation pairs or to access the FIFO queue to add elements thereto or remove elements therefrom, in accordance with the system load; and

means for attempting elimination of enqueue-dequeue operations pairs, wherein attempting elimination comprises updating one or more entries of the elimination data structure.

56. The system of claim 55, wherein said controlling access is dependent on a heuristic.

57. The system of claim 55, further comprising means for tracking enqueue and dequeue operations for the central queue.

58. A computer readable storage medium storing program instructions computer-executable to implement:

a first-in-first-out (FIFO) queue, wherein the FIFO queue comprises;

a central queue for values to be enqueued therein and dequeued therefrom, wherein each element of the central queue indicates a value that has been enqueued and an associated enqueue order value; and

an elimination data structure comprising one or more entries to attempt to eliminate as part of an enqueue-dequeue operation pair, wherein each entry indicates an enqueue operation that would add an element to the FIFO queue or dequeue operation that would remove an element from the FIFO queue, and wherein attempting elimination comprises updating one or more entries of the elimination data structure.

59. The computer readable storage medium of claim 58, wherein the elimination data structure includes a collision array.

60. The computer readable storage medium of claim 58, wherein each element of the elimination data structure indicates a version for the indicated operation.

61. The computer readable storage medium of claim 58, wherein each element of the elimination data structure indicates a timestamp corresponding to the indicated operation.