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