6 ms·

Note it's important to be "wait-free" and not just "lock-free". The first item here does appear to be "wait-free".

fmstephe 12y ago
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).

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).