The difference is that in a true lockless algorithm, no thread "holds" the lock (because there is no lock). Therefore, if a thread gets scheduled out while in the middle of any operation, every other running thread can still continue working. That’s in contrast to a locking implementation where it’s very possible for a thread to get swapped out while holding a lock, thus causing every other thread to spin endlessly until the scheduler ends up swapping the original thread back in so it can release the lock.
This is one key advantage of using the OS supplied mutex facility rather than rolling your own spinlocks. The OS mutex has the ability to know that if a thread is blocking on the mutex and the thread which holds it is currently not running, it might as well start running the original thread again so that it can release the lock (as nothing else can get done until that happens anyway).
I believe this is why (in my personal experience) userspace spinlocks perform better than mutexes up until about the point of where you have many more threads than CPUs. My guess is that the probability of a thread getting scheduled out while holding the lock increases with both the number of threads as well as the overall contention for the lock.
By definition, a lock-free algorithm guarantees at least one thread makes forward progress at each time step. So yes, there is no chance of deadlock.
If you want to guarantee that all threads make progress per unit time, you need wait-free.
what am i missing?
Passing msg with different Threads/Process is not "rolling your own locks with atomic variables".
Basically, each T/P need to receive msg will create MsgQ with msgQLen and return Q_id.
msgQ_Send() Api will use atomic_add() to get the next slot on the msgQ to place the value and/or MsgPtr.
There is no lock needed, only Atomic_add().
Performance wise, it works very well in SMP environments and I ported the library to vxWorks, Linux kernel, user space and QNX.
I have tons of validation tests on the correctness of the message orders, contain and constantly run them on multiple 4 core Xeon machine to check the correctness and benchmark performance.
Such an algorithm wouldn't even be obstruction-free.