3 ms·

> CAS is "lock free" only in the sense that it doesn't require the processor to stop the world in order to flip the mutex boolean. It's still a mutex, and it st

by dbaupp 10y ago

> CAS is "lock free" only in the sense that it doesn't require the processor to stop the world in order to flip the mutex boolean. It's still a mutex, and it still gates access to a critical section, and you still need some kind of strategy to deal with waiting for the critical section to become available (e.g., spinlocking, signaling the OS to sleep thread execution). CAS can/"must" be used to implement normal mutex locks, but this definitely isn't it's only use. The only way you could view CAS itself as locking something is at a low cache-coherency level, where it requires the processor to lock a cache line (https://en.wikipedia.org/wiki/MESI_protocol https://en.wikipedia.org/wiki/MESI_protocol ); however, this is at a level that isn't semantically observable: it is atomic with respect to things like OS thread scheduling, unlike mutexes. In some sense, this is the critical reason that CAS and lock-free programming is interesting, as it avoids problems like priority inversion, and gives the guarantee of at least one thread always making progress. > That's just putting one giant mutex around all access to the object. Having finer granularity != "lockless". Is this a comment about the article, or just a general statement? Because the article doesn't propose finer granularity locks as a lockless solution.

ajamesm 10y ago
The linked list discussed in the article forgoes mutexes, but in exchange, operations aren't guaranteed to succeed: Because we are no longer taking explicit locks, there is no guarantee that insert operation will succeed. Therefore, CAS based algorithms are usually implemented using a loop (aka CAS loop) to retry the operation when CAS fails. So you're still getting spinlocks (or context switches, etc.) assuming these inserts have to eventually succeed. Implicitly, the CAS does "lock" in the sense of forcing other accesses into retry loops. You're still dealing with the problems inherent to your waiting strategy. This data structure doesn't prevent problems like starvation. In the pathological case, you'll get stuck forever in a spinlock trying to insert. > In some sense, this is the critical reason that CAS and lock-free programming is interesting Right. The article's preface criticizes implementations of mutexes in C++ and Java as unscalable, which is certainly a problem, but categorically a different concern from that of designing lock-free algorithms or data structures.
- chrisseaton 10y ago
  > This data structure doesn't prevent problems like starvation But that's fine! Lock-free permits starvation. Not every data structure can solve every problem. If you can't have starvation then lock-free isn't enough. In which case, this article isn't for you.
  - ajamesm 10y ago
    You realize you cherry-picked a snippet of my post, and then made the exact point I just made, which is: There aren't deadlocks, but there is still waiting and potential starvation, all of which can be informally called "locks" and so we need to be careful about qualifying "locking". This isn't a criticism of lock-free methodology, but a consideration of the ways in which "lock-free" could be interpreted.
    - chrisseaton 10y ago
      > all of which can be informally called "locks" > the ways in which "lock-free" could be interpreted This is only a problem if you use a definition of the 'lock' in 'lock-free' that isn't the same as everyone else's. I guess I must be misunderstanding what you're trying to say if that isn't it. I'll stop criticising.
- dbaupp 10y ago
  One thread possibly being starved is very different to all threads being starved, as can happen with blocking algorithms (the classic example being the thread holding a lock is descheduled: no-one needing it can make any progress). Atomic instructions like CAS do not inherently have this problem, and can be used in ways to avoid it (such as how the article describes it), but the same is not true of mutexes. I personally find it makes sense think of this is more of a transactional thing (one thread invalidates the transactions of others), rather than a mutex-esque critical section. In any case, the article (accidentally or otherwise) does actually use the correct technical term for code where some threads may be starved while others make progress (lock-free). If it was trying to discuss code that avoid this, it would be "Notes on Wait Free Programming", and would likely be significantly longer.

by dbaupp 10y ago

ajamesm 10y ago

The linked list discussed in the article forgoes mutexes, but in exchange, operations aren't guaranteed to succeed: Because we are no longer taking explicit locks, there is no guarantee that insert operation will succeed. Therefore, CAS based algorithms are usually implemented using a loop (aka CAS loop) to retry the operation when CAS fails. So you're still getting spinlocks (or context switches, etc.) assuming these inserts have to eventually succeed. Implicitly, the CAS does "lock" in the sense of forcing other accesses into retry loops. You're still dealing with the problems inherent to your waiting strategy. This data structure doesn't prevent problems like starvation. In the pathological case, you'll get stuck forever in a spinlock trying to insert. > In some sense, this is the critical reason that CAS and lock-free programming is interesting Right. The article's preface criticizes implementations of mutexes in C++ and Java as unscalable, which is certainly a problem, but categorically a different concern from that of designing lock-free algorithms or data structures.

chrisseaton 10y ago
> This data structure doesn't prevent problems like starvation But that's fine! Lock-free permits starvation. Not every data structure can solve every problem. If you can't have starvation then lock-free isn't enough. In which case, this article isn't for you.
- ajamesm 10y ago
  You realize you cherry-picked a snippet of my post, and then made the exact point I just made, which is: There aren't deadlocks, but there is still waiting and potential starvation, all of which can be informally called "locks" and so we need to be careful about qualifying "locking". This isn't a criticism of lock-free methodology, but a consideration of the ways in which "lock-free" could be interpreted.
  - chrisseaton 10y ago
    > all of which can be informally called "locks" > the ways in which "lock-free" could be interpreted This is only a problem if you use a definition of the 'lock' in 'lock-free' that isn't the same as everyone else's. I guess I must be misunderstanding what you're trying to say if that isn't it. I'll stop criticising.
dbaupp 10y ago
One thread possibly being starved is very different to all threads being starved, as can happen with blocking algorithms (the classic example being the thread holding a lock is descheduled: no-one needing it can make any progress). Atomic instructions like CAS do not inherently have this problem, and can be used in ways to avoid it (such as how the article describes it), but the same is not true of mutexes. I personally find it makes sense think of this is more of a transactional thing (one thread invalidates the transactions of others), rather than a mutex-esque critical section. In any case, the article (accidentally or otherwise) does actually use the correct technical term for code where some threads may be starved while others make progress (lock-free). If it was trying to discuss code that avoid this, it would be "Notes on Wait Free Programming", and would likely be significantly longer.