Task scheduler for a fault tolerant multiple node processing system
First Claim
1. In a mutliple node fault tolerant processing system for processing a set of application tasks in which each node has an applications processor for executing a predetermined subset of said set of application tasks and an operations controller for controlling its own node and scheduling the application tasks in said predetermined subset of tasks that are to be executed by the applications processor through an exchange of inter-node messages containing data and operation information with each node in the processing system, the operations controller generating at least two timing period intervals, a fundamental timing period and a master period which is an integer multiple of the fundamental timing period, the master period defining a timing interval during which every task in said predetermined subset of tasks is scheduled for execution by the applications processor at least once, each operations controller having a task scheduler comprising:
- a task activity list containing an entry for each application task in said multiple node processing system, each entry containing an execution periodicity and a node allocation for that application task;
a priority scan list containing a selected portion of said application tasks in the task activity list which are available for execution, said selected portion of said application tasks being stored in their preferred order of execution;
a completion status list storing said selected portion of said application tasks stored in said priority scan list;
a selection queue storing for each node said application tasks ready for selection in their preferred order of execution;
a period counter for counting said fundamental timing periods to generate a period count corresponding to a number of fundamental periods which have expired since a beginning of a new master period;
wake-up sequencer means connected to said task activity list, said priority scan list, said completion status list and said period counter for interrogating said task activity list to transfer to said priority scan list and said completion status list all of said application tasks whose periodicity is greater than said period count;
priority scan means connected between said priority scan list and said selection queue for transferring to said selection queue for each node entry three application tasks which are ready for execution by that node, which have a highest priority in said preferred order of execution;
task selector means connected to said selection queue for selecting in said preferred order of execution, said application task currently stored in said selection queue for its own node as a next task scheduled for execution by its own applications processor; and
a task interactive consistency handler connected to said task activity list, said priority scan list, said completion status list and said selection queue for updating the status of each task in said task activity list, said priority scan list, said completion status list and said selection queue which are identified in inter-node messages reporting the completion of a task.
1 Assignment
0 Petitions
Accused Products
Abstract
A task scheduler for a fault tolerant multiple node processing system having a task activity list storing a set of application tasks, a priority scan list storing a selected portion of the set of application tasks, a completion status list also storing the same selected portion of the set of application tasks. A wake-up sequencer transfers the application tasks from the task activity list to the priority scan list, and a priority scanner transfers the application tasks ready for execution from the priority scan list to a selection queue. A next task selector selects the next application task that its node will execute, and a task started register stores the identity of the application tasks completed by the other nodes. A task interactive consistency (TIC) handler updates the status of the application tasks stored in the task activity list, the priority scan list, and the completion status list in response to messages received from the other nodes identifying which nodes completed tasks. The task interactive consistency handler checks the scheduling process of each node by comparing the application tasks it reported to have started with the highest priority application task scheduled for that node in its selection queue.
192 Citations
19 Claims
-
1. In a mutliple node fault tolerant processing system for processing a set of application tasks in which each node has an applications processor for executing a predetermined subset of said set of application tasks and an operations controller for controlling its own node and scheduling the application tasks in said predetermined subset of tasks that are to be executed by the applications processor through an exchange of inter-node messages containing data and operation information with each node in the processing system, the operations controller generating at least two timing period intervals, a fundamental timing period and a master period which is an integer multiple of the fundamental timing period, the master period defining a timing interval during which every task in said predetermined subset of tasks is scheduled for execution by the applications processor at least once, each operations controller having a task scheduler comprising:
-
a task activity list containing an entry for each application task in said multiple node processing system, each entry containing an execution periodicity and a node allocation for that application task; a priority scan list containing a selected portion of said application tasks in the task activity list which are available for execution, said selected portion of said application tasks being stored in their preferred order of execution; a completion status list storing said selected portion of said application tasks stored in said priority scan list; a selection queue storing for each node said application tasks ready for selection in their preferred order of execution; a period counter for counting said fundamental timing periods to generate a period count corresponding to a number of fundamental periods which have expired since a beginning of a new master period; wake-up sequencer means connected to said task activity list, said priority scan list, said completion status list and said period counter for interrogating said task activity list to transfer to said priority scan list and said completion status list all of said application tasks whose periodicity is greater than said period count; priority scan means connected between said priority scan list and said selection queue for transferring to said selection queue for each node entry three application tasks which are ready for execution by that node, which have a highest priority in said preferred order of execution; task selector means connected to said selection queue for selecting in said preferred order of execution, said application task currently stored in said selection queue for its own node as a next task scheduled for execution by its own applications processor; and a task interactive consistency handler connected to said task activity list, said priority scan list, said completion status list and said selection queue for updating the status of each task in said task activity list, said priority scan list, said completion status list and said selection queue which are identified in inter-node messages reporting the completion of a task. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
Specification