Facilitating communication within shared memory environments using lock-free queues

• US 20050283577A1
• Filed: 06/22/2004
• Published: 12/22/2005
• Est. Priority Date: 06/22/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Xue, Hanhong, Sivaram, Rajeev
• Granted Patent: US 7,219,198 B2
• Time in Patent Office: Days
• US Class Current: 711/152
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

Lock-free queues of a shared memory environment are used to facilitate communication within that environment. The lock-free queues can be used for interprocess communication, as well as intraprocess communication. The lock-free queues are structured to minimize the use of atomic operations when performing operations on the queues, and to minimize the number of enqueue/dequeue operations to be performed on the queues.

Claims

26. A method of processing queues of a shared memory environment, said method comprising:

enqueuing a message on a lock-free queue of the shared memory environment using a single atomic operation, the lock-free queue capable of being written to by a plurality of processing entities.

27. A method of processing queues of a shared memory environment, said method comprising:

dequeuing a message from a lock-free queue of the shared memory environment absent an atomic operation, the lock-free queue capable of being written to by a plurality of processing entities.

28. A shared memory comprising:

a queue, said queue comprising;

a first end of the queue, said first end being concurrently accessible by a plurality of processing entities;

a second end of the queue, said second end being non-concurrently accessible by a plurality of processing entities; and

wherein said queue is lock-free and sized to not reach a full condition.

29. A system of facilitating communication within a shared memory environment, said system comprising:

a lock-free queue of the shared memory environment for use in communication, said lock-free queue being concurrently accessible at one end of the lock-free queue for writing to the lock-free queue by a plurality of processing entities of the shared memory environment, being non-concurrently accessible at another end of the lock-free queue, and sized to not reach a full condition; and

means for employing, by a processing entity of the shared memory environment, the lock-free queue.

1. A method of facilitating communication within a shared memory environment, said method comprising:

employing, by a processing entity of the shared memory environment, a lock-free queue of the shared memory environment for use in communication, said lock-free queue being concurrently accessible at one end of the lock-free queue for writing to the lock-free queue by a plurality of processing entities of the shared memory environment, being non-concurrently accessible at another end of the lock-free queue, and being sized to not reach a full condition.

2. The method of claim 1, wherein the processing entity comprises a process, and the plurality of processing entities comprise a plurality of processes.

3. The method of claim 1, wherein the processing entity comprises a thread of a process, and the plurality of processing entities comprise a plurality of threads of the process.

4. The method of claim 1, wherein the employing comprises enqueuing an element on the lock-free queue using a single atomic operation.

5. The method of claim 4, wherein the enqueuing comprises:

determining an identifier of a tail of the lock-free queue;

incrementing the identifier of the tail to identify a new tail; and

storing at the tail identified by the identifier prior to being incremented an indicator associated with the element.

6. The method of claim 5, wherein the element indicated by the indicator stored at the tail is located in shared memory.

7. The method of claim 5, wherein the determining and the incrementing are performed by the single atomic operation.

8. The method of claim 7, wherein the single atomic operation comprises a fetch and add operation.

9. The method of claim 1, wherein the employing comprising dequeuing an element of the lock-free queue absent an atomic operation.

10. The method of claim 9, wherein the dequeuing comprises:

determining an identifier of a head of the lock-free queue; and

retrieving from the head identified by the identifier an indicator associated with the element.

11. The method of claim 10, wherein the dequeuing further comprises incrementing the identifier of the head to identify a new head.

12. The method of claim 10, wherein the element indicated by the indicator retrieved from the head is located in shared memory.

13. The method of claim 10, further comprising:

checking whether the lock-free queue is empty; and

proceeding with the determining the identifier, in response to the checking indicating a non-empty lock-free queue.

14. The method of claim 10, further comprising:

checking whether the lock-free queue at the head identified by the identifier is empty; and

waiting until the head is not empty before proceeding to the retrieving of the indicator.

15. The method of claim 1, wherein the one end is at a tail of the lock-free queue and the another end is at a head of the lock-free queue.

16. The method of claim 1, wherein the employing comprises:

obtaining an indicator of a slot in shared memory to place data;

storing data in the slot specified by the indicator; and

providing the indicator to the lock-free queue to enable access to the data stored in the slot.

17. The method of claim 16, wherein the slot is a slot used by an incoming message to the processing entity.

18. The method of claim 17, wherein the incoming message is a last received message by the processing entity.

19. The method of claim 16, wherein the indicator is obtained from a free slot data structure.

20. The method of claim 16, wherein the providing the indicator comprises:

atomically determining an identifier of a tail of the lock-free queue and incrementing the identifier of the tail to identify a new tail; and

storing at the tail identified by the identifier prior to being incremented the indicator of the slot.

21. The method of claim 1, wherein the employing comprises:

obtaining from the lock-free queue an indicator of a slot in shared memory storing data to be processed; and

processing data of the slot identified by the indicator.

22. The method of claim 21, wherein the obtaining comprises:

determining an identifier of a head of the lock-free queue; and

retrieving from the head identified by the identifier the indicator of the slot.

23. The method of claim 21, further comprising saving the slot for an outgoing message.

24. The method of claim 23, further comprising:

determining whether another slot is saved; and

returning the another slot to a free slot data structure, in response to the determining indicating the another slot is saved.

25. The method of claim 21, further comprising returning the slot to a free slot data structure.

30. The system of claim 29, wherein the means for employing comprises means for enqueuing an element on the lock-free queue using a single atomic operation.

31. The system of claim 30, wherein the means for enqueuing comprises:

means for determining an identifier of a tail of the lock-free queue;

means for incrementing the identifier of the tail to identify a new tail; and

means for storing at the tail identified by the identifier prior to being incremented an indicator associated with the element.

32. The system of claim 31, wherein the means for determining and the means for incrementing are performed by the single atomic operation.

33. The system of claim 29, wherein the means for employing comprising means for dequeuing an element of the lock-free queue absent an atomic operation.

34. The system of claim 33, wherein the means for dequeuing comprises:

means for determining an identifier of a head of the lock-free queue; and

means for retrieving from the head identified by the identifier an indicator associated with the element.

35. The system of claim 34, further comprising:

means for checking whether the lock-free queue is empty; and

means for proceeding with the determining the identifier, in response to the checking indicating a non-empty lock-free queue.

37. The system of claim 29, wherein the means for employing comprises:

means for obtaining an indicator of a slot in shared memory to place data;

means for storing data in the slot specified by the indicator; and

means for providing the indicator to the lock-free queue to enable access to the data stored in the slot.

38. The system of claim 37, wherein the slot is a slot used by an incoming message to the processing entity.

39. The system of claim 38, wherein the incoming message is a last received message by the processing entity.

40. The system of claim 37, wherein the indicator is obtained from a free slot data structure.

41. The system of claim 37, wherein the means for providing the indicator comprises:

means for atomically determining an identifier of a tail of the lock-free queue and means for incrementing the identifier of the tail to identify a new tail; and

means for storing at the tail identified by the identifier prior to being incremented the indicator of the slot.

42. The system of claim 29, wherein the means for employing comprises:

means for obtaining from the lock-free queue an indicator of a slot in shared memory storing data to be processed; and

means for processing data of the slot identified by the indicator.

43. The system of claim 42, wherein the means for obtaining comprises:

means for determining an identifier of a head of the lock-free queue; and

means for retrieving from the head identified by the identifier the indicator of the slot.

44. The system of claim 42, further comprising means for saving the slot for an outgoing message.

45. The system of claim 44, further comprising:

means for determining whether another slot is saved; and

means for returning the another slot to a free slot data structure, in response to the determining indicating the another slot is saved.

35-1. The system of claim 34, further comprising:

means for checking whether the lock-free queue at the head identified by the identifier is empty; and

means for waiting until the head is not empty before proceeding to the retrieving of the indicator.

46. A system of facilitating communication within a shared memory environment, said system comprising:

a processing entity of the shared memory environment to employ a lock-free queue of the shared memory environment for use in communication, said lock-free queue being concurrently accessible at one end of the lock-free queue for writing to the lock-free queue by a plurality of processing entities of the shared memory environment, being non-concurrently accessible at another end of the lock-free queue, and sized to not reach a full condition.

47. An article of manufacture comprising:

at least one computer usable medium having computer readable program code logic to manage facilitating communication within a shared memory environment, the computer readable program code logic comprising;

employ logic to employ, by a processing entity of the shared memory environment, a lock-free queue of the shared memory environment for use in communication, said lock-free queue being concurrently accessible at one end of the lock-free queue for writing to the lock-free queue by a plurality of processing entities of the shared memory environment, being non-concurrently accessible at another end of the lock-free queue, and sized to not reach a full condition.

48. The article of manufacture of claim 47, wherein the employ logic comprises enqueue logic to enqueue an element on the lock-free queue using a single atomic operation.

49. The article of manufacture of claim 48, wherein the enqueue logic comprises:

determine logic to determine an identifier of a tail of the lock-free queue;

increment logic to increment the identifier of the tail to identify a new tail; and

store logic to store at the tail identified by the identifier prior to being incremented an indicator associated with the element.

50. The article of manufacture of claim 49, wherein the determining and the incrementing are performed by the single atomic operation.

51. The article of manufacture of claim 47, wherein the employ logic comprises dequeue logic to dequeue an element of the lock-free queue absent an atomic operation.

52. The article of manufacture of claim 51, wherein the dequeue logic comprises:

determine logic to determine an identifier of a head of the lock-free queue; and

retrieve logic to retrieve from the head identified by the identifier an indicator associated with the element.

53. The article of manufacture of claim 52, further comprising:

check logic to check whether the lock-free queue is empty; and

proceed logic to proceed with the determining the identifier, in response to the checking indicating a non-empty lock-free queue.

54. The article of manufacture of claim 52, further comprising:

check logic to check whether the lock-free queue at the head identified by the identifier is empty; and

wait logic to wait until the head is not empty before proceeding to the retrieving of the indicator.

55. The article of manufacture of claim 47, wherein the employ logic comprises:

obtain logic to obtain an indicator of a slot in shared memory to place data;

store logic to store data in the slot specified by the indicator; and

provide logic to provide the indicator to the lock-free queue to enable access to the data stored in the slot.

56. The article of manufacture of claim 55, wherein the slot is a slot used by an incoming message to the processing entity.

57. The article of manufacture of claim 56, wherein the incoming message is a last received message by the processing entity.

58. The article of manufacture of claim 55, wherein the indicator is obtained from a free slot data structure.

59. The article of manufacture of claim 55, wherein the provide logic comprises:

logic to atomically determine an identifier of a tail of the lock-free queue and to increment the identifier of the tail to identify a new tail; and

store logic to store at the tail identified by the identifier prior to being incremented the indicator of the slot.

60. The article of manufacture of claim 47, wherein the employ logic comprises:

obtain logic to obtain from the lock-free queue an indicator of a slot in shared memory storing data to be processed; and

process logic to process data of the slot identified by the indicator.

61. The article of manufacture of claim 60, wherein the obtain logic comprises:

determine logic to determine an identifier of a head of the lock-free queue; and

retrieve logic to retrieve from the head identified by the identifier the indicator of the slot.

62. The article of manufacture of claim 60, further comprising save logic to save the slot for an outgoing message.

63. The article of manufacture of claim 62, further comprising:

determine logic to determine whether another slot is saved; and

return logic to return the another slot to a free slot data structure, in response to the determining indicating the another slot is saved.