Fault resilient/fault tolerant computing

• US 5,790,397 A
• Filed: 09/17/1996
• Issued: 08/04/1998
• Est. Priority Date: 09/17/1996
• Status: Expired due to Term

• Current Assignee: Stratus Technologies Bermuda Ltd. (Stratus Technologies Bermuda Holdings Ltd.)
• Original Assignee: Marathon Technologies Corporation (Stratus Technologies Bermuda Holdings Ltd.)
• Inventors: Leveille, Paul A., McCollum, James D., Muench, Erik, Tremblay, Glenn A., Bissett, Thomas D., Fitzgerald, V, Martin J.
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US08/710,404
• Time in Patent Office: 686 Days
• Field of Search: 364/131-136, 364/184-187, 395/182.09, 395/182.1, 395/185.08, 395/185.1, 395/200, 395/78, 395/881, 395/733, 395/734, 395/736, 395/737, 395/739, 395/740, 395/200.53, 371/68.1, 371/47.1
• US Class Current: 700/2
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0745 in an input/output transactions management context input/output processing in general G06F13/00
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06F 11/1641 where the comparison is not performed by the redundant processing components
• CPC Class Codes: G06F 11/1645 and the comparison itself uses redundant hardware
• CPC Class Codes: G06F 11/165 with continued operation after detection of the error
• CPC Class Codes: G06F 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• CPC Class Codes: G06F 11/1683 at instruction level
• CPC Class Codes: G06F 11/1691 using a quantum
• CPC Class Codes: G06F 11/20 using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
• CPC Class Codes: G06F 11/3065 Monitoring arrangements determined by the means or processing involved in reporting the monitored data error or fault reporting or logging G06F11/0766
• CPC Class Codes: G06F 11/327 Alarm or error message display
• CPC Class Codes: G06F 2201/845 Systems in which the redundancy can be transformed in increased performance

Abstract

Data transfer to computing elements is synchronized in a computer system that includes the computing elements and controllers that provide data from data sources to the computing elements. A request for data made by a computing element is intercepted and transmitted to the controllers. At least a first controller responds by transmitting requested data to the computing element and by indicating how a second controller will respond to the intercepted request.

Claims

1. A method of synchronizing data transfer to a computing element in a computer system, the computer system including the computing element and controllers that provide from data sources to the computing element, said method comprising the steps of:

intercepting a request for data made by a computing element;

transmitting the intercepted request to the controllers; and

at least two controllers responding to the computing element in response to the intrecepted request, wherein at least a first controller responds by transmitting requested data to the computing element and by indicating how a second coontroller will respond to the intercepted request.

2. The method of claim 1, further comprising the step of responding, through the second controller, to the intercepted request by indicating that the second controller has no data corresponding to the intercepted request and by indicating that the first controller will respond to the intercepted request by transmitting data to the computing elements.

3. The method of claim 1, further comprising the step of including, in each response to the intercepted request by a controller, an indication as to how each other controller will respond to the intercepted request.

4. The method of claim 1, further comprising the step of comparing the responses to the intercepted request for consistency.

5. The method of claim 4, further comprising the step of including in each response an indication as to how each other controller will respond to the intercepted request,

wherein the step of comparing comprises comparing the indications for consistency.

6. The method of claim 5, wherein, when responses of multiple controllers include requested data, the step of comparing further comprises comparing the data for consistency.

7. The method of claim 4, further comprising the steps of:

comparing, through the computing element, the responses for consistency after the computing element has received responses from all of the controllers, and

notifying the controllers, through the computing element, of the outcome of the comparison and that responses have been received from all of the controllers.

8. The method of claim 4, further comprising the step of disabling one of the controllers when the responses are not consistent.

9. The method of claim 1, further comprising the step of generating an error condition if the computing element does not receive responses from all of the controllers within a predetermined time period.

10. The method of claim 1, wherein a data source is associated with the first controller, the method further comprising the step of obtaining, in response to the intercepted request and through the first controller, the requested data from the data source.

11. The method of claim 1, further comprising the steps of:

maintaining, through the first controller, a record of a status of the second controller, and

using the record when indicating how the second controller will respond to the intercepted request.

12. The method of claim 11, wherein a data source is associated with the second controller, and further comprising the steps of:

maintaining, through the first controller, a record of a status of the data source, and

using the record when indicating how the second controller will respond to the intercepted request.

13. The method of claim 11, further comprising maintaining, through each controller, records of statuses of all other controllers and having controllers use the records when indicating how the other controllers will respond to the intercepted request.

14. The method of claim 13, further comprising:

associating each controller with a data source;

maintaining, through each controller, records of statuses of data sources associated with all other controllers; and

having controllers use the records when indicating how the other controllers will respond to the intercepted request.

15. The method of claim 12, further comprising, when a status of the data source associated with the second controller changes, transmitting, through the second controller, an instruction to the computing element to discard responses to the intercepted request from other controllers.

16. The method of claim 15, further comprising responding, through the computing element, to the instruction by discarding responses from other controllers to the intercepted request and by transmitting to the controllers a notification that the responses have been discarded.

17. The method of claim 16, further comprising responding, through the first controller, to the notification by updating the record of the status of the data source associated with the second controller.

18. The method of claim 17, further comprising, after updating the record, retransmitting, through the first controller, the requested data to the computing element and indicating, through the first controller, how the second controller will respond to the intercepted request.

19. The method of claim 1, wherein a data source is associated with each controller and each of the controllers responds to the intercepted request by:

determining whether an associated data source is expected to process the request;

when the associated data source is expected to process the request, transmitting the request to the associated data source, receiving results of the request from the associated data source, and forwarding the results of the request to the computing element; and

when the associated data source is not expected to process the request, informing the computing element that no data will be provided in response to the request.

20. A method of synchronizing data transfer to computing elements in a computer system, the computer system including the computing elements, data sources, and controllers that provide data from the data sources to the computing elements, said method comprising the steps of:

intercepting a request for data made by a computing element;

transmitting the intercepted request to the controllers; and

responding to the intercepted request, through each of the controllers, by;

determining whether an associated data source is expected to process the request;

when the associated data source is expected to process the request, transmitting the request to the associated data source, receiving results of the request from the associated data source, and forwarding the results of the request to the computing element; and

when the associated data source is not expected to process the request, informing the computing element that no data will be provided in response to the request.

21. A method of maintaining synchronization between computing elements processing identical instruction streams in a computer system, the computer system including the computing elements and controllers that provide data from data sources to the computing elements, wherein the controllers operate asynchronously to the computing elements, said method comprising the steps of:

at computing elements processing identical instruction streams, each computing element;

stopping processing of the instruction stream at a common point in the instruction stream, generating a freeze request message, and transmitting the freeze request message to controllers;

at a controller;

receiving a freeze request message from a computing element, waiting for a freeze request message from other computing elements, and, upon receiving a freeze request message from each computing element processing an identical instruction stream, generating a freeze response message and transmitting the freeze response message to the computing elements; and

at the computing elements processing identical instruction streams, each computing element;

upon receiving a freeze response message from a controller, waiting for freeze response messages from other controllers to which a freeze request message was transmitted, and, upon receiving a freeze response message from each said controller, generating a freeze release message, transmitting the freeze release message to controllers, and resuming processing of the instruction stream.

22. The method of claim 21, wherein the common point in the instruction stream corresponds to an I/O operation.

23. The method of claim 21, wherein the common point in the instruction stream corresponds to occurrence of a predetermined number of instructions without an I/O operation.

24. The method of claim 21, wherein the step of generating a freeze response message comprises including a time update in the freeze response message, the method further comprising having a computing element, upon receiving a freeze response message from each controller to which a freeze request message was transmitted, updating a system time using the time update from a freeze response message.

25. The method of claim 24, wherein the step of updating a system time comprises using the time update from a freeze response message generated by a particular controller.

26. The method of claim 21, further comprising having a computing element, upon receiving a freeze response message from each controller to which a freeze request message was transmitted, processing data received from a controller prior to receipt of a freeze response message.

27. A computer system including:

a computing element,

data sources, and

controllers that provide data from the data sources to the computing element, wherein;

the computing element is configured to intercept a request for data made by software running on the computing element and to transmit the intercepted request to the controllers; and

at least a first controller is configured to respond to the intercepted request by transmitting requested data to the computing element and by indicating how a second controller will respond to the intercepted request.

28. The system of claim 27, wherein the second controller is configured to respond to the intercepted request by indicating that the second controller has no data corresponding to the intercepted request and by indicating that the first controller will respond to the intercepted request by transmitting data to the computing element.

29. The system of claim 27, wherein each controller is configured to include in response to the intercepted request an indication as to how each other controller will respond to the intercepted request.

30. The system of claim 27, wherein the computing element is configured to compare the responses to the intercepted request for consistency.

31. The system of claim 30, wherein the computing element is configured to compare the responses for consistency after the computing element has received responses from all of the controllers and to notify the controllers of the outcome of the comparison and that responses have been received from all of the controllers.

32. The system of claim 27, wherein the computing element is configured to generate an error condition if the computing element does not receive responses from all of the controllers within a predetermined time period.

33. The system of claim 27, wherein:

a first data source is associated with the first controller, and

the first controller is configured to obtain the data requested in the intercepted request from the first data source.

34. The system of claim 27, wherein the first controller is configured to maintain a record of a status of the second controller and to use the record when indicating how the second controller will respond to the intercepted request.

35. The system of claim 34, wherein:

a first data source is associated with the second controller, and

the first controller is configured to maintain a record of a status of the first data source and to use the record when indicating how the second controller will respond to the intercepted request.

36. The system of claim 35, wherein the second controller is configured to transmit an instruction to the computing element to discard responses from other controllers to the intercepted request when a status of the first data source changes.

37. The system of claim 36, wherein the computing element is configured to respond to the instruction by discarding responses from other controllers to the intercepted request and by transmitting to the controllers a notification that the responses have been discarded.

38. The system of claim 37, wherein the first controller is configured to respond to the notification by updating the record of the status of the first data source.

39. The system of claim 38, wherein the first controller is configured, after updating the record, to retransmit the requested data to the computing element and to indicate how the second controller will respond to the intercepted request.

40. The system of claim 27, wherein:

a data source is associated with each controller, and

each controller is configured to respond to the intercepted request by;

determining whether an associated data source is expected to process the request;

when the associated data source is expected to process the request, transmitting the request to the associated data source, receiving results of the request from the associated data source, and forwarding the results of the request to the computing element; and

when the associated data source is not expected to process the request, informing the computing element that no data will be provided in response to the request.

41. A computer system including:

a computing element,

data sources, and

controllers that provide data from the data sources to the computing element, wherein;

the computing element is configured to intercept a request for data made by software running on the computing element and to transmit the intercepted request to the controllers; and

each controller is configured to respond to the intercepted request, by;

determining whether an associated data source is expected to process the request;

when the associated data source is expected to process the request, transmitting the request to the associated data source, receiving results of the request from the associated data source, and forwarding the results of the request to the computing element; and

when the associated data source is not expected to process the request, informing the computing element that no data will be provided in response to the request.

42. A computer system including:

computing elements configured to process identical instruction streams,

data sources, and

controllers configured to provide data from the data sources to the computing elements and to operate asynchronously to the computing elements, wherein;

each of the computing elements is further configured to;

stop processing of the instruction stream at a common point in the instruction stream,

generate a freeze request message, and

transmit the freeze request message to the controllers;

a controller is further configured to;

receive a freeze request message from a computing element,

wait for a freeze request message from other computing elements, and,

upon receiving a freeze request message from each computing element, generate a freeze response message and transmit the freeze response message to the computing elements; and

each of the computing elements is further configured to;

upon receiving a freeze response message from a controller, to wait for freeze response messages from other controllers to which a freeze request message was transmitted, and,

upon receiving a freeze response message from each said controller, to generate a freeze release message, transmit the freeze release message to the controllers, and resume processing of the instruction stream.