3 ms·

I think I better understand what "lock-free" means now, thank you for the explanation. I will review what I said in my article and ensure I'm not spreading any

I think I better understand what "lock-free" means now, thank you for the explanation. I will review what I said in my article and ensure I'm not spreading any misinformation. When I learned of lock-free I was presented with a spin-lock like system as an example, but that is clearly incorrect. The key I guess is that any thread could halt at any point and the other threads are not blocked (within obvious practical limitations). This doesn't mean other works may not have to redo some work, such as finding a new terminal node in a lock-free list. In practice lock-free is likely sufficient, even in real-time systems. One would need a very high level of contention to render lock-free incapable (though with a high number of cores it's definitely possible).

fmstephe 12y ago
It's a very tricky collection of definitions. All descriptions of it are a bit vague. For instance under lock-free on wikipedia we read "An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress)." That definitely sounds like locks would be included. I am pretty sure that if my program runs for long enough that descheduled thread will get rescheduled and continue to make progress. And then there is the hand-wavy 'sensible definition of progress' what is that? If we take an example from a single producer single consumer queue which is certainly non-blocking. With two methods. // Returns true if o was successfully added to the queue, false otherwise public boolean enqueue(Object o) // Returns null if the queue is empty, otherwise returns a FIFO object public Object dequeue() There can only be two threads running. So lets suspend one indefinitely to test that our implementation is non blocking. If we suspend the producer then the consumer will eventually stop returning objects from dequeue() and just return null. If we suspend the consumer then the producer will eventually start returning false from enqueue(). In either of these cases we could definitely argue that our system has stopped making progress and the definition 'actually enqueue or dequeue some useful thing' seems like a sensible one. But this definition should really just be 'always return from enqueue or dequeue' and this second definition allows us to say our queue is non blocking. It's pretty hard to pin down what constitutes a 'sensible definition of progress'. For a user space spin lock saying that a thread continues to spin in a tight loop could be a sensible definition of progress, but isn't helpful for our purposes of deciding if an algorithm or data structure is non blocking. This trickiness makes it surprisingly difficult to coherently discuss non-blocking x-free algorithms. (Luckily, in practice, these algorithms are so much fun that it is worth the difficulty :)
- mortoray 12y ago
  Yes, they are fun. At least in practice the decision to use one or the other would come from variance guarantees. From this view we can define a "practical" meaning to each one. * blocking: very high variance in operation time * lock-free: lower average, likely lower variance, but prone to spikes * wait-free: lowest variance, approaching zero, cannot have spikes

fmstephe 12y ago

It's a very tricky collection of definitions. All descriptions of it are a bit vague. For instance under lock-free on wikipedia we read "An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress)." That definitely sounds like locks would be included. I am pretty sure that if my program runs for long enough that descheduled thread will get rescheduled and continue to make progress. And then there is the hand-wavy 'sensible definition of progress' what is that? If we take an example from a single producer single consumer queue which is certainly non-blocking. With two methods. // Returns true if o was successfully added to the queue, false otherwise public boolean enqueue(Object o) // Returns null if the queue is empty, otherwise returns a FIFO object public Object dequeue() There can only be two threads running. So lets suspend one indefinitely to test that our implementation is non blocking. If we suspend the producer then the consumer will eventually stop returning objects from dequeue() and just return null. If we suspend the consumer then the producer will eventually start returning false from enqueue(). In either of these cases we could definitely argue that our system has stopped making progress and the definition 'actually enqueue or dequeue some useful thing' seems like a sensible one. But this definition should really just be 'always return from enqueue or dequeue' and this second definition allows us to say our queue is non blocking. It's pretty hard to pin down what constitutes a 'sensible definition of progress'. For a user space spin lock saying that a thread continues to spin in a tight loop could be a sensible definition of progress, but isn't helpful for our purposes of deciding if an algorithm or data structure is non blocking. This trickiness makes it surprisingly difficult to coherently discuss non-blocking x-free algorithms. (Luckily, in practice, these algorithms are so much fun that it is worth the difficulty :)

mortoray 12y ago
Yes, they are fun. At least in practice the decision to use one or the other would come from variance guarantees. From this view we can define a "practical" meaning to each one. * blocking: very high variance in operation time * lock-free: lower average, likely lower variance, but prone to spikes * wait-free: lowest variance, approaching zero, cannot have spikes