StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Lock-free algorithms typically involve using compare-and-swap (CAS) or similar instructions that update some value in memory not only atomically, but also conditionally and with an indicator of success. That way you can code something like this:</p> <pre><code>do { read the current value calculate the new value } while(!compare_and_swap(current_value, new_value); </code></pre> <ul> <li>exact calling syntax will vary with the CPU, and may involve assembly language or system/compiler-provided wrapper functions <ul> <li>use provided wrappers if available - there may be other compiler optimisations or issues that their usage restricts to safe behaviours, otherwise check your docs</li> </ul></li> </ul> <p>The significance is that when there's a race, the compare and swap instruction will fail because the state from which you're updating is <em>not</em> the one you used to calculate the desired target state. Such instructions can be said to "spin" rather than lock, as they go round and round the loop until spat out successfully.</p> <p>Crucially, your existing threading library may well have a two-stage locking approach for mutex, read-write locks etc. involving spinning using CAS or similar (i.e. spin on { read the current value, if it's not set then cas(current = not set, new = set) }) - which means other threads doing a quick update often won't result in your thread swapping out to wait, and all the relatively time-consuming overheads associated with that. The second stage will be to tell the operating system to queue the thread until it finds the mutex free. The implication of this is that if you're using a mutex to protect access to a variable, then you are unlikely to do any better by implementing your own "mutex" to protect the same variable.</p> <p>Lock free algorithms come into their own when you are working directly on a variable that's small enough to update directly with the CAS instruction itself. Instead of being...</p> <ul> <li>get a mutex (by spinning on CAS, falling back on slower OS queue)</li> <li>update variable</li> <li>release mutex</li> </ul> <p>...they're simplified (and made faster) by simply having the spin on CAS. Of course, you may find the work to calculate new value from old painful to repeat speculatively, but unless there's a LOT of contention you're not doing that often.</p> <p>This ability to update only a single location in memory has far-reaching implications, and work-arounds can require some creativity. For example, if you had a container using lock-free algorithms, you may decide to calculate a potential change to an element in the container, but can't sync that with updating a size variable elsewhere in memory. You may need to live without size, or be able to use an approximate size where you do a CAS-spin to increment or decrement the size later, but any given read may be slightly wrong. You may need to merge two logically-related data structures - such as a free list and the element-container - to share an index, then bit-pack the core fields for each into the same atomically-sized word at the start of each record. These kinds of data optimisations can be very invasive, and sometimes won't get you the behavioural characteristics you'd like. Mutexes et al are much easier in this regard, and at least you know you won't need a rewrite <em>to</em> mutexes if requirements evolve just that step too far. That said, clever use of a lock-free approach really can be adequate for a lot of needs, and yield a very gratifying performance and scalability improvement.</p> <p>A core (good) consequence of lock-free algorithms is that one thread can't be holding the mutex then happen to get swapped out by the scheduler, such that other threads can't work until it resumes; rather - with CAS - they can spin safely and efficiently without an OS fallback option.</p> <p>Things that lock free algorithms can be good for include updating usage/reference counters, modifying pointers to cleanly switch the pointed-to data, free lists, linked lists, marking hash-table buckets used/unused, and load-balancing. Many others of course.</p> <p>As you say, simply hiding use of mutexes behind some API is not lock free.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload