My question is related to multithreading lock-free synchronization. I wanted to know the following:
What are general approaches to achieve this? I read somewhere about LockFreePrimitives like CompareAndExchange (CAS) or DoubleCompareAndExchange (DCA) but no explanation for those were given? Any approaches to MINIMIZE use of locks?
How does Java/.NET achieve their concurrent containers? Do they use locks or lock-free synch?
Thanks in advance.
Here are some general approaches that can minimize the use of locks, assuming your algorithm has some particular exploitable features:
When updating a single numeric variable, you can use non-blocking primitives such as CAS, atomic_increment, etc. They are usually much faster that a classic blocking critical section (lock, mutex).
When a data structure is read by multiple threads, but only written by one or few threads, an obvious solution would be a read-write lock, instead of a full lock.
Try to exploit fine grain locking. For example, instead of locking an entire data structure with a single lock, see if you can use multiple different locks to protect distinct sections of the data structure.
If you're relying on the implicit memory fence effect of locks to ensure visibility of a single variable across threads, just use volatile1, if available.
Sometimes, using a conditional variable (and associated lock) is too slow in practice. In this case, a volatile busy spin is much more efficient.
More good advice on this topic here: http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/
A nice read in another SO question: Lock-free multi-threading is for real threading experts (don't be scared by the title).
And a recently discussed lock-free Java implementation of atomic_decrement: Starvation in non-blocking approaches
1 The use of volatile here applies to languages such as Java where volatile has defined semantics in the memory model, but not to C or C++ where volatile preceded the introduction of the cross-thread memory model and doesn't integrate with it. Similar constructs are available in those languages, such as the various std::memory_order specifiers in C++.
volatile is the most misunderstood keyword). Since the question isn't tagged "Java", this should at least be made clear. –
Concentre atomic<T> / C11 _Atomic is called volatile in Java. Thanks Java for using a C keyword with related but different semantics. (volatile in C/C++ does not have all the things required to make num++ atomic.) –
Harcourt volatile and atomic<T> in C++ is not very exact. Syntactically, volatile in C/C++ and Java are pretty much the same: both are qualifiers that don't change the syntax of accessing the underlying value. Semantically (memory-model wise) volatile is a bit like a restricted form of atomic where the only things you can do are loads with memory_order::acquire and stores with memory_order::release. The various Atomic* classes in Java are basically the direct equivalent of atomic<T> (with the usual caveat that Java is inherently reference based). –
Dyarchy volatile were pretty reasonably on the face of it - in fact people used volatile for cross-thread communication "since forever" in C/C++, long before they had a formal memory model (since it was the only semi-portable way to accomplish that), and at least MSVC formalized this with the same release/acquire semantics as Java. –
Dyarchy volatile in Java isn't complete: there is a "total access order" component to volatile that isn't present in basic acquire/release semantics (this makes store expensive). –
Dyarchy volatile in Java was called atomic in C++. (in herbsutter.com/2013/02/11/…). So in Java you get seq_cst loads/stores, but not atomic RMW. I take back my criticism of the naming, that's annoying but pretty obviously makes sense, especially given the (ab)use of C volatile in practice at the time for lack of anything better. (But there were libraries what wrapped volatile unsigned with synchronization semantics, weren't there?) –
Harcourt volatile is something less than seq_cst in C++ but something more than seq_acq for loads and seq_rel for stores. It is usually thought of as acquire/release since that's how it interacts with with other (plain) loads and stores, but then it has this additional total order requirement which only applies to the set of volatile accesses, which makes things like Dekker possible (and it's what makes volatile stores slow). Does that make it strong enough to be equivalent to seq_cst in C++? I'd don't know enough to say. –
Dyarchy seq_cst gives you, when you leave out RMW operations. But possibly it's not, so I probably shouldn't assume without looking at Java carefully. –
Harcourt seq_cst store in C++ would not be reordered with a following plain (or relaxed) store. Such a re-ordering is allowed in Java since the volatile store only has release semantics with respect to non-volatile accesses. @peter Do you know what C++ allows? –
Dyarchy volatile gave seq_release semantics, not just regular release. If not, then it's not like seq_cst. C++ works the way you suggest, and gcc demonstrates this (godbolt.org/g/mRggrj) by hoisting a non-atomic load before a mo_release store, but not before a mo_seq_cst store. –
Harcourt stlr as having sequential-release semantics, in part 2 of herbsutter.com/2013/02/11/…. Some CPUs need to use expensive barriers that go far beyond what C++11 seq_cst requires, but the newly-designed AArch64 provides just what the standard requires but not much more, so the C++11 default seq_cst is as cheap as possible. (gcc bug? It hoists in both cases godbolt.org/g/iTdQFS on AArch64) I hadn't heard it before that, so IDK if he made it up and your typo just happened to match it.. –
Harcourt seq_cst pretty much zero reordering is allowed, so it's not surprising the heaviest barriers are needed there. The mismatch is more usually when there is a mix of other other operations, like seq_acq and seq_rel where some platforms still have to use the same heavy barriers. Rading more of the C++ memory model I now agree that java volatile is similar to seq_cst: the guarantees of the latter were weaker than I thought. –
Dyarchy na = 1 in favor of the later store na = 3 which kills it unconditionally. The way acquire-release works if you see a = 2 it means you'll see at least the na = 1 operation, but it could be any later operation in the modification order too, and in this case gcc compiles it so it is always a later operation. In fact this code is UB because there is no necessary happens before the various cross-thread modifications of na. –
Dyarchy a == 2, you aren't allowed to see na == 0 or whatever other old value, only na == 1 or na==3. Seeing the original value is possible when there's no store to na before doing a release-store. Hmm, na isn't atomic at all, so possible gcc decided that it's UB for another thread to read it while this thread is writing it, because it's still written after the release-store? –
Harcourt weak. IDK how to create conditions that would "tempt" gcc to sink a non-atomic store past a release without writing the non-atomic object after the release, too. –
Harcourt weak.store(3, mo_relaxed) above sync.store(2, mo_release) either, of course. (And BTW, I'm imagining a use-case where only one thread ever calls these functions to publish, and another thread reads sync and then maybe na. So not cross-modification, but yeah there was UB.) –
Harcourt __restrict__ for this to work at least for the non-atomic case since otherwise it assumes the int values may alias. There the store order is swapped only for the two-non-atomic-stores case, but not in any of the cases where an atomic is involved, even when allowed (relaxed). You see the x86 advantage in the release case. –
Dyarchy clang recognizes totally local atomic vars and essentially removes their atomic nature), and so it's not really surprising they also don't recordering around them in the cases it would be allowed, since that's complicated. The "killed stores" optimization is different and I think it's just working as it always had (removing a store shouldn't break things). –
Dyarchy stlr is a lot cheaper than mov + mfence, or xchg. Anyway, I am surprised that gcc doesn't reorder even relaxed stores. clang and ICC don't either. (And don't even reorder the non-atomic case.) –
Harcourt Compare and swap is useful, but there is an even simpler (so called 'lock-free') technique that is useful in certain producer/consumer use cases that might be useful so I will mention it.
Imagine you have a function doWork() that writes to a buffer.
There are multiple ways for A to wait for doWork to finish depending on how long you expect it to take:
If you expect it to be a few nanoseconds, use thread affinities to schedule a and b as hyper threads on the same cpu core and use a busy wait buffered by cpu-specific wait/pause/relax instructions to help the CPU’s pipeline digest the busy wait more efficiently.
if you expect a few hundreds nanoseconds to a few microseconds, test once, and skip the busy wait straight to a futex syscall, which will perform its own in-kernel highly optimized cooperative busy wait for a few microseconds
if you expect more than a few dozen microseconds, use pthread conditionals, which have high upfront overhead but take into account dozens of peripheral circumstances and possibilities and ensure the most optimal approach for longer waits.
This only works because A only reads and B only writes, but this use case is fairly common for 'background worker' threads. This will only sure to work on Java or C# where volatile comes with the guarantees.
mov var1,%eax; test %eax,%eax; jz somewhere; mov var2,%eax. Reading var2 is done after var1 was read and verified to be non-zero. But the CPU can still reorder, and read var2 first, var1 later (maybe because var2 was in a nearer cache). If var1 ends up 0, the var2 value is discarded. But if it ends up non-zero, the old value will be used. –
Concentre _Atomic int. In C++11, use atomic<int>. That gives you what volatile does in Java / C# for loads/stores, and also supports atomic RMW. –
Harcourt There are some useful way to use lock-free sychronization (such as those @Tudor mentions). But I want to warn about one thing - lock-free syncrhonization doesn't compose.
You may have, for example, an integer maintained by compare&swap, and it's OK. You may also have a queue, maintained by a lock-free algorithms (it's a bit tricky, but there are good algorithms for it), and the queue is also OK.
But if you try to use the counter to count the elements in a queue, you'll get wrong answers. There will be times when an element was added, but the counter doesn't yet reflect it (or vice versa), and you can get bugs if you trust it (e.g. you may try to add to a full queue).
In short - you can have each element consistent with itself, but not consistent with each other.
© 2022 - 2024 — McMap. All rights reserved.
volatiledoesn't do what you expect it to do. It may prevent the compiler from doing some optimizations, but doesn't prevent the processor from reordering reads, and therefore can't replace a barrier. – Concentre