Apparatus and method for fault-tolerant computing

• US 5,748,882 A
• Filed: 05/08/1996
• Issued: 05/05/1998
• Est. Priority Date: 09/30/1992
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Huang, Yennun
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): LE, DIEU MINH T
• Application Number:
  US08/643,274
• Time in Patent Office: 727 Days
• Field of Search: 395/184.01, 395/183.14, 395/182.09, 395/182.11, 395/182.14, 395/182.21, 395/182.13, 395/182.18, 395/183.07, 395/183.2, 395/200.11, 395/200.12, 364/264.7, 364/269.4, 364/268.9, 364/285.2, 364/285.3
• US Class Current: 714/47.3
• CPC Class Codes: G06F 11/0715 in a system implementing multitasking multitasking per se G06F9/46
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1479 Generic software techniques for error detection or fault masking
• CPC Class Codes: G06F 11/203 using migration
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups

Abstract

Techniques for fault-tolerant computing which do not require fault-tolerant hardware or a fault-tolerant operating system. The techniques employ a monitor daemon which is implemented as one or more user processes and a fault-tolerant library which can be bound into application programs. A user process which is executing on ordinary hardware under an ordinary operating system is made fault tolerant by registering it with the monitor daemon. The degree of fault tolerance can be controlled by means of the fault-tolerant library. Included in the fault-tolerant library is a function which defines portions of a user process'"'"'s memory as critical memory, a function which copies the critical memory to persistent storage, and a function which restores the critical memory from persistent storage. The monitor daemon monitors fault-tolerant processes, and when such a process hangs or crashes, the daemon restarts it. When the techniques are employed in a multi-node system, the monitor daemon on each node monitors one other node in addition to the processes in its own node. In addition, the monitor daemon may maintain copies of the state of fault-tolerant processes running at least on the monitored node. When the monitored node fails, the monitor daemon starts the processes from the monitored node for which the monitor daemon has state on its own node. When a node leaves or rejoins the multi-node system, what other node a given monitor daemon monitors is automatically redetermined for the new configuration of the multi-node system.

Claims

1. Fault-tolerant computing apparatus for use in a computer system, said apparatus comprising:

a monitor for observing the state of a process executing on a processing unit in the computer system and restarting the process when the process is observed to be unable to continue executing, and

a plurality of fault tolerant library routines, a selected one or ones of said fault tolerant library routines being invocable by said process to provide said process with a corresponding one of a plurality of degrees of fault tolerance such that said observing by said monitor is performed in accordance with said selected fault tolerant routine.

2. The apparatus set forth in claim 1 wherein:

execution of said selected fault tolerant library routine or routines is in response to an invocation of the routine by the process.

3. The apparatus set forth in claim 1 wherein:

said selected fault tolerant library routine or routines includes routines which define and save critical memory used by the process and which restore the critical memory when the process is restarted.

4. The apparatus set forth in claim 1 wherein:

said selected fault tolerant library routine or routines includes routines which define and maintain a logfile of read operations for the process which operations are repeated when the process is restarted.

5. The apparatus set forth in claim 1 wherein:

said selected fault tolerant library routine or routines includes a routine which registers the process with the monitor.

6. The apparatus set forth in claim 1 wherein:

said selected fault tolerant library routine or routines includes a routine which, when executed, sends a signal to the monitor; and

the monitor determines that the process is unable to continue if the monitor does not receive the signal within a predetermined period of time.

7. The apparatus set forth in claim 6 wherein:

the routine which sends the signal further sends a value indicating a predetermined time for a next signal.

8. A computer system for fault tolerant computing comprising:

at least one processor for executing user level processes;

a first user level process executing on said at least one processor;

a user level daemon process executing on said at least one processor;

means for providing a registration message specifying said first user level process to said user level daemon process, said user level daemon process being responsive to said registration message by initiating observation of said first user level process to determine whether said first user level process is unable to continue execution and for restarting said first user level process when said first user level process is observed to be unable to continue execution.

9. The computer system of claim 8 further comprising:

a plurality of fault tolerant library routines, each of said routines being executable by said first user level process.

10. The computer system of claim 9 wherein:

the fault tolerant library routines include routines which define, save, and restore memory used by said first user level process.

11. The computer system of claim 9 wherein:

the fault tolerant library routines include routines which define and maintain a logfile of read operations for said first user level process, which operations are repeated when said first user level process is restarted.

12. The computer system of claim 9 wherein said means for providing a registration message comprises a fault tolerant library routine.

13. The computer system of claim 9 wherein:

the fault tolerant library routines include a routine which, when executed, sends a signal to said user level daemon process; and

the user level daemon process determines that said first user level process is unable to continue execution if said user level daemon does not receive the signal within a predetermined time period.

14. The computer system of claim 13 wherein:

the routine which sends the signal further sends a value indicating said predetermined time period.

15. The computer system of claim 8 further comprising:

a fault tolerant group table specifying a group of user level processes to which said first user level process belongs, said user level daemon being responsive to said fault tolerant group table for restarting each user level process specified in said group at the same time at which said user level daemon restarts said first user level process.

16. The computer system of claim 8 wherein said user level daemon process comprises:

a first daemon process for using polling to determine whether said first user level process is unable to continue execution; and

a second daemon process for restarting said first user level process when the first daemon process determines that said first user level process is unable to continue execution.

17. A computer system for fault tolerant computing comprising:

a plurality of nodes, each of said nodes comprising at least one processor for executing user level processes;

a first user level process executing in a first one of said nodes;

a first user level daemon process executing in a second one of said nodes for actively polling said first one of said nodes for determining whether said first one of said nodes is inoperable, and for restarting said first user level process on said second one of said nodes when said first user level daemon process determines that said first one of said nodes is inoperable;

a second user process executing in said second one of said nodes, wherein said first user level daemon further observes whether said second user process is unable to continue execution and restarts said second user level process on said second one of said nodes when said second user level process is observed to be unable to continue;

a second one of said user level daemon processes executing on said first one of said nodes, said second one of said user level daemon processes copies state information from said first user level process to said first user level daemon process, and said first user level daemon process employs said state information in restarting execution of said first user level process; and

computer program code executed by said first user level process, said computer program code comprising a first fault tolerant library routine which, when executed, saves said state information.

18. A distributed computer system for fault tolerant computing comprising:

a plurality of nodes, each of said nodes comprising;

at least one processor for executing user level processes;

a user level daemon process executing on said at least one processor;

means for providing a registration message specifying a user level process to said user level daemon, said user level daemon being responsive to said registration message by initiating observation of a specified user level process to determine whether said specified user level process is unable to continue execution and for restarting said specified user level process when said specified user level process is observed to be unable to continue executing; and

wherein a first one of said user level daemon processes executing in a first one of said plurality of nodes further observes whether a second one of said plurality of nodes is operating.

19. The distributed computer system of claim 18 wherein said second one of said plurality of nodes is executing a first user level process;

and

wherein said first one of said user level daemon processes responds to a failure of said second one of said plurality of nodes by starting execution of a process equivalent to said first user level process on said first one of said plurality of nodes.

20. The distributed computer system of claim 19 wherein:

a second one of said user level daemon processes executing on said second one of said plurality of nodes copies state information from said first user level process to said first one of said user level daemon processes;

and wherein said first one of said user level daemon processes employs said state information in starting execution of a process equivalent to said first user level process.

21. The distributed computer system of claim 20 wherein each of said nodes further comprises:

computer program code executable by said user level processes, said computer program code comprising a first fault tolerant library routine which, when executed, saves user level process state information.

22. The distributed computer system of claim 18 wherein the user level daemon process in each of said nodes further comprises:

means for deleting a second user process which is equivalent to a first user level process if said user level daemon determines that said first user level process is executing on an associated primary node and said second user process is executing on a node other than said primary node.

23. The distributed computer system set forth in any of claims 18, 19, or 22 wherein:

said nodes being arranged such that each of said nodes is observed by a single one of said user level daemons and each of said user level daemons observes a single one of said nodes.

24. The distributed computer system of claim 23 wherein each of said user level daemons further comprises means for maintaining said arrangement when a node observed by the user level daemon fails.

25. A method for operation of a fault tolerant computer system, said system comprising at least one processor for executing user level processes, said method comprising the steps of:

providing a registration message specifying a particular user level process which is executing on a processor to a user level daemon process, said user level daemon process being responsive to said registration message for performing the steps of;

monitoring said specified user level process to determine whether said specified user level process is unable to continue executing; and

restarting said specified user level process if said specified user level process is unable to continue executing.

26. The method of claim 25 wherein said step of providing a registration message further comprises the step of executing a fault tolerant library routine.

27. The method of claim 25 wherein said specified user level process performs the step of:

sending a signal to said user level daemon process, and wherein said step of monitoring further comprises the step of;

determining that said specified user level process is unable to continue if said user level daemon does not receive said signal within a predetermined time period.

28. The method of claim 25 wherein said fault tolerant computer system further comprises a fault tolerant group table specifying a group of user level processes to which said specified user level process belongs, said user level daemon process further responsive to said fault tolerant group table for performing the step of:

restarting each user level process specified in said fault tolerant group table at the same time as when said user level daemon process restarts said specified user level process.

29. A method for operation of a fault tolerant distributed computer system, said system comprising a plurality of nodes, each node comprising at least one processor for executing user level processes, the method comprising the steps of:

executing a first user level daemon process on a first node, said first user level daemon process performing the steps of;

monitoring a second node to determine whether said second node is inoperable, wherein said second node is executing a second user level process; and

restarting said second user level process on said first node when it is determined that said second node is inoperable;

executing a third user level process on said first node;

said first user level daemon process performing the further steps of;

monitoring said third user level process to determine whether said third user level process is unable to continue executing;

restarting said third user level process if said third user level process is unable to continue executing; and

executing a second user level daemon process on said second node;

said second user level daemon process performs the step of;

copying state information from said second user level process to said first user level daemon;

said step of restarting said second user level process on said first node further comprises the step of;

restarting said second user level process using said state information.