SYSTEM AND METHOD FOR USING A SEQUENCER IN A CONCURRENT PRIORITY QUEUE

• US 20140245313A1
• Filed: 02/28/2013
• Published: 08/28/2014
• 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
• Granted Patent: US 9,110,715 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• 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 for supporting a concurrent priority queue, comprising:

one or more microprocessors;

a priority queue that allows a plurality of threads to interact with the priority queue; and

a sequencer, running on the one or more microprocessors, wherein the sequencer operates to detect a plurality of threads that contend for one or more requests in the priority queue, and

wherein the priority queue operates to reduce the contention among the plurality of threads.

2. The system according to claim 1, wherein:

the priority queue contains a calendar ring, wherein the calendar ring operates to store various requests with a target response time less than a pre-configured quality of service (QoS).

3. The system according to claim 2, wherein:

the pre-configured quality of service (QoS) is specified to be about two seconds.

4. The system according to claim 2, wherein:

a bit map updated in synchronization with the calendar ring is used for faster scanning.

5. The system according to claim 2, 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 2, 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 that can order the plurality of threads.

8. The system according to claim 7, wherein:

the ticket mechanism keeps a reader count that is increased everytime when 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 contending thread, wherein the ticket allows the contending thread to access the priority queue.

10. The system according to claim 1, wherein:

the sequencer operates to preserve a first-in-first-out (FIFO) order of a outlier list in the priority queue.

11. A method for supporting a concurrent priority queue, comprising:

allowing a plurality of threads to interact with the concurrent priority queue;

detecting, via a sequencer, a plurality of threads that contend for one or more requests in the priority queue,

reducing, via the priority queue, the contention among the plurality of threads.

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

containing a calendar ring in the priority queue, wherein the calendar ring operates to store various requests with a target response time less than a pre-configured quality of service (QoS).

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

specifying the pre-configured quality of service (QoS) to be about two seconds.

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

using a bit map updated in synchronization with the calendar ring for faster scanning.

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

Associating, with the priority queue, 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 according to claim 12, further comprising:

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

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

using, via the sequencer, a ticket mechanism that can order the plurality of threads.

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

Keeping, via the ticket mechanism, a reader count that is increased everytime when a consumer try to access the priority queue.

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

issuing, via the sequencer, a ticket to a contending thread, wherein the ticket allows the contending thread to access the priority queue.

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

allowing a plurality of threads to interact with the concurrent priority queue;

detecting, via a sequencer, a plurality of threads that contend for one or more requests in the priority queue,

reducing, via the priority queue, the contention among the plurality of threads.