Method and apparatus for synchronizing data queues in asymmetric reflective memories

• US 5,588,132 A
• Filed: 10/20/1994
• Issued: 12/24/1996
• Est. Priority Date: 10/20/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Cardoza, Wayne M.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): KIM, HONG CHONG
• Application Number:
  US08/326,682
• Time in Patent Office: 796 Days
• Field of Search: 395/446, 395/457, 395/475, 395/474, 395/468, 395/881, 395/200.01, 395/200.03, 395/874, 395/200.08
• US Class Current: 711/148
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A network of processors synchronize modification of a common data structure stored in an asymmetric reflective memory by using a queue. A first processor stores a queue element in a global write-only address space of the reflective memory, the reflective memory to copy the queue element to a local read/write address space of a second processor. The first processor also stores a queue header in the global write-only address space. In response to detecting the queue element, the second processor reads the queue header and then overwrites the queue header with a zero. The reading and writing of the queue header are performed atomically in the local read/write address space of the second processor. The second processor processes the queue element, and marks the queue element as processed in the global address space of the reflective memory.

Claims

1. In a computer system, a method for synchronizing modification of a common data structure stored in an asymmetric reflective memory shared by a plurality of processors, comprising:

in a first processor, storing a queue element in a global write-only address space of the asymmetric reflective memory, the asymmetric reflective memory to copy the queue element to a local read/write address space of a second processor, the queue element storing common data to be shared by the plurality of processors;

in the first processor, storing a queue header in the global write-only address space, the asymmetric reflective memory to copy the queue header to the local read/write address space of the second processor;

in the second processor, in response to detecting the queue element, reading the queue header and disabling the queue header, the reading and disabling performed atomically in the local read/write address space of the second processor;

in the second processor, processing the common data stored in the queue element; and

in the second processor, marking the queue element as processed in the global address space of the asymmetric reflective memory, the asymmetric reflective memory to copy the queue element to a local read/write address space of the first processor after marking.

2. The method of claim 1 wherein the queue element includes a valid/invalid field, an address field, and a data field, the valid/invalid field for indicating a processing state of the common data stored in the queue element, the data field for storing the common data and wherein the step of marking further comprises:

writing an invalid flag in the valid/invalid field of the queue element, and wherein the step of disabling the queue header includes writing a zero in the queue header.

3. The method of claim 2 further comprising:

determining if the address field of the queue element points to a subsequent queue element having a valid flag in a corresponding valid/invalid field; and

in response to detecting the valid flag, processing the subsequent queue element.

4. An apparatus for synchronizing modification of a common data structure shared by a plurality of processors, comprising:

an asymmetric reflective memory having a global write-only address space shared by the plurality of processors and a local read/write address space for each of the plurality of processors;

a queue element stored in the global write-only address space of the asymmetric reflective memory by a first processor, the asymmetric reflective memory to copy the queue element to the local read/write address space of a second processor the queue element storing common data to be shared by the plurality of processors;

a queue header stored in the global write-only address space of the asymmetric reflective memory by the first processor, the asymmetric reflective memory to copy the queue header to the local read/write address space of the second processor;

in response to detecting the queue element, means for reading the queue header and writing a zero in the queue header, the means for reading and writing the queue header performing the reading and writing steps atomically in the local read/write address space of the second processor;

means for processing the common data stored in the queue element; and

means for marking the queue element as processed in the global address space.

5. The apparatus of claim 4 wherein the queue element includes a valid/invalid field, an address field and a data field, the valid/invalid field for indicating a processing state of the common data stored in the queue element, the data field for storing the common data and further comprising, the data field for storing the common data:

means for marking the valid/invalid field as valid to detect the queue element; and

means for marking the valid/invalid field as invalid to indicate that the queue element has been processed.

6. The apparatus of claim 5 further comprising:

means for detecting if the address field of the queue element points at a subsequent queue element having a corresponding valid/invalid field marked as valid;

means for processing the subsequent queue element if the corresponding valid/invalid field is marked as valid.

7. In a computer system, a method for synchronizing modification of a queue, the queue including a header and queue elements, the queue stored in a memory shared by a plurality of processors, comprising:

writing a new queue element in a global write-only address space of an asymmetric reflective memory, the queue element storing common data to be shared by the plurality of processors, the asymmetric reflective memory copying the new queue element to a local read/write address space of the asymmetric reflective memory, the local read/write address space accessible by a second processor;

writing an address of the new queue element in the queue header, the queue header stored in the global write-only address space;

detecting the new queue element by the second processor;

reading the queue header and writing a zero in the queue header, the reading and writing of the queue header performed atomically in the local read/write address space of the second processor;

processing the common data stored in the new queue element by the second processor; and

marking the new queue element as processed in the global address space of the asymmetric reflective memory.