3 ms·

Dining philosophers is solved by always acquiring locks in the same order.

• deleted 4y ago
  [deleted]
• chrisseaton 4y ago
  ...if it's possible to do that for your application! It isn't always, if what lock you need next depends on the value of a previously locked value.
  • JoeAltmaier 4y ago
    Right, perhaps in a nested call or library, maybe even a semaphore you didn't know about! Multithreading with semaphores/locks is about as dirty as it can get.
  • syrrim 4y ago
    The top level comments strategy with queues seems similar, in that it isn't always possible. It requires the queues form a DAG, which is another word for partial ordering. Thus, requiring the locks form a partial ordering doesn't seem like a comparatively excessive restriction.
    • chrisseaton 4y ago
      > doesn't seem like a comparatively excessive restriction I think there are some applications and algorithms that we just don't know a way to create an ordering for realistically fine-grained locks. For example airline seat reservation. Someone clicking on seats to reserve them. You can't apply locks in a total order because... you can't read the person's mind on what seat they're going to click next. Or Lee's algorithm. (I wrote the first half a PhD on this.) https://chrisseaton.com/research-symposium-2012/seaton-irregular-parallelism-poster.pdf https://chrisseaton.com/research-symposium-2012/seaton-irreg...
    • anonymoushn 4y ago
      You don't need a DAG. It's fine to have a complete graph!