What's the difference between lock and lock-free data structures? And what's lock freedom?
Also, what are some good resources for getting started with building our own lock-free DS in rust? Thanks!
A "lock-free" algorithm is an algorithm that guarantees system-wide progress even if some thread gets suspendes/fails.
A lock is trivially non lock-free because if the thread holding the lock gets suspendes/fails no other thread can make any kind of progress.
I suggest Mara Bos's Rust Atomics and Locks book to start with.
so in "locking" algorithms if a thread fails or panics then no other threads can make progress? is this what we call a deadlock?
where as in "lock-free" algorithms if a thread gets preempted then other threads would be given a chance to progress? correct?
also, what's a live lock?
alright, thanks!
No, a failure will usually unlock or do something else. The problem is not making progress because another thread has the lock. Using a lock means that you may have to wait, doing nothing, to acquire the lock, and lock-free means never doing any of that kind of waiting.
Deadlock is when two (or more) threads each have a lock, and are trying to also acquire a lock on a resource locked by the other thread, so they are both waiting forever for the other to release the lock they need.
This sounds complicated, but it is very easy to create by accident if you use many Mutexes without a plan for how you are going to use them well (e.g. trying to simulate conventional OOP-like shared mutable state using Arc<Mutex<MyStruct>>).
A livelock (not "live lock") is a problem similar to deadlock, but instead of every involved thread waiting, every thread is performing actions that don’t add up to overall progress.
For a silly but simple example: suppose you have a counter whose current value is 500. Now suppose that thread A is trying to set the counter to 0 by repeatedly decrementing it, and thread B is trying to set the counter to 1000 by repeatedly incrementing it. This could take a very long time for either one to finish (if they do at all). Real livelocks are less directly opposed than this tug-of-war, but still contain some form of threads defeating each other’s attempts to make progress.
Using a lock-free algorithm for a purpose it is not suited for could result in livelock. Locks can avoid this problem by letting one thread win and finish its work on the shared resource without interruption (but livelock can still occur at higher levels of the system).
So in lock-free as none of the threads have to do the waiting then progress of all threads are guaranteed?
See the final paragraph:
Lock free algorithms will also tend to have higher constant factor costs: you are ultimately doing a lot more total work in order to gain the benefit of never stopping.
Look at non-Rust resources: 1024cores and the book Shared-memory synchronization by Michael Scott. Also it's good to just take a look at a few libraries (std, crossbeam, and tokio::sync) and see how they implement stuff. (Even though a mutex isn't lock free it is worth understanding the implementation. Most of the complexity in these libraries has to do with parking and unparking.)
No, but progress of the system as a whole is guaranteed.
The guarantee that each thread individually makes progress is called wait-free.