Advanced contention detection

• US 7,831,779 B2
• Filed: 10/05/2007
• Issued: 11/09/2010
• Est. Priority Date: 10/05/2006
• Status: Active Grant

• Current Assignee: Waratek Limited (Waratek Holdings Ltd.)
• Original Assignee: Waratek Pty Limited
• Inventors: Holt, John M.
• Primary Examiner(s): Thai; Tuan V.
• Application Number:
  US11/973,385
• Publication Number:
  US 20080133711A1
• Time in Patent Office: 1,131 Days
• Field of Search: 711/100, 711/147, 711/148, 711/154
• US Class Current: 711/147
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A multiple computer system is disclosed in which n computers (M1, M2 . . . Mn) each run a different portion of a single application program written to execute only on a single computer. The local memory of each computer is maintained substantially the same by updating all computers with every change made to addressed memory locations. Contention can arise when the same memory location is substantially simultaneously updated by two or more machines because of transmission delays and latency of the communications network interconnecting all the computers. Contention detection and resolution is disclosed. A count value (99) indicative of the cumulative number of times each memory location has been updated is utilized. Contention is indicated if the currently stored count value and the incoming updating count value are the same. A method of echo suppression and a method of echo rejection are disclosed. In particular incrementing the count value by two in the case of consecutive sequential transmission to the same memory location (D) is disclosed.

Claims

1. In a multiple computer system including a multiplicity of computers, each interconnected via at least one communications network, and each of the multiplicity of computers executing a different portion of an application program written to execute only on a single computer, each of the multiplicity of computers having an independent local memory with at least one memory location being replicated in each said local memory of each said multiplicity of computers, a method for handing contention in replica memory updating in which a memory location having a specific location identifier and replicated on at least two computers, can be updated substantially simultaneously from a plurality of sources, said method of handling contention in replica memory updating comprising:

(A) detecting a memory updating contention comprising;

(i) utilizing an updating format for the signal or packet carrying out the replica memory updating, said format comprising the specific identifier of the memory location to be updated, the content with which said memory location is to be updated, and a resident updating count of the updating source, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating;

(ii) storing for each replicated memory location the updating count of the previously sent or received updating;

(iii) comparing the resident updating count associated with the replicated memory location to be updated with the updating count of the currently received updating signal or packet; and

(iv) indicating a contention situation if the compared updating counts are the same;

(B) resolving said detected memory updating contention, including;

(i) storing for each receiving replicated memory location a resolution value with the updating count of the previously received updating;

(ii) comparing the presently resident updating count associated with the replicated memory location to be updated with the updating count of any currently received updating signal or packet; and

(iii) actioning or not actioning the incoming signal or packet according to predetermined policies;

(C) broadcasting a memory updating signal or packet over a communications network interconnecting a plurality of computers, including;

(i) utilizing said updating format for the signal or packet carrying out the updating, wherein said updating count comprises a resident updating count of the updating source and comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and at least one resolution value of the updating source, each said resolution value comprising a unique value of the updating source;

(D) consolidating data in addressed memory updating so that a memory location having a specific address or identifier can be updated substantially simultaneously from a plurality of sources, including;

(i) utilizing said updating format for the signal or packet;

(ii) storing for each said memory location the updating count of the previously received updating; and

(iii) from time to time on the occurrence of a predetermined condition, consolidating the stored updating count;

(E) ensuring correct operation of at least one finite counter each storing an updating count value including;

(i) providing at least one further data bit in addition to, and associated with, each said counter;

(ii) changing the state of the further data bit of each counter if said counter reaches a predetermined maximum count value; and

(iii) modifying the comparison of the count values of sequentially received updating messages or signals in accordance with the state of the further data bit associated with each said received message and the state of the further data bit of the previously received message; and

(F) overcoming possible memory updating echoes where at least one memory location is replicated at different memories and substantially simultaneously memory updating is accomplished from a plurality of sources transmitting an updating message including the address of the location, the new content for the location, and an updating count indicative of the position of the updating message in a sequence of updating messages, said updating count being incremented by a predetermined number to indicate consecutive updating messages, and further including;

(i) determining which source was the last to transmit in respect of a specific memory location; and

(ii) where the same source is to transmit sequentially in respect of the same memory location, incrementing said updating count for the second transmission by more than said predetermined number.

3. A computer program stored in a tangible computer readable storage media, the computer program adapted for execution in a processor within at least one computer or information appliance, for modifying the operation of at least one computer, the modification including performing a method of handling contention in replica memory during updating as recited in claim 1.

2. A multiple computer system comprising:

(A) a multiplicity of computers, each interconnected via at least one communications network, and each of the multiplicity of computers executing a different portion of an application program written to execute only on a single computer, each of the multiplicity of computers having an independent local memory with at least one memory location being replicated in each said local memory of each said multiplicity of computers, a method for handing contention in replica memory updating in which a memory location having a specific location identifier and replicated on at least two computers, can be updated substantially simultaneously from a plurality of sources, said method of handling contention in replica memory updating comprising;

(B) means for detecting a memory updating contention including;

(i) means for utilizing an updating format for the signal or packet carrying out the replica memory updating, said format comprising the specific identifier of the memory location to be updated, the content with which said memory location is to be updated, and a resident updating count of the updating source, said count comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating;

(ii) means for storing for each replicated memory location the updating count of the previously sent or received updating;

(iii) means for comparing the resident updating count associated with the replicated memory location to be updated with the updating count of the currently received updating signal or packet; and

(iv) means for indicating a contention situation if the compared updating counts are the same;

(C) means for resolving said detected memory updating contention, including;

(i) means for storing for each receiving replicated memory location a resolution value with the updating count of the previously received updating;

(ii) means for comparing the presently resident updating count associated with the replicated memory location to be updated with the updating count of any currently received updating signal or packet; and

(iii) means for actioning or not actioning the incoming signal or packet according to predetermined policies;

(D) means for broadcasting a memory updating signal or packet over a communications network interconnecting a plurality of computers, including;

(i) means for utilizing said updating format for the signal or packet carrying out the updating, wherein said updating count comprises a resident updating count of the updating source and comprising a number indicative of the sequence of occasions on which the updating source has been updated inclusive of the current updating, and at least one resolution value of the updating source, each said resolution value comprising a unique value of the updating source;

(E) means for consolidating data in addressed memory updating so that a memory location having a specific address or identifier can be updated substantially simultaneously from a plurality of sources, including;

(i) means for utilizing said updating format for the signal or packet;

(ii) means for storing for each said memory location the updating count of the previously received updating; and

(iii) means for from time to time on the occurrence of a predetermined condition, consolidating the stored updating count;

(F) means for ensuring correct operation of at least one finite counter each storing an updating count value including;

(i) means for providing at least one further data bit in addition to, and associated with, each said counter;

(ii) means for changing the state of the further data bit of each counter if said counter reaches a predetermined maximum count value; and

(iii) means for modifying the comparison of the count values of sequentially received updating messages or signals in accordance with the state of the further data bit associated with each said received message and the state of the further data bit of the previously received message; and

(G) means for overcoming possible memory updating echoes where at least one memory location is replicated at different memories and substantially simultaneously memory updating is accomplished from a plurality of sources transmitting an updating message including the address of the location, the new content for the location, and an updating count indicative of the position of the updating message in a sequence of updating messages, said updating count being incremented by a predetermined number to indicate consecutive updating messages, and further including;

(i) means for determining which source was the last to transmit in respect of a specific memory location; and

(ii) means for incrementing said updating count for the second transmission by more than said predetermined number where the same source is to transmit sequentially in respect of the same memory location.