Task communicator for multiple computer system

• US 4,333,144 A
• Filed: 02/05/1980
• Issued: 06/01/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
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chan, Eddie P.
• Application Number:
  US06/118,813
• Time in Patent Office: 847 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 371/9, 371/36, 371/68
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A task communicator for each computer in a multiple computer system is disclosed. The task communicator provides communication of data values between cooperating tasks executed by different computers. The task communicator comprises a data values table (804) storing the current data values required for the execution of each task assigned to its computer. A store data value module (802) which stores the data values received from the other computers in the data values table. A task dispatcher (806) which copies the data values required for the execution of a selected task into a task input table (810). A release task module (814), which releases for execution the identified task and data values stored in the task input table. A task output table (812) storing the values of the data resulting from the execution of each task by its own computer. A task results message sender (818) which sends to all of the computers in the system messages containing the new data values stored in the task output table by the executed task.

Claims

1. A task communicator for each computer in a multiple computer system wherein each computer is capable of executing an assigned set of tasks, and each computer includes means for selecting the tasks it will execute, means for scheduling for execution the selected tasks in their order of selection, and an applications computer for executing the scheduled tasks, and wherein all of the computers in the system send messages to each other, said messages containing the identity and the values of the data variables resulting from the execution of the tasks by its own applications computer and wherein said applications computer generates a task done signal when it completes the execution of each task and is ready for a new task and said means for scheduling generates sequential dispatch task signals in response to said task done signal, each of said sequential dispatch task signals containing the identity of a scheduled task in its sequential order of selection, each of said task communicators comprising:

a data value table storing the values of the data variables required for the execution of each assigned task, each data variable being generated at different times, and several values of the same data variable may be generated before a task is executed requiring an earlier generated value for that data variable, each data variable having an associated storage location in said data values table for storing at least one data value for that data variable;

store data value means responsive to the identity of the data variable contained in said messages received from all of said computers for recording in said associated storage locations of the data values table the values of the data variables contained in said messages;

task input means interfacing said applications computer for temporarily storing a task input message containing the values of the data variables required by said applications computer for the execution of the next scheduled task;

task dispatcher means responsive to the task identified in each of said dispatch task signals for selecting from said data values table the values of the data variables required for the execution of the scheduled task identified in said dispatch task signal and for recording said selected values in said task input means to generate said task input message;

task releaser means responsive to said task done signal generated by said applications computer signifying it has completed the execution of the preceeding scheduled task for releasing said task input message stored in said task input means to said applications computer for the execution of the scheduled task;

task output means for temporarily storing the values of the data variables produced by the execution of the task currently being executed by said applications computer; and

task results message sender means responsive to said task done signal generated by the applications computer signifying it has completed the execution of its current task for sending said messages to all of the computers, said messages containing the identity and values of the data variables stored in said task output means.

2. The task communicator of claim 1 wherein said applications computer includes a program memory storing a set of instructions for each assigned task and wherein the set of instructions for each task has a predetermined starting address, said task dispatcher means further includes:

look up table means storing the starting address in the computer'"'"'s memory where the set of instructions for each assigned task begins; and

means for recording in said task input means the starting address stored in said look-up table corresponding to the task identified by said dispatch task signal.

3. The task communicator of claim 1 wherein the data variables required for the execution of any task being generated at different times, and several values of the same data variable may be generated before a task is executed requiring an earlier generated value for that data variable, and wherein said dispatch task signal further includes an execution number distinguishing the execution of the identified task from all other executions of the same task, said task results message sender means further includes means for inserting in each message containing the value of a data variable, a sequence number corresponding to the execution number of the task that generated the data variable, and

wherein said associated storage location in said data values table includes a plurality of entries for each data variable and each entry for the same data variable further storing a different sequence number;

and

wherein said store data value means comprises;

means for recording the value of the data variable contained in a received message in the entry for that data variable having the same sequence number as the sequence number contained in the message;

means for recording the value of the data variable contained in a received message in the entry for that data variable having the oldest sequence number when no entry is found for that data variable having the sequence number contained in the message and the oldest sequence number is older than the sequence number contained in the received message; and

means for recording said sequence number contained in the received message in the entry where the value of the data variable is recorded; and

wherein said task dispatcher means includes;

means for identifying the data variables required for the execution of the task identified by said dispatch task signal;

look up table means storing a delay integer for each identified data variable required for the execution of each task; and

means for computing the sequence number of each identified data variable from the corresponding delay integer and the execution number contained in said dispatch task signal to identify said selected data variable.

4. The task communicator of claims 1 or 3 further including:

an execution time table storing numbers indicative of the maximum and minimum execution times for each task;

watch-dog timer means responsive to sequential release task signals for generating a number indicative of the time required by the computer to execute each task; and

means for comparing the number generated by said watch-dog timer means with said numbers indicative of maximum and minimum execution times to generate an error signal when the number generated by said watch-dog timer means is greater than the number indicative of the maximum execution time or smaller than the number indicative of said minimum execution time; and

means for sending an error message to all of the other computers identifying the computer as being faulty in response to said error signal.

5. The task communicator of claim 1 wherein said task input means comprises a first and a second task input table, each capable of storing a task input message, said task dispatcher means includes means for alternately recording said task input messages in said first and second task input tables in response to said sequentially received dispatch task signals;

and

wherein said task releaser means further includes means for identifying to said applications computer which of said first and second task input table contains the task input message to be executed, and wherein said applications computer accesses in an alternating sequence of said first and second task input tables during task execution while the task input message for the next task to be executed is simultaneously being recorded in the other task input table.

6. The task communicator of claim 5 wherein said task output means comprises a first and a second task output table, said task releaser further includes means for identifying to said applications computer in an alternating sequence, which of said first and second task output tables the values of the data variables produced by the execution of the current task are to be recorded and for identifying to said task results message sender means in a complementary alternating sequence which of said first and second task output table said values of the data variables to be contained in said messages sent to all of the computers are to be extracted;

whereby said applications computer can record the values of the data variables produced by the execution of the current task in one of said first and second task output tables while said task results message sender means may simultaneously access the other of said task output tables to send said messages.

7. The task communicator of claim 6 wherein predetermined data variables are redundantly computed by more than one computer, said output tables further include a redundant value indicator set by said computer identifying each value of a data variable which is redundantly computed;

and

said task results sender means is responsive to the state of said redundant value indicator and sends to all of the computers a first message type signifying that the contained value of a data variable is not redundantly computed when the redundant value indicator is not set and a second message type signifying that the contained value of a data variable was redundantly computed when the redundant value indicator is set.

8. A method for communicating values of data variables between tasks executed by a multiple computer system wherein each computer is capable of executing an assigned set of tasks, and each computer includes means for selecting in a cooperative manner with all of the other computers the tasks it will execute, means for scheduling the selected tasks in the sequential order in which they are selected, and an applications computer for executing the scheduled tasks and wherein all of the computers send to each other messages containing the identities and values of the data variables resulting from the execution of the scheduled tasks, and wherein said applications computer generates a task done signal signifying it has completed the execution of its current task and is ready for a new task, said method comprising the steps of:

recording the values of the data variables contained in said messages to generate a data values table in each computer, each data variable being generated at different times, and several values of the same data variable may be generated before a task is executed requiring an earlier generated value for that data variable;

generating sequential dispatch task signals in response to said task done signals each of said sequential dispatch task signals containing in a sequential order the identity of a scheduled task in its order of selection;

selecting from said data values table in response to said dispatch task signals all of the values of the data variables required for the execution of the scheduled task identified in said dispatch task signals;

temporarily storing said selected values of the data variables for each scheduled task in a task input table to generate a task input message;

releasing said task input message to said applications computer in response to said applications computer generating a task done signal signifying it has completed the execution of the preceeding scheduled task;

executing by said applications computer the scheduled task with the values of the data variables contained in said task input message to produce new values for the data variables;

recording said new values of the data variables produced by the execution of the scheduled task by the applications computer to generate a task output table;

enabling a message sender means in response to said applications computer generating a task done signal signifying it has completed the execution of its current task to send to all of the computers said messages containing the identities and new values of the data variables stored in said task output table.

9. The method of claim 8 wherein said step of enabling a message sender means further includes the step of enabling said message sender means to send to all of the computers a message identifying the task completed and the new task started after sending said messages containing the values of the data variables.

10. The method of claim 8 wherein said applications computer has a program memory storing the instructions for the execution of each assigned task said method further includes the steps of:

storing in a starting address table the starting address in the applications computer'"'"'s program memory where the instructions for the execution of each assigned task begins;

copying in response to said dispatch task signal the starting address of the instructions for the task identified by said dispatch signal from said starting address table into said input table.

11. The method of claim 8 wherein the data variables required for the execution of any task being generated at different times and several values for the same data variable being generated before a task is executed requiring an earlier generated value for that same data variable, and wherein said step of enabling a message sender to send messages containing the values of the data variables further enables said message sender to include in said messages a sequence number distinguishing that particular value of the data variable from all other values of the same data variable generated before and after said particular value, and wherein said data values table further includes a plurality of entries for each data variable, each entry storing a different sequence number corresponding to the value of the stored data variable, said step of recording to generate a data values table further comprising the steps of:

interrogating the sequence numbers stored in the data values table for the data variables contained in the received message to locate an entry for that data variable, having the same sequence number;

recording the value of the data variable contained in the message in the entry having the same sequence number when said same sequence number is found;

recording the value of the data variable contained in the message in the entry having the oldest sequence number when no entry is found having the same sequence number and the oldest found sequence number is older than the sequence number contained in the message; and

recording in the entry where the data value contained in the message is recorded, the sequence number contained in the message.

12. The method of claim 11 wherein said dispatch task signal further includes an execution number indicative of the execution of the same task using values of data variables having different sequence numbers said step of selecting the data variables required for the execution of the task further includes the steps of:

storing in a look up table the identity of each data variable required for the execution of each task and a corresponding delay interger for each data variable;

extracting from said look up table in response to said dispatch task signal the identity of each data variable required for the execution of the task identified in said dispatch task signal and the delay interger corresponding to each extracted data variable;

computing a sequence number for each data variable from said delay intergers and from the execution number contained in the dispatch task signal; and

wherein said step of recording to generate a task input table further includes the step of recording the value of the data variable from the data values table entry having a sequence number corresponding to said computed sequence number to generate said task input table.

13. The method of claim 12 wherein said task input table comprises a first and a second task input table, said step of recording to generate a task input table alternately records the values of the data variables into said first and second task input tables in response to sequential dispatch task signals, and wherein said step of releasing alternately releases the values of the data variables from said first and second task input tables to said applications computer in a complementary sequence in response to sequential task done signals;

whereby while said step of recording records the values of the data variables for one task into one of said task input tables said step of releasing simultaneously releases values of the data variables for the task previously recorded in the other task input table.

14. The method of claims 11 or 12 wherein said task output table comprises a first and a second task output table, said step of recording to generate a task output table alternately records said values of data variables resulting from sequentially executed tasks to generate first and second output tables and wherein said step of enabling said message sender means enables said message sender means to access said first and second task output tables in a complementary sequence for generating said messages containing values of the data variables;

whereby while the computer is recording the values of the data variables in one of said task output tables, said step of enabling said message sender means accesses the other of said task output tables.

15. The method of claim 14 wherein a predetermined data variables are redundantly computed by more than two computers, said output tables further include a redundant value indicator set by said applications computer to identify each value of a data variable which is redundantly computed, said step of enabling said message sender means further includes the steps of:

detecting the state of said redundant value indicator to determine if said redundant value indicator is set;

sending a first type message signifying that the contained value is a redundantly computed data variable when said redundant value indicator is set; and

sending a second type message signifying that the contained value is a singularly computed data variable when said redundant value indicator is not set.

16. The method of claim 13 further including the steps of:

measuring the time between successives task done signals to determine the execution time of each task;

comparing the measured execution time with predetermined maximum and minimum times to generate an error signal when the measured execution time is not between said maximum and minimum times; and

sending an error message to all of the computers identifying the computer as faulty in response to said error signal.

17. The method of claim 15 further including the steps of:

measuring the time between successive task done signals to determine the execution time of each task; and

comparing the measured execution time with predetermined maximum and minimum times to send to all of the computers an error message signifying the computer as being faulty when the measured execution time is not between said maximum and minimum times.