Lock-up free data sharing

• US 5,787,480 A
• Filed: 07/17/1996
• Issued: 07/28/1998
• Est. Priority Date: 07/17/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Scales, Daniel J., Gharachorloo, Kourosh
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): KING, CONLEY BURRELL
• Application Number:
  US08/684,281
• Time in Patent Office: 741 Days
• Field of Search: 395/474, 395/475, 395/608, 395/617, 395/472, 395/183.11, 395/704, 395/705, 395/709, 711/147, 711/148, 711/145, 707/8, 707/201
• US Class Current: 711/148
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A software implemented method for lock-up free data sharing operates in a networked computer system including a plurality of workstations. Each workstation including a processor, a memory having addresses, and an input/output interface connected to each other by a bus. A set of addresses of the memories are designated as virtual shared addresses to store shared data. A portion of the virtual shared addresses is allocated to store the shared data as a plurality of blocks accessible by programs executing in any of the processors, each block including an integer number of lines. A program is instrumented to request an exclusive copy of the block if the program includes a store instruction which attempts to access data stored in a non-exclusive copy of the block. Additional instructions of the program are executed while the request for the exclusive copy of the block is pending. Addresses of data of the block modified by the additional instructions are recorded. In response to receiving the exclusive copy of the block, the modified data stored at the recorded addresses are merged with the data of the exclusive copy of the block.

Claims

1. A software implemented method for accessing shared data of a computer system including a plurality of workstations, each workstation including a processor, a memory having addresses, and an input/output interface connected to each other by a bus, the input/output interfaces connecting the workstations to each other by a network, comprising the steps of:

designating addresses of the memories as virtual shared addresses to store the shared data;

allocating a portion of the virtual shared addresses to store the shared data as a plurality of blocks accessible by any of the processors, each block including an integer number of lines;

instrumenting a particular program to request an exclusive copy of the block if the particular program includes a store instruction which is to store shared data in the block;

executing additional store instructions of the particular program while the request for the exclusive copy of the block is pending, and noting addresses of data of the requested block modified by the additional instructions;

in response to receiving the exclusive copy of the block, merging the modified data stored at the noted addresses with the shared data of the exclusive copy of the block to enable lock-up free data sharing.

2. The method of claim 1 further comprising:

executing additional load instructions of the particular program while the request for the exclusive copy of the block is pending, as long as the data being loaded is from a valid line or a valid part of a pending line.

3. A system for accessing shared data, the system comprising:

a first memory, including a first block of data having a first plurality of entries, each entry having a corresponding address;

a second memory, including a second block of data having a second plurality of entries, each entry having a corresponding address; and

a processor configured to;

request a copy of the first block of data,

modify a particular one of the second plurality of entries in the second block which corresponds to a particular one of the first plurality of entries in the first block; and

merge the particular one of the second entries with the requested copy of the first block of data.

4. The system of claim 3, wherein the processor records the address of the modified particular one of the second plurality of entries prior to merging.

5. The system of claim 3, further comprising:

a third memory; and

a set of instructions stored on the third memory, the set of instructions having a particular instruction that directs data to be stored in the first block.

6. The system of claim 3, wherein the processor is configured to modify the particular one of the second plurality of entries while the request for the copy of the first block is pending.

7. The system of claim 3, wherein merging results in the particular one of the second entries merging with the corresponding particular one of the first plurality of entries.

8. The system of claim 3, further comprising:

a virtual memory formed of at least portions of the first memory and the second memory.

9. The system of claim 3, wherein the processor is a first processor and the first processor is connected to the second memory, the system further comprising:

a second processor connected to the first memory; and

a network connecting the first processor and the second processor.

10. The system of claim 3, wherein the processor is configured to request an exclusive copy of the first block of data.

11. The system of claim 3, wherein the second block in the second memory is a local copy of the first block in the first memory.

12. The system of claim 3, further comprising:

a third memory; and

a set of instructions stored on the third memory, the set of instructions having a particular instruction that directs data to be loaded from one of the first block and the second block;

wherein the data to be loaded has a valid current status.

13. A method for accessing shared data stored on a plurality of computers, including a first computer having a first memory for storing a first block of data having a plurality of entries including a first entry and a second computer having a second memory for storing a second block of data having a second entry, the method comprising the steps of:

requesting a copy of the first block of data;

modifying the second entry in the second block of data;

recording the address of the second entry substantially simultaneous with the step of modifying; and

merging the first block of data with at least a portion of the second block of data.

14. The method of claim 13, wherein the step of modifying is responsive to an instruction executed while the request for the copy of the first block of data is pending.

15. The method of claim 13, wherein the second plurality of entries initially corresponds with the first plurality of entries.

16. The method of claim 13, wherein the second entry located in the second block data merges with a corresponding one of the first plurality of entries.

17. The method of claim 13, wherein the step of requesting a copy of the first block of data requests an exclusive copy of the first block of data.