US5535365A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for locking shared memory locations in multiprocessing systems
Assignee: Morgan Stanley and Co LLC
•
Filing: 1993-10-22
•
Granted: 1996-07-09
•
Expires: 2013-10-22
Abstract
Abstract A method of synchronizing accesses to shared data in a multiprocessing system having an atomic swap capability. A distinguished lock value is defined. A processor which wishes to access a shared data memory location performs an atomic swap of the lock value to the shared data memory location. If the data received from the atomic swap is equivalent to the lock value the processor knows that the memory location has been locked by another processor. The processor then repeats the atomic swap at intervals until data is received which is not equivalent to the lock value. The processor operates on the data and then performs a write to the shared data memory location to replace the lock value with the updated data. In an alternate embodiment, in situations where a unique lock value cannot be defined, an array is created to store lock values associated with particular shared data memory locations. A processor seeking access to a shared data memory location performs atomic swaps of the lock value to the lock array to determine access to a shared data memory location.
Inventors
- 👤 Frank R. Barriuso
- 👤 Douglas M. Pase
- 👤 David J. Sielaff
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 14:57
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; G06F9/526
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
130 words
A computer system, comprising: an interconnect network; and a plurality of processing nodes, wherein the plurality of processing nodes includes a first processing node, wherein each of the plurality of processing nodes are connected to the first processing node through said interconnect network and wherein each processing node comprises: a memory having a plurality of memory locations, including a first memory location; a local swap register; and processing means for operating on data stored in the first memory location of said first processing node, wherein the processing means performs an atomic swap operation in which data stored in the first memory location of said first processing node is transferred to the processing means and a lock value stored in the local swap register is stored in said first memory location.
Claim 2
Dependent Claim
130 words
A computer system, comprising: an interconnect network; and a plurality of processing nodes, wherein the plurality of processing nodes includes a first processing node, wherein each of the plurality of processing nodes are connected to the first processing node through said interconnect network and wherein each processing node comprises: a memory having a plurality of memory locations, including a first memory location; a local swap register; and processing means for operating on data stored in the first memory location of said first processing node, wherein the processing means performs an atomic swap operation in which data stored in the first memory location of said first processing node is transferred to the processing means and a lock value stored in the local swap register is stored in said first memory location.
Claim 3
Dependent Claim
235 words
In a computer system having a plurality of processor nodes connected through an interconnect network, wherein the plurality of processor nodes includes first and second processor nodes and wherein each processor node includes a local swap register for storing a lock value, a method of protecting data stored on the first processor node when that data is being accessed by a process on said second processor node, the method comprising the steps of: a) defining a lock value; b) writing the lock value in the local swap register of the second processor node; c) providing a hash table having a plurality of hash table cells, including a first hash table cell, wherein the first hash table cell contains a lock entry for a protected memory location; d) selecting said first hash table cell from the plurality of hash table cells, wherein the step of selecting comprises calculating a hash value; e) reading the lock entry at the selected first hash table cell, wherein the step of reading the lock entry comprises the step of atomically swapping the lock value stored in the local swap register of the second processor node with the lock entry at the selected first hash table cell; f) comparing the lock entry read from the selected first hash table cell to the defined lock value; and g) if the lock entry read does equal the defined lock value, repeating steps e-g.
Claim 4
Dependent Claim
235 words
In a computer system having a plurality of processor nodes connected through an interconnect network, wherein the plurality of processor nodes includes first and second processor nodes and wherein each processor node includes a local swap register for storing a lock value, a method of protecting data stored on the first processor node when that data is being accessed by a process on said second processor node, the method comprising the steps of: a) defining a lock value; b) writing the lock value in the local swap register of the second processor node; c) providing a hash table having a plurality of hash table cells, including a first hash table cell, wherein the first hash table cell contains a lock entry for a protected memory location; d) selecting said first hash table cell from the plurality of hash table cells, wherein the step of selecting comprises calculating a hash value; e) reading the lock entry at the selected first hash table cell, wherein the step of reading the lock entry comprises the step of atomically swapping the lock value stored in the local swap register of the second processor node with the lock entry at the selected first hash table cell; f) comparing the lock entry read from the selected first hash table cell to the defined lock value; and g) if the lock entry read does equal the defined lock value, repeating steps e-g.
Claim 5
Dependent Claim
26 words
The method according to claim 2 wherein the step of reading comprises storing the lock entry read from the selected hash table cell in a cache.
Claim 6
Dependent Claim
39 words
The method according to claim 2 wherein the method further comprises the step of: h) if the lock entry read from the selected first hash table cell does not equal the defined lock value, accessing the protected memory location.
Claim 7
Dependent Claim
21 words
The method according to claim 4 wherein the step of repeating comprises waiting a period of time before executing step e.
References Cited (Backward Citations)
US4584644A
Cited
JPS58165166A
Cited
US5027316A
Cited
US4977498A
Cited
US5265245A
Cited
US5093912A
Cited
US5237668A
Cited
US5327570A
Cited
US5261106A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-09 | 2000-01-08 | 2000-07-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-09 | 2004-01-08 | 2004-07-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-09 | 2008-01-08 | 2008-07-09 | $7700.00 | Window Closed / Lapsed |