Low-latency real-time dispatching in general purpose multiprocessor systems

• US 5,928,322 A
• Filed: 11/20/1996
• Issued: 07/27/1999
• Est. Priority Date: 11/20/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Ananthanarayanan, Rajagopal, Bitar, Nawaf K., English, Robert M.
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US08/752,925
• Time in Patent Office: 979 Days
• Field of Search: 395/733, 395/672, 395/635, 395/677, 395/595, 395/736, 395/200.53, 395/673
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A low-latency real-time dispatching scheme performed by the operating system of a general purpose multiprocessor system having N processors, assigns a priority to each of multiple real-time threads to be executed on the N processors. The multiple real-time threads include up to N top priority real-time threads, which are bound to a corresponding processor. The assigned priority of each bound real-time thread is the highest priority for being executed on its corresponding processor, and any other real-time thread being executed on the corresponding processor is preempted if the bound real-time thread becomes runnable.

Claims

1. A method of real-time dispatching in a general purpose multiprocessor system having N processors, the method comprising:

assigning a priority to each of the multiple real-time threads to be executed on one of the N processors, such that the multiple real-time threads include up to N top priority real-time threads; and

binding each of the up to top N priority real-time threads to a corresponding processor such that the assigned priority of each bound real-time thread is the highest priority for being executed on its corresponding processor and any other thread being executed on the corresponding processor is preempted if the bound real-time thread becomes runnable, wherein binding includes;

preallocating a processor to each one of the N top priority real-time threads; and

dispatching the bound real-time thread to its preallocated processor when the real-time thread becomes runnable.

2. The method of claim 1 further comprising queuing unbound real-time threads not in the top N priority real-time threads in a global queue available for access by all of the N processors if there is not available processors for the executing all real-time threads.

3. The method of claim 2 further comprising queuing time-share threads in a time-share queue available for access by all of the N processors if there is not available processors for the executing time-share threads, wherein the time-share threads in the time-share queue all have lower priorities than the unbound real-time threads in the global queue.

4. The method of claim 2 further comprising searching for an available processor for executing the unbound queued real-time threads.

5. The method of claim 1 further comprising:

destroying one of the bound real-time threads; and

binding a highest priority unbound real-time thread in the general purpose multiprocessor system to said corresponding processor.

6. A method of real-time dispatching in a general purpose multiprocessor system having N processors, the method comprising:

assigning a priority to each of the multiple real-time threads to be executed on ones of the N processors, such that the multiple real-time threads include up to N top priority real-time threads;

binding each of the up to top N priority real-time threads to a corresponding processor such that the assigned priority of each bound real-time thread is the highest priority for being executed on its corresponding processor and any other thread being executed on the corresponding processor is preempted if the bound real-time thread becomes runnable;

creating a new real-time thread having an assigned priority;

re-evaluating the assigned priorities of the real-time threads to ascertain if the priority of the new real-time thread is greater than the priority of one of the previous top N priority real-time threads; and

if the priority of the new real-time thread is greater than the priority of one of the previous top N priority real-time threads;

breaking the binding of the lowest priority bound real-time thread from its corresponding processor; and

binding the new real-time thread to said corresponding processor.

7. The method of claim 6, wherein assigning a priority includes queuing unbound real-time threads not in the top N priority real-time threads in a global queue available for access by all of the N processors.

8. The method of claim 7, wherein assigning a priority further includes queuing timeshare threads in a time-share queue available for access by all of the N processors, wherein the time-share threads in the time-share queue all have lower priorities than the unbound real-time threads in the global queue.

9. A method of real-time dispatching in a general purpose multiprocessor system having N processors, the method comprising:

assigning a priority to each of the multiple real-time threads to be executed on ones of the N processors, such that the multiple real-time threads include up to N top priority real-time threads; and

binding each of the up to top N priority real-time threads to a corresponding processor such that the assigned priority of each bound real-time thread is the highest priority for being executed on its corresponding processor and any other thread being executed on the corresponding processor is preempted if the bound real-time thread becomes runnable;

assigning a new priority to at least one of the real-time threads;

reevaluating the assigned priorities of the real-time threads to ascertain if the priority of at least one unbound real-time thread is greater than the priority of at least one of the previous top N priority real-time threads as a result of assigning a new priority; and

if the priority of the at least one unbound real-time thread is greater than the priority of the at least one of the previous top N priority real-time threads;

breaking the binding of the at least one lowest priority bound real-time thread from its corresponding processor; and

binding the at least one unbound real-time thread to said corresponding processor.

10. The method of claim 9, wherein assigning a priority includes queuing unbound real-time threads not in the top N priority real-time threads in a global queue available for access by all of the N processors.

11. The method of claim 10, wherein assigning a priority further includes queuing timeshare threads in a time-share queue available for access by all of the N processors, wherein the time-share threads in the time-share queue all have lower priorities than the unbound real-time threads in the global queue.

12. A method of real-time dispatching in a general purpose multiprocessor system having a first processor and a second processor, the method comprising:

binding a first real-time thread to the first processor such that the first real-time thread has the highest priority for being executed on the first processor and any other thread being executed on the first processor is preempted if the first real-time thread becomes runnable; and

binding a second real-time thread to the second processor such that the second real-time thread has the highest priority for being executed on the second processor and any other thread being executed on the second processor is preempted if the second real-time thread becomes runnable wherein binding of said first and second real-time threads includes preallocating the first and second processors to the first and second real-time threads, respectively.

13. A general purpose multiprocessor system comprising:

N processors;

assigning means for assigning a priority to each of the multiple real-time threads to be executed on ones of the N processors, such that the multiple real-time threads include up to N top priority real-time threads; and

binding means for binding each of the up to top N priority real-time threads to a corresponding processor such that the assigned priority of each bound real-time thread is the highest priority for being executed on its corresponding processor and any other thread being executed on the corresponding processor is preempted if the bound real-time thread becomes runnable, wherein the binding means includes;

means for preallocating a processor to each one of the N top priority real-time threads; and

means for dispatching the bound real-time thread to its preallocated processor when the real-time thread becomes runnable.

14. The general purpose multiprocessor system of claim 13 further comprising a global queue, available for access by all of the N processors, for queuing unbound real-time threads not in the top N priority real-time threads if there is not available processors for the executing all real-time threads.

15. The general purpose multiprocessor system of claim 14 further comprising a time-share queue, available for access by all of the N processors, for queuing time-share threads if there are no available processors for the executing time-share threads, wherein the time-share threads in the time-share queue all have lower priorities than the unbound real-time threads in the global queue.

16. The general purpose multiprocessor system of claim 14 further comprising means for searching for an available processor for executing the unbound queued real-time threads.

17. The general purpose multiprocessor system of claim 13, wherein the binding means destroys one of the bound real-time threads and binds a highest priority unbound real-time thread in the general purpose multiprocessor system to said corresponding processor.

18. A general purpose multiprocessor system comprising:

N processors;

assigning means for assigning a priority to each of the multiple real-time threads to be executed on ones of the N processors, such that the multiple real-time threads include up to N top priority real-time threads; and

binding means for binding each of the up to top N priority real-time threads to a corresponding processor such that the assigned priority of each bound real-time thread is the highest priority for being executed on its corresponding processor and any other thread being executed on the corresponding processor is preempted if the bound real-time thread becomes runnable;

wherein the assigning means assigns a priority to a new real-time thread and reevaluates the assigned priorities of the real-time threads to ascertain if the priority of the new real-time thread is greater than the priority of one of the previous top N priority real-time threads, and wherein if the priority of the new real-time thread is greater than the priority of one of the previous top N priority real-time threads, the binding means breaks the binding of the lowest priority bound real-time thread from its corresponding processor and binds the new real-time thread to said corresponding processor.

19. The general purpose multiprocessor system of claim 18, further comprising a global queue, available for access by all of the N processors, for queuing unbound real-time threads not in the top N priority real-time threads.

20. A general purpose multiprocessor system comprising:

N processors;

assigning means for assigning a priority to each of the multiple real-time threads to be executed on ones of the N processors, such that the multiple real-time threads include up to N top priority real-time threads; and

binding means for binding each of the up to top N priority real-time threads to a corresponding processor such that the assigned priority of each bound real-time thread is the highest priority for being executed on its corresponding processor and any other thread being executed on the corresponding processor is preempted if the bound real-time thread becomes runnable;

wherein when the assigning means assigns a new priority to at least one of the real-time threads, wherein the assigning means reevaluates the assigned priorities of the real-time threads to ascertain if the priority of at least one unbound real-time thread is greater than the priority of at least one of the previous top N priority real-time threads as the result of the assigning, and wherein if the priority of the at least one unbound real-time thread is greater than the priority of the at least one of the previous top N priority real-time threads, the binding means breaks the binding of the at least one lowest priority bound real-time thread from its corresponding processor and binds the at least one unbound real-time thread to said corresponding processor.

21. The general purpose multiprocessor system of claim 20, further comprising a global queue, available for access by all of the N processors, for queuing unbound real-time threads not in the top N priority real-time threads.