System and method for using a sequencer in a concurrent priority queue

• US 9,110,715 B2
• Filed: 02/28/2013
• Issued: 08/18/2015
• Est. Priority Date: 02/28/2013
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Otenko, Oleksandr
• Primary Examiner(s): SWIFT, CHARLES M
• Application Number:
  US13/781,493
• Publication Number:
  US 20140245313A1
• Time in Patent Office: 901 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A system and method can support a concurrent priority queue. The concurrent priority queue allows a plurality of threads to interact with the priority queue. The priority queue can use a sequencer to detect and order a plurality of threads that contend for one or more requests in the priority queue. Furthermore, the priority queue operates to reduce the contention among the plurality of threads.

Claims

1. A system comprising:

one or more microprocessors;

a priority queue for prioritizing a plurality of requests received from a plurality of consumers;

wherein the priority queue comprises a synchronized block having a continuation passing function and manages a plurality of threads for non-blocking receiving of said plurality of requests from said plurality of consumers;

wherein the priority queue comprises a calendar ring buffer comprising a calendar ring buffer memory which operates to store a first subset of said plurality of requests having a target response time less than a pre-configured time;

wherein the priority queue comprises an outlier list comprising an outlier list memory which operates to store a second subset of said plurality of requests having a target response time greater than the pre-configured time;

wherein the priority queue comprises a sequencer which operates to enforce a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list; and

wherein the priority queue operates to reduce the contention among the plurality of consumers and the plurality of requests.

2. The system according to claim 1, wherein:

each of said first subset of said plurality of requests is stored in the calendar ring buffer at a position dependent upon a value of a QoS associated with each of said first subset of said plurality of requests.

3. The system according to claim 1, wherein:

the pre-configured time is specified to be two seconds.

4. The system according to claim 1, wherein:

the sequencer implements a ticket mechanism to enforce a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list without requiring a synchronization mechanism or a lock mechanism.

5. The system according to claim 1, wherein:

the priority queue contains a list of stolen requests that can be used to reduce contention on the calendar ring when workload is intensive, wherein the list of stolen requests contains one or more requests that land on a same calendar entry.

6. The system according to claim 1, wherein:

the priority queue contains a fast lane that can be used to support cooperative concurrency.

7. The system according to claim 1, wherein:

the sequencer uses a ticket mechanism to enforce a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list.

8. The system according to claim 7, wherein:

the ticket mechanism keeps a reader count that is increased every time a consumer tries to access the priority queue.

9. The system according to claim 7, wherein:

the sequencer operates to issue a ticket to a consumer of said plurality of consumers, wherein the ticket allows the consumer to access the priority queue.

10. The system according to claim 7, wherein:

the ticket mechanism keeps a reader count that is increased when a consumer of said plurality of consumers tries to access the priority queue; and

wherein said reader count is used to detect contention between said plurality of consumers and said plurality of requests.

11. A method for prioritizing a plurality of requests received from a plurality of consumers in a middleware machine environment, the method comprising;

receiving said plurality of requests from said plurality of consumers using a synchronization block having a continuation passing function which manages a plurality of threads for non-blocking receiving of said plurality of requests from said plurality of consumers;

storing a first subset of said plurality of requests having a target response time less than a pre-configured time in a calendar ring buffer;

storing a second subset of said plurality of requests having a target response time greater than the pre-configured time in an outlier list;

enforcing a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list using a sequencer; and

reducing contention among said plurality of consumers and said plurality of requests.

12. The method of claim 11, further comprising:

storing each of said first subset of said plurality of requests in the calendar ring buffer at a position dependent upon a value of a QoS associated with said each of said first subset of said plurality of requests.

13. The method of claim 11, wherein the pre-configured time is specified to be two seconds.

14. The method of claim 11, further comprising:

implementing a ticket mechanism in said sequencer to enforce said first-in-first-out order for said second subset of said plurality of requests stored in the outlier list without requiring a synchronization mechanism or a lock mechanism.

15. The method of claim 11, further comprising:

storing a list of stolen requests that can be used to reduce contention on the calendar ring when workload is intensive, wherein the list of stolen requests contains one or more requests that land on a same calendar entry.

16. The method of claim 11, further comprising:

providing a fast lane which supports cooperative concurrency.

17. The method of claim 11, further comprising:

implementing a ticket mechanism in said sequencer to enforce a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list; and

maintaining with said ticket mechanism a reader count that is increased every time a consumer tries to access the priority queue.

18. The method of claim 11, further comprising:

implementing a ticket mechanism in said sequencer to enforce a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list; and

issuing a ticket to a consumer of said plurality of consumers, wherein the ticket allows the consumer to access said outlier list.

19. The method of claim 11, further comprising:

implementing a ticket mechanism in said sequencer to enforce a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list;

maintaining with said ticket mechanism a reader count that is increased every time a consumer tries to access the priority queue; and

used said reader count to detect contention between said plurality of consumers and said plurality of requests.

20. A non-transitory computer readable medium including instructions stored thereon for prioritizing a plurality of requests received from a plurality of consumers in a middleware machine environment, which instructions, when executed by a computer, cause the computer to perform steps comprising:

receiving said plurality of requests from said plurality of consumers using a synchronization block having a continuation passing function which manages a plurality of threads for non-blocking receiving of said plurality of requests from said plurality of consumers;

storing a first subset of said plurality of requests having a target response time less than a pre-configured time in a calendar ring buffer;

storing a second subset of said plurality of requests having a target response time greater than the pre-configured time in an outlier list;

enforcing a first-in-first-out order for said second subset of said plurality of requests stored in the outlier list using a sequencer; and

reducing contention among said plurality of consumers and said plurality of requests.