Functional Lockstep Arrangement for Redundant Processors

The present invention pertains to redundant processor systems and more particularly to a functional lockstep arrangement for redundant processors in real-time processing applications.

Processor systems used for critical real-time processing applications have inherent problems in determining when a hardware failure has occurred and taking subsequent corrective action. One method of detecting such failures and maintaining consistent operation is to use redundant processors with synchronous processing. In such situations, the processors each perform the same exact instruction at the same time. This is called clock lockstep processing. Usually a third processor monitors the operation of the redundant processors by comparing the inputs and outputs of the processors. If a mismatch of the inputs or the outputs of the processors is detected, the third processor determines which of the two processors is operating properly and disconnects the other processor.

The redundant lockstep implementation has several drawbacks. First, increasing microprocessor throughput requires an increase in the processor's clock speed. With increasing clock speeds and processor complexity, clock lockstep is very difficult to achieve and maintain. For example, even when processors are in a known condition such as a reset, maintaining clock lockstep is very difficult. The setup and hold times for synchronous reset signals become narrower as clock speeds are increased. As a result, the circuitry needed to meet setup and hold time conditions becomes more complex and expensive.

Second, asynchronous inputs to a redundant processors will generally fail in the clock lockstep mode. Whenever asynchronous signals are sampled, there are times when the input signal will change during the sampling time. When this occurs, there is a probability that the input signals change may not be seen by one of the processors. Further, when the input signal causes a processor interrupt to occur, it would be possible for one processor to respond to the interrupt and start execution of an interrupt service routine while the second processor would not see the interrupt until one clock cycle later. Hence, the two processors will not remain in clock lockstep although there is not a hardware fault.

Third, internal processor states cannot always be guaranteed to be the same even though redundant processors are executing the same instruction. The internal processor states are especially hard to predict after the processors have undergone a reset or initialization process. Hence, it may be difficult or impossible to insure clock lockstep in such situations.

Accordingly, it is an object of the present invention to provide a functional lockstep processor arrangement.

According to the present invention, a novel functional lockstep apparatus for redundant processors is shown.

A function lockstep arrangement simultaneously operates a plurality of N redundant processors. The functional lockstep arrangement includes a first plurality of redundant processors and a peripheral devices. Control logic is also included which is coupled between the plurality of redundant processors and the peripheral devices. The control logic asynchronously requests by the plurality of redundant processors for access to the peripheral devices. The control logic determines that the requests of the processor means are substantially identical and permits access to the peripheral devices.

The above and other objects, features, and advantages of the present invention will be better understood from the following detailed description taken in conjunction with the accompanying drawings.

FIG. 1 is a block diagram of the functional lockstep arrangement for redundant processors in accordance with the present invention.

FIG. 2 is a block diagram of the comparison logic of FIG. 1.

FIG. 3 is a flow diagram of the functional lockstep write operation flow.

FIG. 4 is a flow diagram of the functional lockstep read operation flow.

FIG. 5 is a block diagram of the processor and memory system shown in FIG. 1.

Referring to FIG. 1, a block diagram of a functional lockstep arrangement for redundant processors is shown. Processors 1 through N and their associated memory are shown in FIG. 1. The number of processors included in the functional lockstep redundant processor arrangement may include two or more processors. This functional lockstep arrangement is particularly suited to microprocessor implementations. Microprocessors such as the Motorola 56000 family, Motorola 68000 family, Motorola 88000 family, or various other processors such as the Intel 286 or 386 family of processors may be employed in this arrangement. In addition to these processors which have built-in cycle stretching capabilities, a static processor could also be used by adding additional circuitry to gate the clock input signal. Further, since the present invention is a functional lockstep arrangement, the processors may be mixed in kind. That is, a Motorola 68030 may be run in functional lockstep with a 286-type processor.

Each processor and memory 1 through N may be implemented as shown in FIG. 5. FIG. 5 shows processor 1, for example, connected to an instruction memory 7 and to a RAM (scratch pad) memory 8. Instruction memory 7 provides microprocessor 1 with the instructions which it is to execute for performing the overall processor functions. Instruction memory 7 is typically a read-only-type memory so that instructions may not be inadvertently destroyed. RAM memory 8 is a scratch pad memory in which processor 1 keeps transient data and performs any calculations required of it. RAM memory 8 is typically a read/write memory under the control of processor 1.

Returning again to FIG. 1, processors 1 through N are shown connected to comparison logic 2 and to synchronization logic 3. Comparison logic 2 and synchronization logic 3 provide for the functional lockstep arrangement. Comparison logic 2 is further connected to the input and output peripherals 4.

The redundant processors 1 through N and their associated memories are configured as if they were stand-alone processors. The instruction memories 7 need not necessarily have the identical program instructions, however, results from the processors must be written to common peripherals in the same order. The comparison logic 2 and synchronization logic 3 cooperate to compare the outputs of the N processors to verify proper synchronous operation. Comparison logic 2 provides a signal to synchronization logic 3 which is used by synchronization logic 3 to functionally synchronize the N processors and to halt any or all of the N processors upon detection of a miscomparison, as required.

Referring to FIG. 2, a block diagram of the comparison logic of FIG. 1 is shown. Each of the N processors is connected to a corresponding register. For example, processor 1 is connected to register 10. Processor N is connected to register 20, etc. Each of the registers 10, 20, etc. is connected to compare logic 15. The compare logic 15 is connected to each of the processors by wait lead. The A space wait lead is connected to processor 1, the N space wait lead is connected to processor N, etc. Register 10 is connected to holding register 25 which stores the data to be output. Compare logic 15 is connected to compare watchdog 30 via the start counter lead and the error lead. A failure signal is generated on the corresponding lead for a watchdog time-out.

For each write operation which is to be compared, each processor 1 through N writes the output into an appropriate register 10, 20, etc. The processor's data and address is held in holding register 25 until the comparison of the processors' output is verified. The advantage of sending the data to a holding register until a valid comparison is made is to prevent any data that miscompares from being written to a peripheral or any other destination.

When the compare logic 15 detects a write operation from any of the processors (1 through N), compare logic 15 asserts the appropriate wait signal via the corresponding lead to that processor to suspend its bus cycle and hold that processor's operation. As the remaining processors perform a similar write to their appropriate registers 10, 20, etc., their wait signal is also asserted via the corresponding lead. When all of the N processors have written into their appropriate registers, compare logic 15 checks the contents of each of the processor's registers. If the contents of the registers match, the signal on the corresponding wait lead is negated or removed and the processors are allowed to continue processing. Instead of a all match-type comparison, a voting scheme may be instituted. Such voting schemes may include an M of N processor match situation. For example, a two-of-three processor match may be considered a valid match under a voting scheme.

If all the outputs fail to compare (or M of N fail to compare in a voting scheme), or if any of the N processors do not write all the data within a predetermined amount of time (a watchdog timer is set at the beginning of the process), a failure condition is indicated on the corresponding lead. The system may then take appropriate action to reconfigure or remove faulty processor from their on-line activity. These system actions could also include indefinitely holding the processors until the system is reset. Once it has been determined by compare logic 15 that a match exists, the enable signal is sent via the corresponding lead to holding register 25. Holding register 25 then transfers the data to the appropriate peripheral device.

When the first processor wrote its data into the corresponding register, compare logic 15 also started the watchdog timer via the start counter lead. This enables the compare watchdog logic 30 to begin overall timing of the processor's write operation. This overall timing is sufficient for each of the processors to respond before the watchdog interval expires. If the watchdog interval expires before each of the processors has responded, the failure signal is generated on the corresponding lead. If a miscompare is detected by compare logic 15, a signal is transmitted on the error lead to compare watchdog logic 30. The generation of the error signal also causes a failure signal to be generated.

Referring to FIG. 3, a flow diagram of the functional lockstep processing for a write operation is shown. Initially, the comparison logic is in wait state 40. When a write operation is performed, the functional lockstep arrangement detects the write and a transition is made to block 41. Block 41 holds the first processor to issue the write operation. This means that the appropriate processor is told via the wait lead to suspend its processing. Next, block 42 determines whether all the processors have performed the write operation. If all the processors have not yet performed the write operation, block 42 transfers control to block 40 which waits until the write operation has been performed by all the processors. When the first processor performed the write operation, a watchdog timer was initiated. This watchdog timer expires after a predetermined time. This time period is sufficient for all the processors to have performed their write operations. When the watchdog timer expires, it indicates that one or more of the processors have failed to perform the appropriate operation within the predetermined time period. If this occurs, a transition is made from the wait state 40 via the time-out-expired path to block 45. Block 45 performs a shutdown and disables the processors performing a restart and other associated operations, as necessary.

When all the processors have performed the write operation, transfer is made from block 42 to block 43 via the YES path. The comparison logic next determines whether the output of the processors all match or satisfies a particular voting scheme (M of N processors match), block 43. If the processor outputs compare, a transfer is made from block 43 to block 44 via the YES path. Block 44 releases the processors to continue their respective processing and allows the write operation to the appropriate peripheral to take place. Next, block 44 transfers control via the continued path to block 40 where the compare logic again enters the wait state.

If the processor's output does not compare or if the voting scheme is not satisfied (M of N processors match), then block 43 transfers control via the NO path to block 45. Block 45 disables the processors, shuts down the system, restarts or issues other appropriate commands for detection of an error condition.

As can be noted from the above, the functional lockstep approach described has the advantage of synchronous operation of redundant processors without the expense of and complex logic to monitor clock lockstep processors. The functional lockstep approach provides for matching on a particular machine instruction such as a write operation or on a functional group of instructions which perform a write or read operation. This has the advantage that different processors may be used as redundant processors. For example, a Motorola processor of the 68000 family may be used with a processor of the 386 family or non-exact program instructions may be used by these processors and still functionally operate as redundant processors.

FIG. 4 is a flow diagram of a functional lockstep read operation. Initially the comparison logic is in wait state, block 50 although processors are correctly operating. When a read operation occurs, block 50 transfers control to block 51 via the READ path. Block 51 holds the first processor to (?) the read command and transfers control to block 52 via the CONTINUE path. Block 52 determines whether all the processors have performed the read operation. If all the processors have not yet performed the read operation, transfer is made from block 52 to block 50 via the NO path. Block 50 waits until another processor has performed the read operation.

If all the processors have performed the appropriate read operation, block 52 transfers control to block 53. Since multiple processors are attempting to read from a single peripheral, it is important to insure that first of all, each of the processors has issued the appropriate read and second of all, the processors read the same information. Since at this point, each of the processors has been held and all the processors are performing a read operation, all the processors will receive the same data. Block 53 releases the processors and transfers control to block 50 via the CONTINUE path. Block 50 waits until the next functional lockstep operation is issued.

When the read command of the first processor to issue a read is received by the compare logic, a watchdog timer is initiated. This watchdog timer is sufficient in time to allow all the processors to issue their respective read commands. If one or more of the processors has failed to respond within the predetermined watchdog time-out period, then block 50 transfers control to block 54 where an error condition is detected and the error noted and appropriate exception procedures executed. The exception procedures may include shutdown, disabling the procedures, or initiating the system clear in restart.

Further, for systems in which processors are interrupt driven, interrupts received by some of the processors and not others may cause a mismatch of functional read/write lockstep. The interrupt-driven system may also use a functional lockstep approach by implementing further control features such as providing a means of turning off interrupts when read or write operations are about to begin by a processor. Secondly, additional control logic may be added to inhibit the interrupt source from occurring when read or write cycles are being executed. Thirdly, a interrupt service status line may be examined prior to read or write operations to determine whether an interrupt is due.

Although the preferred embodiment of the invention has been illustrated, and that form described in detail, it will be readily apparent to those skilled in the art that various modifications may be made therein without departing from the spirit of the invention or from the scope of the appended claims.