Oh god, "non-blocking" is even worse, no thanks to Javascripters. Lock-free data structures can wait, and can block if they deal with failed operations by spinlocking.
The muddled concepts are:
waiting - what you do until you eventual acquire a contested resource (spinlock)
mutexes - objects used to enforce critical sections
stopping the world - a processor stopping the execution of all threads in order to ensure proper order of thread-critical instructions (is there a formal name for this?)
CAS - an atomic primitive often used to avoid the overhead of stopping the world to enter critical sections, or to avoid deadlock by implementing algorithms that do not have critical sections
critical section - a routine that must be executed by only one thread at a time
blocking - being unable to proceed with a given routine on account of another thread
non-blocking / async - threading in general, or, instead of spinlocking, yielding execution to another thread
deadlocking - a systematic failure wherein there is a cyclical dependency of threads on resources, and no thread can progress
All of these can be informally referred to by "locking", and lock-free (formal definition) algorithms avoid deadlocking by avoiding having critical sections or locks on resources at all. They're generally more performant, but that's coincidental.
If you have a critical section, and you implement a mutex using CAS, you've probably sped up your application because you no longer have to pause other threads. That's "lock free" in the sense that "stopping the world" is "locking" other threads, but not "lock free" in the sense of avoiding deadlock. If a thread enters a critical section with a CAS mutex and then waits forever, you can get deadlock.
The muddled concepts are: waiting - what you do until you eventual acquire a contested resource (spinlock) mutexes - objects used to enforce critical sections stopping the world - a processor stopping the execution of all threads in order to ensure proper order of thread-critical instructions (is there a formal name for this?) CAS - an atomic primitive often used to avoid the overhead of stopping the world to enter critical sections, or to avoid deadlock by implementing algorithms that do not have critical sections critical section - a routine that must be executed by only one thread at a time blocking - being unable to proceed with a given routine on account of another thread non-blocking / async - threading in general, or, instead of spinlocking, yielding execution to another thread deadlocking - a systematic failure wherein there is a cyclical dependency of threads on resources, and no thread can progress
All of these can be informally referred to by "locking", and lock-free (formal definition) algorithms avoid deadlocking by avoiding having critical sections or locks on resources at all. They're generally more performant, but that's coincidental.
If you have a critical section, and you implement a mutex using CAS, you've probably sped up your application because you no longer have to pause other threads. That's "lock free" in the sense that "stopping the world" is "locking" other threads, but not "lock free" in the sense of avoiding deadlock. If a thread enters a critical section with a CAS mutex and then waits forever, you can get deadlock.