Prerequisite-based scheduler

• US 7,370,326 B2
• Filed: 04/02/2004
• Issued: 05/06/2008
• Est. Priority Date: 04/02/2004
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Emulex Design & Manufacturing Corp. (Broadcom, Inc.)
• Inventors: Siewert, Samuel Burk, Jones, Marc Timothy, Nottberg, Curtis Edward
• Primary Examiner(s): An; Meng-Al T.
• Assistant Examiner(s): Truong; Camquy
• Application Number:
  US10/817,290
• Publication Number:
  US 20050240924A1
• Time in Patent Office: 1,495 Days
• Field of Search: 718/102, 718/104, 709/238
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals

Abstract

A prerequisite-based scheduler is disclosed which takes into account system resource prerequisites for execution. Tasks are only scheduled when they can successfully run to completion and therefore a task, once dispatched, is guaranteed not to become blocked. In a prerequisite table, tasks are identified horizontally, and resources needed for the tasks are identified vertically. At the bottom of the table is the system state, which represents the current state of all resources in the system. If a Boolean AND operation is applied to the task prerequisite row and the system state, and if the result is the same as the prerequisite row, then the task is dispatchable. In one embodiment of the present invention, the prerequisite based scheduler (dispatcher) walks through the prerequisite table from top to bottom until a task is found whose prerequisites are satisfied by the system state. Once found, this task is dispatched.

Claims

1. A method for scheduling a plurality of tasks in a processing system having a plurality of defined resources, comprising:

identifying prerequisites for each task, the prerequisites representing all defined resources needed for that task to execute to completion;

identifying one or more higher priority task paths and one or more lower priority task paths, each of the paths having a plurality of tasks in series;

representing each defined resource by one or more resource flags that provide information about that resource;

storing the prerequisites for each task as a collection of resource flags known as a prerequisite row;

storing the system state as a collection of resource flags;

creating a prerequisite table, the prerequisite table having one prerequisite row for each instantiated task arranged in descending order according to a task priority order determined in accordance with the higher priority task paths and the lower priority task paths, and having one column for each resource flag;

in a descending row order, performing a comparison of the prerequisite row for the task in a given row against a system state representing a current state of the defined resources until a task is identified for which the comparison reveals that the prerequisites for the identified task are currently available; and

dispatching the identified task.

2. The method as recited in claim 1, further comprising:

arranging the task priority order such that the tasks in the priority task paths have a higher priority than other tasks.

3. The method as recited in claim 2, further comprising:

modifying a scope of the prerequisites for the tasks in a particular priority task path to adjust a processing speed of that priority task path.

4. The method as recited in claim 1, further comprising:

identifying one or more fast paths in a task processing sequence; and

for a given fast path, arranging the task priority order such that the tasks in the given fast path have a higher priority than other tasks.

5. The method as recited in claim 4, further comprising:

identifying a processing order of the tasks in the given fast path; and

arranging the task priority order such that a last task in the given fast path has a higher priority than a first task in the given fast path.

6. The method as recited in claim 4, further comprising:

identifying a processing order of the tasks in the given fast path; and

arranging the task priority order such that a first task in the given fast path has a higher priority than a last task in the given fast path.

7. The method as recited in claim 1, further comprising comparing the prerequisite row for the particular task against the system state by performing a Boolean AND of the prerequisite row and the system state.

8. The method as recited in claim 1, further comprising:

creating a decision tree from the prerequisite table according to the task priority order, the decision tree having one leaf for each instantiated task, one node for each resource, and one edge for each resource flag; and

traversing the decision tree in accordance with the availability of resources.

9. The method as recited in claim 1, further comprising updating the system state after resources are actually used.

10. The method as recited in claim 9, wherein after the system state has been updated, the method further comprises implementing fair-share scheduling by resuming the comparison of prerequisite rows against the updated system state at a next row in the prerequisite table.

11. The method as recited in claim 9, wherein once the system state has been updated, the method further comprises implementing priority scheduling by resuming the comparison of prerequisite rows against the updated system state at a first row in the prerequisite table.

12. The method as recited in claim 9, further comprising:

grouping consecutive prerequisite rows in the prerequisite table into one or more blocks;

when a task is identified and scheduled for dispatch, identifying the block to which the identified task belongs; and

once the identified task is dispatched and the system state is updated, resuming the comparison at a next row within the identified block, or resuming the comparison at a first row of the prerequisite table if the dispatched task was a last task in the identified block.

13. The method as recited in claim 1, further comprising:

creating one or more priority flags representing various priority levels as defined priority flag resources in the processing system; and

adding the priority flag resources to the prerequisites of selected tasks in accordance with priority levels desired for those tasks;

wherein the priority flag resources effectively change the task priority order as the prerequisites for the selected tasks are compared against the system state.

14. The method as recited in claim 1, the defined resources including one or more queues, the method further comprising:

changing a depth of one or more queues to alter the scheduling of tasks having those queues as prerequisites.

15. The method as recited in claim 1, the defined resources including one or more buffer pools, the method further comprising:

changing a depth of one or more buffer pools to alter the scheduling of tasks having those buffer pools as prerequisites.

16. The method as recited in claim 1, further comprising:

storing the prerequisite rows in M N-bit words, each bit in each N-bit word representing a resource flag and each resource flag being either asserted to indicate that the resource flag is a prerequisite of the task represented by the prerequisite row or deasserted to indicate that the resource flag is not a prerequisite of that task;

storing the system state in M N-bit words, each bit in each N-bit word representing a resource flag, each resource flag being either asserted or deasserted in accordance with the current state of the processing system;

storing an indicator of the last N-bit word containing an asserted resource flag;

comparing the prerequisites and the system state of successive N-bit words only up to the last N-bit word containing an asserted resource flag; and

determining whether the prerequisites for the identified task are currently available using only the compared N-bit words.

17. The method as recited in claim 16, further comprising:

arranging the resource flags that make up the prerequisite rows and the system state so that when the prerequisite rows are stored in the M-bit words, the number of asserted resource flags appearing in the first M-bit word is maximized.

18. The method as recited in claim 1, further comprising:

storing the prerequisite rows in M N-bit words, each bit in each N-bit word representing a resource flag, each resource flag being either asserted to indicate that the resource flag is a prerequisite of the task represented by the prerequisite row or deasserted to indicate that the resource flag is not a prerequisite of that task;

storing the system state in M N-bit words, each bit in each N-bit word representing a resource flag, each resource flag being either asserted or deasserted in accordance with the current state of the processing system;

comparing the prerequisites and the system state of successive N-bit words only as long as the comparison indicates that the prerequisites for the identified task are currently available.

19. In a processing system having a plurality of defined resources, the processing system for executing a plurality of tasks, a computer program for scheduling the plurality of tasks, the computer program being stored on a machine readable medium and executable to perform acts comprising:

identifying prerequisites for each task, the prerequisites representing all defined resources needed for that task to execute to completion;

identifying one or more higher priority task paths and one or more lower priority task paths, each of the paths having a plurality of tasks in series;

representing each defined resource by one or more resource flags that provide information about that resource;

storing the prerequisites for each task as a collection of resource flags known as a prerequisite row;

storing the system state as a collection of resource flags;

creating a prerequisite table, the prerequisite table having one prerequisite row for each instantiated task arranged in descending order according to a task priority order determined in accordance with the higher priority task paths and the lower priority task paths, and having one column for each resource flag;

in a descending row order, performing a comparison of the prerequisite row for the task in a given row against a system state representing a current state of the defined resources until a task is identified for which the comparison reveals that the prerequisites for the identified task are currently available; and

scheduling the identified task for dispatch.

20. The computer program as recited in claim 19, further executable to perform acts comprising:

arranging the task priority order such that the tasks in the priority task paths have a higher priority than other tasks,

21. The computer program as recited in claim 20, further executable to perform acts comprising:

modifying a scope of the prerequisites for the tasks in a particular priority task path to adjust a processing speed of that priority task path.

22. The computer program as recited in claim 19, further executable to perform acts comprising:

identifying one or more fast paths in a task processing sequence; and

for a given fast path, arranging the task priority order such that the tasks in the given fast path have a higher priority than other tasks.

23. The computer program as recited in claim 22, further executable to perform acts comprising:

identifying a processing order of the tasks in the given fast path; and

arranging the task priority order such that a last task in the given fast path has a higher priority than a first task in the given fast path.

24. The computer program as recited in claim 22, further executable to perform acts comprising:

identifying a processing order of the tasks in the given fast path; and

arranging the task priority order such that a first task in the given fast path has a higher priority than a last task in the given fast path.

25. The computer program as recited in claim 19, further executable to perform acts comprising comparing the prerequisite row for the particular task against the system state by performing a Boolean AND of the prerequisite row and the system state.

26. The computer program as recited in claim 19, further executable to perform acts comprising:

creating a decision tree from the prerequisite table according to the task priority order, the decision tree having one leaf for each instantiated task, one node for each resource, and one edge for each resource flag; and

traversing the decision tree in accordance with the availability of resources.

27. The computer program as recited in claim 19, further executable to perform acts comprising updating the system state as resources are actually used.

28. The computer program as recited in claim 27, wherein after the system state has been updated, the computer program is further executable to perform acts comprising fair-share scheduling by resuming the comparison of prerequisite rows against the updated system state at a next row in the prerequisite table.

29. The computer program as recited in claim 27, wherein once the system state has been updated, the computer program is further executable to perform acts comprising priority scheduling by resuming the comparison of prerequisite rows against the updated system state at a first row in the prerequisite table.

30. The computer program as recited in claim 27, further executable to perform acts comprising:

grouping consecutive prerequisite rows in the prerequisite table into one or more blocks;

when a task is identified and scheduled for dispatch, identifying the block to which the identified task belongs; and

once the identified task is dispatched and the system state is updated, resuming the comparison at a next row within the identified block, or resuming the comparison at a first row of the prerequisite table if the dispatched task was a last task in the identified block.

31. The computer program as recited in claim 19, further executable to perform acts comprising:

creating one or more priority flags representing various priority levels as defined priority flag resources in the processing system; and

adding the priority flag resources to the prerequisites of selected tasks in accordance with priority levels desired for those tasks;

wherein the priority flag resources effectively change the task priority order as the prerequisites for the selected tasks are compared against the system state.

32. The computer program as recited in claim 19, the defined resources including one or more queues, the computer program further executable to perform acts comprising:

changing a depth of one or more queues to alter the scheduling of tasks having those queues as prerequisites.

33. The computer program as recited in claim 19, the defined resources including one or more buffer pools, the computer program further executable to perform acts comprising:

changing a depth of one or more buffer pools to alter the scheduling of tasks having those buffer pools as prerequisites.

34. The computer program as recited in claim 19, further executable to perform acts comprising:

storing the prerequisite rows in M N-bit words, each bit in each N-bit word representing a resource flag and each resource flag being either asserted to indicate that the resource flag is a prerequisite of the task represented by the prerequisite row or deasserted to indicate that the resource flag is not a prerequisite of that task;

storing the system state in M N-bit words, each bit in each N-bit word representing a resource flag, each resource flag being either asserted or deasserted in accordance with the current state of the processing system;

storing an indicator of the last N-bit word containing an asserted resource flag;

comparing the prerequisites and the system state of successive N-bit words only up to the last N-bit word containing an asserted resource flag; and

determining whether the prerequisites for the identified task are currently available using only the compared N-bit words.

35. The computer program as recited in claim 34, further executable to perform acts comprising:

arranging the resource flags that make up the prerequisite rows and the system state so that when the prerequisite rows are stored in the M-bit words, the number of asserted resource flags appearing in the first M-bit word is maximized.

36. The computer program as recited in claim 19, further executable to perform acts comprising:

storing the prerequisite rows in M N-bit words, each bit in each N-bit word representing a resource flag, each resource flag being either asserted to indicate that the resource flag is a prerequisite of the task represented by the prerequisite row or deasserted to indicate that the resource flag is not a prerequisite of that task;

storing the system state in M N-bit words, each bit in each N-bit word representing a resource flag, each resource flag being either asserted or deasserted in accordance with the current state of the processing system;

comparing the prerequisites and the system state of successive N-bit words only as long as the comparison indicates that the prerequisites for the identified task are currently available.

37. The computer program as recited in claim 19, wherein the machine readable medium on which the computer program is stored is included within a host bus adapter (HBA).

38. The computer program as recited in claim 37, wherein the HBA further comprises an Internet Small Computer System Interface (iSCSI) or fibre channel (FC) controller circuit.

39. The computer program as recited in claim 38, wherein the HBA is included within a host computer.

40. The computer program as recited in claim 39, wherein the host computer is included within a storage area network (SAN) and wherein an iSCSI or a FC network is coupled to the iSCSI or FC controller circuit, respectively, and one or more storage devices are coupled to the iSCSI or FC network.