Reliable distributed processing system

• US 6,321,344 B1
• Filed: 12/10/1998
• Issued: 11/20/2001
• Est. Priority Date: 12/10/1998
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Fenchel, Gary Grant
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US09/209,099
• Time in Patent Office: 1,076 Days
• Field of Search: 714/4, 714/10, 714/25, 714/31, 712/11, 712/16, 710/107, 710/240, 710/244, 709/201, 709/208, 709/226, 370/400, 370/424, 340/825.06
• US Class Current: 714/4.1
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs

Abstract

A method and apparatus for implementing a highly reliable distributed processing system. The group of processors of the system are linked in a circular list, the final processor being linked to the first processor. Only one of the processors is a lead processor, and has the “Watchdog” data required of a lead processor. Only a lead processor can seize a global resource, and only a lead processor can switch another processor out of service. The successor processor to the lead processor contains a Ghost Object token, which is initially identical to the contents of the Watchdog token, except for an indication that it is a Ghost Object token. This next processor times from the time that it receives the Ghost Object token to insure that it will receive the Watchdog token within a pre-determined time. If it fails to receive the Watchdog token by the end of the time-out, it converts the Ghost Object token to a Watchdog token, and sends a new Ghost Object token to its own successor processor. Eventually, one of the successor processors tests the processor which timed-out, to insure that it is still operative, and if necessary, switches that processor out of service and changed the linkage of the list of processors to by-pass the processor that has been switched out of service. Advantageously, this arrangement allows for a highly reliable distributed multi-processing system without requiring extra hardware.

Claims

1. A multi-processing system comprising:

a plurality of processors; and

means for communicating among the processors;

wherein the processors are linked in an ordered list;

wherein one of the processors has in its memory, the data of a Watchdog token; and

wherein a next processor to said one processor has in its memory, a Ghost Object token;

wherein said Ghost Object token is initially the same as said Watchdog token, except for an indication that the Ghost Object token is not the Watchdog token;

wherein the one processor that has the Watchdog token is the lead processor of the multi-processing system; and

wherein the Watchdog token is passed periodically to a next processor; and

the next processor then passes a Ghost Object token to the following processor.

2. The multi-processing system of claim 1, wherein only the lead processor can allocate global resources.

3. The multi-processing system of claim 1, wherein only the lead processor can switch another processor out of service.

4. The multi-processing system of claim 3, wherein when a processor is switched out of service, linking an immediate predecessor processor of the processor being switched out of service to a next processor of the processor being switched out of service.

5. The multi-processing system of claim 1, wherein a processor holding a Ghost Object token performs timing to insure that the processor holding the Ghost Object token receives the Watchdog token within a pre-specified period of time;

and

if the holder of Ghost Object token does not receive the Watchdog token within the pre-determined time, the holder converts the Ghost Object token to a Watchdog token, and sends a Ghost Object token to its successor processor.

6. The multi-processing system of claim 5, wherein a successor processor of the processor which failed to pass a Watchdog token within a time-out interval tests that processor, and if necessary, switches that processor out of service.

7. The multi-processing system of claim 1, wherein only a lead processor can allocate a global resource;

and

wherein allocating a global resource comprises reserving said global resources by a particular lead processor, and only seizing said global resource when the particular processor again becomes the lead processor after having relinquished the role of lead processor.

8. In a multi-processing system comprising:

a plurality of processors, and means for communicating among the processors, a method for obtaining reliable performance, comprising the steps of;

linking the processors in an ordered list;

storing in one of the processors data of a Watchdog token;

storing in a next processor to said one processor a Ghost Object token;

periodically passing the Watchdog token to a next processor; and

then passing a Ghost Object token from the next processor to the following processor;

wherein the one processor that has the Watchdog token is the lead processor of the multiprocessing system; and

wherein said Ghost Object token is initially the same as said Watchdog token, except for an indication that the Ghost Object token is not the Watchdog token.

9. The method of claim 8, further comprising the step of:

allocating global resources only from said lead processor.

10. The method of claim 8, further comprising the step of:

switching another processor out of service;

wherein only said lead processor can perform the step of switching another processor out of service.

11. The method of claim 10, further comprising the step of:

when a processor is switched out of service, linking an immediate predecessor processor of the processor being switched out of service to a next processor of the processor being switched out of service.

12. The method of claim 8, further comprising the steps of:

a processor holding a Ghost Object token performs timing to insure that the processor holding the Ghost Object token receives the Watchdog token within a pre-specified period of time; and

if the holder of Ghost Object token does not receive the Watchdog token within the predetermined time, the holder converts the Ghost Object token to a Watchdog token, and sends a Ghost Object token to its successor processor.

13. The method of claim 12, further comprising the step of:

one of the successor processors of the processor which failed to pass a Watchdog token within a time-out interval tests that processor, and if necessary, switches that processor out of service.

14. The method of claim 8, further comprising the step of:

a lead processor and only a lead processor allocates a global resource;

wherein allocating a global resource comprises reserving said global resource by a lead processor, and only seizing said global resource when the particular processor again becomes the lead processor after having relinquished the role of lead processor.