Sequentially performed compound compare-and-swap
A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A 2 is invalid and the contents of memory address A 1 are unequal to C 1 . In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.
1. A method for executing a compound synchronization operation (CSO), comprising:
identifying, by a processor executing the CSO, a first memory location and a second memory location specified by the CSO in a plurality of memory locations, wherein the first memory location and the second memory location are within a single memory;
locking the first memory location according to a fixed total order of the plurality of memory locations, wherein locking the first memory location comprises generating a copy of a cache line in the single memory comprising the first memory location and storing the copy in a single cache associated with the processor;
determining, by the processor executing the CSO, that the second memory location is invalid after locking the first memory location;
fetching, by the processor executing the CSO, an existing value from the first memory location in the single cache after determining that the second memory location is invalid;
comparing, by the processor executing the CSO, the existing value with a test value specified by the CSO, wherein the existing value does not equal the test value;
identifying, by the processor executing the CSO, a first new value specified by the CSO, wherein the first new value is for storage in the first memory location;
replacing, by the processor executing the CSO, the first new value with the existing value in response to the existing value not equaling the test value;
unlocking the first memory location without signaling a fault associated with the second memory location, after comparing the existing value and the test value; and
terminating the CSO.
2. The method of claim 1 , wherein the fixed total order of the plurality of memory locations is based on ascending memory address.
3. The method of claim 1 , wherein the CSO is a compound compare-and-swap operation.
4. The method of claim 1 , wherein the CSO is at least one selected from a group consisting of a compare-and-swap operation, a test-and-set operation, a read-compute-conditional write operation, and a read-modify-write operation.
5. The method of claim 1 , further comprising:
identifying, by the processor executing the CSO, a second new value specified by the CSO, wherein the second new value is for storage in the second memory location;
replacing, by the processor executing the CSO, the second new value with zero in response to the existing value not equaling the test value.
6. A computer readable medium storing instructions to perform a compound synchronization operation (CSO), the instructions executable on a processor and comprising functionality to:
identify a first memory location and a second memory location specified by the CSO in a plurality of memory locations, wherein the first memory location and the second memory location are within a single memory;
lock the first memory location according to a fixed total order of the plurality of memory locations, wherein locking the first memory location comprises generating a copy of a cache line in the single memory comprising the first memory location and storing the copy in a single cache associated with the processor;
determine that the second memory location is invalid after locking the first memory location;
fetch an existing value from the first memory location in the single cache after determining that the second memory location is invalid;
compare the existing value with a test value specified by the CSO, wherein the existing value does not equal the test value;
identify a first new value specified by the CSO, wherein the first new value is for storage in the first memory location;
replace the first new value with the existing value in response to the existing value not equaling the test value;
unlock the first memory location without signaling a fault associated with the second memory location, after comparing the existing value and the test value; and
terminate the CSO.
7. The computer readable medium of claim 6 , wherein the fixed total order is descending memory address.
8. The computer readable medium of claim 6 , wherein the CSO is a compound compare-and-swap operation.
9. The computer readable medium of claim 6 , wherein the computer readable medium is selected from a group consisting of a magnetic storage medium, an optical storage medium, and an electronic storage medium.
10. The computer readable medium of claim 6 , the instructions further comprising functionality to:
identify a second new value specified by the CSO, wherein the second new value is for storage in the second memory location;
replace the second new value with zero in response to the existing value not equaling the test value.