A simple example would be concurrently writing into a shared queue. To make it really simple, let's assume that this queue's buffer can only be written once, and then the program has to exit.
If we have a buffer in this queue that can hold 20 messages, and an atomic integer that represents the current index, then we could have two (or however many) threads writing into it at the same time by just doing "index = myAtomic.fetch_add(1)", which will atomically add one to the index, then return the previous value. Atomics are supported at a hardware level, so they're generally pretty efficient, and there definitely is no lock like a Mutex involved here. In the end, both threads are able to write into shared memory without conflicting with each other. Using one or two more atomic integers, we could support having one or more readers reading off of the queue at the same time that we're writing to it, and we could get to the point where we're able to start reusing the buffer in a circular fashion.
With a mutex you can lock for an entire ”transaction” where you fetch a unique index and write your value to the queue. With just atomics you can get a unique index into the queue concurrently with other threads, sure, but how do you mark it as ready to be unqueued once you are done writing your data?
Thats where lock free data structures come into play. They have solved this intricate synchronization between multiple atomics so you don’t have to.
Eventually when it comes down to the hardware level the processor will have to assert #LOCK (or whatever mechanism it uses). So arguably even atomics aren't "lock" free, somewhere along the line some piece of hardware will have to block all other hardware to do its thing. DRAM can only read one thing at a time (and has to write it back afterwards).
RAM does the locking inside it, and expose it as "compare-and-set" and "compare-and-swap" etc primitives. Various computing languages that use those primitives usually call that "atomic data structures". The thing is that RAM is way faster in that regard than locking on user/kernel level, so for program it looks like there's no locks. But atomics indeed do slow down your program, if just a little, because "compare-and-set" is still slower than just "set".
Much of the foundational theoretical work in this area was done by Maurice Herlihy in the 1980s and 1990s. For example, https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf I briefly paid for an ACM membership just so I could read his original work. (Well, I paid so I could read the literature in transactional memory, but I mostly ended up reading papers authored by Herlihy, co-authored by Herlihy, or analyzing Herlihy's work.)
https://preshing.com/20120612/an-introduction-to-lock-free-p...
From [0]: "An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress)."
Note that there's also the distinction between lock-free algorithms and lock-free data structures. Crossbeam is the latter, I believe (but I could be wrong).
[1] https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf
This environment only happens to exist in very specific and uncommon settings, so it's not a generally useful concept for lock-free programming. It's common in the linux kernel to see spinlocks taken in sections which have disabled all interrupts, for example, but this is not an environment that normal programs can live in.
I think the key paragraph from the Wikipedia article is:
"In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)"
There is an x86 instruction prefix named 'lock', but it only applies to a single instruction and is considered in the family of being atomic rather than a mutex.
On that base, you can build lock-free data structures.
When people say "lock-free", they mean they rely on basic hardware primitives that end up doing pretty much what you would do with locks in your code, but you can't see it. Generally, the hardware can do it faster, but rarely as much faster as people think, or want. In particular, you will still have stalls -- 30 cycles, 100 cycles, sometimes longer, whenever anything clashes, "lock-free" or no. Everything you do to cut contention at your level will pay just as it would if you were using regular locking. If you can cut your contention enough, lock-free ends up little faster (although it can still reduce latency spikes).
If the lock-free stuff is buried in a library well-maintained by somebody else who is terrifyingly competent, then use it. But it is very, very unlikely that maintaining your own will be worthwhile; the most likely outcome is extremely subtle bugs. And who cares how fast buggy code is? There are much easier ways to make wrong code fast.
At the end of the day, how can something that is safely concurrent also be lock-free? At the lowest level, what is the primitive that enforces the safety, if it's not a lock or mutex?
My brain starts to run in cricles when I think of this scenario: two threads trying to write to one piece of data. To do so safely, they need to take turns. Therefore, one has to wait for the other to complete. Therefore, one must acquire a mutually exclusive... hold on, that's a mutex!
Can someone please clear this up for me?