It's true that lock-free algorithms don't block, but they generally degrade under contention too, just in a different way. Whereas a contended mutex blocks, a contended lock-free data structure can cause the compare-and-swap step to fail a potentially arbitrary number of times (unless the algorithm is wait-free, which few are AFAIK).
Also, a surprisingly hard problem with lock free data structures is knowing when you can free/unmap any of their memory. Since there is no mutual exclusion, there is no way of knowing that another thread didn't just read the address of the thing you want to delete. He could read that address and then get swapped out for 100 years, and you can't unmap that memory until he gets rescheduled and finishes his load. Maged Michael published a technique for dealing with this problem he calls "Safe Memory Reclamation" or SMR.
Don't get me wrong, I like lock-free data structures. I just think it's important to understand that they have their issues too, and it's not as though everyone should replace all their mutexes with lock-free structures.
I also think it's important to realize that atomic operations and memory barriers are not application-level constructs as mutexes are. People should leave the atomic operations and memory barriers to the experts, and only use higher-level abstractions in applications, like lock-free stack, queue, etc. You wouldn't dream of implementing a mutex yourself in real code; the same should be true of using atomic operations or memory barriers, unless you're really an expert. One possible exception is atomic increment and decrement for simple reference counting.
Comments
It's true that lock-free algorithms don't block, but they generally degrade under contention too, just in a different way. Whereas a contended mutex blocks, a contended lock-free data structure can cause the compare-and-swap step to fail a potentially arbitrary number of times (unless the algorithm is wait-free, which few are AFAIK).
Also, a surprisingly hard problem with lock free data structures is knowing when you can free/unmap any of their memory. Since there is no mutual exclusion, there is no way of knowing that another thread didn't just read the address of the thing you want to delete. He could read that address and then get swapped out for 100 years, and you can't unmap that memory until he gets rescheduled and finishes his load. Maged Michael published a technique for dealing with this problem he calls "Safe Memory Reclamation" or SMR.
Don't get me wrong, I like lock-free data structures. I just think it's important to understand that they have their issues too, and it's not as though everyone should replace all their mutexes with lock-free structures.
I also think it's important to realize that atomic operations and memory barriers are not application-level constructs as mutexes are. People should leave the atomic operations and memory barriers to the experts, and only use higher-level abstractions in applications, like lock-free stack, queue, etc. You wouldn't dream of implementing a mutex yourself in real code; the same should be true of using atomic operations or memory barriers, unless you're really an expert. One possible exception is atomic increment and decrement for simple reference counting.