An Introduction to Lock-Free Programming (2012)
preshing.com
preshing.com
To be more precise... I like to use single-writer ring buffers. (Technically you could say they are a sort of lock-free queue. But there is little to go wrong in a ring buffer.) Mainly, I reduce coupling enough that taking the occasional mutex is not a noticeable drain. Explicit mutex locking is less prone to obscure heisenbugs than lock-free techniques.
What I rip out are queues treated as if "lock-free" coupling were free. It's not free; it is at least 50 cycles, each interaction. Nowadays you can get a hell of a lot of work done in 50 cycles. Each "lock-free" operation engages bus-level interactions more like a mutex than not, so it doesn't buy what you hope.
To reduce coupling, you increase batching. Instead of one event per interaction, do ten, or fifty.
Most "lock-free" implementations you find are not portable off of x86 systems, which have a much more forgiving memory model than, say, ARM. You think you were careful, but the system is better at finding your mistakes than you are.
If you can do that it makes your previous argument, caring that an interaction takes 50 cycles, basically irrelevant.
If it is done as a linked list there may be good multiple insert options, but then you have a linked list and all the extra jumping around memory that involves compared to a ring buffer.
The approach used in that article is to publish the events into multi-producer/single-consumer queues. When a queue is full, then the batch can be performed under a lock to replay and catch-up the LRU. This way the lock is used to ensure single-writer, but does not suffer lock contention. The ring buffer is lock-free, but the cache itself is not. Lock-free can suffer contention or be more expensive algorithmically than if under a lock, so whichever strategy chosen requires careful consideration of the system performance.
[1] http://highscalability.com/blog/2016/1/25/design-of-a-modern...
And get better throughput.
[1] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15...
[2] http://ranger.uta.edu/~sjiang/pubs/papers/ding16_BP-wrapper....
I promise you that practically nobody doing it has ever heard of "BP-Wrapper", or of flat-combining.
This property in turn could get you better performance in the end because you may not have to size everything for such a big range of contention, so you can optimize utilization of the hardware more without risking things hitting a peak and experiencing severe degradation.
I think you may be confusing lock-free with wait-free here. I believe it's wait-free that gives you a bound on the number of steps the process can take to complete an operation, but I'm not an expert.
http://www.1024cores.net/home/lock-free-algorithms/introduct...
They define wait free as not even having thread starvation and lock free as not having to wait for anything as long as you have CPU to actually run.
Its always interesting how any given topic always fragments into much more complexity than you expected once you start learning about it!
> Wait-freedom means that ... Each operations is executed in a bounded number of steps.
Lock-free queues are not fixed-time, because operations on them involve negotiations on the bus to reclaim the cache line involved, often behind other queued operations.
With the ring buffer, the writer never gives up ownership of the head cache line, and the next one can be pre-fetched (speculatively) because the writes are walking memory sequentially. There is a little hiccup when you wrap around, so it's not absolutely fixed-time.
I put my ring buffers on hugepages so I am not competing for page-map TLB cache.
Another possibility is that the thread dies while holding a mutex (or exclusively possessing a resource). It may seem like a stretch for shared memory systems, but not so much for distributed systems. Recovering the resource is not an easy task, especially considering the fact that recovering threads may also die or that the thread assumed dead all of a sudden returns to life. In my opinion, making a parallel system robust to that kind of malfunction goes far beyond what the industry considers acceptable as lock-free algorithms. I gave some thought to that scenario in my project Robusta [1]. I doubt it could be useful for any practical purpose but at least it works for a universal computational model.
[...]
A final precision: Operations that are designed to block do not disqualify the algorithm. For example, a queue’s pop operation may intentionally block when the queue is empty. The remaining codepaths can still be considered lock-free. ```
I don't get it ; how could "locking a mutex" not be considered as an "operation that are designed to block" ?
Would somebody be kind enough to tell me what am I missing here? Thanks !
That's not what is being claimed here. What is being said is that an algorithm that blocks a thread can still be considered lock-free. There's a difference between lock-freedom and wait-freedom.
That seems too extreme to me. If the scheduler itself is potentially malicious, then no multi-threaded implementation is safe, since we can't assume that any thread we start will ever actually run.
Or, another way to look at it - a lock-free algorithm that allows starvation or livelock/deadlock.
Remembering that you are your own worst enemy, what this implies is that some other perfectly sane decision you made in the past has come to bite you in the arse.
If the properties of concern for your thread or program are only safety properties (“never does a bad thing”) then the fact that the program may never do anything at all is just fine!
Then, if you want some liveness properties (“eventually does something good”) you’ll need to embed some assumption about fairness/scheduling/progress just as you’ve said!
This appears in early concurrency literature (TLA etc which I can’t be bothered to look for)
As omazurov mentioned as a top-level comment, threads can also die, which is rather like never being scheduled. In practice, I suspect that you're right that it's often too extreme of a model—many programs use locks and don't worry too much about this issue.
The queue implementation that blocks on an empty queue is fine if inserting into the queue is still lock-free, ie, your insert operation eventually completes or makes progress regardless of if a reader is spinning on the lock that allows you to pop a value from the queue.
That means, while the popping of a value is locking, inserting is not. Hence the mutex locking the read does not turn the queue into a locking algorithm.
Is there such thing as a non-shared mutex?