5 ms·

Allow me to ask a dumb question: At the end of the day, how can something that is safely concurrent also be lock-free? At the lowest level, what is the primit

Allow me to ask a dumb question: At the end of the day, how can something that is safely concurrent also be lock-free? At the lowest level, what is the primitive that enforces the safety, if it's not a lock or mutex? My brain starts to run in cricles when I think of this scenario: two threads trying to write to one piece of data. To do so safely, they need to take turns. Therefore, one has to wait for the other to complete. Therefore, one must acquire a mutually exclusive... hold on, that's a mutex! Can someone please clear this up for me?

jaccarmac 8y ago
I've read one of these articles and bookmarked the other. They give some introduction to the problem space, with pictures. I'm no expert though and can't rate their accuracy; Just know they helped me feel a little more confident about the basics. https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p... http://lucteo.ro/2018/11/18/look-ma-no-locks/ http://lucteo.ro/2018/11/18/look-ma-no-locks/
coder543 8y ago
One word: atomics. A simple example would be concurrently writing into a shared queue. To make it really simple, let's assume that this queue's buffer can only be written once, and then the program has to exit. If we have a buffer in this queue that can hold 20 messages, and an atomic integer that represents the current index, then we could have two (or however many) threads writing into it at the same time by just doing "index = myAtomic.fetch_add(1)", which will atomically add one to the index, then return the previous value. Atomics are supported at a hardware level, so they're generally pretty efficient, and there definitely is no lock like a Mutex involved here. In the end, both threads are able to write into shared memory without conflicting with each other. Using one or two more atomic integers, we could support having one or more readers reading off of the queue at the same time that we're writing to it, and we could get to the point where we're able to start reusing the buffer in a circular fashion.
- pmalynin 8y ago
  While what you said is all true, its not turtles all the way down. Eventually when it comes down to the hardware level the processor will have to assert #LOCK (or whatever mechanism it uses). So arguably even atomics aren't "lock" free, somewhere along the line some piece of hardware will have to block all other hardware to do its thing. DRAM can only read one thing at a time (and has to write it back afterwards).
  - gpderetta 8y ago
    The hardware guarantees forward progress at the very least and possibly some amount t of fairness. So the underlying hardware is at least lock free and possibly wait free. Usually a CPU cannot hold a cache line indefinitely, another CPU can always sneak in and steal it.
  - deepsun 8y ago
    Yes, you're right. It's turtles until RAM locking mechanisms. RAM does the locking inside it, and expose it as "compare-and-set" and "compare-and-swap" etc primitives. Various computing languages that use those primitives usually call that "atomic data structures". The thing is that RAM is way faster in that regard than locking on user/kernel level, so for program it looks like there's no locks. But atomics indeed do slow down your program, if just a little, because "compare-and-set" is still slower than just "set".
    - Gladdyu 8y ago
      The RAM does not know anything about locking, it's the cache coherence protocol. The CPU will request a cache line in exclusive state, it does the operation on the memory and ensures that during it has always been exclusive to that core. After all the other cores will observe the change (and depending on the memory model+ordering, the operations that have/will happen before and after).
- tobbebex 8y ago
  It’s when you want to synchronize multiple atomics it gets complicated. With a mutex you can lock for an entire ”transaction” where you fetch a unique index and write your value to the queue. With just atomics you can get a unique index into the queue concurrently with other threads, sure, but how do you mark it as ready to be unqueued once you are done writing your data? Thats where lock free data structures come into play. They have solved this intricate synchronization between multiple atomics so you don’t have to.
nine_k 8y ago
You can't completely remove locks. You can make them very small and hold them for a very short tine using hardware support. Atomic increments, atomic compare-and-exchange are supported by modern CPUs. On that base, you can build lock-free data structures.
wahern 8y ago
For a general overview of what lock-free and wait-free algorithms mean, see https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm. Much of the foundational theoretical work in this area was done by Maurice Herlihy in the 1980s and 1990s. For example, https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf I briefly paid for an ACM membership just so I could read his original work. (Well, I paid so I could read the literature in transactional memory, but I mostly ended up reading papers authored by Herlihy, co-authored by Herlihy, or analyzing Herlihy's work.)
- gpderetta 8y ago
  "The Art of multiprocessor programming" by Herilhy and Shavit is also great.
kllrnohj 8y ago
What are you calling the "lowest level"? Because at the CPU level there is no arbitrary scope mutex. That's not a thing that exists at the lowest levels. The mutex/lock that exists in basically every language is actually built on top of atomics, that's your "building block" so to speak. There is an x86 instruction prefix named 'lock', but it only applies to a single instruction and is considered in the family of being atomic rather than a mutex.
elteto 8y ago
FYI lock-free programming does not mean "free of locks" but rather "free of lockups", as in, there isn't any possible arrangement in which two threads could end up blocking each other indefinitely (as could happen with mutexes and deadlocks). From [0]: "An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress)." [0] https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm
- atombender 8y ago
  As I understand it, it does actually mean "free of locks", since a lock-free algorithm, by definition, cannot be implemented in terms of classical locks (typically mutexes) [1] [2]. It's "free of lockups" by virtue of, well, being free of locks. Note that there's also the distinction between lock-free algorithms and lock-free data structures. Crossbeam is the latter, I believe (but I could be wrong). [1] https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf [2] https://erdani.com/publications/cuj-2004-10.pdf https://erdani.com/publications/cuj-2004-10.pdf
  - physguy1123 8y ago
    If you are in an environment where you can guarantee that a piece of code runs in bounded time (no interrupts, no faults, etc), then locks can actually be used in lock-free algorithms since code inside the lock will always be making forward progress and will exit in or before some deterministic time. If the lock is fair and there's a bounded number of threads accessing the lock, then it technically becomes wait-free under these conditions since time to completion is bounded by n_threads * task_time; This environment only happens to exist in very specific and uncommon settings, so it's not a generally useful concept for lock-free programming. It's common in the linux kernel to see spinlocks taken in sections which have disabled all interrupts, for example, but this is not an environment that normal programs can live in.
- dagenix 8y ago
  I don't think that is quite correct. By that definition, any alhorithm that is free of deadlocks would be a lock free algorithm. But, I'm fairly sure that isn't the case - otherwise a hashmap protected by a single mutex would be considered a lock free data structure since as there is only a single mutex, deadlock would be impossible. I think the key paragraph from the Wikipedia article is: "In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)"
ncmncm 8y ago
There are some pretty good answers to this question posted, but the simple one is that there is, really, no such thing as a lock-free anything. When people say "lock-free", they mean they rely on basic hardware primitives that end up doing pretty much what you would do with locks in your code, but you can't see it. Generally, the hardware can do it faster, but rarely as much faster as people think, or want. In particular, you will still have stalls -- 30 cycles, 100 cycles, sometimes longer, whenever anything clashes, "lock-free" or no. Everything you do to cut contention at your level will pay just as it would if you were using regular locking. If you can cut your contention enough, lock-free ends up little faster (although it can still reduce latency spikes). If the lock-free stuff is buried in a library well-maintained by somebody else who is terrifyingly competent, then use it. But it is very, very unlikely that maintaining your own will be worthwhile; the most likely outcome is extremely subtle bugs. And who cares how fast buggy code is? There are much easier ways to make wrong code fast.
- gpderetta 8y ago
  The take away is that lock free != Fast. Some lock free algorithms and data structures happen to be fast, but in general maintaining the lock-, and especially wait-, free guarantees is not cheap.

jaccarmac 8y ago

I've read one of these articles and bookmarked the other. They give some introduction to the problem space, with pictures. I'm no expert though and can't rate their accuracy; Just know they helped me feel a little more confident about the basics. https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p... http://lucteo.ro/2018/11/18/look-ma-no-locks/ http://lucteo.ro/2018/11/18/look-ma-no-locks/

coder543 8y ago

One word: atomics. A simple example would be concurrently writing into a shared queue. To make it really simple, let's assume that this queue's buffer can only be written once, and then the program has to exit. If we have a buffer in this queue that can hold 20 messages, and an atomic integer that represents the current index, then we could have two (or however many) threads writing into it at the same time by just doing "index = myAtomic.fetch_add(1)", which will atomically add one to the index, then return the previous value. Atomics are supported at a hardware level, so they're generally pretty efficient, and there definitely is no lock like a Mutex involved here. In the end, both threads are able to write into shared memory without conflicting with each other. Using one or two more atomic integers, we could support having one or more readers reading off of the queue at the same time that we're writing to it, and we could get to the point where we're able to start reusing the buffer in a circular fashion.

pmalynin 8y ago
While what you said is all true, its not turtles all the way down. Eventually when it comes down to the hardware level the processor will have to assert #LOCK (or whatever mechanism it uses). So arguably even atomics aren't "lock" free, somewhere along the line some piece of hardware will have to block all other hardware to do its thing. DRAM can only read one thing at a time (and has to write it back afterwards).
- gpderetta 8y ago
  The hardware guarantees forward progress at the very least and possibly some amount t of fairness. So the underlying hardware is at least lock free and possibly wait free. Usually a CPU cannot hold a cache line indefinitely, another CPU can always sneak in and steal it.
- deepsun 8y ago
  Yes, you're right. It's turtles until RAM locking mechanisms. RAM does the locking inside it, and expose it as "compare-and-set" and "compare-and-swap" etc primitives. Various computing languages that use those primitives usually call that "atomic data structures". The thing is that RAM is way faster in that regard than locking on user/kernel level, so for program it looks like there's no locks. But atomics indeed do slow down your program, if just a little, because "compare-and-set" is still slower than just "set".
  - Gladdyu 8y ago
    The RAM does not know anything about locking, it's the cache coherence protocol. The CPU will request a cache line in exclusive state, it does the operation on the memory and ensures that during it has always been exclusive to that core. After all the other cores will observe the change (and depending on the memory model+ordering, the operations that have/will happen before and after).
tobbebex 8y ago
It’s when you want to synchronize multiple atomics it gets complicated. With a mutex you can lock for an entire ”transaction” where you fetch a unique index and write your value to the queue. With just atomics you can get a unique index into the queue concurrently with other threads, sure, but how do you mark it as ready to be unqueued once you are done writing your data? Thats where lock free data structures come into play. They have solved this intricate synchronization between multiple atomics so you don’t have to.

nine_k 8y ago

You can't completely remove locks. You can make them very small and hold them for a very short tine using hardware support. Atomic increments, atomic compare-and-exchange are supported by modern CPUs. On that base, you can build lock-free data structures.

wahern 8y ago

For a general overview of what lock-free and wait-free algorithms mean, see https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm. Much of the foundational theoretical work in this area was done by Maurice Herlihy in the 1980s and 1990s. For example, https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf I briefly paid for an ACM membership just so I could read his original work. (Well, I paid so I could read the literature in transactional memory, but I mostly ended up reading papers authored by Herlihy, co-authored by Herlihy, or analyzing Herlihy's work.)

gpderetta 8y ago
"The Art of multiprocessor programming" by Herilhy and Shavit is also great.

kllrnohj 8y ago

What are you calling the "lowest level"? Because at the CPU level there is no arbitrary scope mutex. That's not a thing that exists at the lowest levels. The mutex/lock that exists in basically every language is actually built on top of atomics, that's your "building block" so to speak. There is an x86 instruction prefix named 'lock', but it only applies to a single instruction and is considered in the family of being atomic rather than a mutex.

elteto 8y ago

FYI lock-free programming does not mean "free of locks" but rather "free of lockups", as in, there isn't any possible arrangement in which two threads could end up blocking each other indefinitely (as could happen with mutexes and deadlocks). From [0]: "An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress)." [0] https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm

atombender 8y ago
As I understand it, it does actually mean "free of locks", since a lock-free algorithm, by definition, cannot be implemented in terms of classical locks (typically mutexes) [1] [2]. It's "free of lockups" by virtue of, well, being free of locks. Note that there's also the distinction between lock-free algorithms and lock-free data structures. Crossbeam is the latter, I believe (but I could be wrong). [1] https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf [2] https://erdani.com/publications/cuj-2004-10.pdf https://erdani.com/publications/cuj-2004-10.pdf
- physguy1123 8y ago
  If you are in an environment where you can guarantee that a piece of code runs in bounded time (no interrupts, no faults, etc), then locks can actually be used in lock-free algorithms since code inside the lock will always be making forward progress and will exit in or before some deterministic time. If the lock is fair and there's a bounded number of threads accessing the lock, then it technically becomes wait-free under these conditions since time to completion is bounded by n_threads * task_time; This environment only happens to exist in very specific and uncommon settings, so it's not a generally useful concept for lock-free programming. It's common in the linux kernel to see spinlocks taken in sections which have disabled all interrupts, for example, but this is not an environment that normal programs can live in.
dagenix 8y ago
I don't think that is quite correct. By that definition, any alhorithm that is free of deadlocks would be a lock free algorithm. But, I'm fairly sure that isn't the case - otherwise a hashmap protected by a single mutex would be considered a lock free data structure since as there is only a single mutex, deadlock would be impossible. I think the key paragraph from the Wikipedia article is: "In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)"

ncmncm 8y ago

There are some pretty good answers to this question posted, but the simple one is that there is, really, no such thing as a lock-free anything. When people say "lock-free", they mean they rely on basic hardware primitives that end up doing pretty much what you would do with locks in your code, but you can't see it. Generally, the hardware can do it faster, but rarely as much faster as people think, or want. In particular, you will still have stalls -- 30 cycles, 100 cycles, sometimes longer, whenever anything clashes, "lock-free" or no. Everything you do to cut contention at your level will pay just as it would if you were using regular locking. If you can cut your contention enough, lock-free ends up little faster (although it can still reduce latency spikes). If the lock-free stuff is buried in a library well-maintained by somebody else who is terrifyingly competent, then use it. But it is very, very unlikely that maintaining your own will be worthwhile; the most likely outcome is extremely subtle bugs. And who cares how fast buggy code is? There are much easier ways to make wrong code fast.

gpderetta 8y ago
The take away is that lock free != Fast. Some lock free algorithms and data structures happen to be fast, but in general maintaining the lock-, and especially wait-, free guarantees is not cheap.