Fault tolerant computer system with provision for handling external events

A fault tolerant computer system employing primary tasks and corresponding backup tasks. The system operates to provide fault tolerant operation even where uncontrolled external events may occur whose time of occurrence may affect task performance. For this purpose, external event data is stored for each external event occurring during performance of a primary task which indicates the event type and the relationship between the occurrence of the external event and the occurrence of a predetermined primary task event, such as a memory access operation. This external event data is sent to each respective backup task along with messages transmitted to the respective primary task. In the event a primary task fails, the backup task will replay the failed primary task by processing these transmitted messages while using the transmitted external event data to redeliver each external signal to the backup task at an appropriate time which will assure that the backup task properly recovers the primary task.

This application contains subject matter related to my prior copending 
patent application Ser. No. 07/521,283, filed May 9, 1990, now U.S. Pat. 
No. 5,271,013. 
BACKGROUND OF THE INVENTION 
This invention relates to improved means and methods for providing fault 
tolerance in a data processing system. 
As computer systems increase in speed, power and complexity, it has become 
of increasing importance to provide fault tolerance in such systems to 
prevent the system from "going-down" in the event of hardware and/or 
software failure. However, providing fault tolerant capabilities in a 
computer system has proven to be expensive as well as introducing 
significant performance penalties. 
A basic way of achieving fault tolerance in a data processing system is to 
provide each task (also called a process) with a backup task such that, if 
the primary task fails, the backup task is automatically able to recover 
and continue execution. For example, a primary task and its backup task 
could be provided using a pair of simultaneously executing CPUs (central 
processing units) intercoupled such that, if one fails, execution 
continues on the other. It will be appreciated that the need to provide 
such duplicate hardware is a very expensive way of achieving fault 
tolerance, particularly since the simultaneously operating duplicate 
hardware cannot be used to provide additional data processing power. 
One known approach for avoiding hardware duplication is to provide a first 
CPU for the primary task, and a second CPU for the backup task, the backup 
becoming active to recover and continue execution only if the primary 
fails. Until then, the backup CPU can do other processing. In order to 
assure that the backup process can take over in the event the primary 
process fails, this known approach provides for a checkpointing operation 
to occur whenever the primary data space changes. This checkpointing 
operation copies the primary's state and data space to that of the backup 
so that the backup task will be able to continue execution if the primary 
task fails. However, the frequent checkpointing required by this approach 
detrimentally affects performance and also uses up a significant portion 
of the added computing power. 
Another known approach is disclosed in U.S. Pat. No. 4,590,554. Although 
this approach also uses checkpointing, it provides the advantage of 
employing a fault tolerant architecture which significantly reduces the 
frequency of checkpointing. However, the approach has the disadvantage of 
requiring a message transmission protocol which is essentially synchronous 
in that it requires messages to be transmitted to primary and backup 
processors substantially simultaneously. Also, the disclosed approach in 
the aforementioned patent has the additional disadvantage of requiring 
atomic transmission, wherein transmittal of a message by a task is not 
allowed unless the receiving tasks and all backups indicate they are able 
to receive the message. Furthermore, no receiving task is allowed to 
proceed until all receiving tasks and backups have acknowledged receipt of 
the message. These message transmission protocol requirements introduce 
constraints that add complexity to the system, as well as having a 
significant detrimental effect on performance. 
Similar approaches to that disclosed in the aforementioned U.S. Pat. No. 
4,590,554 are described in an article by A. Borg, et al., "A Message 
System Supporting Fault Tolerance," Ninth Symposium on Operating Systems 
Principles (Breton Woods, N.H., October 1983), Pages 90-99, ACM, New York, 
1983, and in an article by A. Borg, et al., "Fault Tolerance Under UNIX," 
ACM Transactions on Computer Systems, Vol. 7, No. 1, February 1989, pages 
1-24. 
A significantly improved approach over that disclosed in the aforementioned 
U.S. Pat. No. 4,590,554 is described in my aforementioned patent 
application Ser. No. 07/521,283, which provides a fault tolerant data 
processing system having the advantages of U.S. Pat. No. 4,590,554, while 
reducing message transmission restraints. More particularly, the system of 
Ser. No. 07/521,283 requires neither simultaneity nor atomicity of 
transmission in order to provide fault tolerant operation, whereby 
enhanced performance is achieved. This system of Ser. No. 07/521,283 will 
henceforth be referred to as the Flexible Fault Tolerant System. 
SUMMARY OF THE PRESENT INVENTIONS 
A broad object of the present invention is to provide improved means and 
methods for achieving fault tolerance in a data processing system. 
A more specific object of the invention is to provide a fault tolerant 
system similar to that disclosed in the aforementioned U.S. Pat. No. 
4,590,550 or similar to the Flexible Fault Tolerant System, wherein a 
process (task) is able to accommodate an uncontrolled external event in 
situations where the task has little or no control over when this external 
event occurs, and where the behavior of the task may differ depending on 
the time of occurrence of this external event. 
A further object of the invention is to provide a fault tolerant data 
system, in accordance with the foregoing objects, which is implemented in 
a relatively simple and economical manner. 
In a particular preferred embodiment of the invention, a fault tolerant 
system similar to the Flexible Fault Tolerant System is provided, wherein 
additional hardware is provided for counting "write" references to memory. 
This "write" memory reference data count is treated as part of the task's 
context. The times of occurrence of external events are associated with 
this memory reference "write" data count such that, during recovery of a 
task by its backup, each uncontrolled external event is redelivered to the 
backup at the same logical point as it was delivered to the primary task, 
thereby assuring that a failed task will properly recover, despite the 
occurrence of such external events.

DETAILED DESCRIPTION 
Like numeral and characters designate like elements throughout the figures 
of the drawings. 
Summary of U.S. Pat. No. 4,590,554 (FIGS. 1 and 2) 
It will be helpful in understanding the contribution of the present 
invention and the detailed description to be provided herein to initially 
summarize the construction and operation of the embodiment disclosed in 
the aforementioned U.S. Pat. No. 4,590,554, the contents of which are 
incorporated herein. For this purpose, reference is directed to FIGS. 1 
and 2 herein which respectively correspond to FIGS. 1 and 2 of U.S. Pat. 
No. 4,590,554. 
FIG. 1 illustrates a parallel computer system PCS comprised of primary 
processors 11 and 21, their respective associated backup processors 12 and 
22, a common memory CM, and an interconnecting message bus MB. 
FIG. 2 illustrates one of the processors in FIG. 1, and comprises a read 
counter RC, a write counter WC, a message queue MQ and the remainder of 
the processor RP. A primary processor (11 or 21) uses only the read 
counter RC, and a backup processor (12 or 22) uses only the write counter 
WC. Both RC and WC are initialized to zero at the start of operations. 
During operation, the read counter RC in each primary processor 
accumulates a count of the number of messages which its respective primary 
processor (11 or 21) reads from its message queue MQ to the remainder of 
the processor RP. The write counter WC in each backup processor (12 or 22) 
accumulates a count of the number of messages transmitted by its 
respective primary processor (11 or 21). 
The operation described for the embodiment disclosed in U.S. Pat. No. 
4,590,554 assumes that a first process (task) is being executed on primary 
processor 11 and a second process (task) is being executed on primary 
processor 21. Each message transmitted by a primary processor (e.g., 11) 
is sent substantially simultaneously to three processors, the destination 
primary processor (e.g., 21), the backup processor 22 of the destination 
processor 21, and the backup processor 12 of the transmitting processor 
11. Only when all three processors have received the message and so 
acknowledged is the message transmission considered complete (atomicity). 
Both the destination processor 21 and its backup processor 22 load the 
message into their respective message queue MQ. However, the transmitting 
processor's backup processor 12 uses the received message merely to 
increment its write counter WC, the message thereafter being discarded. 
Each time a primary processor processes a received message, it increments 
its read counter by one. 
Checkpointing is automatically initiated between primary and backup 
processors in the embodiment of U.S. Pat. No. 4,590,554 when the number of 
messages in the message MQ of a backup processor becomes too large. 
Checkpointing causes the backup process to be brought to the same state as 
its primary process, including making their data spaces identical. In 
addition, checkpointing causes the primary process to zero its read 
counter RC after sending the accumulated read count to its backup process. 
It will be remembered that this read count RC indicates the number of 
messages read by the primary process from its message queue MQ since the 
start or the last checkpointing. The backup process uses this read count 
during checkpointing to discard the same number of messages from its 
message queue MQ. Thus, if the primary process should fail, the backup 
process will not process messages already processed by the primary 
process. 
As an example of the operation of the embodiment of aforementioned U.S. 
Pat. No. 4,590,554, it will be assumed that primary processor 21 fails. In 
such a case, its backup processor 22 will start from the point of the last 
checkpointing (or from the start), and begin processing the messages in 
its message queue MQ (FIG. 2). These are the same messages which were sent 
to the primary processor 21. In order to provide proper recovery, the 
backup processor 22 is prevented from retransmitting any messages that its 
failed primary processor 21 transmitted before failure. This is 
accomplished by using the accumulated count in the write counter WC of the 
backup processor 22, which it will be remembered corresponds to the number 
of messages sent by its respective primary processor 21. Each time an 
output message is produced by the backup processor 22 during recovery, 
this write counter WC is decremented by one. The backup processor 22 is 
allowed to transmit a message only after the write counter WC has reached 
zero. The backup processor 22 is thus brought up to the state of its 
failed primary processor 21 and can now take over processing of the 
process (task) which the failed primary processor 21 had been executing. 
Description of Flexible Fault Tolerant System (FIGS. 3-9) 
Initially, it will be helpful to consider some insights relevant to fault 
tolerant operation. 
If a task receives a message, and then fails immediately, one may proceed 
as if the task failed before receiving the message. 
In fact, one may choose to proceed as if the task failed before receiving 
the message until the task performs some action that will persist after 
the failure, for example, the task writes to a disk or terminal, or sends 
a message to another task that survives the failure. Since a CPU failure 
causes the failure of all tasks resident in that CPU, a message sent to 
another task running in the same CPU is not an action that will persist 
after a CPU failure, unless the receiver in turn performs a "persistent 
action". 
More generally, if a CPU fails, it is important that all devices and tasks 
external to that CPU (other CPUs, disks, terminals, etc.) agree on the 
state of the CPU at the time of failure. It is not important whether the 
agreed upon state is the actual state of the CPU at the time of the 
failure. 
The failed CPU may in fact have performed many additional processing steps, 
but no persistent actions, in which case the backups need not take them 
into account in order to recover properly. Recovery can thus commence at 
the agreed on state, and recompute the processing steps up to and beyond 
the actual state at the time of failure. In fact, recovery may perform 
different processing steps than the original CPU, but this is transparent 
to the user, as will be understood from the above insights, since no 
consequences of the original processing steps are visible. 
As shown in FIG. 3, three primary tasks 31, 41 and 51 are implemented on 
CPU A, and communicate with each other and with an outgoing CPU Queue via 
an internal message network 35, which may be a conventional bus 
arrangement. Although only three primary tasks 31, 41 and 51 are 
illustrated on CPU A, it will be understood that additional tasks could be 
provided. 
As also shown in FIG. 3, task 31 on CPU A is provided with a backup task 32 
implemented on CPU B, task 41 on CPU A is provided with a backup task 42 
implemented on CPU C, and task 51 on CPU A is provided with a backup task 
52 implemented on CPU D. More than one backup task could be implemented on 
the same CPU. Each CPU includes a memory M coupled to the internal 
communication network 35 which provides a respective data space for each 
task implemented on the CPU. CPU's B, C and D may each have a CPU Queue 
(as does CPU A), but it is not used if the CPU contains only backup tasks. 
Communication between CPUs A, B, C and D14 is provided by an external 
communication network 45 which may take various forms known in the art, 
such as indicated by the message BUS MB in the aforementioned U.S. Pat. 
No. 4,590,554. As shown in FIG. 3, peripherals P are also coupled to the 
external communication network 45 via an I/O. The peripheral P may, for 
example, include one or more disk drives. 
Each of the primary tasks 31, 41, 51 and their respective backup tasks 32, 
42, 52 will now be considered in more detail. One skilled in the art will 
understand from the description herein that different arrangements can be 
used with additional tasks and CPUs. For the purposes of the embodiment 
being considered herein, it will be assumed that primary tasks 31, 41, 51 
which are all on CPU A, receive messages only from each other, via 
internal communication network 35, and not from outside of their 
respective CPU A. It will also be assumed that message deliveries from 
tasks 31, 41, 51 outside of CPU A are only to their respective backup 
tasks 32, 42, 52 on CPUs B, C, D respectively, via external communication 
network 45. As will be evident to those skilled in the art, the structure 
and operations described herein for a task are implemented by its 
respective CPU. 
As shown in FIG. 3A, each task (31, 32, 41, 42, 51, 52 in FIG. 3) includes 
a message queue MQ for receiving and storing messages. Each task also 
includes a read counter RC and a write counter WC. If the task is a 
primary task (such as 31, 41, 51 in FIG. 3), then only the read counter RC 
is used, this use being to accumulate a count of the number of messages 
read by the primary task from its message queue MQ. If, on the other hand, 
the task is a backup task (such as 32, 42 and 52 in FIG. 3), then only the 
write counter WC is used, this use being to accumulate a count of the 
messages sent by its respective primary task (31, 41, 51 in FIG. 3). 
The operation of the message queue MQ, read counter RC and write counter WC 
may typically be as previously described herein with respect to the 
aforementioned U.S. Pat. No. 4,590,554. Also, checkpointing and recovery 
by a backup task may likewise typically be provided as described in 
aforementioned U.S. Pat. No. 4,590,554, except for the differences pointed 
out herein resulting from taking advantage of the previously considered 
"insights." The operation of the embodiment illustrated in FIGS. 3 and 3A 
will now be considered in more detail. As mentioned previously, it is 
assumed that primary tasks 31, 41, 51 on CPU A communicate only with each 
other, via internal communication network 35, and that respective backup 
tasks 32 are provided on CPUs B,C and D, respectively. Each message sent 
by a primary task (31, 41 or 51) typically includes an associated task 
address which is used by the internal communication network 35 to direct 
the message to the indicated task. Messages required to be sent to backup 
tasks (32, 41, 52 on CPUs B,C,D, respectively) are sent by the internal 
communication network 35 to the outgoing CPU Queue, which operates in a 
first-in, first-out (FIFO) manner. 
An important feature is that, by taking advantage of the insights 
considered earlier herein, a primary task which transmits a message to 
another task on the same CPU is allowed to continue its processing 
immediately, so long as delivery of the message to this other task and the 
respective CPU Queue are assured, even though corresponding backup 
messages in the CPU Queue have not been sent to the backup tasks, thereby 
providing high speed processing. Unlike in the aforementioned U.S. Pat. 
No. 4,590,544, these backup messages can be sent to the appropriate backup 
tasks via the external communication network 45 when convenient to do so. 
This applies so long as a primary task does not perform a persistent 
action, which it will be remembered is an action taken by a primary task 
which will persist after failure, such as when the task writes to a disk 
or terminal, or sends a message to another task that survives the failure. 
When a primary task (21 or 31) is required to perform a persistent action, 
the primary task first checks the outgoing CPU Queue to determine whether 
all backup messages corresponding to messages already processed by the 
task have been delivered to the backups. If the delivery of all such 
required messages has been assured, the task performs the persistent 
action and continues processing. If not, the primary task initiates the 
required delivery to the backups, after which the primary task then 
performs the persistent action and continues processing. The task may 
again continue processing without being concerned about delivery of 
processed messages to their backups until the next persistent action is 
required to be performed. It will be understood that various techniques 
well known in the art may be employed for assuring the delivery of a 
transmitted message, such as for example, by using acknowledgment signals, 
handshaking, echoes, error checking, or other appropriate means. 
Various examples illustrative of operations of FIG. 3 will next be 
presented. These examples are presented in summarized form in the flow 
charts provided in FIGS. 4-9. These flow charts also indicate the point in 
the flow corresponding to the state tables included for each example. 
Additionally, it will be helpful to compare these examples and tables to 
those presented in the aforementioned U.S. Pat. No. 4,590,554. 
The examples presented below involve only primary tasks 31 and 41 on CPU A, 
and respective backup tasks 32 and 42 on CPU B and CPU C, respectively. 
Accordingly, only these tasks and CPUs are referred to in these examples. 
In addition, since only CPU A need have a CPU Queue for these examples, 
references to a CPU Queue refer to the CPU Queue of CPU A. In addition, it 
is assumed that appropriate provision is made for assuring the delivery of 
transmitted messages, as indicated above. 
EXAMPLE 1 (FIG. 4) 
TABLE I below shows the start state of the write counter WC, the read 
counter RC, the message queue MQ and the CPU Queue for primary tasks 31, 
41 on CPU A, and their respective backup tasks 32, 42 on CPUs B and C, 
respectively. 
TABLE I 
______________________________________ 
(Example 1, FIG. 4): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 empty empty 
32/B 0 unused empty 
41/A unused 0 empty 
42/C 0 unused empty 
______________________________________ 
Assume that primary task 31 transmits three messages M1, M2, M3 to primary 
task 41, which are stored in task 41's message queue MQ. These messages 
are also stored in the CPU 1 for later delivery to backup CPUs B and C. 
Task 31 may continue its processing even though messages M1, M2, M3 are 
not transmitted to backup CPUs B and C which contain backup tasks 32 and 
42, respectively. CPU A may transmit messages M1, M2, M3 at its leisure so 
long as no persistent action is required by primary tasks 31 or 41. For 
this example, it is assumed that CPU A does not transmit these messages 
M1, M2, M3 at this time. The result is shown in TABLE II below: 
TABLE II 
______________________________________ 
(Example 1, FIG. 4): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 empty M1,M2,M3 
32/B 0 unused empty 
41/A unused 0 M1,M2,M3 
42/C 0 unused empty 
______________________________________ 
Next, task 41 reads M1 and M2 stored in its message MQ, processes them, and 
advances its read counter RC to two to indicate that two messages have 
been processed. The result is shown in TABLE III below: 
TABLE III 
______________________________________ 
(Example 1, FIG. 4): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 empty M1,M2,M3 
32/B 0 unused empty 
41/A unused 2 M3 
42/C 0 unused empty 
______________________________________ 
In response to messages M1 and M2, task 41 generates two messages M4 and 
M5, and sends them to task 31. Messages M4 and M5 are stored in task 31's 
message queue MQ and are also stored in the CPU Queue for later delivery 
to CPUs B and C. The result is shown in TABLE IV below: 
TABLE IV 
______________________________________ 
(Example 1, FIG. 4): 
Write Read Message 
Counter Counter Queue 
Task/CPU 
WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 M4,M5 M1,M2,M3,M4,M5 
32/B 0 unused empty 
41/A unused 2 M3 
42/C 0 unused empty 
______________________________________ 
Assume that CPU A fails at this point, taking down primary tasks 31 and 41. 
Backup tasks 32 and 42 agree CPU A was in a state such that no messages 
were sent or processed by primary tasks 31 and 41 (since none were sent by 
the CPU Queue of CPU A). Backup tasks 32 and 42 thus replay based on this 
agreed on state, starting from the last known state, which is the initial 
state. Thus, the entire processing up to this point is correctly repeated 
from the initial state by backup tasks 32 and 42 which communicate with 
each other via external communication network 45. Note that successful 
recovery is achieved even though the state of CPU A prior to its failure 
(TABLE IV) was in fact very different from that agreed to by backup tasks 
32 and 42. 
EXAMPLE 2 (FIG. 5) 
The beginning state of this example is represented by TABLE IV from example 
1 above, which shows the state prior to CPU A's failure. This Example 2 
assumes that CPU A transmits message M1 in its CPU Queue to backup tasks 
32 and 42 on CPUs B and C respectively, before CPU A fails. Message M1 is 
thus stored in backup task 42's message Queue MQ and backup task 31's 
write counter WC is advanced to one to indicate one message sent by its 
respective primary task 41. The result of this transmission by CPUA V is 
shown in TABLE V below: 
TABLE V 
______________________________________ 
(Example 2, FIG. 5): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 M4,M5 M2,M3,M4,M5 
32/B 1 unused empty 
41/A unused 2 M3 
42/C 0 unused M1 
______________________________________ 
If CPU A now fails, backup tasks 32 and 42 both agree that CPU A was in a 
state where only M1 had been sent by primary task 31 to primary task 41. 
Recovery by backup tasks 32 and 42 is thus performed based on this 
agreement with tasks 32 and 42 restarting from the last known state (the 
initial state). This recovery may typically be provided as described in 
connection with the aforementioned U.S. Pat. No. 4,590,554. It will thus 
be understood that, when task 32 regenerates M1 during recovery, its write 
counter WC (which is at 1 as shown in TABLE V above), is decremented by 
one to zero, and M1 is discarded. When M2 and M3 are regenerated by backup 
task 32, they are transmitted normally to task 42 via the external 
communication network 45, since task 32's write counter WC is now zero. 
When task 42 restarts and attempts to process its first message, it is 
given the original message M1, stored in its message queue MQ (TABLE V 
above). Since message queue MQ is now empty, further message reads by 
backup task 42 use the regenerated M2 and M3 transmitted from recovering 
backup task 32. 
EXAMPLE 3 (FIG. 6) 
The beginning state of this example is shown by TABLE III from Example 1 
above. This Example 3 assumes that task 41 needs to perform a persistent 
action at this time, such as a write-to-disk (this disk may typically be 
located in peripheral P in FIG. 3). Before the disk is written, all 
messages processed in CPU A must be transmitted to their respective backup 
tasks. Thus, messages M1 and M2 (which have been processed) must be 
transmitted to CPUs B and C containing backup tasks 32 and 42 before the 
write-to-disk, since M1 and M2 have been processed (by task 41). To insure 
that messages M1 and M2 are sent before the write-to-disk is performed) a 
marker D is stored in the CPU Queue at a position at least after M1 and M2 
so that D is not reached for performance until after M1 and M2 have been 
sent. The result of storing D in the CPU Queue is shown in TABLE VI below: 
TABLE VI 
______________________________________ 
(Example 3, FIG. 6): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 empty M1,M2,D,M3 
32/B 0 unused empty 
41/A unused 2 M3 
42/C 0 unused empty 
______________________________________ 
Note with respect to TABLE VI above that D could be placed in the CPU Queue 
at any point after M1 and M2 (for example, after M3) since sending M3 
along with M1 and M2 will not interfere with recovery. 
In order to permit primary task 41 to perform the write-to-disk, CPU A now 
transmits M1 and M2 from its CPU Queue to CPUs B and C. Messages M1 and M2 
are thus stored in the message queue MQ of backup task 42 on CPU C, and 
the write counter WC of backup task 32 is advanced to 2 to indicate that 
two messages (M1 and M2) have been sent by its respective primary task 31 
on CPU A. The result is shown in TABLE VII below: 
TABLE VII 
______________________________________ 
(Example 3, FIG. 6): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 empty D,M3 
32/B 2 unused empty 
41/A unused 2 M3 
42/C 0 unused M1,M2 
______________________________________ 
Task 41 now deletes the D entry from CPU A's queue, and performs the 
write-to-disk. 
In order to prevent task 41's backup task 42 on CPU from repeating the 
write-to-disk if CPU A should fail, the performance of the write-to-disk 
by primary task 41 also results in a message being sent to CPU C which 
causes backup task 42's write counter WC to be advanced to 1. The result 
is shown in TABLE VIII below: 
TABLE VIII 
______________________________________ 
(Example 3, FIGS. 6 and 7): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 empty M3 
32/B 2 unused empty 
41/A unused 2 M3 
42/C 1 unused M1,M2 
______________________________________ 
Assume that task 41 next reads M3 from its message queue MQ, processes M3, 
and then replies by sending messages M4 and M5 to task 31, which are 
stored in task 31's message queue MQ and also in the CPU Queue. The result 
is shown in TABLE IX below: 
TABLE IX 
______________________________________ 
(Example 3, FIG. 7): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 M4,M5 M3,M4,M5 
32/B 2 unused empty 
41/A unused 3 empty 
42/C 1 unused M1,M2 
______________________________________ 
If CPU A fails at this point (TABLE IX above), both CPUs B and C agree with 
respect to CPU A that Messages M1 and M2 have been sent, and that the 
write-to-disk is done. The fact that task 41 processed M3 and sent M4 and 
M5 to task 31 before the failure is irrelevant to satisfactory recovery 
since no further persistent action occurred prior to CPU's failure. 
Recovery thus proceeds normally in the manner previously described. Since 
no checkpointing has yet occurred, recovery starts from the initial state 
(TABLE I). More specifically, with respect to backup task 32, messages M1 
and M2 generated by task 41 during recovery are not sent but discarded, 
since write counter WC will not have decremented to "0" until after M2 is 
regenerated. With respect to backup task 42, messages M1 and M2 in its 
message queue MQ will be processed as occurred for the primary task 41 in 
now failed CPU A. When recovering backup task 41 reaches the point at 
which the write-to-disk is to be performed (which it will be remembered 
was performed by primary task 41), this write-to-disk operation is 
prevented from being performed again as result of task 42's write counter 
WC being "1" at this time. It is only after task 42's write counter is 
decremented to "0" (following this disk-to-write prevention) that messages 
are sent by task 42. Accordingly since WC will thus be "0" when messages 
M4 and M5 are generated by task 42, they will be sent to task 32, thereby 
achieving recovery to the point reached prior to CPU A's failure. 
Processing then continues beyond the recovery point using backup tasks 32 
and 42 communicating via external communications network 45. 
EXAMPLE 4 (FIG. 8) 
The purpose of this Example 4 (and Example 5) is to demonstrate 
checkpointing in the embodiment of FIG. 3, and assumes a beginning state 
corresponding to TABLE IV from Example 1 above. 
Assume that, after reaching the state shown in TABLE IV above, task 41 
initiates a checkpointing operation. This is a persistent action, since 
checkpointing requires that state information about task 41 be transmitted 
outside of CPU A. Accordingly, task 41 places the checkpointing data (or 
an appropriate checkpointing marker CK) in the CPU Queue at a position at 
least after M1 and M2, since they have been processed. The result is shown 
in TABLE X below: 
TABLE X 
______________________________________ 
(Example 4, FIG. 8): 
Write Read Message 
Task/ Counter Counter Queue 
CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 M4,M5 M1,M2,M3,M4,M5,CK 
32/B 0 unused empty 
41/A unused 0 M3 
42/C 0 unused empty 
______________________________________ 
Note in TABLE X above that task 41's read counter RC has been zeroed since, 
as far as task 41 is concerned, the required checkpointing has already 
occurred. Also note that both tasks 31 and 41 can proceed with processing 
without concern as to when the checkpointing data is actually sent to its 
backup task 42 in CPU C, so long as any subsequently occurring persistent 
actions are delayed until after the checkpoint data is transmitted to its 
respective backup. Also note in TABLE X that CK was placed in the CPU 
Queue after M5, rather than directly after M1 and M2, which means that M3, 
M4 and M5 as well as M1 and M2 will be transmitted before the 
checkpointing data CK. This will not cause any problem, since CPU A is 
able to transmit messages from its CPU Queue at its convenience (as 
mentioned earlier), unless a persistent action is encountered, in which 
case processed messages have to be transmitted to their respective backups 
before the persistent action can be performed. 
Assume for the purposes of Example 4 that CPU A now begins to transmit M1 
through M5 to backup tasks 32 and 42 on CPUs B and C, respectively, but 
that CPU A fails after successfully transmitting M1, M2, M3, M4 so that 
neither M5 nor the checkpointing data CK are transmitted. The resulting 
state just prior to failure is shown in TABLE XI below: 
TABLE XI 
______________________________________ 
(Example 4, FIG. 8): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 M4,M5 M5,CK 
32/B 3 unused M4 
41/A unused 0 M3 
42/C 1 unused M1,M2,M3 
______________________________________ 
Backup tasks 32 and 42 on CPUs B and C, respectively, initiate recovery 
from the initial state (TABLE I) based on their agreed on perceptions that 
only messages M1, M2, M3, M4 were transmitted, and that checkpointing has 
not yet occurred. 
EXAMPLE 5 (FIG. 9) 
This Example assumes an initial state corresponding to TABLE X of Example 4 
above. However, instead of failing after transmitting M1-M4, as described 
in Example 4, this Example 5 assumes that CPU A's transmission of M1-M5 
and CK is successful, resulting in TABLE XII below: 
TABLE XII 
______________________________________ 
(Example 5, FIG. 8): 
Write Read Message 
Counter Counter Queue 
Task/CPU WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 M4,M5 empty 
32/B 3 unused M4,M5 
41/A unused 0 M3 
42/C 0 unused M3 
______________________________________ 
As will be remembered from the previous discussion, checkpointing brings 
the backup task 42 to the same state as its primary task 41, as well as 
making their data spaces identical in their respective memories M. 
It will be understood that while messages M1 through M5 and CK are being 
transmitted, CPU A is free to continue processing further work for primary 
tasks 31 and 41, provided that further persistent actions are delayed 
until after the checkpointing data has been successfully transmitted. 
If a failure of CPU A should subsequently occur, backup task 32 will 
recover from START and backup task 42 will recover from the above 
checkpoint. 
HANDLING EXTERNAL EVENTS (FIGS. 10-16) 
In the previously described systems, inputs to a task are provided by 
messages. Calls to the operating system may be treated as messages and, 
thus, are readily handled by these systems. However, task behavior may be 
affected in other ways which are not easily handled by these systems. For 
example, the state of a task may be changed by an uncontrolled external 
event where the task has little or no control over when the external event 
occurs, and where the behavior of the task may differ depending on the 
time of occurrence of this external event. 
For example, such an external event may occur because of the action of an 
interrupt handler, or as a result of another process writing to a common 
memory. The following examples, although simplistic, illustrate how such 
an uncontrolled external event may affect the behavior of a task. 
For this purpose, assume that a task executes the program illustrated in 
FIG. 10. If no uncontrolled external event occurs during performance of 
this program, the program output (occurring at program step PC=2 in FIG. 
10) will be as shown in FIG. 11. 
It will be understood from the previous descriptions of U.S. Pat. No. 
4,590,554 and the Flexible Fault Tolerant System that, if the task should 
fail, the Program Output of FIG. 11 can be accurately reproduced using a 
backup task running the same program and initialized in the same manner. 
Now assume that the above program is run again with the difference that an 
uncontrolled external event (such as might be produced by another process 
writing to a common memory) causes a memory action of 
MEM(STATE.rarw.GREEN) to occur while the task program above is being run. 
If this externally caused memory action occurs after the second RED output 
in FIG. 11 (i.e., between Program Output lines 3 and 4 in FIG. 11), and 
between program steps PC=2 and PC=3 in FIG. 10, then the program will 
proceed to PC=5, which will change the memory state back to 
MEM(STATE)=RED). The resulting Program Output will then be as shown in 
FIG. 12. 
On the other hand, if the external event MEM(STATE.rarw.GREEN) were to have 
occurred after the first GREEN Program Output (i.e., between Program 
Output Lines 2 and 3 in FIG. 11) the original Program Output shown in FIG. 
11 would not be changed, since the external event would not affect the 
state of the memory at PC=2 in FIG. 10. The original Program Output in 
FIG. 11 would likewise not be changed if the external event were to occur 
between program steps PC=3 and PC=4 in FIG. 10, since this also would not 
affect the state of the memory at PC=2 in FIG. 10. 
Clearly then, the time at which an uncontrolled external event occurs may 
affect how a task will perform. Thus, if a backup task is to properly 
replay a failed primary task which can be affected by such uncontrolled 
external events, provision has to be made to appropriately account for 
these external events during task performance. The present invention 
provides a particularly advantageous way of solving this problem. 
The approach employed by the preferred embodiment of the present invention 
for handling uncontrolled external events in a fault tolerant system, such 
as previously disclosed herein, will next be described. The basic approach 
is to relate the occurrence of these external events to particular events 
occurring in a primary task. These particular events are treated as part 
of the task context so that, during recovery of a failed task, each 
external event can be redelivered during playback of the backup task at 
the same logical point as it occurred during performance of the primary 
task, thereby assuring that the backup will properly recover. In the 
preferred embodiment described herein, this is accomplished by providing 
for counting "write" data references to memory, the resulting "write" 
counts being part of the task context. Such memory "write" counting can 
readily be provided by these skilled in the art. For example, if the CPU 
employs Motorola 88000 chips, this counting can be performed by counting 
completed memory store (write) instructions. 
Reference is now directed to a preferred embodiment of the present 
invention illustrated in FIG. 13, which is basically similar to FIG. 3, 
except that CPU A, CPU B and CPU C in FIG. 11 each have added thereto a 
memory reference counter MRC and a memory reference counter compare 
register MRCCR which are used in performing the memory "write" counting 
function and in providing recovery. In each CPU, MRC and MRCCR may 
communicate with tasks 31, 41, 51 and memory M via internal communication 
network 35. 
During operation of a primary task, each "write" data reference to memory M 
causes MRC to be incremented by one, except when a task performs a call to 
the operating system and starts executing operating system code, the task 
remaining asleep until the operating system call is completed. It is 
advantageous to zero MRC after each operating system call, as well as 
after each checkpoint, since this results in smaller counts, and thus 
reduces the possibility of a counter overflow. Zeroing MRC after each 
operating system call does not create any problem with respect to memory 
"write" counting, since system calls are treated as messages. 
When an uncontrolled external event occurs during performance of a primary 
task, such as an external signal which changes the task's memory (as 
exemplified previously), the existing memory reference count in MRC along 
with an indication of the type of external signal and the task's register 
context have to be sent to the respective backup task for storage in the 
memory M of its respective CPU. Using the fault tolerant system of U.S. 
Pat. No. 4,590,554 (FIGS. 1 and 2), this data has to be sent immediately 
to the backup, as explained in the summary of this patent. In the Flexible 
Fault Tolerant System (FIGS. 3-9), however, this data is treated like 
other messages and is placed in the CPU Queue of CPU A. For example, if it 
is assumed that the state of the fault tolerant system is as illustrated 
in TABLE II, the occurrence of an uncontrolled external signal with 
respect to task 31 will cause a marker S indicative of the task and type 
of signal to be placed in the CPU Queue along with the task 31 register 
context R, which includes the current count of MRC. This is illustrated in 
TABLE XIII below: 
TABLE XIII 
______________________________________ 
(Example 5, FIG. 8): 
Write Read Message 
Counter Counter Queue 
Task/CPU 
WC RC MQ CPU-Queue 
______________________________________ 
31/A unused 0 empty M1,M2, M3,S,R 
32/B 0 unused empty 
41/A unused 0 M1,M2,M3 
42/C 0 unused empty 
______________________________________ 
Alternatively, the register context R stored in CPU Queue could merely be a 
marker, the full register context being stored in task 31's memory space 
in memory M. Then, when the marker S is reached in the CPU Queue, the 
stored register context R would then be called up from memory M for 
transmission to the backup for storage in the backup memory M. 
Next, an example is presented of how the recovery of a failed task by a 
backup is accomplished when an uncontrolled external event occurs during 
performance of a primary task prior to its failure. For this purpose, it 
will be assumed that a primary task performs the program illustrated in 
FIG. 14, which is the same as shown in FIG. 10. This example assumes that 
the CPU on which the primary task is to be run at least contains a memory 
reference counter MRC (FIG. 13), and that its respective backup CPU at 
least contains a memory reference counter MRC and a memory reference 
compare counter register MRCCR. 
FIG. 15 illustrates performance of the program of FIG. 14 by a primary task 
on CPU A in FIG. 13. Note that FIG. 15 indicates, during running of the 
program, the occurrence of "Events", the "Hardware Context" and the 
"Program Output". The first "Event" is a CHECKPOINT which sets MRC=0. At 
this time PC=3 and CF=FALSE, and the state of the memory is 
MEM(STATE=RED). As shown in FIG. 15, the running of the program begins 
with this CHECKPOINT and then proceeds in an expected manner with the 
"Program Output" alternating GREEN, RED, GREEN, RED, GREEN and the value 
of MRC being incremented by one in response to each memory change (write). 
As shown in FIG. 15, the EXTERNAL SIGNAL MEM(STATE.rarw.GREEN) occurs after 
MRC=5, when MEM(STATE=RED). At this time, the "Hardware Context" registers 
have values of PC=8, CF=FALSE, and MRC=5. In the system of U.S. Pat. No. 
4,590,554, this register context is sent to the respective task backup 
along with an indication of signal type. In the Flexible Fault Tolerant 
System, sending of this data to the backup could be delayed by storing 
this data in the CPU Queue, as illustrated in TABLE XIII. 
Continuing with the example in FIG. 15, the occurrence of the EXTERNAL 
SIGNAL MEM(STATE.rarw.GREEN) changes the state of the memory from 
MEM(STATE=RED) to MEM(STATE=GREEN). Thus, the next program output is GREEN 
(as was the previous output instead of RED, as it would have been if the 
EXTERNAL SIGNAL MEM(STATE.rarw.GREEN) had not occurred. The program then 
continues. A FAILURE occurs when MRC=8, as shown. 
Attention is now directed to FIG. 16, which is an example of how a backup 
would play back the failed task in FIG. 15. This example assumes that the 
register context and the signal type were sent to the backup prior to 
failure. Since there were no system calls following the CHECKPOINT in FIG. 
15, the backup starts at this CHECKPOINT, which sets PC=3, CF=FALSE and 
MRC=0 to correspond to the values which they had at the CHECKPOINT in FIG. 
15. In addition, MRCCR is set to MRCCR=5, which was the value of the 
primary task's MRC when the EXTERNAL SIGNAL occurred, and which value was 
sent to the backup as part of the register context, as explained in 
connection with FIG. 15. It will be understood that MRCCR=5 tells the 
backup that the external signal (whose type was also sent to the backup) 
should be delivered after five "write" references to memory. 
Thus, as illustrated in FIG. 16, backup proceeds normally with MRC being 
incremented by one for each memory "write". At each incrementing of MRC, a 
comparison is made with MRCCR=5. When MRC=5, the registers are set in 
accordance with the register context which existed just prior to the time 
that the EXTERNAL SIGNAL was delivered during performance of the primary 
task, this register context having been sent to the backup and stored 
therein, as explained previously. Accordingly, PC and CF are set to PC=8 
and CF=FALSE, respectively; in addition, MRCCR is zeroed so that MRCCR=0. 
The EXTERNAL SIGNAL MEM(STATE.rarw.GREEN) is then derived from backup 
storage and delivered, following which playback continues correctly 
replaying the primary task, as will be evident from a comparison of the 
Program Outputs of FIGS. 15 and 16. 
It will be understood that, if a second external signal had been sent to 
the backup before the primary task failed, MRCCR would not have been 
zeroed when MCR=MRCCR in FIG. 16, but would have been set to the value MCR 
had in the primary task at the time that this second signal occurred. 
Operation with this second external signal would then have been the same 
as described for the first external signal. In this regard, note in FIG. 
16 that MRC continues to increment beyond MRC=5 so as to provide a count 
for controlling the time of delivery of other external signals which may 
have occurred during the performance of the primary task and sent to the 
backup as previously described. It is further to be noted that, because 
the count of MRC is part of the task context, the replay illustrated in 
FIG. 16 does not need to be continuous. The replay could be preempted at 
any time, and other tasks performed without affecting the correct 
redelivery of an external signal. 
While the present invention has been described herein with respect to 
particular preferred embodiments and operational examples, it is to be 
understood that a wide variety of modifications, additions and extensions 
in construction, arrangement, use and operation are possible without 
departing from the scope of the invention. For example, the invention is 
not limited to employing memory "write" references for providing a count 
to which uncontrolled external events can be related for accurate 
playback. For example, both memory "reads" and "writes" could be counted 
if it were more convenient to do so. Also, program steps could be counted, 
but this is unduly burdensome in most cases. 
It is also to be understood that the reference count set into MRCCR at the 
start of playback in FIG. 16 could be used in various other ways for 
determining when to deliver an external signal. For example, instead of 
comparing MRCCR with MCR, as in FIG. 16, MRCCR could be counted down to 
zero in order to indicate when delivery of the external signal should be 
provided. 
It is additionally to be understood that the page fault capability of a 
CPU's operating system could be used to implement delivery of the external 
signal in the backup. For example, after MRC=MRCCR in FIG. 16, the 
backup's operating system could be used to produce a page fault on the 
next memory reference in order to initiate delivery of the external 
signal. 
It is further to be understood that, although the example of FIGS. 15 and 
16 does not include a call to the operating system, such calls would not 
interfere with proper playback. As mentioned previously, an operating 
system call can be used to zero MRC during performance of the primary 
task, since such zeroing can be accurately reproduced during playback. 
This has the advantage of preventing overflow of MRC. 
The above examples of possible modifications and extensions are merely 
representative and not exhaustive. Accordingly, the present invention is 
to be considered as including all possible modifications, variations and 
extensions encompassed by the appended claims.