15 ms·

Does Rust do anything to prevent deadlocks?

JoshTriplett 11y ago
If you directly use low-level locking primitives, no. However, Rust provides many higher-level concurrency mechanisms that avoid the problem entirely. And typically, if you had some complex data structure with multiple levels of locks and ordering requirements on those locks to prevent deadlock, you'd want to encapsulate that data structure with methods that handle those locking requirements internally.
- acconsta 11y ago
  >Rust provides many higher-level concurrency mechanisms I'm looking at the standard library and I see only threads and channels. Is there anything higher level? Parallel map, reduce, etc., something like OpenMP?
rancur 11y ago
one of the design goals of rust is to design the language in such a way that they're simply not possible. I thought it was a new FOTM language but after reading a bit more about it I'm very excited for its future. That said, I wish they would have looked a little further outside Reddit's homepage rendering for parallelization inspiration. Reddit does not take a long time to render. However, CNN.com [which they looked at too] does, so...
- kibwen 11y ago
  Be careful with terminology here when you say that something is simply not possible. The parent is asking about deadlocks, which includes scenarios such as entering an infinite loop or having a channel block on a message that will never come, and neither of these are things that Rust can guarantee will never happen. As I say in my sibling comment, what Rust's typesystem guarantees is the absence of data races, which is still an amazing achievement (unprecedented AFAIK) but is only a subset of the general category of race conditions.
  - rancur 11y ago
    good points, thank you for the clarification
kibwen 11y ago
Eliminating deadlocks in general isn't possible in a Turing-complete language. What's cool about Rust is that it does statically eliminate a certain subset of race conditions known as data races. So while deadlocks are still possible in Rust, the typesystem is guaranteed to prevent concurrency errors that would result in corrupted data.
- cwzwarich 11y ago
  Eliminating deadlocks with a type system is just as possible as eliminating data races (albeit maybe a bit more awkward). The question of Turing completeness doesn't really come into it, because you are rejecting some dynamically correct programs with a static type system.
  - kibwen 11y ago
    To expand on my reply to pcwalton, I consider a deadlock to be anything that causes my program to become unresponsive from which it will never recover, which includes infinite looping (or its ilk, such as infinite (possibly mutual) recursion (and even if that blows the stack eventually in practice, I don't consider that a form of recovery :P )). Can you suggest better terminology for what I mean?
    - samth 11y ago
      This is what's usually called a "liveness" property: eventually the system will do some particular thing. These two in particular are often called "progress" in some contexts, but that's rarely formal. In general, any of these properties can be checked statically, just like czwarich said. You have to be conservative, but that's not any different than a type system, or Rust's borrow checker. There are certainly languages that enforce termination, and you can design systems that enforce higher-level progress properties (such as absence of deadlock). The major difference between a liveness property and the other kind (called a safety property: at no point does this bad thing happen) is that you can't check for liveness properties dynamically.
      - 11y ago
Manishearth 11y ago
https://github.com/Munksgaard/rust-sessions https://github.com/Munksgaard/rust-sessions actually goes quite far in doing this (without compiler support, just using the type system).

If you directly use low-level locking primitives, no. However, Rust provides many higher-level concurrency mechanisms that avoid the problem entirely. And typically, if you had some complex data structure with multiple levels of locks and ordering requirements on those locks to prevent deadlock, you'd want to encapsulate that data structure with methods that handle those locking requirements internally.

acconsta 11y ago
>Rust provides many higher-level concurrency mechanisms I'm looking at the standard library and I see only threads and channels. Is there anything higher level? Parallel map, reduce, etc., something like OpenMP?

rancur 11y ago

one of the design goals of rust is to design the language in such a way that they're simply not possible. I thought it was a new FOTM language but after reading a bit more about it I'm very excited for its future. That said, I wish they would have looked a little further outside Reddit's homepage rendering for parallelization inspiration. Reddit does not take a long time to render. However, CNN.com [which they looked at too] does, so...

kibwen 11y ago
Be careful with terminology here when you say that something is simply not possible. The parent is asking about deadlocks, which includes scenarios such as entering an infinite loop or having a channel block on a message that will never come, and neither of these are things that Rust can guarantee will never happen. As I say in my sibling comment, what Rust's typesystem guarantees is the absence of data races, which is still an amazing achievement (unprecedented AFAIK) but is only a subset of the general category of race conditions.
- rancur 11y ago
  good points, thank you for the clarification

kibwen 11y ago

Eliminating deadlocks in general isn't possible in a Turing-complete language. What's cool about Rust is that it does statically eliminate a certain subset of race conditions known as data races. So while deadlocks are still possible in Rust, the typesystem is guaranteed to prevent concurrency errors that would result in corrupted data.

cwzwarich 11y ago
Eliminating deadlocks with a type system is just as possible as eliminating data races (albeit maybe a bit more awkward). The question of Turing completeness doesn't really come into it, because you are rejecting some dynamically correct programs with a static type system.
- kibwen 11y ago
  To expand on my reply to pcwalton, I consider a deadlock to be anything that causes my program to become unresponsive from which it will never recover, which includes infinite looping (or its ilk, such as infinite (possibly mutual) recursion (and even if that blows the stack eventually in practice, I don't consider that a form of recovery :P )). Can you suggest better terminology for what I mean?
  - samth 11y ago
    This is what's usually called a "liveness" property: eventually the system will do some particular thing. These two in particular are often called "progress" in some contexts, but that's rarely formal. In general, any of these properties can be checked statically, just like czwarich said. You have to be conservative, but that's not any different than a type system, or Rust's borrow checker. There are certainly languages that enforce termination, and you can design systems that enforce higher-level progress properties (such as absence of deadlock). The major difference between a liveness property and the other kind (called a safety property: at no point does this bad thing happen) is that you can't check for liveness properties dynamically.
    - 11y ago

Manishearth 11y ago

https://github.com/Munksgaard/rust-sessions https://github.com/Munksgaard/rust-sessions actually goes quite far in doing this (without compiler support, just using the type system).