Free Sync Lock

Question

My question is about multi-threaded synchronization without blocking. I wanted to know the following:

• What are the common approaches to achieve this? I read somewhere about LockFreePrimitives like CompareAndExchange (CAS) or DoubleCompareAndExchange (DCA), but no explanation was given for them? Any approaches to using MINIMIZE locks?

• How does Java / .NET reach its parallel containers? Do they use locks or synchronized synchronization?

Thanks in advance.

Answer 1

Here are some common approaches that can minimize the use of locks, assuming your algorithm has some special features:

• When updating a single numeric variable, you can use non-blocking primitives such as CAS, atomic_increment, etc. They are usually much faster than the classic blocking critical section (lock, mutex).

• When a data structure is read by multiple threads, but only written by one or more threads, the obvious solution would be to lock read and write, not a full lock.

• Try using a shallow grain block. For example, instead of locking the entire data structure with a single lock, see if you can use several different locks to protect individual sections of the data structure.

• If you rely on the effect of hidden locking of memory locks to ensure that one variable is visible in threads, just use volatile ¹ if possible.

• Sometimes the use of a conditional variable (and associated lock) is too slow in practice. In this case, the volatile spin is much more efficient.

More useful tips on this topic: http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/

Good reading on another SO question: Keyless multithreading is for real thread experts (don't be afraid of the name).

And the recently reviewed non-blocking implementation of Java atom_decrement: Starving in non-blocking approaches

---

¹ The use of volatile here applies to languages ​​such as Java, where volatile defined semantics in the memory model, but not in C or C ++, where volatile preceded by the introduction of a cross-thread memory model and does not integrate with it. Similar constructs are available in languages ​​such as various std::memory_order specifiers in C ++.

Answer 2

There are several useful ways to use synchronous locking (e.g. mentioning @Tudor). But I want to warn about one thing: synchronization is not blocked.

You may have, for example, an integer supported by comparison and exchange, and that’s fine. You may also have a queue supported by non-blocking algorithms (this is a bit complicated, but there are good algorithms for this), and the queue is also fine.
But if you try to use a counter to count the items in the queue, you will get the wrong answers. There will be times when an item has been added, but the counter does not yet reflect it (or vice versa), and you may get errors if you trust it (for example, you can try adding to the full queue).

In short, you can have every element that matches itself, but does not match each other.

Answer 3

Comparison and exchange are useful, but there is an even simpler (so-called “blocking”) technique that is useful in some cases when the producer / consumer uses it, which can be useful, so I mentioned this.

Imagine you have a doWork () function that writes to the buffer.

• Thread A initializes a volatile boolean (flag) to false, available both for Thread A and for creating a volatile buffer that doWork will output to Thread B (Global, etc.).
• Thread A creates thread B, which calls doWork ().
• Thread B doWork () starts creating / writing to the buffer. Upon completion, it sets boolean to true.
• Thread A can query the global boolean flag that starts with false. When it returns (not false), it can access the data in the buffer object, assuring that it is complete. Between polls, Thread A may do other work. (So, for example, it polls once in an update call and does not wait for the true value). This does not account for error handling, but it can also be handled in the buffer.

This only works because A only reads and B only writes, but this use case is pretty common for background worker threads. This will certainly work in Java or C #, where volatility will come with guarantees.