[md5person]

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

[dbaupp]

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

[chrisseaton]

‘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]

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.

[sriram_malhar]

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]

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]

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]

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]

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]

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]

> "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]

In terms of the level at which we reason about thread interleavings, which is what we’re talking about, it is bound.

[md5person]

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

[coder543]

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]

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

[coder543]

> why not just ignore it then?

Because it's misleading and/or missing the point. As stated. Why would I want more people to read something that I believe is misleading?

> Clearly it's not "fine"

Once again missing the point. The prevailing opinion on HN is what will get upvoted, and a lot of other stuff will get downvoted. I have seen that prevailing opinion be hilariously wrong before.

If you want to be heard with an unpopular opinion, you have to make a compelling argument... you can't expect to be upvoted to the top just because you're sharing an opinion. It's rare for a comment to be lukewarm enough for no one to feel strongly enough to downvote it. It's going up, going down, or it's on a thread no one is reading. Downvotes don't mean people hate the person leaving the downvoted comments; it's just a tool for disagreeing with comments.

> This is my last comment on HN.

Because people disagreed with you? People even left explanations, but that wasn't enough.