US 5,826,081 A · Real time thread dispatcher for multiprocessor applications

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.

Claims17

Dependent claims

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.

2 more elements

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.

4 more elements

Dependencies are inferred from the claim text.

Real time thread dispatcher for multiprocessor applications

Life of this patent

Real time thread dispatcher for multiprocessor applications

Life of this patent

Abstract

Claims17