Patent US2873850A successfully refreshed from Google Patents.
Patent US5826081A successfully refreshed from Google Patents.
US5826081A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Real time thread dispatcher for multiprocessor applications
Assignee: Oracle America Inc
•
Filing: 1996-05-06
•
Granted: 1998-10-20
•
Expires: 2016-05-06
Abstract
Abstract The present invention provides a process scheduler or dispatcher for a multiprocessor system for real time applications. This embodiment of the present invention proposes a dispatcher model that maintains a dispatch queue for each processor and a separate global dispatch queue for unbound higher priority real time threads. A processor has its own queue and a dispatcher. Each queue has a separate schedule lock associated with it to protect scheduling operations. A processor's dispatcher selects a thread for execution from one of the queues in the system as a candidate thread to execute. When a candidate thread is selected for execution, the processor proceeds to verify against threads in the global real time queue and the processor's own dispatch queue to select a highest priority runnable thread in the system. Thus, the present invention allows the dispatcher to prevent race conditions and minimize lock contention while assuring that high-priority threads are dispatched as quickly as possible. The present invention is implemented by a synchronization between the operations of dispatching a thread and making a thread runnable.
Inventors
- 👤 John E. Zolnowsky
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 06:22
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
163 words
A method for scheduling a thread in a multiprocessor system based on a preemptive priority scheduling, said multiprocessor system comprising a plurality of processors, said method comprising: selecting a first thread as a candidate thread to execute from a first local dispatch queue of a plurality of local dispatch queues and a global queue, said plurality of local dispatch queues for storing threads to be scheduled, each of said plurality of local dispatch queues coupled to one of said plurality of processors, said global queue for storing threads to be scheduled, said global queue accessible by each of said plurality of processors; notifying said plurality of processors of the candidate thread; checking whether a higher priority thread having higher priority than said first thread is available in said first local dispatch queue and said global queue; preempting the first thread and selecting the higher priority thread as the candidate thread to execute when said higher priority thread is available; executing the candidate thread.
Claim 2
Independent Claim
163 words
A method for scheduling a thread in a multiprocessor system based on a preemptive priority scheduling, said multiprocessor system comprising a plurality of processors, said method comprising: selecting a first thread as a candidate thread to execute from a first local dispatch queue of a plurality of local dispatch queues and a global queue, said plurality of local dispatch queues for storing threads to be scheduled, each of said plurality of local dispatch queues coupled to one of said plurality of processors, said global queue for storing threads to be scheduled, said global queue accessible by each of said plurality of processors; notifying said plurality of processors of the candidate thread; checking whether a higher priority thread having higher priority than said first thread is available in said first local dispatch queue and said global queue; preempting the first thread and selecting the higher priority thread as the candidate thread to execute when said higher priority thread is available; executing the candidate thread.
Claim 3
Dependent Claim
32 words
The method of claim 1 wherein said step of selecting a thread as a candidate thread to execute further comprises the step of selecting the highest priority thread from said global queue.
Claim 4
Dependent Claim
47 words
The method of claim 2 wherein said step of selecting a thread as a candidate thread to execute further comprises the step of selecting the highest priority thread from one of said plurality of local dispatch queues when there is no runnable thread in said global queue.
Claim 5
Dependent Claim
44 words
The method of claim 3 wherein said step of selecting a thread as a candidate thread to execute further comprises the step of selecting a thread from other processor's local dispatch queue when there is no runnable thread in said processor's local dispatch queue.
Claim 6
Dependent Claim
40 words
The method of claim 4 wherein said step of selecting a thread as a candidate thread to execute further comprises the step of selecting an idle thread when there is no runnable thread in said other processor's local dispatch queue.
Claim 7
Dependent Claim
27 words
The method of claim 1 further comprising the step of: placing a thread on a processor's local dispatch queue when the thread is bound to said processor.
Claim 8
Dependent Claim
24 words
The method of claim 6 further comprising the step of placing the thread on said global queue when the thread has real time property.
Claim 9
Dependent Claim
37 words
The method of claim 7 further comprising the steps of: identifying a last processor that the thread ran on; placing the thread on the last processor's dispatch queue when the thread does not have real time property.
Claim 10
Dependent Claim
29 words
The method of claim 1 wherein said step of notifying processors of the candidate thread comprises: changing a memory register value, said register accessible by said plurality of processors.
Claim 11
Dependent Claim
230 words
An article of manufacture comprising: a computer usable medium having computer readable program code embodied therein for scheduling a thread in a multiprocessor system based on a preemptive priority scheduling, said multiprocessor system comprising a plurality of processors, the computer readable program code in said article of manufacture comprising: computer readable code configured to cause one of said plurality of processors to select a candidate thread to execute using a thread select and verify method comprising the steps of: selecting a first thread as said candidate thread to execute from a first local dispatch queue of a plurality of local dispatch queues and a global queue, said plurality of local dispatch queues for storing threads to be scheduled, each of said plurality of local dispatch queues coupled to one of said plurality of processors, said global queue for storing threads to be scheduled, said global queue accessible by each of said plurality of processors; notifying said plurality of processors of the candidate thread; checking whether a higher priority thread having higher priority than said candidate thread is available in said first local dispatch queue and said global queue; preempting the first thread and selecting the higher priority thread as the candidate thread to execute when said higher priority thread is available; computer readable code configured to cause said one of said plurality of processors to execute the selected candidate thread.
Claim 12
Dependent Claim
230 words
An article of manufacture comprising: a computer usable medium having computer readable program code embodied therein for scheduling a thread in a multiprocessor system based on a preemptive priority scheduling, said multiprocessor system comprising a plurality of processors, the computer readable program code in said article of manufacture comprising: computer readable code configured to cause one of said plurality of processors to select a candidate thread to execute using a thread select and verify method comprising the steps of: selecting a first thread as said candidate thread to execute from a first local dispatch queue of a plurality of local dispatch queues and a global queue, said plurality of local dispatch queues for storing threads to be scheduled, each of said plurality of local dispatch queues coupled to one of said plurality of processors, said global queue for storing threads to be scheduled, said global queue accessible by each of said plurality of processors; notifying said plurality of processors of the candidate thread; checking whether a higher priority thread having higher priority than said candidate thread is available in said first local dispatch queue and said global queue; preempting the first thread and selecting the higher priority thread as the candidate thread to execute when said higher priority thread is available; computer readable code configured to cause said one of said plurality of processors to execute the selected candidate thread.
Claim 13
Dependent Claim
49 words
The article of manufacture of claim 10 wherein said computer readable code configured to cause one of said plurality of processors to select a candidate thread comprises computer readable code configured to cause one of said plurality of processors to select the highest priority thread from said global queue.
Claim 14
Dependent Claim
64 words
The article of manufacture of claim 11 wherein said computer readable code configured to cause one of said plurality of processors to select a candidate thread comprises computer readable code configured to cause one of said plurality of processors to select the highest priority thread from one of said plurality of local dispatch queues when there is no runnable thread in said global queue.
Claim 15
Dependent Claim
62 words
The article of manufacture of claim 12 wherein said computer readable code configured to cause one of said plurality of processors to select a candidate thread comprises computer readable code configured to cause one of said plurality of processors to select a thread from other processor's local dispatch queue when there is no runnable thread in said processor's own local dispatch queue.
Claim 16
Dependent Claim
63 words
The article of manufacture of claim 10 further comprising: computer readable code configured to cause one of said plurality of processors to select one of said plurality of local dispatch queues to place a thread on; computer readable code configured to cause one of said plurality of processors to place the thread on said processor's local dispatch queue when the thread is bound.
Claim 17
Dependent Claim
36 words
The article of manufacture of claim 10 further comprising computer readable code configured to cause one of said plurality of processors to place the thread on said global queue when the thread has real time property.
Claim 18
Dependent Claim
62 words
The article of manufacture of claim 15 further comprising: computer readable code configured to cause one of said plurality of processors to identify a last processor that the thread ran on; computer readable code configured to cause one of said plurality of processors to place the thread on the last processor's dispatch queue when the thread does not have real time property.
Claim 19
Dependent Claim
44 words
The article of manufacture of claim 10 wherein said step of notifying processors of the candidate thread comprising: computer readable code configured to cause one of said plurality of processors to change a memory register value, said register accessible by said plurality of processors.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-19 | 2002-04-20 | 2002-10-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-19 | 2006-04-20 | 2006-10-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-19 | 2010-04-20 | 2010-10-20 | $7700.00 | Window Closed / Lapsed |