Scheduler for a multiple computer system

Abstract

A scheduler for selecting and scheduling the tasks to be executed by a computer in a multiple computer system is disclosed. One scheduler is associated with each computer, and the schedulers coordinate their operation by sending and receiving messages. Each scheduler comprises a status table (604) storing the status of each task assigned to its computer, and a scheduling status table (608) storing the tasks recently selected for execution by the computer. The scheduler further includes a record data ready module (600) which records in the status table (604) the reception of the data variables required for the execution of each task. A completed task recorder (612) records which tasks have been executed by itself or any other computer in the system. An unselected/selected task recorder records the selection and unselection of tasks by other computers. A task unselector records the tasks which have been unselected by itself. A task selector (610) selects from the status table and records in the scheduling status table the highest priority task ready for execution which has not been selected by any computer in the system. A task releaser (618) forwards the selected task for execution each time the computer signals the completion of the preceding scheduled task.

Claims

What is claimed is:

1. A scheduler in each computer in a multiple computer system wherein each computer is assigned a set of tasks it is capable of selecting and executing in a predetermined order of priority and each task is assigned to more than one computer and wherein each computer is assigned an execution priority to resolve multiple selection of the same task and each computer includes an applications computer for executing the assigned tasks and for generating a signal signifying it has completed the execution of a task and a task communicator interfacing the scheduler and the applications computer and storing data variables required for the execution of the tasks, said task communicator operative to assemble the data variables required for the execution of each task identified in a task dispatch message and to release to the applications computer the assembled data variables in response to a task release message and to send messages to all of the computers in the system, these messages containing the values of the data variables produced by the applications computer in the execution of the completed task, each scheduler comprising:

status table means for storing current status information for each task capable of being executed by its own computer, said status table storing in the order of execution priority, the identification number of each task and its associated status information, said status information including data variable indicators for signifying the receipt of each data variable required for the execution of the associated task, a task ready indicator signifying that all of the data variables required for the execution of the associated task have been received, task selected indicators signifying the task has been selected and the computer which selected that task, and task completed indicators signifying that the selected task has been completed;

recorder means for recording in said status table means the status information contained in the messages received from all of the computers in the multiple computer system, said recorder means setting said data variable indicators to signify the receipt of each data variable required for the execution of that task, setting said task ready indicator to signify all the required data variables for that task have been received, setting said task selected indicator to signify the identity of the computer which selected the task, and setting said task completed indicator to signify the selected task has been completed;

means for generating a task select signal in response to said recorder means setting said task ready indicator for the first time in response to a received message;

task selector means for selecting from said status table means the highest priority task having its task ready indicator set and none of its task selected indicators set in response to said task select signal, to generate said dispatch task message identifying the selected task to said task communicator, and to send to all of the computers a message containing the identity of the selected task;

task unselector means connected to said status table means and said task selector means and responsive to a message from a computer having a higher execution priority and containing an identification of a selected task which is the same as a task previously selected by said task selector means and which does not have its task completed indicator in said status table means set signifying the task has been completed, for recording in said status table means that the task is selected by the computer identified in the message and that the task is unselected by its own computer, and for generating said select task signal enabling said task selector means to select a new task and wherein said message sent to all of the computers by said task selector means further includes the identity of the unselected task; and

task releaser means for generating said task release message in response to the signal received from the applications computer signifying it has completed the execution of the preceding task, said task release message enabling the task communicator to release the selected task and the assembled task data variables to the applications computer.

2. The scheduler of claim 1 wherein said task selector means includes a scheduling status table means for storing at least the next task to be executed by the applications computer; and

wherein said task selector means further includes means for recording in said scheduling status table means the identity of the selected task and wherein said dispatch task message identifies to the task communicator the selected task stored in said scheduling status table.

3. The scheduler of claim 1 wherein said multiple computer system is a fault tolerant multiple computer system and wherein each of said computers further includes means for determining faulty computers and for sending error messages to the scheduler identifying the computers determined to be faulty, said means for recording further includes system status monitor means responsive to said error messages for recording as unselected in said status table means each task previously recorded as being selected by the computer determined to be faulty and generating a task select signal.

4. The scheduler of claim 3 wherein said system has a normal mode of operation, and at least one degraded mode of operation, said system status monitor means further includes means for generating a mode signal indicative of the system's mode of operation determined from the number of computers currently determined to be faulty from received error messages and wherein said task status table means comprises a plurality of task status tables, each task status table containing the tasks to be executed in one of said modes of operation, said mode signal identifying to said task selector means the task status table from which the tasks are to be selected.

5. The scheduler of claim 4 wherein the lowest priority task in each task status table is a health check task which is always ready for execution and wherein said means for selecting will select said health check task in response to said select task signal when no other task is ready for execution.

6. The scheduler of claim 8 wherein said task releaser means further includes means for recording in said scheduling status table the health check task as the selected task each time the current selected task is dispatched to said task communicator and wherein said task selector means includes means for unselecting said health check task whenever a task having a higher priority is selected.

7. The scheduler of claim 1 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 is executed requiring an earlier generated value for that data variable, and wherein the messages containing the values of the data variables further contain a sequence number indicative of the sequential order in which that value of that data variable was generated, said 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 means for recording includes:

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

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

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

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

8. The scheduler of claim 6 wherein the data variables required for the execution of any task may be generated at different times and several values for the same data variable may be generated before the task is executed requiring an earlier generated value for that data variable and wherein the messages containing the values of the data variables further contain a sequence number indicative of the sequential order in which that value of that data variable was generated, said task 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 includes:

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

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

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

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

9. A method for scheduling the tasks to be executed by a multiple computer system capable of executing a predetermined set of tasks to produce an output to a device in response to inputs from external sources, and wherein said system has a plurality of computers, each computer having an assigned execution priority to resolve multiple selection of the same task and an assigned set of tasks it is capable of selecting and executing and each task is assigned to more than one computer and wherein each computer includes an applications computer for executing the assigned tasks and for generating a signal signifying the completion of each task it executes and a task communicator interfacing the applications computer and storing the data variables required for the execution of the tasks, said task communicator operative to assemble the data variables required for the execution of each task identified in a task dispatch meassage, to release to the applications computer the assembled data variables in response to a task release message and to send to all of the computers in the system messages containing the values of the data variables produced by the applications computer in the execution of the completed task, comprising the steps of:

recording in a status table the current status of each task in response to messages received from all of the computers in the system, said status table listing in the order of execution priority, the identification number of each task capable of being executed by its own computer and its associated status information, said status information including data variable indicators for signifying the receipt of each data variable required for the execution of the associated task, a task ready indicator signifying that all of the data variable required for the execution of the associated task have been received, task selected indicators signifying the task has been selected and the computer that selected the task, and a task completed indicator signifying that the execution of that task has been completed by its own computer or any other computer in the system;

detecting when said task ready indicator is recorded for a task in said status table to generate a select task signal;

selecting from said status table in response to said select task signal the highest priority task having its task ready indicator signifying that all of the data variables have been received and its task selected indicator signifying that the task has not been selected by another computer;

setting the task selected indicator signifying the task has been selected;

recording the selected task in a task scheduling status table;

comparing the selected tasks identified in messages received from the other computers with the tasks previously selected by its own computer in said step of selecting and to reset the task selected indicator for any previously selected incomplete task also selected by a computer having a higher execution priority and to generate in response to resetting said task selected indicator a task select signal enabling said step of selecting to select a new task;

generating in response to selecting a task a message containing the identity of the tasks unselected and selected to inform all of the computers in the multiple computer system that the identified tasks have been unselected and selected;

generating in response to selecting a task a dispatch task signal enabling the task communicator to assemble the data variables required for the execution of the selected task; and

generating a release task signal in response to the signal sent by the applications computer signifying the execution completion of the preceding task, said release task signal identifying the selected task and enabling said task communicator to release the selected task and assembled data variables for execution by the applications computer.

10. The method of claim 9 wherein said step of recording in said task status table means comprises the steps of:

identifying the tasks which await the arrival of a data variable contained in a received message;

setting the data value indicator corresponding to that data variable in each identified task;

setting the task selected indicator associated with the computer which sent the message for the task identified in a message containing the identity of a task selected by a computer; and

setting the task completed indicator for the task identified in a message containing the identity of a task completed.

11. The method of claim 10 wherein each computer further includes means for determining that a computer in the system has become faulty said step of recording in said status table includes the step of:

resetting the task selected indicator corresponding to the new faulty computer for each task previously selected by the new faulty computer and not completed in response to the determination that the computer has become faulty.

12. The method of claim 9 wherein said step of comparing includes the steps of:

comparing the selected task recorded in said scheduling status table with the selected task contained in each received message from the other computers to determine if the same task has been selected by the receiving computer;

comparing the priority of the computer which sent the message with the priority of the receiving computer when the same task is selected by both computers to determine which computer has the higher priority;

recording the task as unselected by the receiving computer when the computer which sent the message has a higher priority than the receiving computer; and

generating a select task signal in response to the sending computer having a higher priority than the receiving computer thereby enabling said step of selecting to select a new task.

13. The method of claim 11 wherein said step of comparing includes the steps of:

interrogating the task selected indicators for the task identified as selected in each received message containing the identity of a selected task to determine if the same task has been selected by the computer receiving the message;

comparing the priority of the computer which sent the message with the priority of the computer which received the message to determine which computer has the higher priority;

recording the task as unselected in the task status table means by the computer which received the message when the priority of the computer which sent the message is higher than the priority of the computer receiving the message; and

generating a select task signal in response to the sending computer having a higher priority than the receiving computer thereby enabling said step of selecting to select a new task.

14. The method of claim 13 wherein the data variables required for the execution of each task are generated at different times using different data variables, and several values for the same data variable are generated before a task is executed requiring an earlier generated data variable, said messages containing a value of a data variable further contain a sequence number distinguishing that value from all other values of the same data variable, said sequence number being indicative of the sequential order in which the value of the data variable was generated; and

wherein said status table includes a plurality of entries for each task with each entry for the same task further containing a different execution number corresponding to different sequence numbers of the values of the data variables to be used in the execution of that task;

said step of recording in the task status table means comprises the steps of:

identifying the tasks which require the value of the data variable contained in the received message;

computing an execution number for each identified task from the sequence number contained in the received message;

searching the status table to find an entry for the identified task having the same execution number as the computed execution number;

setting the data value indicator in the entry for the identified task having the computed execution number to signify that the value for the data variable contained in the received message has been received when the computed execution number is found;

searching the entries for the identified task to find the oldest execution number and setting the data value indicator in the oldest entry corresponding to the data variable contained in the message when the computed execution is not found and the oldest execution number is older than the computed execution number;

recording the computed execution number in the entry having the oldest execution number in response to the oldest found execution number being older than the computed execution number; and

repeating all of the above steps for each identified task until the reception of the value of the data variable is recorded for every identified task awaiting that data variable.

Description

CROSS REFERENCE

The disclosed invention is related to the commonly assigned co-pending applications application Ser. Nos. 118,691; 118,692; 118,693; 118,694; 118,811 and 118,813, filed concurrently herewith.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention is related to Multiple Computer Systems, and in particular to Fault-Tolerant Multiple Computer Systems not having multiple Computers performing each system function.

2. Prior Art

The earliest attempts to produce Fault-Tolerant Control Systems provided redundant computers in which each computer simultaneously executed every task required for the control operation. Voting circuits monitoring the outputs of the multiple computers determined the "correct" system output, the "correct" system output being the output produced by the majority of computers. When a faulty computer produces an output which differs from the "voted" output, the differing output is discarded and does not affect the "voted" or "correct" output of the control system. In this type of Fault-Tolerant System, the failure of a computer may or may not be detected and that computer may or may not be turned "off".

This method, though highly successful, is expensive since it requires multiple equivalent computers, each simultaneously performing the same function. These systems require relatively powerful computers, since each computer has to perform every task required for the operation of the system.

As an alternative, a master-slave concept was introduced in which the operation of several computers was coordinated through a master control. The master designated which tasks were to be executed by the individual computers. This reduced the execution time of the control operation since the good computers no longer were required to execute each and every task. When a fault was detected in the operation of one of the computers, that computer was disconnected and the master distributed the tasks among the good or operative computers. The master-slave concept is dependent upon the continued operation of the master and if the master failed, the system failed. This situation may be rectified by using redundant masters, however, the increased cost of redundant masters limit the applicability of these types of systems to situations where the user is willing to pay for the added reliability, such as in space exploration, nuclear energy facilities, or any other situation where failure of the system would endanger lives.

Recent efforts to improve upon master-slave and redundant execution Fault-Tolerant Multiple Computer Systems are exemplified in the October, 1978 Proceedings of the IEEE, Volume 66, No. 10, which is dedicated to fault-tolerant control systems. Of particular interest are the papers entitled "Pluribus: An Operational Fault-Tolerant Multiprocessor" by D. Katsuki et al., pp. 1146-1159 and "SIFT: The Design and Analysis of A Fault Tolerant Computer for Aircraft Control" by J. H. Wensley et al., pp. 1240-1255. The Pluribus and SIFT control systems are believed to represent the present state of the art. The SIFT system uses redundant execution of each system task, and of the master control functions. The Pluribus system has a single "master" copy of most current information, which can be lost when a fault occurs. such loss of current information can cause interruption of system operation for several seconds or minutes.

SUMMARY OF THE INVENTION

The invention is a data driven scheduler for each computer in a multiple computer system, for selecting and scheduling the tasks to be executed by its own computer in a cooperative, non-redundant manner. The scheduler comprises a status table, a scheduling status table, a record data ready module, a completed task recorder, an unselected/selected task recorder, a task unselector, a task selector and a task releaser.

The status table stores the status of each task assigned to its computer, in the order of execution priority. This table is continuously updated as messages are received by the record data ready module, the completed task recorder and the unselected/selected task recorder. When used in a fault-tolerant system, the status table may comprise more than one table, each table indicative of a different mode of fault-tolerant operation. The record data ready module records in the status table an indication that a data variable required for the execution of a task has been received. The completed task recorder records that the execution of a particular task has been completed.

The unselected/selected task recorder records the selection and unselection of each task identified in a message received from another computer. If the task selected by another computer is the same task as currently selected by its own computer, the unselected/selected task recorder in the lower priority computer initiates unselection of that task by the task unselector. The scheduling status table stores the tasks last selected, started, completed and unselected by the scheduler. This table is updated as tasks are selected and unselected by the task selector and as tasks are released by the task releaser. The task selector selects from the status table the highest priority ready task which has not been selected by another computer, and records the task selected in the scheduling status table. The task selector then sends a message to the other computers informing them of the tasks selected and unselected. The task releaser responds to the completion of each task executed by its own computer, and forwards for execution the selected task recorded in the scheduling status table.

The object of the invention is a scheduler which, in cooperation with like schedulers in the other computers of a multiple computer system, selects the tasks to be executed by its own computer. One advantage of the disclosed scheduler is that each computer selects the tasks it executes without the need for a master scheduler or controller. Another advantage is that task selection is coordinated with task selections by the schedulers in the other computers, so that the task execution by the plurality of computers is non-redundant. Another advantage of the scheduler is that tasks are considered ready when the necessary data is available, avoiding the need to detect and signal when another task is ready. Another advantage is that tasks are scheduled dynamically, avoiding the need to predetermine proper task execution sequences. Another advantage is that failure of a computer or scheduler does not prevent the remaining schedulers from properly scheduling their own computer. Another advantage of the scheduler is that any task improperly executed or not completed by a faulty computer will be rescheduled for execution by an alternate computer.

These and other advantages of the disclosed scheduler will become apparent from a reading of the detailed description in conjunction with the drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram showing the basic architecture of the Fault-Tolerant Multiple Computer System.

FIG. 2 is a block diagram of the Fault-Tolerant Multiple Computer System showing further detail of the system.

FIG. 3 is a block diagram of the Applications Computer.

FIG. 4 is a block diagram of the Operations Controller.

FIG. 5 is a block diagram of the Fault Handler.

FIGS. 6A and 6B are a flow diagram for the Message Format Checker.

FIG. 7 is a circuit implementation of the Message Format Checker.

FIG. 8 is a flow diagram for the Reasonable Limits Checker.

FIG. 9 is a circuit implementation of the Reasonable Limits Checker.

FIG. 10 shows the waveforms of the timing signals used in the discussion of the Message Format Checker and Reasonable Limits Checker.

FIG. 11 is a flow diagram for the Redundant Value Voter.

FIG. 12 is a flow diagram for the "Check Agreement" subroutine of the Redundant Value Voter.

FIG. 13 is a flow diagram for the "Find Values That Agree" subroutine of the Redundant Value Voter.

FIG. 14 is a flow diagram for the "Record Voted Value" subroutine of the Redundant Value Voter.

FIG. 15 is a block diagram of the Message Sequence Checker.

FIG. 16 is a block diagram of the Execution Time Checker.

FIG. 17 is a block diagram of the Synchronizer.

FIGS. 18, 19 and 20 are time-sequence charts used in the discussion of the Synchronizer.

FIG. 21 is a time-sequence chart showing the sequence of events during normal operation of the Synchronizer.

FIG. 22 is a time-sequence chart showing the sequence of events during a start or restart of the Synchronizer.

FIG. 23 is a block diagram of the Fault Tolerator.

FIG. 24 is a block diagram of the Scheduler.

FIG. 25 is a schematic showing the arrangement of the data and subtables of the Status Table.

FIG. 26 is a block diagram of the Task Communicator.

FIG. 27 is a block diagram of the Internal Watch-Dog Timer.

BRIEF DESCRIPTION OF THE TABLES

Architecture of the Fault-Tolerant Multiple Computer System

Table I

Tables used in the System

Messages

Table II-A

*Inter-Computer Messages

Table II-B

Internal Messages

Fault Handler

Table III-A

Message Format Checker

Table III-B

Reasonable Limits Checker

Table III-C

Redundant Data Table

Table III-D

*Redundant Value Voter

Table III-E

*Check Agreement

Table III-F

*Find Values That Agree

Table III-G

*Record Voted Value

Table III-H

*Task Unselected/Selected Message Module

Table III-I

*Task Completed/Started Message Module

Table III-J

*Watch Dog Timer Checker

Table III-K

*Start Watch Dog Timer Module

Table III-L

Sampling Data Table

Table III-M

*Start Synchronizer Module

Table III-N

*Check Sampling Timer Module

Table III-O

*Find Sampling Number Agreement Module

Table III-P

*Find Computers That Agree

Table III-Q

*Restart Sampling Timer

Table III-R

*Record Voted Sampling Number

Table III-S

Fault State Table

Table III-T

*Send Good Message Module

Table III-U

*End Time Period Module

Table III-V

*Check Error Message Agreement Module

Table III-W

*Record Error Module

Table III-X

*Display Faulty Computer

Table III-Y

*Start Fault Handler Module

Scheduler

Table IV-A

Task Status Table

Table IV-B

Task Index Table

Table IV-C

Scheduling Status Table

Table IV-D

Awaiting Task Table

Table IV-E

*Record Data Ready

Table IV-F

*Find Awaiting Execution Number

Table IV-G

*Test If Health Check Selected

Table IV-H

Special Tasks Table

Table IV-I

*Record Special Tasks

Table IV-J

*Task Selector

Table IV-K

*Record Task Selected By Own Computer

Table IV-L

*Completed Task Recorder

Table IV-M

*Test If Last Completed Task

Table IV-N

*Unselected/Selected Task Recorder

Table IV-O

*Record Task Selected

Table IV-P

*Test If Selected Task

Table IV-Q

*Task Unselector

Table IV-R

*Task Releaser

Table IV-S

*System Status Monitor

Table IV-T

*Start Scheduler Module

Task Communicator

Table V-A

Data Values Table

Table V-B

Task Input Table

Table V-C

Task Output Table

Table V-D

*Store Data Value Module

Table V-E

Task Data Table

Table V-F

*Task Dispatcher

Table V-G

*Release Task Module

Table V-H

*Task Results Message Sender

Table V-I

*Starter

Table V-J

*Counter

Table V-K

*Start Task Communicator

Applications Computer

Table VI

*Applications Computer Executive Program

Microprocessor Based Implementation of Operations Controller

Table VII-A

*General Executive Program

Table VII-B

Conditions for Module Execution

Table VII-C

*General "Task" Program

Table VII-D

*Fault Handler Executive Program

Table VII-E

Module Modifications

The tables indicated with asterisks (*) are psuedo code programs

DETAILED DESCRIPTION OF THE INVENTION

Architecture of the Fault-Tolerant Multi-Computer System

The architecture of the disclosed Fault-Tolerant Multi-Computer System is illustrated in FIG. 1. The system comprises a plurality of Computers 10 connected by means of input lines 12 to various sensors and manual inputs collectively represented by block 14.

The outputs of Computers 10 are transmitted by means of output lines 22 to a Combiner/Voter Network 24, which selects and/or combines the output data generated by the various Computers. The Combiner/Voter Network 24 distributes this data, by designated line 26, to the appropriate actuators and displays collectively represented by block 28.

Each Computer 10 has its own private communication link, such as Communication Links 16, 18, and 20, over which it can transmit messages containing data to every other Computer. For example, messages originating in Computer A are transmitted to all the other Computers via Communication Link 16. All the other Computers connected to Communication Link 16 can only receive messages over Communication Link 16. To transmit a message back to Computer A, they must use their own communication link, i.e., Computer B would use Communication Link 18 and Computer N would use Communication Link 20. The messages and data sent over the communication links are sent in serial form; therefore, each link may be a single pair of wires or other serial transmission medium such as an optical fiber. Each communication link is also connected back to the transmitting Computer, permitting verification that the message sent on the communication link is correct. This is part of the fault detection features of the system to be discussed later.

Each Computer such as Computer 10a through 10n consists of one or more computers (or processors), depending upon the number of tasks to be executed by that particular Computer for a particular application and upon the fault-tolerant sophistication of the system. Each Computer 10a through 10n is hereinafter referred to as Computer 10 without the identifying subscript.

Each Computer has an assigned set of tasks which it is capable of executing, where the set of tasks assigned to each Computer 10 is less than the total set of tasks to be executed by the system. One feature of the system, however, is that each task to be executed is assigned to at least two different Computers. Certain tasks critical to the operation of the system are assigned to several or possibly all of the Computers. Each Computer in the system is capable of individually executing each assigned task.

For example, consider a relatively simple system having three Computers and required to execute fifteen (15) different tasks, of which the tasks designated Tasks 7 and 11 are critical to the operation of the system. Further, consider each Computer in the system to be capable of executing at least eleven (11) of the required tasks. In this example, Computer A may be assigned Tasks 1 through 11, Computer B assigned Tasks 5 through 15 and Computer C assigned Tasks 11 through 15, Tasks 1 through 5, and Task 7. In the example, Tasks 7 and 11 are assigned to each Computer; however, in a system having more than three Computers; Tasks 7 and 11 would have been assigned to more than two Computers but not necessarily to all of them.

The execution of each assigned task in each of the Computers 10 is data driven, i.e., when all of the data required for the execution of a particular task is available, each Computer to which the task is assigned is capable of selecting and executing the task. The data is usually the results of one or more previously executed tasks. When execution of a task is completed, the task results are communicated to each of the computers by sending messages via the communication link. When the task results are received by Computers which require the particular data for the performance of a subsequent assigned task, the receiving Computer will store the received data. The Computers which have no assigned task requiring the particular data may discard the received data.

The selection of each task to be executed by each Computer is made dynamically by each Computer. This is done in such a manner that all Computers assigned a task will not necessarily proceed to execute that task. Stated alternatively, a Computer may not execute all tasks which are assigned to that Computer. Each Computer makes its own decisions, based upon knowledge of previous decisions by all Computers, as communicated in messages received via the communication links.

The task selection is performed by a Scheduler described in detail hereinafter with reference to FIG. 24. Briefly, the selection of each task to be executed by each Computer is made dynamically on a priority basis. To this end, a priority number is assigned to each Computer and a priority number is assigned to each task within a given Computer. When a given Computer needs to select a task, the task status information is scanned to determine which of the assigned tasks are ready for execution. A task is ready for execution when all of the data necessary for the execution of the task is available. The Computer selects the ready task having the highest task priority and sends out a message on its communication link signifiying to the other Computers that it has selected the task. When a Computer receives a message indicating that another Computer has selected a task, the selected task is removed from the ready status in all of the other Computers capable of performing the same task.

In the time interval between task selection and starting the execution of the selected task, the computer checks to determine if another Computer has selected the same task. If the Computer which selected a task does not receive a message indicating that another Computer has selected the same task, the Computer initiates the execution of the selected task.

In the event another Computer selects the same task before the first Computer initiates the execution of the task, the priority of each Computer which selected the task is analyzed, and the task remains selected by the Computer having the highest priority. The remaining Computers unselect the previously selected task, and proceed to select the next highest priority task ready for execution. When it is desirable that certain identified tasks be executed by more than one Computer, the same functional task is duplicated for scheduling purposes, one copy for each execution desired.

Fault detection in the system is accomplished by a combination of methods. Faults may be detected by comparing the results of each executed task with stored range limits, by comparing the results of the same task executed by two or more different computers, by error detecting codes on information communicated, by analyzing the scheduling sequence or by the use of watch-dog timers. The system may embody all five fault detection methods, any lesser number of the above methods in combination, or in special applications, any one of the above listed methods.

The messages sent by a Computer are received and analyzed in every Computer in the system to determine if an error exists. If an error is detected, each Computer detecting the error sends out an error message via its communication link to all of the other Computers. An error message signals the detection of an error and identifies the Computer which made the error. The error messages received are analyzed in each Computer. When a Computer receives error messages from two or more Computers, the computer which is identified as making the error is assumed to be faulty.

When a computer is deemed faulty by another Computer, the messages signaling task selection and containing data results of any task executed by the faulty Computer are discarded or ignored. The receipt of messages signifying an error detected by two or more Computers also reinstates the ready status of the tasks presently selected and being executed by the Computer which is deemed to be faulty. The tasks selected and being executed by the faulty Computer are subsequently re-selected and re-executed by other Computers capable of executing those tasks.

In the disclosed system, a Computer determined to be faulty is not turned off or disabled, but is permitted to remain active and to continue to execute each of the assigned tasks, if it can. The remaining Computers continue to check the messages sent by the faulty Computer to determine if the malfunction is temporary or permanent. If the malfunction is temporary, the faulty Computer will eventually return to normal operation and the results of the tasks executed in that Computer will be correct. After a Computer deemed to be faulty correctly executes its assigned tasks for a predetermined period of time, the malfunction is assumed to have been temporary and the excluded Computer is restored to full participation in task selection and task execution.

If a faulty Computer sends incorrect information to Actuators and Displays, the faulty information is corrected by the Combiner/Voter Network 24. The output or task results of any task used for actuator activation or display purposes are generated by the Computers 10 to which the specific tasks are assigned. The output of each Computer 10 is transmitted on lines 22 to the Combiner/Voter Network 24. The Combiner/Voter Network 24 combines the appropriate output data for actuator activation or display purposes as required. When duplicate outputs are provided by multiple Computers, the output data to be used is selected by a voting process.

FIG. 2 shows in greater detail the architecture of the multi-computer system, shown in FIG. 1. Each Computer 10 comprises an Applications Computer 100, such as Applications Computers 100a through 100n, and an Operations Controller 200, such as Operations Controllers 200a through 200n. Each Applications Computer 100 and its associated Operations Controller 200 are interconnected by a buss 30, as indicated by busses 30a through 30n.

The data from the sensors and manual controls, indicated by block 14, are received directly by the Applications Computers 100. Similarly, the data to the Actuators and Displays 28, via the Combiner/Voter Network 24, are obtained directly from the outputs of the Applications Computers. Only the Operations Controllers are interconnected by the communication links 16 through 20.

The Applications Computers 100 are of conventional architecture as shown on FIG. 3. Each Applications Computer comprises a Power Supply 102, a Central Processing Unit (CPU) 104, a Memory 106, and an Input-Output Network 108. The Operations Controllers 200 each comprise a plurality of Receivers 202, a Fault Handler 204, a Scheduler 206, a Task Communicator 208, and a Transmitter 212, as shown on FIG. 4.

The structure of the Operations Controllers 200a through 200n shown in FIG. 2, including the interconnecting communication links 16 through 20, represent the novel aspects of the disclosed Fault-Tolerant Multi-Computer System. The system does not contain a master controller to determine or control which Computer 10 will execute a designated task. Further, the system is not a fully redundant system wherein each Computer 10 is capable of executing and does execute every task.

Applications Computer

FIG. 3 shows the structure of a typical Applications Computer 100. Each Applications Computer 100 has a Power Supply 102, which supplies electrical power to the Central Processing Unit 104, the Memory 106, the Input-Output Network 108, and the associated Operations Controller 200, as indicated. The Central Processing Unit 104, Memory 106 and Input-Output Network 108 are connected by the buss 30. The Input-Output Network 108 is further connected to the Sensors and Manual Controls 14 by line 12, and to the Combiner/Voter Network by line 22. As previously indicated, the Operations Controller 200 is also connected to the buss 30.

The Central Processing Unit 104 may comprise one or more microcomputers, such as Central Processor 8086 manufactured by Intel Corporation of Santa Clara, Calif. The memory 106 may comprise one or more read only memories, such as Erasable PROM 8708 also manufactured by Intel Corporation, which store the programs to be executed by the Central Processing Unit. The Memory 106 may also include one or more read-write (RAM) memories, such as Static RAM 8102A also manufactured by Intel Corporation. The Input-Output Network 108 may comprise one or more commercially available integrated circuits, such as Programmable Peripheral Interface 8255A manufactured by Intel Corporation, with attendant A/D and D/A converters. Alternatively, the Central Processing Unit 104, Memory 106 and Input-Output Network 108 may be incorporated in a single integrated circuit such as Microcomputer 8748 manufactured by Intel Corporation.

The operation of the Applications Computer 100 is as follows. The Operations Controller 200 generates a task signal indicative of the task to be executed by the Central Processing Unit 104, and sends the task signal along with the requisite data to the Central Processing Unit over Buss 30. The Central Processing Unit 104 responds to the task signal, accesses the appropriate program in the Memory 106, executes the task with the provided data, and outputs the results on Buss 30. Data from the Sensors and Manual Controls are received over lines 12 at the input of the Input-Output Network 208, which makes the received data available for use in the execution of an assigned task. The results of those executed tasks which are used for actuator control or display are output to the appropriate actuator and/or display through the Input-Output Network 108. Other results from a task executed by the Central Processing Unit 104, which are required for further computation within the system, are transmitted to all other Computers via the Operations Controller 200 and the communications link. When the execution of the task is completed, the Central Processing Unit initiates execution of the next task selected by the Operations Controller.

Operations Controller

FIG. 4 shows the structure of the Operations Controller 200 in block diagram form. The Operations Controller 200 has a plurality of Receivers 202a through 202k, each connected to a communication link associated with one of the Computers 10. There may be as many Receivers 202 as there are Computers 10, or there may be fewer Receivers if the computer associated with this Operations Controller has no need to receive communications from one or more other Computers in the system, i.e., the results of none of their tasks are needed by this Computer for the execution of its assigned tasks.

The input to one of the receivers, designated Receiver 202k, is connected by means of line 214 to the output of Transmitter 212, which sends the messages and data over the communication link from the associated Operations Controller. This feedback connection between the Transmitter 212 and Receiver 202k is part of the fault detection system to check the message sent over the communication link, and also permits the task results to be input back into the generating Computer for subsequent task execution. This feedback connection may be direct, or preferably in the form of a loop connection from Transmitter 212 to the appropriate Receivers in each other Computer and finally back to Receiver 202k in the same Computer.

The Receivers 202a through 202k receive the messages serially transmitted over the communication links and convert them to a parallel format for subsequent utilization in the Operations Controller and Application Computer. As used hereinafter, the term "messages" will include all messages, such as Task Completed/Started, Task Unselected/Selected, Error, Task Data Values, and other messages communicating information between the Computers via the communication links.

The Receivers 202 also include circuits which establish message protocol and perform other necessary format conversions. The Transmitter 212 performs the reverse function, receiving parallel data and converting it to a serial format for transmission over the communication link. The format conversion may strip or add carriers, provide padding or add special codes for transmission error control as is known in the art.

The Receivers 202 and Transmitter 212 each contain buffers permitting a message to be received some time before it can be output. Each buffer is capable of holding more than one message; for example, each buffer may be capable of holding up to ten (10) messages. Receivers 202 and Transmitter 212 may be commercially available integrated circuits incorporating both a receiver and transmitter, such as the Programmable Communications Interface (PCI) 2651 manufactured by Signetics of Sunnyvale, Calif. or the SDLC Protocol Controller 8273 manufactured by Intel Corporation of Santa Clara, Calif. These circuits are supplemented with additional buffering using commercially available integrated circuits such as FIFO 33512 manufactured by Fairchild Corporation of Mountain View, Calif.

The parallel data outputs of the Receivers 202 are transmitted to a Fault Handler 204, where each received message is analyzed to determine if it is good or faulty. The Fault Hander 204 may be a micro-computer having storage capabilities, a part of a micro-computer, or a special purpose circuit. The Fault Handler 204 performs one or more of the following fault detection checks:

1. Compare the received data value with predetermined limit values to determine if it is reasonable, i.e., has a value between predetermined minimum and maximum values.

2. Compare the received data with the results of other Computers performing the same task, to determine the most probable value, and to identify Computers providing values which differ significantly from the most probable value,

3. Determine if the scheduling information was received in a proper sequence,

4. Determine by means of watch-dog timers if the task execution was completed within a predetermined time period after the execution was started, or

5. Check error detecting codes, determined over other information communicated and included in each message.

In addition to performing fault detection checks, the Fault Handler 204 also performs the following functions:

1. Transmits an Error message to the Transmitter 212 when an error is detected. 2. Stores Error messages received from all Computers.

3. Decides if one or more of the Computers is faulty.

4. Discards all messages received from the Computers determined to be faulty.

5. Transmits to the Scheduler 206 error-free messages from non-faulty Computers.

6. Generates a faulty display indicating the Computers which have been determined to be faulty.

7. Decides that a Computer is no longer faulty and readmits the Computer previously determined faulty, after the faulty Computer sends good messages for a predetermined period of time,

8. Generates the required input/output sampling commands, and

9. Initiates startup of the Applications Computer and Operations Controller, when the Computer is first turned on or power is returned after a temporary power failure.

The function of the Scheduler 206 is to schedule the tasks to be executed by its own Applications Computer 100. The Scheduler performs the following functions:

1. Keeps track of the status of all assigned tasks and determines which of the tasks are ready for execution, i.e., all the data needed for execution is available.

2. Selects the ready task having the highest task priority for next execution and generates a signal indicative of the task selected, and

3. Unselects the selected task and selects the next highest priority task when it receives a task selection message for the same task from another Computer having a higher assigned Computer priority.

The Scheduler 206 may be implemented by means of a micro computer or a part thereof, or with special purpose hardware, depending upon the number of assigned tasks and complexity of the system.

The Task Communicator 208 stores the current values of the data required for the execution of each task assigned to the associated Applications Computer 100. The Task Communicator responds to each task signal generated by the Scheduler 206 and makes available to the associated Applications Computer 100 the data required for the execution of the task identified by the task signal. Upon completion of each task, data values produced by the executed task, or an error message if an error was detected in the execution of the task, are sent by the Task Communicator 208 to the Transmitter 212.

The Transmitter 212 also receives the Task Completed/Started messages from the Task Communicator, Task Unselected/Selected messages from the Scheduler 206, and Sampling Number and Error messages from the Fault Handler 204. The transmitter 212 converts the received messages to a serial format which is sent to the other computers via the associated communication link.

The data sent over the associated commmunication link is also received by Receiver 202k over line 214. The messages received by the Fault Handler 204 from Receiver 202k are treated in the same way as any other message received from the other Computers in the system. In this way, the data generated by the associated Applications Computer, required for the execution of a subsequent task, is communicated to and stored in the associated Task Communicator 208 of each Computer 10.

The operation of the Operations Controller 200 requires the maintenance of various tables of information. These tables store the recent actions of all Computers, including itself. Table I below lists the various tables used in the system and the elements to which these tables are assigned.

                  TABLE I
    ______________________________________
    TABLES USED IN THE SYSTEM
    TABLE              ELEMENT
    ______________________________________
    Redundant Data     Fault Handler 204
    Computer Status    Fault Handler 204
    Sampling Data      Fault Handler 204
    Fault State        Fault Handler 204
    Scheduling Status  Scheduler 206
    Task Status        Scheduler 206
    Data Values        Task Communicator 208
    Internal Watch-Dog Timer
                       Task Communicator 208
    ______________________________________

                  TABLE II-A
    ______________________________________
    INTER-COMPUTER MESSAGES
    Message Type  Byte No.  Byte Contents
    ______________________________________
    Task Data Value
                  1         Message Type
                  2         Sending Computer
                  3         Data I.D.
                  4         Sequence number
                  5-12      Data Value
                  13-14     Error Detecting Code
    Redundant Data
                  1         Message Type
    Value         2         Sending Computer
                  3         Data I.D.
                  4         Sequence Number
                  5-12      Data Value
                  13-14     Error Detecting Code
    Task Completed/
                  1         Message Type
    Started       2         Sending Computer
                  3         Completed Task
                  4         Completed Execution
                            Number
                  5         Started Task
                  6         Started Execution
                            Number
                  7-8       Error Detecting Code
    Task Unselected/
                  1         Message Type
    Selected      2         Sending Computer
                  3         Unselected Task
                  4         Unselected Execution
                            Number
                  5         Selected Task
                  6         Selected Execution
                            Number
                  7-8       Error Detecting Code
    Error         1         Message Type
                  2         Sending Computer
                  3         Faulty Computer
                  4         Error Type Code
                  5-6       Null (not used)
                  7-8       Error Detecting Code
    Sampling Number
                  1         Message Type
                  2         Sending Computer
                  3         Sampling Number
                  4         Starting Flag
                  5-6       Excluded Bits
                  7-8       Error Detecting Code
    ______________________________________

                  TABLE II-B
    ______________________________________
    INTERNAL MESSAGES
                 BYTE
    MESSAGE TYPE NO.     BYTE CONTENTS
    ______________________________________
    EXCLUDE      1       MESSAGE TYPE
    COMPUTER . . . . . .
                 2       EXCLUDED COMPUTER
                 3-4     EXCLUDED BITS
    INITIATE     1       MESSAGE TYPE
    SPECIAL TASKS
                 2       TASK TYPE
                 3       EXECUTION NUMBER
    RESTART . . . . . . . .
                 1       MESSAGE TYPE
    DISPATCH TASK . .
                 1       MESSAGE TYPE
                 2       TASK
                 3       EXECUTION NUMBER
    RELEASE TASK . .
                 1       MESSAGE TYPE
                 2       COMPLETED TASK
                 3       COMPLETED EXECUTION
                         NUMBER
                 4       STARTED TASK
                 5       STARTED EXECUTION
                         NUMBER
    TASK DONE . . . . . .
                 1       MESSAGE TYPE
                 2       TASK
    RECORD ERROR . .
                 1       MESSAGE TYPE
                 2       NEW FAULTY COMPUTER
                 3       ERROR INDICATOR
    TASK INPUT . . . . .
                 1       MESSAGE TYPE
                 2-3     TASK ADDRESS
    THE FOLLOWING SET OF BYTES ARE REPEATED FOR
    EACH DATA VARIABLE USED AS A TASK INPUT. SEE
    TASK COMMUNICATOR DISCUSSION FOR MORE
    DETAIL.
                 4-11    INPUT VALUE
                 12      ACTUAL DELAY INTEGER
    TASK OUTPUT . . . .
                 1       MESSAGE TYPE
    THE FOLLOWING SET OF BYTES ARE REPEATED FOR
    EACH DATA VARIABLE COMPUTED AS A TASK
    OUTPUT. SEE TASK COMMUNICATOR DISCUSSION
    FOR MORE DETAIL.
               2     DATA I.D.
               3     REDUNDANT VALUE
               4-11  OUTPUT VALUE
    ______________________________________

                  TABLE III-A
    ______________________________________
    MESSAGE FORMAT CHECKER
    ______________________________________
    /* IF ERROR DETECTED BY RECEIVER */
    IF ERROR DETECTED BITS NOT = 0
    THEN
    ERROR INDICATOR =
    FUNCTION OF (ERROR DETECTED BITS)
    ELSE /*IF MESSAGE TYPE CODE NOT VALID*/
    IF MESSAGE TYPE > MAXIMUM TYPE
    ORIF MESSAGE TYPE = 0
    THEN
    ERROR INDICATOR = MESSAGE TYPE ERROR
    ELSE /*CHECK SENDING COMPUTER CODE*/
    IF SENDING COMPUTER NOT = RECEIVER
    THEN
    ERROR INDICATOR =
    SENDING COMPUTER CODE ERROR
    ELSE
    ERROR INDICATOR = 0
    ENDIF
    ENDIF
    ENDIF
    IF ERROR INDICATOR NOT = 0 /* IF ERROR WAS
    DETECTED*/
    THEN
    CALL: SEND MESSAGE TO FAULT TOLERATOR
    INPUT DATA:
    MESSAGE TYPE = RECORD ERROR TYPE
    NEW FAULTY COMPUTER = RECEIVER
    ERROR INDICATOR = ERROR INDICATOR
    OUTPUT DATA: NONE
    ELSE /*FORWARD RECEIVED MESSAGE*/
    /*CASE OF MESSAGE TYPE*/
    IF MESSAGE TYPE = TASK DATA VALUE TYPE
    THEN
    CALL: SEND MESSAGE TO
    REASONABLE LIMITS CHECKER
    INPUT DATA: MESSAGE = RECEIVED MESSAGE
    OUTPUT DATA: NONE
    ELSE IF MESSAGE TYPE = REDUNDANT DATA
    VALUE TYPE
    THEN
    CALL: SEND MESSAGE TO REDUNDANT VALUE
    VOTER
    INPUT DATA: MESSAGE = RECEIVED MESSAGE
    OUTPUT DATA: NONE
    ELSE IF MESSAGE TYPE =
    TASK COMPLETED/STARTED TYPE
    THEN
    CALL: SEND MESSAGE TO EXECUTION TIME
    CHECKER
    INPUT DATA: MESSAGE = RECEIVED MESSAGE
    OUTPUT DATA: NONE
    ELSE IF MESSAGE TYPE =
    TASK UNSELECTED/SELECTED TYPE
    THEN
    CALL: SEND MESSAGE TO
    MESSAGE SEQUENCE CHECKER
    INPUT DATA: MESSAGE = RECEIVED MESSAGE
    OUTPUT DATA: NONE
    ELSE IF MESSAGE TYPE = SAMPLING NUMBER TYPE
    THEN
    CALL: SEND MESSAGE TO SYNCHRONIZER
    INPUT DATA: MESSAGE = RECEIVED MESSAGE
    OUTPUT DATA: NONE
    ELSE /*MESSAGE TYPE = ERROR MESSAGE TYPE*/
    CALL: SEND MESSAGE TO FAULT TOLERATOR
    INPUT DATA: MESSAGE = RECEIVED MESSAGE
    OUTPUT DATA: NONE
    ENDIF ENDIF ENDIF ENDIF ENDIF
    /*END CASE*/
    ENDIF
    RETURN
    END:
    ______________________________________

                  TABLE III-B
    ______________________________________
     REASONABLE LIMITS CHECKER
    ______________________________________
    /*IF DATA ID NOT VALID*/
    IF DATA ID > MAXIMUM DATA ID
    THEN
    ERROR INDICATOR = DATA ID ERROR
    ELSE /*IF DATA VALUE NOT WITHIN LIMITS*/
    IF DATA VALUE > MAXIMUM DATA VALUE
    (DATA ID)
    ORIF DATA VALUE < MINIMUM DATA VALUE
    (DATA ID)
    THEN
    ERROR INDICATOR = LIMIT ERROR
    ELSE
    ERROR INDICATOR = 0
    ENDIF
    ENDIF
    IF ERROR INDICATOR NOT = 0 /*IF ERROR WAS
    DETECTED*/
    THEN
    CALL: SEND MESSAGE TO FAULT TOLERATOR
    INPUT DATA:
    MESSAGE TYPE = RECORD ERROR TYPE
    NEW FAULTY COMPUTER = COMPUTER
    ERROR INDICATOR = ERROR INDICATOR
    OUTPUT DATA: NONE
    ELSE
    CALL: SEND MESSAGE TO FAULT TOLERATOR
    INPUT DATA:
    MESSAGE = TASK DATA VALUE MESSAGE
    OUTPUT DATA: NONE
    ENDIF
    RETURN
    END
    ______________________________________