Computer OS dispatcher operation with virtual switching queue and IP queues

• US 7,167,916 B2
• Filed: 08/30/2002
• Issued: 01/23/2007
• Est. Priority Date: 08/30/2002
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Stanton, Michael F., Carter, John, Morris, Robert, Willen, James W., Hancock, Peter John, Mikkelsen, Hans Christian
• Primary Examiner(s): SALAD, ABDULLAHI ELMI
• Application Number:
  US10/232,199
• Publication Number:
  US 20040054999A1
• Time in Patent Office: 1,607 Days
• Field of Search: 709/226, 718/100, 718102-104
• US Class Current: 709/226
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 9/5044 considering hardware capabilities

Abstract

Driving task dispatching by an operating system in a multiprocessor computer system is accomplished with a virtual switching queue which accepts highest priority tasks from multiple switching queues which in turn are accessed by instruction processors seeking tasks. Overload, plucking and stealing of tasks may be used to effectively balance load within the computer system. Dynamic reconfiguration used where regular queues lose underlying instruction processors.

Claims

1. A virtual queue method for allocating tasks by a dispatcher algorithm to switching queues of individual processors in a multiprocessor computer system, said method comprising;

a) allowing a user to establish priority for tasks to be allocated to individual processor switching queues,

b) placing a value, indicating a priority for each said task queued for an said individual processor for on said individual processor switching queues, said value being associated with said user established priority,

c) placing a reference for a highest priority task of said each task having a queued value on said individual processor switching queue, from each said individual processor switching queue onto a virtual queue,

d) at a time a given processor is ready to perform a task, searching said virtual queue for a said reference for any tasks which may have a higher priority than any priority value that currently exists on said given processor'"'"'s individual processor switching queue, and

e) if a task reference on said virtual queue has a higher priority than task priority values existing on said given processor'"'"'s individual processor switching queue, plucking said task from said virtual queue and,

running said plucked task on said given processor,

else, if no task reference on said virtual queue has a higher priority than at least one task priority on said given processor'"'"'s individual processor switching queue, running a one of said at least one tasks from said given processor'"'"'s individual processor switching queue.

2. The method of claim 1 wherein said given processor may be any one of all individual processors used by said multiprocessor computer system and wherein said virtual queue is accessed to determine if a higher priority task has been placed thereon by said all individual processors.

3. The method of claim 1 wherein the decision step e) requires an additional decision to determine if a second processor which has a task on said virtual queue that has higher priority than a task on said given processor'"'"'s individual switching queue is one that said given processor is entitled to pluck from, and if said second processor is not one said given processor is entitled to pluck from, then said decision step e) performs the task identified in the else statement.

4. The method of claim 3 wherein said additional decision is determined with reference to a buddy mask.

5. The method of claim 3 wherein said additional decision is determined with reference to a steal-from mask.

6. The method of claim 1 wherein when a task is created the method comprises the additional step;

f) determining if a newly created task is a part of a predetermined dedicated Data Sharing Group, if yes, setting a stealable mask for said newly created task to allow stealing by any processor in its assigned cache neighborhood based on the stealable mask parameters related to said predetermined dedicated Data Sharing Group, or if no, setting a stealable mask for said newly created task to allow stealing by any cache neighborhood.

7. The method of claim 1 further comprising, each time a user applies a dedication list, updates a dedication list or a processor configuration changes in a multiprocessor computer system employing the method of claim 1:

I. for each dedication to a Data Sharing Group in the list,

finding the highest-numbered non-exclusive cache neighborhood which satisfies said dedication'"'"'s requirements creating a steal-from mask for this found cache neighborhood, indicating this Data Sharing Group'"'"'s dedication,

II. after I. Is complete, creating a system-wide steal-from mask for non-dedicated cache neighborhoods.

8. The method of claim 7 wherein part I further comprises;

indicating if said Data Sharing Group is exclusive or if non dedicated tasks are permitted to run in this Data Sharing Group'"'"'s cache neighborhood and wherein said part II. further comprises

for each processor not in an exclusive assignment, setting said each not in an exclusive assignment processor'"'"'s steal-from mask to that of the non-exclusively assigned neighborhood.

15. The storage medium of claim 9 further comprising, each time a user applies a dedication list, updates a dedication list or a processor configuration changes in a multiprocessor computer system employing the method of claim 1:

III. for each dedication to a Data Sharing Group in the list,

finding the highest-numbered non-exclusive cache neighborhood which satisfies said dedication'"'"'s requirements creating a steal-from mask for this found cache neighborhood, indicating this Data Sharing Group'"'"'s dedication,

IV. after I. Is complete, creating a system-wide steal-from mask for non-dedicated cache neighborhoods.

16. The storage medium of claim 15 wherein part I further comprises;

indicating if said Data Sharing Group is exclusive or if non dedicated tasks are permitted to run in this Data Sharing Group'"'"'s cache neighborhood and wherein said part II. further comprises

for each processor not in an exclusive assignment, setting said each not in an exclusive assignment processor'"'"'s steal-from mask to that of the non-exclusively assigned neighborhood.

9. A digital storage medium having stored thereon a sequence of instructions to cause a device to perform a virtual queue method for allocating tasks by a dispatcher algorithm to switching queues of individual processors in a multiprocessor computer system, said method comprising;

a) allowing a user to establish priority for tasks to be allocated to individual processor switching queues,

b) placing a value, indicating a priority for each said task queued for an said individual processor for on said individual processor switching queues, said value being associated with said user established priority,

c) placing a reference for a highest priority task of said each task having a queued value on said individual processor switching queue, from each said individual processor switching queue onto a virtual queue,

d) at a time a given processor is ready to perform a task, searching said virtual queue for a said reference for any tasks which may have a higher priority than any priority value that currently exists on said given processor'"'"'s individual processor switching queue, and

e) if a task reference on said virtual queue has a higher priority than task priority values existing on said given processor'"'"'s individual processor switching queue, plucking said task from said virtual queue and,

running said plucked task on said given processor,

else, if no task reference on said virtual queue has a higher priority than at least one task priority on said given processor'"'"'s individual processor switching queue, running a one of said at least one tasks from said given processor'"'"'s individual processor switching queue.

10. The storage medium of claim 9 wherein said given processor may be any one of all individual processors used by said multiprocessor computer system and wherein said virtual queue is accessed to determine if a higher priority task has been placed thereon by said all individual processors.

11. The storage medium of claim 9 wherein the decision step e) requires an additional decision to determine if a second processor which has a task on said virtual queue that has higher priority than a task on said given processor'"'"'s individual switching queue is one that said given processor is entitled to pluck from, and if said second processor is not one said given processor is entitled to pluck from, then said decision step e) performs the task identified in the else statement.

12. The storage medium of claim 11 wherein said additional decision is determined with reference to a buddy mask.

13. The storage medium of claim 11 wherein said additional decision is determined with reference to a steal-from mask.

14. The storage medium of claim 9 wherein when a task is created the method comprises the additional step;

f) determining if a newly created task is a part of a predetermined dedicated Data Sharing Group, if yes, setting a stealable mask for said newly created task to allow stealing by any processor in its assigned cache neighborhood based on the stealable mask parameters related to said predetermined dedicated Data Sharing Group, or if no, selling a stealable mask for said newly created task to allow stealing by any cache neighborhood.