My main takeaway from this excellent guide is that I suck at multithreaded reasoning and should stick to single threaded languages.
There go my dreams of being a C-slinging kernel ninja master.
There go my dreams of being a C-slinging kernel ninja master.
A lock should be used to lock a data structure, that's it. Corollary: Never hold a lock while calling a function.
Most common deadlocking scenario is people taking a lock, calling a function, that they don't know takes a different lock. If you can't get by just taking a lock, touching some data structure (lightly), and releasing the lock then you need to look at your data structures.
Code that looks like what you describe, "implementing something that requires calling a function", tends to deadlock or be wrong. A really smart guy I worked with wrote some database driver that looked like that, it worked, except when it deadlocked, and finding that deadlock was a nightmare. I'm sure there are exceptions but this rule will get you out of a lot of trouble. If you need to violate the rule try find a different synchronization/concurrency mechanism or a different data structure.
Even if the code is initially correct, inevitably someone will refactor it without realizing a lock is taken and break it.
yeah but what if "you insert an item" is literally hundreds of lines, and there are 3 layers of api functions below you? What if you need to to take other locks for example to apply backpressure / flush out data on the layers below?
> Code that looks like what you describe, "implementing something that requires calling a function", tends to deadlock or be wrong
It happens. What you do is you work hard until it's fixed.
I've digged into the filesystem layer of Linux for a while. Going through all the locking rules and making sure your fs is in line with them, that's not a lot of fun. Maybe you should tell the Linux filesystem people how to do it instead?
https://docs.kernel.org/filesystems/locking.html
> Even if the code is initially correct, inevitably someone will refactor it without realizing a lock is taken and break it.
Yup, and if there's a practical means to improve the situation with static type systems that is a net benefit, I'm all for it.
Well- that's what software engineering is about. If insert an item to a shared data structure is hundreds of lines of code I'd say there's something very wrong. You shouldn't need to take another lock to create backpressure, e.g. look at Go's concurrency model.
I think it's a bad pattern as a rule. There are always situations where you break rules. My tip was for most of the situations where you don't do that and most of the people that shouldn't do that. If you know what you're doing, you understand concurrency very well and synchronization very well, then you probably don't need this tip. You can be a very smart and experienced developer and easily create stuff with rare deadlocks that's almost impossible to debug if you're not careful. I've fixed these sorts of issues in multiple code bases.
I've never worked on the Linux filesystem so I'm not going to tell them what to do. We'll have to assume the people working on that know what they're doing, otherwise it'd be a bit scary. Given that we don't see the Linux filesystem deadlocking - probably ok.
EDIT: I've given this rule to many junior/intermediate engineers and I've used it myself so I would say it is applicable to almost any situations where you need to use locking. It results in code is thread safe and simply can't deadlock. This other deadlocking code base I worked on would have been much cleaner if this rule was applied, and it could have been applied, and then it wouldn't deadlock once a year at one random customer site and take their system down. Again, like anything software, sometimes you do things differently in different situations, but maybe the generalization of the rule is you don't just sprinkle locks willy-nilly all over the place, you need to somehow rationalize/codify how the locks and structures work together in a way that guarantees no corner cases will lead to issues. And sure at the "expert" level there are many more patterns for certain situations.
The big win in Rust is that the mutexes are tied to the data they protect. The compiler won't let you access data until it's locked. You can still deadlock, though.
You can get this kind of behavior in C++ with, e.g., folly::Synchronized<T>.
And this is coming from someone that has written a lot of C++ and no Rust at all..
But a simple templated type like GP proposed does indeed fix the issue discussed here. To access the thing in the first place you need to lock the correct mutex. Looking at Folly::Synchronized, locking doesn't even return the protected item itself directly. In most cases -- unless the bare pointer is needed -- you will access the item through the returned "locked view" object which does the unlocking in its destructor.
In a small problem the textual advice is enough, I've written gnarly C with locks that "belong" to an object and so you need to make sure you take the right lock before calling certain functions which touch the object. The textual advice (locks are associated with objects) was good enough for that code to be correct -- which is good because C has no idea how to reflect this nicely in the language itself nor does it have adequate type safety enforcement.
But in a large problem enforcement makes all the difference. I had maybe two kinds of lock, a total of a dozen functions which need locking, it was all in my head as the sole programmer on that part of the system. But if we'd scaled up to a handful of people working on that code, ten kinds of lock, a hundred functions needing locking I'd be astonished if it didn't begin to have hard to debug issues or run into scaling challenges as everybody tries to "keep it simple" when that's no longer enough.
folly::Synchronized<int> lockedObj;
auto lockHandle = lockedObj.wlock();
auto& myReference = *lockHandle;
lockHandle.unlock();
myReference = 5; // bad
The lowest level is understanding things on the hardware memory model level--knowing how atomic operations work, and being able to build primitives based on these atomics. And quite frankly, there be real dragons here (weak memory models are mind-bending), but--like assembly programming--it's not really necessary to resort to this level unless you really need to care about the performance, and the first rule of performance engineering applies [1].
The second level is the level of the standard multithreaded primitives: mutexes, condition variables, semaphores, barriers, etc. This level is important to learn because it's generally the level of principles of how things work that matters most. But it's kind of like a BASIC programming language: it's certainly possible to write in it, but at scale, you get fatigue trying to keep all of the details straight, and it's rapidly apparent that there are lots of common patterns that could be handled more simply.
The highest level of understanding is recognizing that there are a few basic common patterns of multithreading, and if you can just resort to appropriate libraries for those patterns, you generally don't have to worry about the details at all. Chief among these is embarrassingly-parallel code, stuff that generally works with a fork-join model, or generally any sort of pattern that's "for each element in a large set", where the work to be done involves no shared mutable state.
Speaking of which, the most important thing to take away from any multithreaded programming is this: shared mutable state is inherently problematic. If you can avoid having any shared mutable state, that is ideal. The next-best option is to move all of the shared mutable state into a library that someone more competent than you has written (e.g., a database).
[1] Don't optimize until you've measured to be sure you know what you need to optimize.
Unless you know what you're doing, just pick the real low-hanging fruit, like throwing some threads at file block decompression.
About sixty years ago structured control flow was rare or non-existent in most languages. Want to do X fifteen times? Well, try setting a counter N to zero, do X, increment the counter N, and if N is less than fifteen jump back to the start of your "do-X" routine. Simple.
Oh wait, sorry, somebody else who wanted to do X is also jumping to the start of that routine, and they didn't set N so now everything is on fire.
Today your programming language has structured control flow. You write a loop, the loop does X fifteen times, it's not possible for some unrelated code to just wander into part of your loop unsuspecting and cause mayhem since it wasn't prepared to count up to fifteen. New keywords appeared like "for" and "while" and "return". It's not that somehow a new tool magically fixed the problem, but instead programmers learned to write software in a more structured way using the better tools.
Structured concurrency is the same idea again, but for concurrency.
It took some time between Dijkstra writing a letter and languages delivering the nice for-each loop we're familiar with today in many languages, and so likewise what we have today as the state of the art for structured concurrency is likely nowhere close to what will be developed over coming decades, but it's already nicer to work with that the chaos of unstructured concurrent programming.