5 ms·

Sorry if I'm missing something obvious, but how do these locks stop a deadlock from happening? To explain, say that I have some code that locks A, then locks B

by jewel 12y ago

Sorry if I'm missing something obvious, but how do these locks stop a deadlock from happening? To explain, say that I have some code that locks A, then locks B, then does something, and another bit of code that locks B, then locks A, then does its thing. There's a race condition that can happen where one thread has A and the other thread has B. This has bitten me so much that I avoid fine-grained locking when possible and instead use a single global lock everywhere, and have new threads start in the locked position, and then only selectively unlock the bits of code that I can prove are thread-safe, or adding fine-grained locks only where absolutely necessary as shown by benchmarking.

steveklabnik 12y ago
> Sorry if I'm missing something obvious, but how do these locks stop a deadlock from happening? This is the difference between a data race and a race condition. We can't generally prevent deadlocks, I would imagine that's (like all race conditions) is an unsolvable problem at the language level. Maybe some PhD will prove me right or wrong, though...
- Jweb_Guru 12y ago
  Deadlocks can be statically prevented by ensuring that all code paths acquire locks in the same order. However, Rust's type system is not capable of enforcing that by itself (except maybe in some very limited cases). Some other substructural type systems (e.g. http://en.wikipedia.org/wiki/Substructural_type_system#Ordered_type_system http://en.wikipedia.org/wiki/Substructural_type_system#Order...) might be up to the task, but I'm far from an expert in this area.
  - steveklabnik 12y ago
    Ah thank you! This is super neat.
- rntz 12y ago
  Preventing deadlocks is not an unsolvable problem. Linear-session-typed process calculi are guaranteed deadlock-free and race-free. (The connection with Rust's ownership type-system makes me wonder if there might be some way to backport this guarantee to Rust, but I suspect the connection doesn't go far enough.) This comes at a price, however: certain process topologies are impossible to construct, and there's no way to ask "give me the first message to arrive on either of these two channels" (no Unix `select()` analogue). The latter in particular bugs me, because `select()` is a necessity in practice. In general, problems of "guarantee property X" can almost always be solved with a sufficiently advanced type system, but at the cost of (a) inventing and using a sufficiently advanced type system and (b) disallowing some perfectly good programs.
  - steveklabnik 12y ago
    Ah, thanks for that, I'll look into it. I guess what I was trying to get at is that 'race conditions' can fall under the same kinds of errors as logic errors. This is the way that people usually attack the phrase "if it compiles, it works."
    - rntz 12y ago
      I'm not sure what you mean when you say that race conditions can be the same kind of error as logic errors. I would define a race condition as "an error due to nondeterministic concurrency". If you ban nondeterminism, for example, race conditions are impossible. In practice, nobody wants to ban nondeterminism, so races creep in. There might be smarter ways to eliminate races (ways of only allowing benign nondeterminism), though. So I'm not sure that practical languages without race conditions are an unachievable goal, just a difficult one. Give it another 20 years and we'll see where we're at. :)
      - steveklabnik 12y ago
        I think I'm just being imprecise with my terms, since this is just a comment. I've seen people describe race conditions in practice as "most of the time, message A comes in, then B, but I didn't write it correctly, so in certain cases, B comes in, and then A." Which I would casually describe as racy, but as you point out, would be more accurately described as a pure logic error.
- codahale 12y ago
  That said, the ergonomics of the mutex design and the ownership system would probably eliminate most of the race conditions I've seen. Lock ordering can be effectively established by nesting mutexes: e.g. `Mutex<(X, Mutex<Y>)>` allows you to establish that any locking of Y has already locked X.
  - Jweb_Guru 12y ago
    Yeah, I've thought about this approach in the past. One problem is that it requires you to acquire the same locks in the same order. That is, if you had Mutex<(X, Mutex<(Y, Mutex<Z>)>)>, you couldn't acquire X, then Z, without first acquiring Y, but it would be perfectly safe to do so. (Although, come to think of it, you can probably work around that with some cleverness; e.g., you could provide the option to access either the data protected by the Mutex or the next Mutex in the sequence through &mut; whichever you chose, you couldn't access the other until you were through with the children. You still have to keep the mutexes structurally in a linked list, though, which is obviously not ideal for all situations. And you still need to deal with the fact that the reference to the first Mutex must be an &-reference, hence can be replicated indefinitely, which allows you to subvert the ordering guarantees; but this was already a problem, and I think there are some clever ways around this using rank-2 lifetimes).

by jewel 12y ago

steveklabnik 12y ago

> Sorry if I'm missing something obvious, but how do these locks stop a deadlock from happening? This is the difference between a data race and a race condition. We can't generally prevent deadlocks, I would imagine that's (like all race conditions) is an unsolvable problem at the language level. Maybe some PhD will prove me right or wrong, though...

Jweb_Guru 12y ago
Deadlocks can be statically prevented by ensuring that all code paths acquire locks in the same order. However, Rust's type system is not capable of enforcing that by itself (except maybe in some very limited cases). Some other substructural type systems (e.g. http://en.wikipedia.org/wiki/Substructural_type_system#Ordered_type_system http://en.wikipedia.org/wiki/Substructural_type_system#Order...) might be up to the task, but I'm far from an expert in this area.
- steveklabnik 12y ago
  Ah thank you! This is super neat.
rntz 12y ago
Preventing deadlocks is not an unsolvable problem. Linear-session-typed process calculi are guaranteed deadlock-free and race-free. (The connection with Rust's ownership type-system makes me wonder if there might be some way to backport this guarantee to Rust, but I suspect the connection doesn't go far enough.) This comes at a price, however: certain process topologies are impossible to construct, and there's no way to ask "give me the first message to arrive on either of these two channels" (no Unix `select()` analogue). The latter in particular bugs me, because `select()` is a necessity in practice. In general, problems of "guarantee property X" can almost always be solved with a sufficiently advanced type system, but at the cost of (a) inventing and using a sufficiently advanced type system and (b) disallowing some perfectly good programs.
- steveklabnik 12y ago
  Ah, thanks for that, I'll look into it. I guess what I was trying to get at is that 'race conditions' can fall under the same kinds of errors as logic errors. This is the way that people usually attack the phrase "if it compiles, it works."
  - rntz 12y ago
    I'm not sure what you mean when you say that race conditions can be the same kind of error as logic errors. I would define a race condition as "an error due to nondeterministic concurrency". If you ban nondeterminism, for example, race conditions are impossible. In practice, nobody wants to ban nondeterminism, so races creep in. There might be smarter ways to eliminate races (ways of only allowing benign nondeterminism), though. So I'm not sure that practical languages without race conditions are an unachievable goal, just a difficult one. Give it another 20 years and we'll see where we're at. :)
    - steveklabnik 12y ago
      I think I'm just being imprecise with my terms, since this is just a comment. I've seen people describe race conditions in practice as "most of the time, message A comes in, then B, but I didn't write it correctly, so in certain cases, B comes in, and then A." Which I would casually describe as racy, but as you point out, would be more accurately described as a pure logic error.
codahale 12y ago
That said, the ergonomics of the mutex design and the ownership system would probably eliminate most of the race conditions I've seen. Lock ordering can be effectively established by nesting mutexes: e.g. `Mutex<(X, Mutex<Y>)>` allows you to establish that any locking of Y has already locked X.
- Jweb_Guru 12y ago
  Yeah, I've thought about this approach in the past. One problem is that it requires you to acquire the same locks in the same order. That is, if you had Mutex<(X, Mutex<(Y, Mutex<Z>)>)>, you couldn't acquire X, then Z, without first acquiring Y, but it would be perfectly safe to do so. (Although, come to think of it, you can probably work around that with some cleverness; e.g., you could provide the option to access either the data protected by the Mutex or the next Mutex in the sequence through &mut; whichever you chose, you couldn't access the other until you were through with the children. You still have to keep the mutexes structurally in a linked list, though, which is obviously not ideal for all situations. And you still need to deal with the fact that the reference to the first Mutex must be an &-reference, hence can be replicated indefinitely, which allows you to subvert the ordering guarantees; but this was already a problem, and I think there are some clever ways around this using rank-2 lifetimes).