Atomic
Operations and Lock-Free Code
Using
synchronization primitives can add a high overhead cost. This is particularly
true if they are implemented as calls into the operating system rather than
calls into a supporting library. These overheads lower the performance of the
parallel application and can limit scalability. In some cases, either atomic operations or lock-free code can produce func-tionally
equivalent code without introducing the same amount of overhead.
An atomic operation is one that will either
successfully complete or fail; it is not possi-ble for the operation to either
result in a “bad” value or allow other threads on the sys-tem to observe a
transient value. An example of this would be an atomic increment, which would
mean that the calling thread would replace a variable that currently holds the
value N with the value N+1. This might sound trivial, but bear in mind that the
operation of incrementing a variable can involve multiple steps, as shown in
Listing 4.12.
Listing 4.12 Steps Involved in Incrementing a Variable
LOAD [%o0], %o1 // Load initial
value
ADD %o1, 1, %o1 // Increment
value
STORE %o1, [%o0] // Store
new value back to memory
During
the execution of the three steps shown in Listing 4.12, another thread could
have interfered and replaced the value of the variable held in memory with a
new value, creating a data race.
An atomic
increment operation would not allow another thread to modify the same variable
and cause an erroneous value to be written to memory. Performing the incre-ment
operation atomically is logically equivalent to implicitly acquiring a mutex before the increment and releasing it
afterward. The difference is that using a mutex relies on other threads using
the same mutex to protect that variable. A thread that did not use the same
mutex could cause an incorrect value to be written back to memory. With atomic
operations, another thread cannot cause an incorrect value to be written to
memory.
Most
operating systems or compilers provide support for a range of atomic
opera-tions. However, hardware typically provides support only for a more
limited range of operations; hence, the more complex atomic operations are
usually made from the sim-ple atomic instructions that the hardware provides.
Atomic
operations are often used to enable the writing of lock-free code. Using a syn-chronization device such as a mutex
lock solves the correctness problem; only one thread can access the protected
memory location at a single time. However, it is not necessarily the approach
with the best scaling, since threads that are waiting for access are blocked
(sent to sleep). A lock-free implementation would not rely on a mutex lock to
protect access; instead, it would use a sequence of operations that would
perform the operation without having to acquire an explicit lock. This can be
higher performance than control-ling access with a lock. Lock-free does not imply
that the other threads would not have to wait; it only indicates that they do
not have to wait on a lock. A wait-free
implementa-tion would allow all the threads to simultaneously make forward
progress.
Most of
the more complex atomic operations are actually lock-free implementations. They
use a low-level, hardware-provided atomic operation and wrap code around that
to ensure that the required higher-level operation is actually atomic.
An
example of a low-level atomic operation would be compare and swap (CAS), which atomically swaps the value held in a
register with the value held in memory if and only if the value held in memory
matches the expected value. As an example of using this hardware-provided
atomic operation to produce a higher-level atomic operation, the CAS
instruction could be used as the basis for an atomic increment operation. To do
this, the CAS instruction would be executed in a loop. Each iteration, it would
attempt to replace the value held in memory with the incremented value. The loop
would exit when the CAS instruction successfully performed the increment
operation.
Lock-free
code can be used to achieve more complex operations; this will be dis-cussed in
Chapter 8, “Hand-Coding Synchronization and Sharing.”
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2026 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.