Operations controller for a fault-tolerant multiple computer system

• US 4,323,966 A
• Filed: 02/05/1980
• Issued: 04/06/1982
• Est. Priority Date: 02/05/1980
• Status: Expired due to Term

• Current Assignee: The Bendix Corporation (Honeywell International Inc.)
• Original Assignee: The Bendix Corporation (Honeywell International Inc.)
• Inventors: Whiteside, Arliss E., Freedman, Morris D., Tasar, Omur, Rothschild, Alexander M.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chan, Eddie P.
• Application Number:
  US06/118,693
• Time in Patent Office: 791 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 371/9, 371/36, 371/68
• US Class Current: 714/1
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0715 in a system implementing multitasking multitasking per se G06F9/46
• CPC Class Codes: G06F 11/0766 Error or fault reporting or storing
• CPC Class Codes: G06F 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• CPC Class Codes: G06F 11/1675 Temporal synchronisation or re-synchronisation of redundant processing components
• CPC Class Codes: G06F 11/183 by voting, the voting not being performed by the redundant components
• CPC Class Codes: G06F 11/187 Voting techniques

Abstract

An operations controller for each computer in a multiple computer system is disclosed. Each operations controller controls the operations of its associated computer, so that all of the computers cooperate to perform system functions in a fault-tolerant manner. Each operations controller comprises a fault handler (204), a scheduler (206), a task communicator (208), plus a transmitter (212) and requisite receivers (202) which receive and send messages to all the other computers in the system. The fault handler (204) checks each message received and decides which computers are operating correctly and which are faulty. A scheduler (206) selects each task its own computer will execute, from the tasks assigned to its own computer. A task communicator (208) assembles the data values required for the execution of the selected task, and forwards this data to the computer for execution. The operations controller sends messages to all of the other computers in the system, informing them of which computer it deems to be faulty, the tasks it selects to execute, when it starts and completes the execution of each selected task, and the data variable values produced by the execution of each task.

Claims

1. In a fault tolerant multiple computer system wherein the multiple computer system is capable of executing, in a coordinated manner, a predetermined set a task in response to inputs from external sources to produce an output to at least one external device, and wherein each computer includes an application computer capable of executing a subset of the predetermined set of tasks, and wherein the subset of tasks for each computer is different, and contains at least one predetermined input/output task for inputting new data from an external source or outputing data to the at least one external device, an operations controller for each computer in the system for selecting the tasks to be executed by the associated applications computer and for sending messages to every other computer;

said messages including task selected messages identifying the tasks it has selected, task data valve messages containing the values of the data variables resulting from the tasks executed by its applications computer, and error messages containing the identification of the computers which sent messages having detected errors, each operations controller comprising;

fault handler means responsive to messages received from all the computers in the system for checking each message received to identify faulty messages, to record as faulty in a fault state table the computers sending messages identified as being faulty, and to record as faulty in said same fault state table each computer identified as being faulty in said error messages received from a predetermined number of other computers, for passing on for further processing the error-free messages received from non-faulty computers and for sending said error messages to the other computers identifying each computer it has recorded to be faulty in said fault state table;

scheduler means storing said subset of tasks in their order of priority and their execution status in response to the error-free task selected and data value messages passed by the fault handler for selecting for execution from said stored subset of tasks said input/output task at predetermined intervals and for selecting in the interval between the selection of said input/output tasks the highest priority unselected task ready for execution, for generating a dispatch signal identifying the task selected for execution, and for sending said task selected messages to all of the computers identifying the tasks it has selected for execution; and

task communicator means interfacing said scheduler means and the associated applications computer for storing the values of the data variables contained in the error-free data value messages passed by the fault handler, for assembling the values of the data variables required for the execution of the selected task in response to said dispatch signal, for sending to the applications computer the assembled values of the data variables in response to the applications computer signifying it has completed the previous task, for sending to all of the computers data value messages containing the values of the data variables resulting from the execution of the selected task by the associated applications computer and for receiving from said external sources and sending to said at least one external device the data values resulting from the execution of said input/output task.

2. The operations controller of claim 1 wherein said fault handler comprises:

checker means for checking each message received and for generating an error signal identifying each received message containing an error and the computer which sent the message; and

fault tolerator means responsive to said error signal generated by said checker means and said error messages received from other computers for determing which computers are considered faulty by its own operations controller, for passing on for further processing only error-free messages received from non-faulty computers and for sending said error messages identifying as faulty each computer which sent a message containing an error detected by its own checker means.

3. The operations controller of claim 2 wherein said operations controller further includes a plurality of receivers, each receiver receiving only the messages sent by an associated other computer.

4. The operations controller of claim 3 wherein said plurality of receivers further includes a receiver receiving only the messages sent by its own computer.

5. The operations controller of claim 2 wherein each of said task selected, data value and error messages has a predetermined format containing information identifying the message as a task selected, data value, or error message and a computer code identifying the computer that sent the message, said checker means includes a message format checker for checking the format of each received message and generating said error signal when an error in said information identifying the message or computer code is detected.

6. The operations controller of claim 5 wherein said message is a task data value message containing the value of a data variable, said checker means further includes a reasonable limits checker for checking the value of the data variable contained in each task data value message against predetermined maximum and minimum values and for generating said error signal when the value of the data variable in the received task data value message is outside said predetermined maximum and minimum values.

7. The operations controller of claim 5 wherein said fault tolerant computer system further sends redundant data value messages containing a data value redundantly computed by more than two computers, said checker means further includes redundant value voter means responsive to said redundant data value messages received from said more than two computers for finding a voted data value when the data value for the same data variable contained in a predetermined number of redundant data value messages agree and for generating said error signals identifying each computer which sent a redundant data value message containing a value which did not agree with the voted data value.

8. The operations controller of claim 5 wherein said fault tolerant multiple computer system further sends task completed/started messages containing the identity of the tasks completed and the new task started by the computer sending said task completed/started message, said checker means further includes execution time checker means responsive to said task completed/started messages for checking the execution time of each task executed by each computer in the system and for generating said error signals when the execution time exceeds predetermined limits.

9. The operations controller of claim 8 wherein said computer system further sends a task selected message containing the identity of the task selected by the computer sending the message said checker means further includes message sequence checker means responsive to said task selected and task completed/started messages for checking the proper sequence in which the tasks are selected and executed by each computer and for generating said error signal when the selection and execution of tasks do not follow a correct sequence.

10. The operations controller of claim 9 wherein each computer is assigned a priority for the execution of tasks and wherein said scheduler further includes means for unselecting a previously selected task when the same task is selected by a higher priority computer, means for selecting a new task in response to a message received from a computer having a higher priority identifying that the higher priority computer has selected the same task and means for generating a task unselected/selected message identifying the task unselected and the new task selected, said message sequence checker is responsive to said task unselected/selected message and said task completed/started message.

11. The operations controller of claim 2 wherein said at least one external source is a plurality of external sources producing a like number of input signals and wherein said input signals need to be sampled at approximately the same time to coordinate the operation of the multiple computers and wherein a first predetermined number of the multiple computers include at least one input task in its subset of tasks enabling its applications computer to sample at least one of said plurality inputs, and wherein a second predetermined number of the multiple computers include at least one output task in their subset of tasks to produce an output to said at least one device, said fault handler further includes synchronizer means for generating an initiate input/output tasks signal in synchronization with the other computers in the system, said initiate input/output task signal activating said scheduler means to select said input and output tasks thereby synchronizing the selection and execution of said input and output tasks by it'"'"'s own computer with the other computers in the system.

12. The operations controller of claim 8 wherein said at least one external source is a plurality of external sources producing a like number of input signals and wherein said input signals need to be sampled at approximately the same time to coordinate the operation of the multiple computers and wherein a first predetermined number of the multiple computers include at least one input task in its subset of tasks enabling its applications computer to sample at least one of said plurality inputs, and wherein a second predetermined number of the multiple computers include at least one output task in their subset of tasks to produce an output to said at least one device, said fault handler further includes synchronizer means for generating an initiate input/output tasks signal in synchronization with the other computers in the system, said initiate input/output task signal activating said scheduler means to select said input and output tasks thereby synchronizing the selection and execution of said input and output tasks by it'"'"'s own computer with the other computers in the system.

13. The operations controller of claim 11 or 12 wherein said synchronizer means includes:

timer means for repetitively generating sampling periods and a sampling number identifying the current sampling period;

means for sending a sampling number messages at the end of each sampling period containing the sampling number identifying of said current sampling period;

voter means for finding a voted sampling number indicative of the sampling number contained in a predetermined number of sampling number messages received from like synchronizer means in the other computers;

means for updating said generated sampling number to agree with said voted sampling number;

means responsive to said voter means finding a voted sampling number for generating said initiate input/output task signal; and

means responsive to the time within each sampling period when said voted sampling number is found for correcting the duration of the sampling period currently being generated to end at approximately the same time as the sampling periods being generated in like synchronizers in the other computers.

14. The operations controller of claim 13 wherein said synchronizer further includes means responsive to the sampling numbers contained in the sampling number messages received from the other computers for generating an error signal identifying each computer which sent a sampling number message containing a sampling number which disagrees with said voted sampling number.

15. The operations controller of claim 2 wherein said fault tolerator means further includes means for cancelling the fault status of a computer previously identified as faulty when said computer previously identified as faulty sends error free messages for a predetermined period of time.

16. The operations controller of claim 14 wherein said fault tolerator means further includes means for cancelling the fault status of a computer previously identified as faulty when said computer previously identified as faulty sends error free messages for a predetermined period of time.

17. The operations controller of claim 1 wherein said scheduler comprises:

status table means for storing current status information for each task capable of being executed by the applications computer said status table means storing said tasks in their order of execution priority;

means receiving said messages identifying the tasks selected by the other computers, and said messages containing the values of the data variables for recording in said status table means for each task, the receipt of each data variable required for the execution of that task, for setting a task ready indicator signifying all the data variables requires for the execution of that task have been received, for recording in said status table means the identity of the computer that selected that task, and for generating a task select signal in response to setting said task ready indicator;

system status monitor means responsive to said messages identifying each computer recorded to be faulty for recording in said status table means as unselected each task previously recorded as being selected by the computer identified as faulty in the message and generating said task select signal;

scheduling status table means for storing the tasks selected in the order in which they are selected;

task selector means responsive to said task select signal for selecting from the status table means the highest priority task having its task ready indicator set and not selected by another computer, for recording said selected task in said scheduling status table means, for generating said dispatch task signal identifying the selected task to said task communicator and for generating a task selected message sent to all of the other computers identifying the task selected.

18. The operations controller of claim 17 wherein the applications computer generates a task done signal each time it completes the execution of a task, said scheduler further includes task releaser means for sending a release task signal to said task communicator in response to said task done signal said release task signal identifying the selected task stored in said scheduling status table means to be executed by the applications computer.

19. The operations controller of claim 17 wherein the data variables required for the execution of any task are generated at different times and several values for the same data variable are generated before the task requiring an earlier generated value for that data variable is ready for execution and wherein the message containing the values of the data variables further contain a sequence number indicative of the sequential order in which the value of that data variable was generated, said status table means further includes a plurality of entries for each task with each entry storing a different execution number for that task;

and

wherein said means for recording information in said status table means includes;

means for identifying each task which requires the value of the data variable contained in the received message;

means for computing for each task requiring that data variable value an execution number from the sequence number contained in the received message;

means for recording the arrival of the data variable value in said status table means in the task entry having the same execution number as the computed execution number; and

means for recording the arrival of the data variable value in said status table means in the task entry having the oldest execution number, when no entry is found having the computed execution number and the oldest found execution number is older than the computed execution number.

20. The oeprations controller of claim 11 wherein said messages sent between computers include task unselected/selected messages identifying the tasks unselected and tasks selected by the sending computer, task completed/started messages identifying the tasks completed and the tasks started by the sending computer, and data value messages containing the values of the data variables, said scheduler comprises:

status table means for storing current status information for each task capable of being executed by the computer, said status table means storing said tasks and their associated status information in their order of priority;

record data means receiving said data value messages for recording in said status table that the data identified in the messages has been received and for generating a task select signal when all the data required for the execution of a task has been received;

completed task recorder means responsive to said completed/started messages for recording in said status table means that the task identified as completed in the received completed/started message has been completed;

means receiving said task unselected/selected messages for recording as unselected in said status table means the task identified in the message as unselected by the computer which sent in the message, for recording in the status table means as selected the task identified in the message as selected by the computer which sent the message;

system status monitor means responsive to said messages identifying each computer to be considered faulty for recording in said status table means as unselected each task previously recorded as being selected but not completed by the computer identified as faulty and for generating said task select signal;

scheduling status table means for storing the selected tasks in the order in which they are selected;

task selector means responsive to said task select signals for selecting from said status table means the highest priority task ready for execution and not selected by any other computer, for recording the selected task in the scheduling status table, for sending a dispatch task signal which identifies the selected task to the task communicator and for generating said task unselected/selected message identifying the task selected; and

task unselector means responsive to the task identified as selected in a task unselected/selected message from a higher priority computer being the same as a task previously selected by said task selector means for recording the identified task as unselected by its own computer in said status table means and said scheduling status table means and for generating said task select signal and wherein the task unselected/selected message generated by said task selector means identifies the task unselected by the task unselector means.

21. The operations controller of claim 20 wherein the applications computer generates a task done signal each time it completes the execution of a task, said scheduler further includes task releaser means for generating a release task signal in response to said task done signal, said release task message identifying the selected task stored in said scheduling status table means.

22. The operations controller of claim 21 wherein the data variables required for the execution of any task are generated at different times and several values for the same data variable are generated before a task requiring an earlier generated value for that data variable is ready for execution and wherein the message containing the values of the data variables further contain a sequence number indicative of the sequential order in which that value of data variable was generated, said task status table means includes a plurality of entries for each task with each entry storing a different execution number for that task;

and

wherein said record data ready means includes;

means for identifying each task which requires the value of the data variable contained in the received message;

means for computing for each task requiring that data variable value an execution number from the sequence number contained in the received message;

means for recording the arrival of the data variable value in said task status table means in the identified task entry having the same execution number as the computed execution number; and

means for recording the arrival of the data variable value in said task status table means in the identified task entry having the oldest execution number, when no entry is found having the computed execution number, and the oldest found execution number is older than the computed execution number.

23. The operations controller of claim 22 wherein said system has a normal mode of operation, and at least one intermediate degraded mode of operation, said system status monitor means further generates a mode signal indicative of the system'"'"'s current mode of operation determined from the number of computers considered to be faulty and wherein said status table means comprises a plurality of task status tables, each task status table corresponding to one of said modes of operation and said mode signal identifying for said task selector means the task status table from which the tasks are to be selected.

24. The operations controller of claim 1 wherein said task communicator comprises:

data values table means storing the values of the data variables;

store data value means for recording in said data values table means the values of data variables contained in messages received from all the computers in the system;

task input means for communicating the values of the data variables required for the execution of the selected task to the applications computer;

task dispatcher means responsive to the task selected by said scheduler for selecting from said data values table means the values of the data variables required for the execution of the selected tasks communicated to the applications computer by said task input means;

task output means for communicating values of the data variables resulting from the execution of each task by the computer to a task results sender means; and

task result sender means responsive to the computer completing the execution of each task for sending to all computers said messages containing the values of the data variables communicated by said task output means.

25. The operations controller of claim 24 wherein said task results sender means further includes means for sending messages to all computers identifying the task completed and the new task started by the applications computer.

26. The operations controller of claim 22 wherein said task communicator means comprises:

data values table means storing the values of the data variables;

store data values means for recording in said data values table means the values of data variables contained in the data value messages received from all the computers;

task input means for communicating the values of the data variables required for the execution of the selected task to the applications computer;

task dispatcher means responsive to the dispatch task signal identifying the selected task for selecting the values of the data variables stored in said data values table means communicated to said applications computer by said task input means;

a task output means for communicating the values of the data variables resulting from the execution of each task by the applications computer to a task results sender means; and

said task results sender means responsive to said applications computer completing the execution of each task for sending said data value messages containing the values of the data variables communicated by said task output means and for sending said task completed/started messages identifying the task completed by the computer and the new task started.

27. The operations controller of claim 26 wherein said data value table means includes a plurality of entries for each data variable and each entry storing a value for a data variable and its corresponding sequence number, and wherein said dispatch task signal further contains the execution number of the selected task;

means for searching the entries corresponding to the data variable contained in the received data value message to find the entry having the same sequence number as the sequence number contained in the message;

means for searching the entries corresponding to the data variable contained in the received message to find the oldest sequence number when the same sequence number is not found;

means for recording the sequence number contained in the message in the entry having the oldest sequence number when the oldest sequence number is older than the sequence number contained in the message; and

recording the value of the data variable contained in the message in the entry having the same sequence number; and

wherein said task dispatcher means comprises;

means for identifying each data variable required for the execution of the task identified in the dispatch task signal; and

means for computing a sequence number for each identified data variable from the execution number contained in the dispatch task signal;

task input table means for storing values of the data variables for at least two sequentially selected tasks; and

means for copying into said task input table means the value of each data variable from the entry in said data values table means having the computed sequence number; and

wherein said means for communicating the values of the data variables to the applications computer comprises release task means responsive to said release task signal for enabling said applications computer to access the values of the data variables previously copied into said task input table means by a preceeding dispatch task signal.

28. The operations controller of claim 27 where the instructions for the execution of each task are stored in the applications computer'"'"'s program memory, said task dispatcher means further comprises:

means for storing the starting address in the applications computer'"'"'s program memory where the instructions for each task begins; and

wherein said means for copying further includes means for copying into said task input table means the starting address for the task identified in the dispatch task signal.

29. The operations controller of claim 27 wherein said task output means includes a task output table storing values of the data variables computed by the applications computer, and wherein said task results sender means sends data value messages containing the values of the data variables stored in said task output table and further includes a sequence number corresponding to the execution number of the task which computed the values of the data variables.

30. The operations controller of claim 27 wherein said task communicator further includes watch-dog timer means responsive to said release task messages for monitoring the execution time of each task executed by the applications computer to generate an error signal sent to the fault handler when the execution time for a task is not within predetermined limits.

31. A method for controlling a plurality of computers to execute, in a coordinated fault tolerant manner, a predetermined set of tasks in response to inputs from external sources to produce an output to at least one external device, and wherein each computer includes an application computer capable of executing a subset of the predetermined set of tasks, and wherein the subset of tasks for each computer is different and includes at least one input/output task for receiving data variables from said external sources and outputing data variables to said at least one external device, and wherein said plurality of computers sends messages to every other computer including task selected messages identifying the tasks it has selected, task data value messages containing the values of the data variables resulting from the executed tasks, and error messages containing the identification of the computers which sent messages having detected errors, said method comprising the steps of:

checking all the messages received from said plurality of computers to detect any errors in said messages and to generate error signals identifying each computer which sent a message having a detected error;

counting the number of computers which sent said error messages identifying each computer which sent a message having a detected error;

comparing said number with a predetermined number to generate said error signal identifying each computer which sent a message having an error detected by a number of computers greater than said predetermined number;

recording as faulty, the identify of each computer identified in said error signals to generate a fault status table storing the identify of each computer which sent a message containing an error;

discarding all messages received from computers recorded as faulty in said fault status table;

storing by each computer its own subset of tasks in a task status table, said task status table listing each task of said subset in its order of execution priority;

recording in said task status table the receipt of each data variable required for the execution of each task in response to said task data value messages;

setting a task ready indicator signifying the task is ready for execution in response to the recording in said task status table all data variables required for the execution of that task;

setting in said task status table task selected indicators signifying the task has been selected by another computer in response to said task selected message received from other computers said task selected indicators further identifying the computer that selected the task;

selecting for execution from said task status table said at least one input/output task at predetermined intervals;

selecting for execution from said task status table in the interval between the selection of said input and output tasks the highest priority unselected task having its task ready indicator set;

setting the task selected indicator associated with its own computer in response to the selection of a task;

generating a dispatch signal identifying the selected task in response to selecting said task;

sending to all of the computers said task selected message identifying the selected task in response to selecting said task;

storing the values of the data variables input in response to said input/output tasks and the data variables contained in said data value messages to generate a data values table;

assembling the values of the data variables stored in the data values table for the selected task in response to said dispatch signal to generate a task input table;

forwarding to the applications computer the values of the data variables stored in said task input table when the applications computer signifies it has completed a preceeding task;

storing the values of the data variables generated by the applications computer in the execution of the selected task;

sending to all of the computers the values of the data variables stored in the task output table in response to the applications computer signifying it has completed the execution of the task; and

repetitively executing all of the above steps.

32. The method of claim 31 wherein each computer is assigned an execution priority for the execution of tasks, said step of setting said task selected indicators in response to a task selected message further includes the steps of:

interrogating said task status table to determine if the task identified in a received task selected message has been previously selected by its own computer;

setting in said task status table said task selected indicator to signify the task has been selected by the computer identified in said received task selected message when the same task had not been previously selected by its own computer;

comparing the execution priority of the computer identified in said task selected message with the execution priority of its own computer to determine if the computer identified in said task selected message has a higher execution priority when the task identified in the task selected message had been previously selected by its own computer;

unselecting said previously selected task by resetting the task selected indicator associated with its own computer and setting the task selected indicator associated with the computer identified in said received task selected message when the computer identified in said received task selected message has a higher execution priority than the execution priority of its own computer; and

selecting from said task status table the highest priority unselected task having its task ready indicator set in response to unselecting said previously selected task; and

wherein said step of sending said task selected message sends a task unselected/selected message to all of the computers containing the identify of the unselected task and the new selected task.

33. The method of claim 32 wherein said step of recording in said task status table further includes the step of unselecting each task previously recorded as selected by a faulty computer by resetting the task selected indicator associated with the faulty computer in response recording said computer as faulty in said fault status table.

34. The method of claim 31 wherein the data variables required for the execution of any task are generated at different times and several values for the same data variable are generated before the task requiring an earlier generated value for that data variable is ready for execution and wherein said task data value messages further contains a sequence number indicative of the sequential order in which the value of that data variable was generated, wherein each task has an associated execution number indicative of the sequential order said task is to be executed and wherein said task status table has a plurality of entries for each task with each entry storing a different execution number for that task, said step of recording in said task status table further includes the steps of:

computing for each task requiring the data variable value contained in a received data value message an execution number from said sequence number contained in the received data value message;

recording in said task status table the arrival of the data variable value in said task status table in the task entry having the computed execution number; and

recording in said task status table the arrival of the data variable value in the task entry having the oldest execution number when no entry is found having the computed execution number and the oldest found execution number is older than the computed execution number.

35. The method of claim 31 wherein said plurality of computers has a normal mode of operation and at least one intermediate degraded mode of operation and wherein said task status table comprises a plurality of task status tables, one storing the subset of tasks it is capable of executing in said normal mode of operation and the others storing different subset of tasks it is capable of executing in said intermediate degraded modes of operation, said method further includes the steps of:

interrogating said fault status table to determine the number of computers recorded as faulty;

comparing said number of computers recorded as faulty with predetermined numerical intervals indicative of the normal mode of operation and said intermediate modes of operation to designate which task status table is to be used in said step of selecting tasks for execution; and

selecting for execution from said designated task status table the highest priority unselected task ready for execution.