you have real problems. The best thing you can do is to find another algorithm with less
contention.
LoadLocked/StoreConditional and Compare and Swap
We mentioned that there are other types of atomic instructions that are a bit more versatile. On
SPARC v9, there is the Compare and Swap if Equal instruction. On the Alpha, there is a different
approach to the same issue, using two instructions, known as Load Locked and Store Conditional
Example 16-2 Atomic Increment Using LoadLocked and StoreConditional
try_again:LoadLocked address_1 -> register_1
add register_1, 1 -> register_2
StoreConditional register_2 -> address_1
Compare register_2, 0
branch_not_equal try_again
The Alpha instructions require a tiny bit more hardware but reward the designer with an atomic
instruction that doesn't lock the memory bus. Alongside the bus snooper hardware is one more
register (Figure 16-7). When a LoadLocked instruction is issued, the data is fetched directly
from main memory, and that address is recorded in the register. Should some other CPU write to
that address, the register notices it. Later the program will issue a StoreConditional
instruction. This instruction looks at the register before doing the store. If the register says that the
address is unchanged, the store proceeds. If the address has been written to already, the store
doesn't take place. After StoreConditional is finished, the programmer must check to see if
the store took place. If so, all is well. If not, go back and repeat.
Figure 16-7. SMP System Architecture
Building a mutex with these instructions is simple. Of more interest are the other types of
synchronization we can do, such as atomic increment/decrement, and atomic list insertion. In
effect we will be implicitly locking the word in question, updating it, and releasing the implicit
lock. The important distinction is that we can now execute these operations with no possibility of
the lock owner going to sleep.
Search WWH :
