7 ms·
Notes on Lock Free Programming
- chinhodado 10y agoI don't quite understand it. When you replace lock with CAS (Compare and Swap), aren't you just replacing one synchronization primitive with another? Is lock not implemented in CPU as a primitive instruction and therefore less performant? What overhead does locking have compared to CAS?
- pzh 10y agoA spin-lock would be more like a CAS loop (and the CAS IS a primitive CPU instruction), where you retry until the CAS succeeds. The point of lock-free algos, though, is that you could usually do something different from just retrying. There is this concept/general approach in lock-free where if a CAS fails at a certain place, you could invoke helpers that would help some other part of the algorithm make progress. E.g. you may be inserting an element in some structure and your CAS fails at some level (usually because another thread is doing a delete). In that case, you would help the delete operation proceed by invoking some idempotent 'post_delete_cleanup' operation on the same node. The idea of lock-free isn't that one particular thread won't block, but rather that the whole system would be making progress (i.e. no deadlock). It doesn't necessarily mean there will be no locks either.
- devbug 10y agoBesides other benefits mentioned, a spinlock is a user-space construct; you don't incur the overhead switching to kernel mode at the loss of the benefits and guarantees those primitives provide. (I'm simplifying some.)
- netule 10y agoOn Win32, this has been abstracted into the critical section API, which lives entirely in user-space and is a lightweight mutex. Many of the functionality implemented in the article are already part of the API (spin-aquire, etc.). Though from what I've read, on Linux, pthreads implements its mutexes in user-space (futex) as well and are fairly cheap to use.
- gpderetta 10y agoYes, the difference is that spin locks never enter the kernel, while a good mutex only does on contention. In practice most mutexes use an hibrid approach.
- siddcoder 10y agoI think spinlock is used when the critical section is relatively smaller where the threads are likely to perform small amount of work after acquiring locks. Thus locks are not expected to be held for longer duration. The other threads contending for the lock prefer to just spin and poll (and of course burn CPU) with the hope that lock will soon be relinquished by the owner thread. This way spinning threads avoid the overhead of context switching as well. Goes without saying, spinlocks are not useful on uniprocessor machines or single core machines.
- deleted 10y ago[deleted]
- deleted 10y ago[deleted]
- deleted 10y ago[deleted]
- scott_s 10y agoThis post doesn't get into the why very much, which is what you're asking about. Yes, locks will eventually be implemented with a primitive instruction. But it's not so much the cost of the mechanism but what those mechanisms allow you to do. Generally, when you protect a data structure with a lock, that means that the thread which has the lock has mutually exclusive access to it. Other threads which want access must wait. When you have many threads which want access, you will tend to have serialized that part of your program. That will tend to hurt performance, if you gain performance from parallelism. Lock-free approaches tend to allow multiple threads to access and modify a structure without having to get mutually exclusive access. Yes, if two threads are trying to touch the exact same part of the structure, they will interfere: one will succeed and move on, and the other will fail and have to retry. That's not much of a win over locks (generally). But, if it's common for the threads to touch different places of your structure, then they can do so without interfering with each other. That tends to allow better performance through parallelism. I'm using a lot of weasel words ("tends to", "generally") because there are tradeoffs. If you have a shared structure which is accessed by multiple threads very rarely, then it may actually be better to use locks. Lock-free data structures tend to be more complicated (and hence, take a bit longer in the unconteded case) than simply protecting a data structure with a lock. So if you're almost always going to have uncontended access, it may actually yield better performance to use a lock. But, locks can also be problematic when they're held too long or indefinitely. What if a thread dies while holding a lock? Or does I/O? Or is rescheduled? Other threads which want the lock must wait. Lock-free approaches tend to be free of such issues.
- pzh 10y agoI see what you're saying, but it seems to me that your description can be misunderstood to mean that lock-free programming is simply more fine-grained locking, which it is very far from. You can use mutexes to do fine-grained locking and still get into a dead-lock. Your algorithm can use only CASs and still not be deadlock-free. The general idea of lock free is to holistically design a data structure that guarantees that when you I invoke its operations in any concurrent scenario, the overall system will make progress and won't get stuck.
- 10y ago
- siddcoder 10y agoThe point is that overhead of locking is too much when the contention on the shared structure is fairly less. The cost of locking/unlocking/blocking/waiting or any other work done as part of enforcing synchronization is something that can be optimized away if the contention on the data structure is less. By contention, I imply -- contention or conflicts on the same portions/pieces of structure. If the data structure is subject to high concurrent access but in fairly disjoint regions of the data structure, we should try to implement fine grained locking scheme to increase the degree of parallelism and thus the scalability of data structure. This is where CAS comes into picture. The article doesn't compare CAS to another locking primitive. Instead, CAS is just used as a mechanism to implement fine grained locking scheme where the methods operating on the data structure don't take global or coarse locks. If the contention on the entire data structure is unreasonably high for some reason, then CAS based approaches or any flavors of it don't buy us much.
- bogomipz 10y agoI've also had some trouble reading(and probably really understanding) the term "lock free algorithms", since things like CAS are always mentioned and a CAS instruction locks the memory bus like any memory access. Isn't it more like "mutex minimization" since you are trying to limit the critical section to a single a single atomic instruction(as opposed to more than one)?
- gpderetta 10y ago>CAS instruction locks the memory bus like any memory access. FYI, this hasn't been the case in at least 20 years, on any of the major architectures. Cache coherency guarantees a single writer for any cache line aligned chunk of memory without any sort of bus lock.
- bogomipz 10y agoSure, but even with MESI a CAS translates into an exclusive lock on the cache line by a single core no? I probably could have articulated my original question better, sorry.
- gpderetta 10y agoI guess you could call holding a cacheline in the exclusive state the same as holding a lock. The difference, I think, is that there's an hard upper bound on response time on serving any remote request for sharing.
- maykr 10y agoThis post directly compliments the original one http://concurrencyfreaks.blogspot.com/2017/02/bitnext-lock-free-queue.html http://concurrencyfreaks.blogspot.com/2017/02/bitnext-lock-f...
- deleted 10y ago[deleted]
- ajamesm 10y agoI don't like usage of the term "lock free" to mean "locks that are less costly". There's a difference between (A) locking (waiting, really) on access to a critical section (where you spinlock, yield your thread, etc.) and (B) locking the processor to safely execute a synchronization primitive (mutexes/semaphores). 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). An example of operation using coarse locks would be a method in Java with “synchronized” keyword. If a thread T is executing a synchronized method on a particular object, no other concurrent thread can invoke any other synchronized method on the same object. That's just putting one giant mutex around all access to the object. Having finer granularity != "lockless".
- codemac 10y agoNon-Blocking works a bit better as a phrase, in my opinion.
- ajamesm 10y agoOh god, "non-blocking" is even worse, no thanks to Javascripters. Lock-free data structures can wait, and can block if they deal with failed operations by spinlocking. The muddled concepts are: waiting - what you do until you eventual acquire a contested resource (spinlock) mutexes - objects used to enforce critical sections stopping the world - a processor stopping the execution of all threads in order to ensure proper order of thread-critical instructions (is there a formal name for this?) CAS - an atomic primitive often used to avoid the overhead of stopping the world to enter critical sections, or to avoid deadlock by implementing algorithms that do not have critical sections critical section - a routine that must be executed by only one thread at a time blocking - being unable to proceed with a given routine on account of another thread non-blocking / async - threading in general, or, instead of spinlocking, yielding execution to another thread deadlocking - a systematic failure wherein there is a cyclical dependency of threads on resources, and no thread can progress All of these can be informally referred to by "locking", and lock-free (formal definition) algorithms avoid deadlocking by avoiding having critical sections or locks on resources at all. They're generally more performant, but that's coincidental. If you have a critical section, and you implement a mutex using CAS, you've probably sped up your application because you no longer have to pause other threads. That's "lock free" in the sense that "stopping the world" is "locking" other threads, but not "lock free" in the sense of avoiding deadlock. If a thread enters a critical section with a CAS mutex and then waits forever, you can get deadlock.
- deleted 10y ago[deleted]
- raphlinus 10y agoNote that the linked paper predates the C++ / C11 memory model, which I would consider essential for anyone implementing lock-free algorithms in C or C++ today. It also long predates an understanding of the ABA problem[0]. [0] http://www.stroustrup.com/isorc2010.pdf http://www.stroustrup.com/isorc2010.pdf
- yongjik 10y agoEh? ABA problem was known since a long time ago. Google scholar[1] shows a paper titled "Correction of a Memory Management Method for Lock-Free Data Structures" in 1995, which in turn cites "ABA problem" mentioned in "System/370 Principles of Operation. IBM Corporation, 1983" (!!). [1] https://scholar.google.com/scholar?q=aba+problem https://scholar.google.com/scholar?q=aba+problem
- raphlinus 10y agoI stand corrected, thanks! I had the feeling that the ABA problem affected a lot of the earlier lock-free algorithms, but didn't know the understanding of it went that far back.
- aardvark179 10y agoThe C/C++ memory model is also inspired by the Java memory model which dates back to the mid 90s and was updated back in 2004.
- raphlinus 10y agoAbsolutely. The Java ecosystem deserves a huge amount of credit for putting lock-free programming on a theoretically sound basis, and it's informative how long it took to get it right. But none of that had a serious effect on C and C++ practice until C++ started formalizing the memory model. Even today, we still have to deal with a lot of legacy code that uses pre-memory model primitives such as __sync_synchronize, __atomic_cmpxchg, InterlockedCompareExchange, etc. I'd like to see all that stuff go sooner rather than later. In my opinion, the original article is not helping, as it shows C code that does reads and writes through pointers, expecting them to behave as atomic operations.
- nhaehnle 10y agoPet peeve: The example linked list implementation suffers from not using double-pointers (or pointers-to-pointers). For example, when the "special case" of adding an element at the head or tail are discussed - those special cases disappear entirely when the search procedure simply returns a pointer to the next field of the preceding element (or a pointer to the root pointer of the linked list, if the new element should be inserted at the head).
- stcredzero 10y agoAre there any lock-free in-memory spatial databases?
- joshuak 10y agoPerhaps an example will help clarify the difference between mutex locking and CAS (lock-free) operations. Check out Sled[0]. Sled is an implementation of a 'ctrie'[1] data structure in go. Sled is a lock free key value store. Because it is lock-free any number of threads can read and write to it simultaneously while never interfering with eachother. The application remains parallel at all times. Locks cause parallel applications to become single threaded for the scope of the lock. This means that most of the time you should just put things that require locks into their own thread and then communicate with that thread from others. "Do not communicate by sharing memory; instead, share memory by communicating." - ancient go proverb However, that is still potentially a locking operation because channels must block until both threads are in sync (with some optional caching, to help reduce the effect). With truly lock free data structures, all threads can share data but do not need to synchronize access. This leads to much, much higher performance. [0]: https://github.com/Avalanche-io/sled https://github.com/Avalanche-io/sled [1]: https://github.com/Avalanche-io/sled/blob/master/ctries_paper.pdf https://github.com/Avalanche-io/sled/blob/master/ctries_pape...
- jankedeen 10y agoLast time I checked lock free meant no locks.