Posting multiple reservations with a conditional store atomic op

Details Posting multiple reservations with a conditional store atomic op Posting multiple reservations with a conditional store atomic op

1995-11-20

1998-04-21

Donaghue, Larry D.

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

39520043, 39580001, 711147, G06F 1516, G06F 938

Patent

active

057427852

ABSTRACT:
Using this invention, more than one variable that is shared in a multiprocessing environment can be updated atomically. Each computer processor operating in the multiprocessing environment contains more than one reservation register which, along with this novel method, are used to place reservations on each of more than one shared variable. During the execution of a program, a plurality of shared variables can be reserved, each by its respective reservation register. A reservation is placed on a shared variable by means of a special instruction. The reservation register keeps track of: the address of the shared variable that it is reserving, the value of the modified results that are to be updated in the shared variable address, whether the variable has been updated, whether the reservation is valid, and whether the processor containing the reservation register has a privilege to update the shared variable. A reservation can be invalidated if a second processor tries to read the address of the reserved shared variable. When an instruction is encountered that tries to update a shared variable, the set of reserved modified shared variables designated by that instruction that have unupdated modified results are updated atomically if and only if all the reservations in the designated set are valid. If any of the reservations in the set are invalid, no shared variable in the set is updated. A condition code reports if the update was successful or did not occur. The condition code can be tested so that the sequence of instructions can be repeated until it is successful.

REFERENCES:
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 4926375 (1990-05-01), Mercer et al.
patent: 5027316 (1991-06-01), Frantz et al.
patent: 5119292 (1992-06-01), Baker et al.
patent: 5136691 (1992-08-01), Baror
patent: 5136717 (1992-08-01), Morley et al.
patent: 5175829 (1992-12-01), Stumpf et al.
patent: 5237694 (1993-08-01), Horne et al.
patent: 5265232 (1993-11-01), Gannon et al.
patent: 5289588 (1994-02-01), Song et al.
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 5524255 (1996-06-01), Beard et al.
patent: 5553267 (1996-09-01), Herlihy et al.
P. Heidelberger et al., "Improved Compare-and-Swap Instruction . . . ", IBM Tech. Disc. Bulletin, Mar. 1992, pp.:177-119.
M. Herlihy et al., "Transactional Memory Support for Lock-Free Data Structures," DEC, Dec. 1, 1992, pp.:1-40.
P. Sweazy et al., "A Class of Compatible Cache Consistency . . . ", Proc. of 13th Annual Symposium on Comp. Architecture, Jun. 1986, pp.:414-423.
Richard Witek et al. "Alpha Architecture Reference Manual" 1992 Digital Press, Digital Equip. Corp.pp.4-8,4-12.
G. Kane & J. Heinrich "MIPS RISC Architecture" MIPS Computer Systems, Prentice Hall, Englewood Cliffs, NJ.
E.G. Coffman, Jr. et al., "System Deadlocks", Computing Surveys, vol. 3, No. 2, Jun. 1971, pp. 70-78.
H.S. Stone, "Multiprocessors", High-Performance Computer Architecture, Chapter 6, Addison-Wesley Publishing Company, USA, pp. 304-360.
H.S. Stone, "Multiprocessor Algorithms", High-Performance Computer Architecture, Chapter 7 Addison-Wesley Publishing Company, USA, pp. 361-432.
D.B. Lomet et al., IBM Tech. Disc. Bulletin, vol. 22, No. 3 Aug., 1979, pp. 1290-1293.
M. Herlihy et al., "Transactional Memory: Architectual Support for Lock-Free Data Structures," believed to be unpublished.

Affiliated with

Also associated with

Rating

Posting multiple reservations with a conditional store atomic op does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Posting multiple reservations with a conditional store atomic op, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Posting multiple reservations with a conditional store atomic op will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2067641