Method for multiprocessor communications

• US 4,718,002 A
• Filed: 06/05/1985
• Issued: 01/05/1988
• Est. Priority Date: 06/05/1985
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Tandem Computers Incorporated (HP Inc.)
• Inventors: Carr, Richard W.
• Primary Examiner(s): Zache, Raulfe B.
• Assistant Examiner(s): Ure, Michael J.
• Application Number:
  US06/741,659
• Time in Patent Office: 944 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 371/9, 340/825.05, 340/825.5, 340/825.51
• US Class Current: 709/201
• 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/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: G06F 11/2048 where the redundant components share neither address space nor persistent storage
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00

Abstract

An improved method for communicating updated information among processors in a distributed data processing system. The system includes a plurality of distributed interconnected processors each having a memory. The method includes the steps of prioritizing the processors into a predetermined order, establishing one of the processors as a control processor for the broadcast of update messages, developing an update message in at least one of the processors, selecting in accordance with the control processor one of the processors which has developed an update message as a sender processor, broadcasting the update message of the sender processor to each of the processors, and causing the next processor in order to be selected as control processor in the event that the former control processor fails in service. As one preferred use, the method enables the system to transmit atomic global update messages with a tolerance to multiple processor faults.

Claims

1. A method for communicating updated information among processors in a distributed data processing system comprising a plurality of distributed, interconnected processors each having a memory, including the steps of:

a. prioritizing the processors into a predetermined order;

b. establishing one of the processors as a control processor for the broadcast of update messages;

c. developing an update message having a plurality of bit positions in at least one of the processors;

d. the one processor broadcasting the update message to each of the processors in the following manner;

(1) sending the update message first to the control processor with at least one bit position set to a first state, the control processor acknowledging the update message if no other update message is in the broadcast process;

(2) sending the update message to each of the other processors with the one bit position set to a second state;

(3) sending the update message again to the control processor with the one bit position set to the second state to indicate completion of the broadcast; and

e. causing, in the event the control processor fails, the next processor in order to be selected as the control processor.

2. The method for communicating updated information set forth in claim 1 wherein the step of broadcasting the update message comprises sending the update message to each processor in accordance with the predetermined order.

3. The method for communicating updated information set forth in claim 1 wherein the step of developing an update message includes the step of providing an update sequence number for the message.

4. A multiple fault tolerant global update method in a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:

a. identifying an initial locker processor and arranging all of said processors into an order,

b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor,

c. after setting the update lock semaphore in the locker, the sender processor broadcasting the message to every other processor,

d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received,

e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast.

5. The global update method set forth in claim 4 including the further step of rebroadcasting from the locker processor of the message to the remaining processors in the event that the sender processor fails after it has sent the message to the locker processor and before the update lock semaphore area of the locker has been cleared.

6. The global update method set forth in claim 4 including the further step of automatically transferring the locker processor role to a next processor in the order in the event that the next processor learns that the current locker processor has failed.

7. The global update method set forth in claim 6 comprising a further step in which said next processor rebroadcasts the latest global update message to all other up processors upon becoming locker processor.

9. The global update method set forth in claim 6 wherein the step of clearing the update lock semaphore area in the next locker processor at the completion of the broadcast comprises the step of resending the message to the next locker processor from itself in order to clear its semaphore area.

10. The global update method set forth in claim 4 wherein messages are passed on a repetition basis between all processors of the system in order for each processor to monitor current operational status of every other processor.

11. The global update method set forth in claim 4 wherein the step of broadcasting the message further comprises the step of providing each processor with an update sequence number for the message.

12. The global update method set forth in claim 4 wherein the step of broadcasting the message from the sender processor to every other processor is carried out as an atomic operation.

13. The global update method set forth in claim 4 wherein the step of setting the update lock semaphore in the storage area of the locker processor can be carried out only when no other message broadcast is in progress.

14. The global update method set forth in claim 13 further comprising the step of sending a message to the locker processor which includes setting a lock bit in order to set the update lock semaphore, and wherein the step of broadcasting the message to the other processors includes the step of clearing the lock bit before transmission.

15. The global update method set forth in claim 11 wherein each processor compares the update sequence number for the message received with the update sequence number previously recorded in the processor corresponding to the last message.

16. The global update method set forth in claim 15 comprising the step of negatively acknowledging to the sender processor of a message when its update sequence number does not correctly correspond with the previously recorded update sequence number.

8. The global update method set forth in claim 8 for recovering from a failure of the locker processor during a message broadcast, including the further step of setting the semaphore to identify the next processor in the order and resending the message from the next processor as successor locker processor to every other processor.

17. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:

a. identifying an initial locker processor and arranging all of said processors into an order,

b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor,

c. after setting the update lock semaphore in the locker, the sender processor broadcasting the message to every other processor,

d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received,

e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast, and

f. rebroadcasting from the locker processor of the message to the remaining processors in the event that the sender processor fails after it has sent the message to the locker processor and before the update lock semaphore area of the locker has been cleared.

18. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processor including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:

a. identifying an initial locker processor and arranging all of said processors into an order,

b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending to the locker processor from the sender processor a message having a plurality of bit positions with at least one of the bit position set to a first state, c. after setting the update lock semaphore in the locker, broadcasting the message from the sender processor to every other processor with the bit position set to a second state,

d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received,

e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast,

f. automatically transferring the locker processor role to a next processor in the order in the event that the next processor learns that the current locker processor has failed.

19. The global update method set forth in claim 18 wherein the step of transferring the locker processor role to the next processor in the order is carried out only after the message has been sent to the next processor in the order.

20. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:

a. identifying an initial locker processor and arranging all of said processors into an order,

b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor,

c. after setting the update lock semaphore in the locker, the sender processor broadcasting the message to every other processor,

d. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received,

e. clearing the update lock semaphore area in the locker processor at the completion of the broadcast, and

f. setting the semaphore to identify the next processor in the order and rebroadcasting the message from the next processor as successor locker processor to every other processor, in the event of a failure of the locker processor during a message broadcast.

21. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving messages to and from every other of said processors for thereby enabling each said processor to monitor current operational status of every other of said processors and to send and receive global update messages, said method including the steps of:

a. identifying an initial locker processor and arranging all of said processors into an order,

b. setting an update lock semaphore in a storage area of the locker processor to identify a current sender processor by first sending a message to the locker processor from the sender processor,

c. providing each message with an update sequence number,

d. after setting the update lock semaphore in the locker, the sender process broadcasting the message to every other processor.

e. storing an update lock semaphore in each processor identifying the sender processor of the last global update message received,

f. maintaining a current update sequence number in each processor and negatively acknowleging any message having an update sequence number which does not correspond with the maintained current update sequence number, and

g. clearing the update lock semaphore area in the locker processor at the completion of the broadcast.

22. A global update method for tolerating multiple processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving test messages to and from every other of said processors on a repetition basis for thereby enabling each said processor to monitor current operational status of every other of said processors, said method including the steps of:

a. ordering said processors into a global update order by which one of said processors is an initial locker processor and every other processor is configured automatically to become locker processor upon failure of the current locker processor in accordance with said order,

b. storing in each processor the last global update message including an update lock semaphore for identifying a sender processor, further including an update sequence number for said message, and further including the text of the global update message,

c. when no other global update is being broadcast, setting the update lock semaphore in the locker processor to identify a current sender processor by first enabling an atomic global update message to said locker processor from said sender processor,

d. after setting said update lock semaphore in said locker, the sender processor broadcasting said global update message to every other processor in said order, and

e. clearing said update lock semaphore by resending said atomic global update to said locker professor from said sender processor after it has broadcast said atomic global update to all of said other processors.

23. The global update method set forth in claim 22 further comprising the step of rebroadcasting of said atomic global update to said remaining processors from said locker processor, in the event that said sender processor fails after it has sent said global update to said locker processor and before it has cleared said update lock semaphore.

24. The global update method set forth in claim 22 further comprising the step of automatically transferring the locker processor role to the next processor in said order in the event that said next processor learns that said current locker processor has failed after said global update has been sent to said next processor in said order.

25. The global update method set forth in claim 22 further comprising the step of setting said semaphore to identify said next processor and resending the global update from said next processor as successor locker processor to every other processor, and then resending the global update to said successor locker processor from itself in order to clear said semaphore, in the event that the sender processor and said current locker processor both fail after said atomic global update has been sent to said next processor.

26. A global update method tolerating multiple near simultaneous or simultaneous processor failures of a distributed data processing system comprising a plurality of distributed, interconnected processors, each of said processors including message passing means for passing and receiving test messages to and from every other of said processors on a repetition basis for thereby enabling each said processor to monitor current operational status of every other of said processors, said method including the steps of:

a. ordering said processors into a global update order by which one of said processors is an initial locker processor and every other processor is configured automatically to become locker processor upon failure of the current locker processor in accordance with said order,

b. providing a buffer area in each processor for storing an update lock semaphore for signalling that an atomic global update message is being transferred by a sender processor, an update sequence number for said message, and a global update message,

c. when no other atomic global update is in progress, setting said update lock semaphore in the buffer area of said locker processor to identify a sender processor by first sending an atomic global update message to said locker processor from said sender processor,

d. after setting said update lock semaphore in said locker, the sender processor broadcasting said atomic global update message to every other processor in said order,

e. clearing said update lock semaphore by resending said atomic global update to said locker processor from said sender processor after it has broadcast said atomic global update to all of said other processors,

f. if said sender processor fails after it has sent said atomic global update to said locker processor and before it has cleared said update lock semaphore, rebroadcasting of said atomic global update to said remaining processors from said locker processor,

g. automatically transferring the locker processor role to the next processor in said order in the event that said next processor learns that said current locker processor has failed after said atomic global update has been sent to said next processor in said order, and

h. if said sender processor and said current locker processor both fail after said atomic global update has been sent to said next processor, setting said semaphore to identify said next processor and resending said atomic global update from said next processor as successor locker processor to every other processor, and then resending said atomic global update to said successor locker processor from itself in order to clear said semaphore.