System and method for supporting a lazy sorting priority queue in a computing environment

• US 9,588,733 B2
• Filed: 01/29/2014
• Issued: 03/07/2017
• Est. Priority Date: 09/22/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Otenko, Oleksandr
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Borromeo, Juanito
• Application Number:
  US14/167,792
• Publication Number:
  US 20150212794A1
• Time in Patent Office: 1,133 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 13/22 using successive scanning, e.g. polling G06F13/24 takes precedence
• CPC Class Codes: G06F 2205/067 Bidirectional FIFO, i.e. system allowing data transfer in two directions
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 2213/2806 Space or buffer allocation for DMA transfers
• CPC Class Codes: G06F 5/065 Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A system and method can support queue processing in a computing environment. A lazy sorting priority queue in a concurrent system can include a priority queue and one or more buffers. The one or more buffers, which can be first-in first-out (FIFO) buffers, operate to store one or more requests received from one or more producers, and move at least one message to the priority queue when no consumer is waiting for processing a request. Furthermore, the priority queue operates to prioritize one or more incoming requests received from the one or more buffers, and allows one or more consumers to pick up the requests based on priority.

Claims

1. A system for supporting queue processing in a computing environment, the system comprising:

a processor;

a priority queue operable to store a set of priority service requests and to prioritize the set of priority service requests as a set of prioritized service requests stored in the priority queue, wherein the set of prioritized service requests are available to an associated consumer in operative communication with the system for processing by the associated consumer;

one or more buffers, wherein each of the one or more buffers is operable to store one or more service requests received from an associated producer in operative communication with the system; and

a thread executable to determine a lack of associated consumers waiting for processing the set of prioritized service requests, and to selectively move a service request of the one or more service requests stored in the one or more buffers to the priority queue as a priority service request exclusively in response to the determining the lack of associated consumers waiting for processing the set of prioritized service requests.

2. The system according to claim 1, wherein:

each of said one or more buffers is configured to allow the associated consumer to process said one or more service requests in a first-in first-out (FIFO) order.

3. The system according to claim 1, wherein:

the thread is responsive to the associated producer to;

obtain a unique ticket from a ticketinq system associate with the producer,

go through a buffer sequencer that is associated with a selected buffer selected from said one or more buffers, and

store a service request in the selected buffer at a position identified by the unique ticket.

4. The system according to claim 3, wherein:

the thread is responsive to a plurality of associated producers to store multiple service requests in the selected buffer concurrently.

5. The system according to claim 1, wherein:

the thread is responsive to the associated consumer to;

obtain a unique ticket from a ticketing system associated with the consumer,

go through a consumer sequencer, and

take i) a priority service request from the priority queue or ii) a service request from said one or more buffers.

6. The system according to claim 5, wherein:

the thread is responsive to the associated consumer to;

retrieve a priority service request from the priority queue responsive to the priority queue being not empty, or

retrieve a first service request from said one or more buffers responsive to the priority queue being empty.

7. The system according to claim 5, wherein:

the thread is operable to check both the consumer sequencer and the ticketing system associated with the consumer.

8. The system according to claim 7, wherein:

the thread is operable to return when there is at least one associated consumer waiting for processing the set of prioritized service requests.

9. The system according to claim 1, wherein:

the thread is operable to maintain the priority queue short to allow for lower complexity in performing an enqueing operation at the priority queue.

10. The system according to claim 9, wherein the thread is operable to:

permit the priority queue to become empty when one or more associated consumers are waiting for processing the set of prioritized service requests, and to process the one or more service requests of the one or more buffers in a first-in first-out (FIFO) order.

11. A method for supporting queue processing in a computing environment, the method comprising:

providing a priority queue wherein the priority queue operable to store a set of priority service requests and to prioritize the set of priority service requests as a set of prioritized service requests stored in the priority queue, wherein the set of prioritized service requests are available to an associated consumer in operative communication with the system for processing by the associated consumer;

providing one or more buffers, wherein each of the one or more buffers is operable to store one or more service requests received from an associated producer in operative communication with the system; and

providing a thread executable to determine a lack of associated consumers waiting for processing the set of prioritized service requests, and the thread being executable to selectively move a service request of the one or more service requests stored in the one or more buffers to the priority queue as a priority service request exclusively in response to the determining the lack of associated consumers waiting for processing the set of prioritized service requests.

12. The method of claim 11, further comprising:

allowing the associated producer to process said one or more service requests in a first-in first-out (FIFO) order.

13. The method according to claim 11, further comprising:

obtaining, via the thread responsive to the associated producer, a unique ticket from a ticketinq system associate with the producer,

going via the thread through a buffer sequencer that is associated with a selected buffer selected from said one or more buffers, and

storing via the thread a service request in the selected buffer at a position identified by the unique ticket.

14. The method according to claim 13, further comprising:

allowing via the thread responsive to the associated producer a plurality of associated producers to store multiple service requests in the selected buffer concurrently.

15. The method according to claim 11, further comprising:

obtaining, via the thread responsive to the associated consumer, a unique ticket from a ticketinq system associated with the consumer,

going through a consumer sequencer, and

taking i) a priority service request from the priority queue or ii) a service request from said one or more buffers.

16. The method according to claim 15, further comprising:

retrieving via the thread a priority service request from the priority queue responsive to the priority queue being not empty, or

retrieving via the thread a first service request from said one or more buffers responsive to the priority queue being empty.

17. The method according to claim 15, further comprising:

checking via the thread both the consumer sequencer and the ticketing system associated with the consumer.

18. The method according to claim 17, further comprising:

returning by the thread when there is at least one associated consumer waiting for processing the set of prioritized service requests.

19. The method according to claim 11, further comprising:

maintaining the priority queue short by the thread to allow for lower complexity in performing an enqueing operation at the priority queue, and

allowing the priority queue to become empty by the thread when one or more associated consumers are waiting for processing the set of prioritized service requests, and processing by the thread the one or more service requests in a first-in first-out(FIFO) order.

20. A non-transitory machine readable storage medium having instructions stored thereon that when executed cause a system to perform steps comprising:

operate a priority queue to store a set of priority service requests and to prioritize the st of priority service requests as a set a set of prioritized service requests stored in the priority queue, wherein the set of prioritized service requests are available to an associated consumer in operative communication with the system for processing by the associated consumer;

store in one or more buffers, one or more service requests received from an associated producer in operative communication with the system; and

execute a thread to determine a lack of associated consumers waiting for processing the set of prioritized service requests, and to selectively move by the thread a service request of the one or more service requests stored in the one or more buffers to the priority queue as a priority service request exclusively in response to the determining the lack of associated consumers waiting for processing the set of prioritized service requests.