4 ms·

I am curious about your definition of wait-free and lock-free. There are a number of conflicting definitions for these two terms floating around the internet.

I am curious about your definition of wait-free and lock-free. There are a number of conflicting definitions for these two terms floating around the internet. If we take a very simple problem, incrementing a shared counter and doing some other work and returning its new value. In pseudo-code (with no exception handling). --- A lock based solution would look like this public void inc() { this.l.lock() this.value++ this.l.unlock() } This has the crucial property that if a thread gets descheduled by the OS while it holds the lock no other thread can make progress until that thread has been restored and releases the lock. Importantly this is true whether we use user space spin locks or OS integrated locks. --- A lock-free solution would look like public void inc() { while(!compareAndSet(&this.value, this.value+1)) } This has the charming property that if a thread gets descheduled by the OS anywhere inside this method other threads will not be impacted. However, there is a pathological case where a single thread may repeatedly fail the call to compareAndSet(...). While this does mean that some other thread(s) must be making progress an unlucky thread may be delayed indefinitely. --- A wait-free solution for this on x64 would look like public void inc() { // do some inline assembly XADD this.value 1 // that's enough assembly } where the XADD instruction is guaranteed to always work atomically and safely regardless of how many other threads are also xadding to the same address. In practice wait-free algorithms are exceptionally complex and often slower than their lock-free counterparts. Wait-free techniques are most popular with academics (because they are so hard :) and with hard real-time systems because you can't risk failing indefinitely on a contended compareAndSet(...). This is a good explanation of what I understand to be lock-free and wait-free http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency/ http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency... Here is a really good discussion about it https://groups.google.com/forum/#!topic/mechanical-sympathy/Tm3xRcvpnzE https://groups.google.com/forum/#!topic/mechanical-sympathy/... Truly no flame intended. I just often find it hard to discuss these things over the net because of the range of possible definitions.

mortoray 12y ago
I'm going on what wikipedia describes as [lock-free](https://en.wikipedia.org/wiki/Lock-free https://en.wikipedia.org/wiki/Lock-free). In that theoretical sense there is no difference between a mutex lock and a spin-lock. But, they may both be "lock-free". By the definition presented there virtually all programs are lock-free... that would be better termed "deadlock-free". Most people I've meet though assume lock-free just implies not using mutexes, but that spin-locks are fine. There appears to be a conflict between this definition (the one you've given) and the theoretical one. I generally stick to the term "wait-free" since it's meaning is less ambiguous.
- fmstephe 12y ago
  The definition for lock free written there is the same as the one I wrote above. The crucial sentence is found in the second paragraph. Where non-blocking is the umbrella term covering both lock, wait and obstruction free algorithms. "In modern usage, therefore, an algorithm is non-blocking if the suspension of one or more threads will not stop the potential progress of the remaining threads" Neither spin locks nor OS locks satisfy this part of the definition. A thread holding a lock who is suspended will prevent any progress being made by any other thread. I would avoid using wait-free in general because it is a very specialised kind of non-blocking algorithm.
  - mortoray 12y ago
    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

I'm going on what wikipedia describes as [lock-free](https://en.wikipedia.org/wiki/Lock-free https://en.wikipedia.org/wiki/Lock-free). In that theoretical sense there is no difference between a mutex lock and a spin-lock. But, they may both be "lock-free". By the definition presented there virtually all programs are lock-free... that would be better termed "deadlock-free". Most people I've meet though assume lock-free just implies not using mutexes, but that spin-locks are fine. There appears to be a conflict between this definition (the one you've given) and the theoretical one. I generally stick to the term "wait-free" since it's meaning is less ambiguous.

fmstephe 12y ago
The definition for lock free written there is the same as the one I wrote above. The crucial sentence is found in the second paragraph. Where non-blocking is the umbrella term covering both lock, wait and obstruction free algorithms. "In modern usage, therefore, an algorithm is non-blocking if the suspension of one or more threads will not stop the potential progress of the remaining threads" Neither spin locks nor OS locks satisfy this part of the definition. A thread holding a lock who is suspended will prevent any progress being made by any other thread. I would avoid using wait-free in general because it is a very specialised kind of non-blocking algorithm.
- mortoray 12y ago
  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 :)