4 ms·

> "lock-free" I never liked that term. Lock-free algorithms will usually boil down to some combination of polling, waiting (sleep(), futex-style), or use what

> "lock-free" I never liked that term. Lock-free algorithms will usually boil down to some combination of polling, waiting (sleep(), futex-style), or use what are essentially more fine-grained, hardware-backed locks (CAS, memory barriers, LOCK instructions, hardware-specific transactional instructions, etc). The locks are very much still there.

sriram_malhar 6y ago
True, but the key difference in the lock-free approach is that the "lock" is basically a pointer-swizzling or timestamp-swizzling operation, and so the lock duration is strictly bounded; it is determined by the application or the thread-scheduler.
- WJW 6y ago
  Naming is hard, but in this case lock-free is just misleading. Why oh why didn't they go with bounded-lock data structures? :)
  - klodolph 6y ago
    Because there is no lock. With a lock, you acquire the lock, you perform your operation, and then you release the lock. Lock-free is typically done differently. You don’t acquire a lock, you start performing the operation “optimistically”, and you commit the result if no other thread has stomped on your data. If another thread has stomped on your data, you start over. One of the important differences here is that it’s a race. Whoever commits first, wins. With a lock, you have to wait for whatever thread acquired the lock first. That thread may not even be running. So, lock-free is fundamentally different because with a lock-free system, a thread that is running will always complete work (you just don’t know which thread). In a system with locks, threads that are running may be prevented from making progress by threads that are not running. Systems with locks can also deadlock, lock-free systems cannot deadlock. Usually, there is some sort of guarantee that lock-free systems always make progress.
    - md5person 6y ago
      Your explanation doesn't make sense to me. > "you commit the result if no other thread has stomped on your data" What does "committing" mean here? If it means performing an atomic write (a-la CAS), then you're using a lock (see my next point). > "If another thread has stomped on your data, you start over." So you let your thread sit there in a spin-loop and CAS a condition-variable. That's a lock for all intents and purposes, and your system can still "dead-lock" (read: your thread will never get to "win the race"), if your "data gets stomped on" over and over again in-between reads (which are obviously non-atomic, otherwise you'd be locking there too). > "Usually, there is some sort of guarantee that lock-free systems always make progress." Getting a time-slice to continue running in a tight-loop while trying to CAS is not the same as "making progress". "Making progress" would be - you'd get a chance to commit your changes and proceed to your next bit of business logic. But with contention, that's not guaranteed to happen at-all?
      - klodolph 6y ago
        I think you’ve just mixed up wait-free with lock-free. - Lock-free: at least one thread will make progress - Wait-free: all threads will make progress The difference between locks and lock-free is very noticeable if a thread holding a lock is suspended (which can happen on a modern system just by accessing memory that is paged out). On real-time systems it’s also possible to guarantee that high-priority tasks will make progress, regardless of how a low-priority task behaves. With locks, a low-priority task can easily prevent a high-priority task from running at all.
      - chrisseaton 6y ago
        A system cannot deadlock with CAS. It can live-lock. I think you’re possibly confusing lock-free and wait-free, which is a stronger guarantee.
- md5person 6y ago
  > "the lock duration is strictly bounded; it is determined by the application or the thread-scheduler" Practically speaking - wouldn't the exact duration be heavily influenced by the countless layers of abstraction beneath the application itself (kernel, scheduler, hardware, speculative execution, etc)? If so, can we ever truly make the claim that the "duration is strictly bounded"?
  - chrisseaton 6y ago
    In terms of the level at which we reason about thread interleavings, which is what we’re talking about, it is bound.
chrisseaton 6y ago
‘Lock-free’ means the application cannot ‘lock up’, rather than there are no locks. CAS does use a kind of hardware-level lock in the cache, but can never cause any application to lock up because there is no per-process state like in a software lock.
- md5person 6y ago
  Yes, that aligns more closely with my mental model of a "lock-free algorithm", but what I see in practicality is people avoiding (or re-inventing) synchronization primitives, thinking that they don't belong in a "lock-free algorithm". You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully.
dbaupp 6y ago
It’s used flippantly at times, but lock-free is a technical term referring to a guarantee of global progress https://en.m.wikipedia.org/wiki/Non-blocking_algorithm https://en.m.wikipedia.org/wiki/Non-blocking_algorithm (I think it’s also sometimes used as a synonym for non-blocking, so including “obstruction-free” too). For instance, if all threads except one are stopped, the single running thread should “finish” (for whatever finish means) in a finite time (lock-free is stronger than this condition, too). An algorithm using mutex-style locks fails this guarantee, if one of the stopped threads is inside the critical section.
- deleted 6y ago
  [deleted]
md5person 6y ago
I wonder why every single comment I leave in this thread is getting down-voted. This community has truly deteriorated over the years.
- coder543 6y ago
  Because a lot of your comments in this thread are "missing the point" or (unintentionally) misleading at best, and it's easier for people to use a downvote to make those comments less prominent in the discussion than to go through the trouble of trying to explain why the comments are missing the point or unintentionally misleading. But, a lot of people have gone through the effort to leave explanations in this case. Isn't that good enough? For one unaddressed example: > You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully. This might be technically true, but atomics provide significant performance benefits compared to using a mutex with a timeout, and I don't think of "lock free" as relying on busy loops as you seem to think in your comments. I'm sure a busy loop makes sense in very specific algorithms, and mutexes themselves often use a limited amount of busy waiting to avoid context switches. You can simulate atomics with mutexes, but that's not the point. Lock free is hard to do correctly. Mutexes create the possibility of a deadlock, which is incompatible with being lock-free, so you have to avoid all the footguns of lock-free and the footgun of using mutexes. So, yes, you can use standard sync objects... but that doesn't make anything better in this case. It misses the point. "Technically correct" isn't always good enough to get an upvote. If you don't agree, that's fine... but this is completely uncalled for and against the community guidelines: > This community has truly deteriorated over the years. No one is obligated to upvote things they consider incorrect, and downvotes are perfectly suitable for this purpose under HN guidelines.
  - md5person 6y ago
    > "While technically true... I don't see how it contributes anything useful to the conversation, so I downvoted it." If you don't see how it contributes to the conversation - why not just ignore it then? Just because you think this doesn't contribute to the conversation, doesn't make it true. > "If you don't agree, that's fine..." Clearly it's not "fine", otherwise you wouldn't try to silence comments you disagree with by down-voting them. This is my last comment on HN.

sriram_malhar 6y ago

True, but the key difference in the lock-free approach is that the "lock" is basically a pointer-swizzling or timestamp-swizzling operation, and so the lock duration is strictly bounded; it is determined by the application or the thread-scheduler.

WJW 6y ago
Naming is hard, but in this case lock-free is just misleading. Why oh why didn't they go with bounded-lock data structures? :)
- klodolph 6y ago
  Because there is no lock. With a lock, you acquire the lock, you perform your operation, and then you release the lock. Lock-free is typically done differently. You don’t acquire a lock, you start performing the operation “optimistically”, and you commit the result if no other thread has stomped on your data. If another thread has stomped on your data, you start over. One of the important differences here is that it’s a race. Whoever commits first, wins. With a lock, you have to wait for whatever thread acquired the lock first. That thread may not even be running. So, lock-free is fundamentally different because with a lock-free system, a thread that is running will always complete work (you just don’t know which thread). In a system with locks, threads that are running may be prevented from making progress by threads that are not running. Systems with locks can also deadlock, lock-free systems cannot deadlock. Usually, there is some sort of guarantee that lock-free systems always make progress.
  - md5person 6y ago
    Your explanation doesn't make sense to me. > "you commit the result if no other thread has stomped on your data" What does "committing" mean here? If it means performing an atomic write (a-la CAS), then you're using a lock (see my next point). > "If another thread has stomped on your data, you start over." So you let your thread sit there in a spin-loop and CAS a condition-variable. That's a lock for all intents and purposes, and your system can still "dead-lock" (read: your thread will never get to "win the race"), if your "data gets stomped on" over and over again in-between reads (which are obviously non-atomic, otherwise you'd be locking there too). > "Usually, there is some sort of guarantee that lock-free systems always make progress." Getting a time-slice to continue running in a tight-loop while trying to CAS is not the same as "making progress". "Making progress" would be - you'd get a chance to commit your changes and proceed to your next bit of business logic. But with contention, that's not guaranteed to happen at-all?
    - klodolph 6y ago
      I think you’ve just mixed up wait-free with lock-free. - Lock-free: at least one thread will make progress - Wait-free: all threads will make progress The difference between locks and lock-free is very noticeable if a thread holding a lock is suspended (which can happen on a modern system just by accessing memory that is paged out). On real-time systems it’s also possible to guarantee that high-priority tasks will make progress, regardless of how a low-priority task behaves. With locks, a low-priority task can easily prevent a high-priority task from running at all.
    - chrisseaton 6y ago
      A system cannot deadlock with CAS. It can live-lock. I think you’re possibly confusing lock-free and wait-free, which is a stronger guarantee.
md5person 6y ago
> "the lock duration is strictly bounded; it is determined by the application or the thread-scheduler" Practically speaking - wouldn't the exact duration be heavily influenced by the countless layers of abstraction beneath the application itself (kernel, scheduler, hardware, speculative execution, etc)? If so, can we ever truly make the claim that the "duration is strictly bounded"?
- chrisseaton 6y ago
  In terms of the level at which we reason about thread interleavings, which is what we’re talking about, it is bound.

chrisseaton 6y ago

‘Lock-free’ means the application cannot ‘lock up’, rather than there are no locks. CAS does use a kind of hardware-level lock in the cache, but can never cause any application to lock up because there is no per-process state like in a software lock.

md5person 6y ago
Yes, that aligns more closely with my mental model of a "lock-free algorithm", but what I see in practicality is people avoiding (or re-inventing) synchronization primitives, thinking that they don't belong in a "lock-free algorithm". You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully.

dbaupp 6y ago

It’s used flippantly at times, but lock-free is a technical term referring to a guarantee of global progress https://en.m.wikipedia.org/wiki/Non-blocking_algorithm https://en.m.wikipedia.org/wiki/Non-blocking_algorithm (I think it’s also sometimes used as a synonym for non-blocking, so including “obstruction-free” too). For instance, if all threads except one are stopped, the single running thread should “finish” (for whatever finish means) in a finite time (lock-free is stronger than this condition, too). An algorithm using mutex-style locks fails this guarantee, if one of the stopped threads is inside the critical section.

deleted 6y ago
[deleted]

md5person 6y ago

I wonder why every single comment I leave in this thread is getting down-voted. This community has truly deteriorated over the years.

coder543 6y ago
Because a lot of your comments in this thread are "missing the point" or (unintentionally) misleading at best, and it's easier for people to use a downvote to make those comments less prominent in the discussion than to go through the trouble of trying to explain why the comments are missing the point or unintentionally misleading. But, a lot of people have gone through the effort to leave explanations in this case. Isn't that good enough? For one unaddressed example: > You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully. This might be technically true, but atomics provide significant performance benefits compared to using a mutex with a timeout, and I don't think of "lock free" as relying on busy loops as you seem to think in your comments. I'm sure a busy loop makes sense in very specific algorithms, and mutexes themselves often use a limited amount of busy waiting to avoid context switches. You can simulate atomics with mutexes, but that's not the point. Lock free is hard to do correctly. Mutexes create the possibility of a deadlock, which is incompatible with being lock-free, so you have to avoid all the footguns of lock-free and the footgun of using mutexes. So, yes, you can use standard sync objects... but that doesn't make anything better in this case. It misses the point. "Technically correct" isn't always good enough to get an upvote. If you don't agree, that's fine... but this is completely uncalled for and against the community guidelines: > This community has truly deteriorated over the years. No one is obligated to upvote things they consider incorrect, and downvotes are perfectly suitable for this purpose under HN guidelines.
- md5person 6y ago
  > "While technically true... I don't see how it contributes anything useful to the conversation, so I downvoted it." If you don't see how it contributes to the conversation - why not just ignore it then? Just because you think this doesn't contribute to the conversation, doesn't make it true. > "If you don't agree, that's fine..." Clearly it's not "fine", otherwise you wouldn't try to silence comments you disagree with by down-voting them. This is my last comment on HN.