Method and apparatus for implementing a shared message queue using a list structure

• US 6,862,595 B1
• Filed: 10/02/2000
• Issued: 03/01/2005
• Est. Priority Date: 10/02/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Warnes, James H., Flaherty, Dermot J., Surman, David H., Elko, David A., Nick, Jeffrey M., Dievendorff, Richard, Westcott, Douglas W.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): PANNALA, SATHYANARAYA R
• Application Number:
  US09/677,341
• Time in Patent Office: 1,611 Days
• Field of Search: 707/104.1, 707/8, 709102-103, 709/314, 380/30, 710/200
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A method and apparatus for implementing a shared message queue using a list structure. A put list is defined comprising a sequence of list entries, each of which corresponds to a message in the queue and has an associated list entry key. Each list entry key corresponding to an uncommitted message falls within an uncommitted key range defining an uncommitted portion of the put list, while each list entry key corresponding to a committed message falls within a committed key range defining a committed portion of the put list. To write a message to the queue, a list entry is added to the put list having a list entry key within the uncommitted key range.

Claims

1. A method of implementing a shared message queue using a list structure comprising the steps of:

defining a list comprising a sequence of list entries, each of said list entries corresponding to a message in said queue and having an associated list entry key, each list entry key corresponding to an uncommitted message falling within an uncommitted key range defining an uncommitted portion of said list and each list entry key corresponding to a committed message falling within a committed key range defining a committed portion of said list;

in response to a request to write a message to said queue, adding a list entry to said list having a list entry key within said uncommitted key range; and

in response to a request to commit said message to said queue, modifying the list entry key associated with said list entry to fall within said committed key range to move said list entry to the committed portion of said list.

2. The method of claim 1 in which list entries in said uncommitted portion of said list have a defined order as determined by said list entry keys that is preserved when said list entries are moved to the committed portion of said list.

3. The method of claim 1, comprising the further step of:

in response to a request to read a message from said queue, retrieving a list entry whose list entry key has an extreme value in said committed key range.

4. The method of claim 3 in which said extreme value is a lowest value in said committed key range.

5. The method of claim 1 in which said list is a first list, said method comprising the further step of:

in response to a request to read a message from said queue, moving a list entry from the committed portion of said fist list to a second list.

6. The method of claim 5, further comprising the step of:

in response to a request to abort a read of said message from said queue, moving said list entry back from said second list to the committed portion of said first list.

7. The method of claim 5, further comprising the step of:

in response to a request to commit a read of said message from said queue, removing said list entry from said second list.

8. The method of claim 1 in which said list entry keys in said uncommitted key range are assigned in order of message priority.

9. The method of claim 8 in which said list entry keys in said uncommitted key range are assigned in order of arrival time for messages of a given priority.

10. The method of claim 1 in which each list entry key has a more significant portion indicating the list portion to which the corresponding list entry belongs and a less significant portion indicating the order of said list entry in said list portion.

11. The method of claim 1, further comprising the step of:

in response to a request from a requester to wait for a message in said queue;

detecting a change in state of the committed portion of said queue from an empty state to a not-empty state;

in response to detecting a change in state of the committed portion of said queue from an empty state to a not-empty sate, notifying said requester of said change of state.

12. Apparatus for implementing a shared message queue using a list structure, comprising:

means for defining a list comprising a sequence of list entries, each of said list entries corresponding to a message in said queue and having an associated list entry key, each list entry key corresponding to an uncommitted message falling within an uncommitted key range defining an uncommitted portion of said list and each list entry key corresponding to a committed message falling within a committed key range defining a committed portion of said list;

means responsive to a request to write a message to said queue for adding a list entry to said list having a list entry key within said uncommitted key range; and

means responsive to a request to commit said message to said queue for modifying the list entry key associated with said list entry to fall within said committed key range to move said list entry to the committed portion of said list.

13. The apparatus of claim 12, further comprising:

means responsive to a request to read a message from said queue for retrieving a list entry whose list entry key has an extreme value in said committed key range.

14. The apparatus of claim 12 in which said list is a first list, said apparatus further comprising:

means responsive to a request to read a message from said queue for moving a list entry from the committed portion of said first list to a second list defined for said queue.

15. The apparatus of claim 14, further comprising:

means responsive to a request to abort a read of said message from said queue for moving said list entry back from said second list to the committed portion of said first list.

16. The apparatus of claim 14, further comprising:

means responsive to a request to commit a read of said message from said queue for removing said list entry from said second list.

17. The apparatus of claim 12, further comprising:

means responsive to a request from a requester to wait for a message in said queue for detecting a change in state of the committed portion of said queue from an empty state to a not-empty state and, in response to detecting said change in state, notifying said requester of said change of state.

18. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for of implementing a shared message queue using a list structure, said method steps comprising:

defining a list comprising a sequence of list entries, each of said list entries corresponding to a message in said queue and having an associated list entry key, each list entry key corresponding to an uncommitted message falling within an uncommitted key range defining an uncommitted portion of said list and each list entry key corresponding to a committed message falling within a committed key range defining a committed portion of said list;

in response to a request to write a message to said queue, adding a list entry to said list having a list entry key within said uncommitted key range; and

in response to a request to commit said message to said queue, modifying the list entry key associated with said list entry to fall within said committed key range to move said list entry to the committed portion of said list.

19. The program storage device of claim 18, comprising the further step of:

in response to a request to read a message from said queue, retrieving a list entry whose list entry key has an extreme value in said committed key range.

20. The program storage device of claim 18 in which said list is a first list, said method comprising the further step of:

in response to a request to read a message from said queue, moving a list entry from the committed portion of said first list to a second list defined for said queue.

21. The program storage device of claim 20, further comprising the step of:

in response to a request to abort a read of said message from said queue, moving said list entry back from said second list to the committed portion of said first list.

22. The program storage device of claim 20, further comprising the step of:

in response to a request to commit a read of said message from said queue, removing said list entry from said second list.

23. The program storage device of claim 18, further comprising the step of:

in response to a request from a requester to wait for a message in said queue;

detecting a change in state of the committed portion of said queue from an empty state to a not-empty state;

in response to detecting a change in state of the committed portion of said queue from an empty state to a not-empty state, notifying said requester of said change of state.