FYI lock-free programming does not mean "free of locks" but rather "free of lockups", as in, there isn't any possible arrangement in which two threads could end up blocking each other indefinitely (as could happen with mutexes and deadlocks).
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)."
As I understand it, it does actually mean "free of locks", since a lock-free algorithm, by definition, cannot be implemented in terms of classical locks (typically mutexes) [1] [2]. It's "free of lockups" by virtue of, well, being free of locks.
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).
If you are in an environment where you can guarantee that a piece of code runs in bounded time (no interrupts, no faults, etc), then locks can actually be used in lock-free algorithms since code inside the lock will always be making forward progress and will exit in or before some deterministic time. If the lock is fair and there's a bounded number of threads accessing the lock, then it technically becomes wait-free under these conditions since time to completion is bounded by n_threads * task_time;
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 don't think that is quite correct. By that definition, any alhorithm that is free of deadlocks would be a lock free algorithm. But, I'm fairly sure that isn't the case - otherwise a hashmap protected by a single mutex would be considered a lock free data structure since as there is only a single mutex, deadlock would be impossible.
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.)"
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)."
[0] https://en.wikipedia.org/wiki/Non-blocking_algorithm