Data processing system

• US 4,562,539 A
• Filed: 02/17/1983
• Issued: 12/31/1985
• Est. Priority Date: 04/28/1982
• Status: Expired due to Term

• Current Assignee: International Computers Limited (Fujitsu Limited)
• Original Assignee: International Computers Limited (Fujitsu Limited)
• Inventors: Vince, Nigel L.
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Munteanu, Florin
• Application Number:
  US06/467,384
• Time in Patent Office: 1,048 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 370/89, 370/90, 370/86, 340/825.05
• US Class Current: 709/214
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004

Abstract

A data processing system comprising multiple processing nodes each containing a processor and a data store. The store holds local data, and also holds copies of shared data required by the node. This reduces conflict between the nodes in accessing the shared data. When one node updates the shared data, it sends an update message to all the other nodes over a transmission link. The processor is then free to continue processing. When the message reaches the other nodes, it updates the other copies of the shared data, so as to ensure consistency. Each node receives messages from the link in the same order, and this defines a unique chronological order for the updates, even though the nodes are asynchronous. A node is temporarily suspended if an update occurs out of this correct chronological order.

Claims

1. A data processing system comprising a plurality of processing nodes interconnected by data transmission means for receiving messages from the nodes and delivering the messages in the same sequence to all the nodes including the nodes which originated the messages, each node comprising:

(a) a data store holding data items unique to the node and also holding a copy of each of a plurality of shared data items,

(b) a data processor coupled to the data store for reading and updating data items in the store,

(c) means responsive to the processor updating a shared data item, for generating a message containing the updated value of the data item and its address,

(d) means for transmitting the message over the transmission means,

(e) means for receiving messages from the transmission means,

(f) means responsive to the reception of a message originating from another node, for updating the shared data item identified by the address contained in the message,

(g) means for producing a signal whenever a message has been generated by the node but has not yet been received back from the transmission means, and

(h) means operative upon reception of a message originating from another node, while said signal is present, for temporarily suspending operation of the processor.

2. A system according to claim 1 wherein the signal producing means comprises:

(a) a counter,

(b) means for incrementing the counter whenever a message is generated by the node,

(c) means for decrementing the counter whenever the node receives a message originating from itself, and

(d) means for generating said signal when the counter is non-zero.

3. A system according to claim 1 wherein each node includes a first-in first-out buffer for holding a queue of generated messages awaiting transmission.

4. A system according to claim 3 wherein the signal producing means comprises:

(a) a counter,

(b) means for incrementing the counter whenever a message is added to said buffer,

(c) means for decrementing the counter whenever the node receives a message originating from itself, and

(d) means for generating said signal when the counter is non-zero.

5. A system according to claim 1 wherein the transmission means comprises a ring network having means for permitting only one message at a time to be present on the ring.

6. A system according to claim 1 wherein said address contained in each said message is a virtual address.

7. A method of operating a data processing system comprising a plurality of processing nodes, each node including a data store and a data processor coupled to the store, and data transmission means for receiving messages from the nodes and delivering the messages in the same sequence to all the nodes, the method comprising the steps:

(a) storing local data items unique to individual nodes in the data stores of the respective nodes,

(b) storing copies of shared data items in the data stores of respective nodes,

(c) whenever the processor in one node updates the copy of a shared data item held in the data store of that node, generating in said one node a message containing the updated value of the shared data item and its address, and making a record that a message has been generated,

(d) transmitting the message from said one node over the link to all the nodes, including said one node,

(e) enabling the processor in said one node to continue processing without waiting for the message to reach the other nodes,

(f) when the message is received by the other nodes, updating the copies of the shared data item held in the data stores of those other nodes,

(g) when the message is received back from the link by said one node, canceling said record, and

(h) in the event that a message originating from another node is received by said one node while said record is present, temporarily suspending operation of the processor in said one node.

8. A system according to claim 7 wherein each node includes a counter, and wherein the step of making a record that a message has been generated comprises incrementing the counter, and the step of canceling said record comprises decrementing the counter.