Method and apparatus for implementing fault-tolerant processing without duplicating working process

• US 6,687,849 B1
• Filed: 06/30/2000
• Issued: 02/03/2004
• Est. Priority Date: 06/30/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cherf, Gerald Scott
• Primary Examiner(s): Iqbal, Nadeem
• Application Number:
  US09/608,047
• Time in Patent Office: 1,313 Days
• Field of Search: 714/5, 714/6, 714/10, 714/12, 714/13, 714/11, 714/41, 714/42, 714/43, 714/56, 714/15, 714/16, 714/20, 714/38, 711/132, 711/133
• US Class Current: 714/5.1
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating

Abstract

Systems and methods for implementing a memory-efficient fault tolerant computing system are provided. A generic backup process may provide fault tolerance to multiple working processes. The backup process need not include a copy of the code segments executed by the working processes, providing very large savings in memory needed to implement the fault tolerant system. Alternatively, multiple backup processes provide fault tolerance but need not include duplicated code segments for the working processes they support.

Claims

1. A method for enabling recovery of an original working process upon failure including:

obtaining state information associated with the original working process;

obtaining a copy of a code segment associated with the original working process;

loading the code segment into a portion of a memory space; and

causing the code segment to execute as an active working process, responsive to said state information;

wherein obtaining state information comprises;

obtaining a backup memory image of the original working process; and

obtaining current stack frame information of the original working process; and

wherein causing the code segment to execute comprises;

associating information in the backup memory image with the code segment;

associating said current stack frame information with the code segment; and

executing a return into the code segment in response to the current stack frame information.

8. A method as in claim 1, wherein associating information in the backup memory image includes copying said backup memory image into a second portion of said memory space.

9. A method as in claim 8, wherein said second portion of said memory space after said copying includes a stack image having a top, and wherein associating said current stack frame information includes putting a most recent portion of said current stack frame information into the top of the stack image.

10. A method as in claim 1, wherein associating the information relating to said current stack frame information includes putting a most recent program counter value into a currently executing stack frame associated with said code segment.

11. A method as in claim 1, wherein said information relating to said current stack frame information includes a most recent program counter value and said executing is done into the code segment at said most recent program counter value.

18. A system as in claim 1, wherein the original working process is included in a memory included in a router.

2. A method for enabling recovery of an original working process upon failure including:

obtaining state information associated with the original working process;

obtaining a copy of a code segment associated with the original working process;

loading the code segment into a portion of a memory space; and

causing the code segment to execute as an active working process, responsive to said state information;

wherein obtaining state information comprises;

obtaining a backup memory image of the original working process; and

obtaining current stack frame information of the original working process; and

wherein causing the code segment to execute comprises;

associating information in the backup memory image with the code segment;

associating said current stack frame information with the code segment; and

restoring a program counter responsive to the state information.

3. A method for enabling recovery of an original working process upon failure including:

obtaining state information associated with the original working process;

obtaining a copy of a code segment associated with the original working process;

loading the code segment into a portion of a memory space; and

causing the code segment to execute as an active working process, responsive to said state information;

wherein obtaining state information comprises;

obtaining a backup memory image of the original working process; and

obtaining current stack frame information of the original working process; and

wherein causing the code segment to execute comprises;

associating information in the backup memory image with the code segment;

associating said current stack frame information with the code segment; and

restoring a program counter to a state associated with a last checkpoint prior to the failure.

4. A method for generically providing backup for a plurality of working processes comprising:

for each of said plurality of working processes performing;

opening a connection;

designating a memory space;

receiving a plurality of messages on the connection; and

for each of the plurality of messages that is a memory update message,

updating the contents of the memory space in response to said each of the plurality of messages; and

for each of the plurality of messages that is a reconnect request indicating previous working process failure, sending information in said memory space to a source of the reconnect request.

5. A method as in claim 4 comprising:

for each of the plurality of messages that is a reconnect request indicating previous working process failure,

in response to the reconnect request, obtaining a copy of a code segment associated with said each of said plurality of working processes;

loading said copy;

executing into said copy responsive to information in said memory space.

6. A method as in claim 4 wherein said memory space does not include a code segment for any of said plurality of working processes.

7. A system for generically providing backup for a plurality of working processes comprising:

a processing system;

a memory storing code for operating said processing system, said code comprising;

computer code that, for each of said plurality of working processes, opens a connection;

computer code that, for each of said plurality of working processes, designates a memory space;

computer code that, for each of said plurality of working processes, receives a plurality of messages on the connection;

computer code, that for each of said plurality of working processes, for each message that is a memory update message updates the contents of the memory space in response to said each of the plurality of messages; and

computer code, that for each of said plurality of working processes, for each of the plurality of messages that is a reconnect request indicating previous working process failure, sends information in said memory space to a source of the reconnect request.

12. A method for enabling recovery of an original working process including:

maintaining state information associated with the original working process;

upon failure of the original working process, performing;

obtaining a copy of a code segment associated with the original working process;

loading the code segment into a portion of a memory space; and

causing the code segment to execute as an active working process, responsive to said state information; and

wherein said maintaining said state information includes;

maintaining a backup memory image associated with the original working process; and

maintaining current stack frame information associated with the original working process.

13. A method as in claim 12, wherein said current stack frame information includes a program counter value.

14. A method as in claim 13, wherein said current stack frame information further includes environmental information.

15. A method as in claim 13, wherein said current stack frame information further includes a stack frame marker.

16. A method for enabling recovery of an original working process including:

maintaining state information associated with the original working process;

upon failure of the original working process, performing;

obtaining a copy of a code segment associated with the original working process;

loading the code segment into a portion of a memory space; and

causing the code segment to execute as an active working process, responsive to said state information; and

wherein said state information includes dynamic memory information and a program counter value.

17. A method for enabling recovery of an original working process including:

maintaining state information associated with the original working process;

upon failure of the original working process, performing;

obtaining a copy of a code segment associated with the original working process;

loading the code segment into a portion of a memory space; and

causing the code segment to execute as an active working process, responsive to said state information; and

wherein said maintaining state information includes;

receiving checkpoint information including current stack frame information from the original working process;

modifying a backup memory image associated with the original working process in response to the checkpoint information;

storing said current stack frame information.

19. A system for running fault-tolerant software including:

a processing system;

a memory storing code for operating said processing system, said code comprising;

a generic backup module;

an original working process in communication with the generic backup module;

a monitor module, capable of monitoring the run state of the original working process;

a nonvolatile storage device including a code segment associated with the original working process, information on said nonvolatile storage device accessible to said monitor module;

a code segment associated with the original working process stored on said nonvolatile storage device.

20. A system as in claim 19, wherein the generic backup module is capable of backing up a plurality of original working processes.

21. A system as in claim 19, wherein the system includes a plurality of original working processes, and a plurality of code segments.

22. A system as in claim 19, wherein the system includes a plurality of monitor modules, each of said plurality of monitor modules capable of monitoring a plurality of original working processes.

23. A system as in claim 19, wherein the processing system includes a single processor unit.

24. A system as in claim 19, wherein the processing system includes two processor units.

25. A system as in claim 24, wherein one of the two processor units runs the original working process and another one of the two processor units runs the generic backup module.

26. A system as in claim 24, wherein the original working process and the monitor module run on a same one of the two processor units.

27. A system as in claim 19, wherein the processing system includes three or more processor units.

28. A system as in claim 19, wherein the processing system is included in a router.

29. A system for running fault-tolerant software including:

a first processor including a generic backup module;

a second processor including a original working process, the second processor coupled to the first processor, the original working process in communication with the generic backup module;

a third processor including a monitor module, the third processor coupled to the second processor, the monitor module capable of monitoring a run state of the original working process; and

a nonvolatile storage device including a code segment associated with the original working process, information on said nonvolatile storage device accessible by said third processor.

30. A system as in claim 29, wherein the first processor and the second processor are a same processor.

31. A system as in claim 29, wherein the second processor and the third processor are a same processor.

32. A system as in claim 29, wherein the first processor and the third processor are a same processor.

33. A system as in claim 29, wherein the first processor, second processor and the third processor are a same processor.

34. A computer program product for enabling recovery of an original working process comprising:

computer code that maintains state information associated with the original working process by maintaining a backup memory image associated with the original working process and maintaining current stack frame information associated with the original working process;

computer code that, upon failure of the original working process,

obtains a copy of a code segment associated with the original working process;

loads the code segment into a portion of a memory space; and

causes the code segment to execute as an active working process, responsive to said state information; and

a computer readable medium that stores the computer code.

35. The computer program product of claim 34, wherein the computer readable medium is a CD-ROM, floppy disk, tape, flash memory, system memory, hard drive, or data signal embodied in a carrier wave.

36. A computer program product for generically providing backup for a plurality of working processes, comprising:

computer code that, for each of said plurality of working processes, opens a connection;

computer code that, for each of said plurality of working processes, designates a memory space;

computer code that, for each of said plurality of working processes, receives a plurality of messages on the connection;

computer code, that for each of said plurality of working processes, for each message that is a memory update message updates the contents of the memory space in response to said each of the plurality of;

computer code, that for each of said plurality of working processes, for each of the plurality of messages that is a reconnect request indicating previous working process failure, sends information in said memory space to a source of the reconnect request; and

a computer readable medium that stores the computer codes.

37. The computer program product of claim 36, wherein the computer readable medium is a CD-ROM, floppy disk, tape, flash memory, system memory, hard drive, or data signal embodied in a carrier wave.

38. A system for generically providing backup for a plurality of working processes comprising:

for each of said plurality of working processes, means for opening a connection;

for each of said plurality of working processes, means for designating a memory space;

for each of said plurality of working processes, means for receiving a plurality of messages on the connection;

for each of said plurality of working processes, for each message that is a memory update message, means for updating the contents of the memory space in response to said each of the plurality of messages; and

for each of said plurality of working processes, for each of the plurality of messages that is a reconnect request indicating previous working process failure, means for sending information in said memory space to a source of the reconnect request.