4 ms·
Re: fearless concurrency... Would Rust prevent you in general from writing code that could deadlock, btw? Thread1: takes lock A, ..., tries to take lock B Th
by megous 4y ago
Re: fearless concurrency... Would Rust prevent you in general from writing code that could deadlock, btw?
Thread1: takes lock A, ..., tries to take lock B
Thread2: takes lock B, ..., tries to take lock A
Looks like you should be able to pass Mutex<A> and Mutex<B> to both threads otherwise what's the point of mutex if there's no way to share data protected by it, so it doesn't look like it prevents you from hitting this scenario.
- bombela 4y agoRust doesn't protect you against deadlock. I wonder if it is similar to the halting problem. Can deadlocks even be prevented in theory?
- Waterluvian 4y agoOnly if the priority is flat and not some sort of graph, is my guess.
- mjn 4y agoIn the general case you're right, it's equivalent to the halting problem. The outline of the proof by reduction: set up two communicating processes in a way that will deadlock iff a particular loop in one process fails to terminate. So if you had a deadlock detector for arbitrary communicating processes, you could use turn it into a termination detector for arbitrary loops.
- jandrewrogers 4y agoYes, deadlock-free lock systems are an ordinary part of OLTP database engines. They don't prevent deadlocks per se so much as detect them and dynamically resolve them. The mechanism is costly but elegant. If a lock you are trying to acquire is owned by another thread, you inspect the locks you own to determine if that thread is waiting on one of your locks. When a deadlock is detected, there are several strategies to automatically resolve it e.g. rolling back one of the threads to a point where forward progress can be safely serialized. No one wants to use these mechanics for ordinary code, due to their cost. For the fashionable thread-per-core software architectures, deadlocks aren't something you commonly have to worry about.
- tialaramex 4y agoNo, Rust doesn't prevent deadlocks, a deadlock is safe (it isn't what you wanted, but it's safe). There are well-known strategies to avoid deadlock (in any language) In the trivial example you gave, one strategy just insists we take locks in alphabetical order. Thread 2 can't take lock A, because it already has lock B and that's not the correct order.
- tick_tock_tick 4y agoI'm pretty sure "fearless concurrency" is just a meme at this point since Rust does very little to make concurrency "fearless".
- jjnoakes 4y agoVery little except statically removing an entire class of bugs that plague other languages in the same design space you mean.
- renox 4y agoThere are two kinds of threading bugs: deadlocks which are easy to detect and race conditions which are far more difficult to detect and to fix. AFAIK Rust helps with the latter not with the former which is a very big improvement (much more than if it was the other way round)
- kaba0 4y agoJust to add, AFAIK Rust only prevents data races, not race conditions in general. Which is still a huge help, but concurrency is still hard without a much more restricted model.
- jandrewrogers 4y agoNo, deadlock-free code requires some additional structure. There is no general way that I know of to prevent deadlocks in any software with non-trivial lock graphs, but there are standard techniques to detect deadlocks programmatically so that they can be broken and resolved. OLTP databases figured out how to do this decades ago, but those techniques are expensive for general purpose programming. The common method for deadlock-free code is roughly that when a thread is required to wait on a lock owned by a second thread, it checks to see if the second thread is waiting on a lock already owned by the first thread. This requires that the lock graph essentially be a high-performance and concurrent global structure. Locks like this can be expensive, particularly under high concurrency or contention, so they aren't used for most software. If you can fit your software in a simpler model e.g. where locks are singular or only acquired as a DAG, then much higher performance options are available that don't require deadlock detection.