4 ms·

Does this avoid the dining philosopher deadlock?

by xmcqdpt2 11mo ago

gpderetta 11mo ago
yes, 'synchronize' uses a try_lock/backoff algorithm, same as std::scoped_lock. edit: it could theoretically livelock, but I believe most if not all STM implementations also do not guarantee forward progress.
- kragen 11mo ago
  Purely optimistic STM implementations that abort transactions early and don't permit other transactions to read uncommitted data can guarantee forward progress, and I believe that both Haskell's STM and Fraser and Harris's STM do, though I could easily be mistaken about that.
  - gpderetta 11mo ago
    Probably you are right. I vaguely remembered the "Why Transactional Memory Should Not Be Obstruction-Free" paper, but I might have misunderstood or forgotten what it meant (the implementation can be non obstruction-free, but it doesn't mean it can live-lock).
    - kragen 11mo ago
      You avoid livelock, as I understand the term in an STM, if the only thing that can prevent a transaction from committing when it tries to commit is some other transaction having committed. That way, forward progress is guaranteed; as long as some transaction commits, you're not livelocked, are you? I'm not familiar with "obstruction-free"ness; should I be?
    - kragen 11mo ago
      I'm reading the Kuznetsov and Ravi paper https://www.researchgate.net/publication/272194871_Why_Transactional_Memory_Should_Not_Be_Obstruction-Free https://www.researchgate.net/publication/272194871_Why_Trans... now; I assume that's the one you mean? Its definition of "obstruction-freedom" is that every transaction "not encountering steps of concurrent transactions" must commit. This seems to be neither necessary nor sufficient for avoiding livelock, but certainly very helpful. Their weaker "progressiveness" property seems almost as good. They claim that their STM "LP" is not obstruction-free but is wait-free, which is a very strong claim! WP explains, "A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. ‘Non-blocking’ was used as a synonym for ‘lock-free’ in the literature until the introduction of obstruction-freedom in 2003." Kuznetsov and Ravi say of LP, "every transactional operation completes in a wait-free manner." Its normative force seems to be founded on claims about performance, but it would be very surprising if the performance cost of guaranteed forward progress or obstruction-freedom were too high for me to want to pay it, since what I'm most interested in is latency and fault-tolerance, not parallel speedups.
      - gpderetta 11mo ago
        I need to re-read the paper, but: >"LP" is not obstruction-free but is wait-free As far as I know, wait-free is a superset of lock-free and lock-free is a superset of obstruction-free. How can LP be wait-free but not obstruction free? In any case a wait-free algorithm can't live-lock by definition (progress and fairness of all threads is guaranteed), but the catch is that while the STM runtime itself might have this property, it doesn't necessarily translate to an algorithm implemented in the runtime (which makes sense, you should be able to implement a lock with an STM). So, yes, the paper is interesting, but probably not relevant for this discussion and I shouldn't have brought it up. Now the question again remains, do concrete STM implementations actually provide the guarantee you mentioned earlier, i.e. does a transaction aborting guarantees that another succeeds? I would think it doesn't as I think it would be very costly to implement: both transactions might end up aborting when detecting conflict. Maybe what concrete runtimes actually guarantee is that there is an upper bound on the spurious aborts and restarts as worst case you can fall back on a single global lock for serialization when the upper bound is reached.
        gpderetta 11mo ago
        > As far as I know, wait-free is a superset of lock-free and lock-free is a superset of obstruction-free. How can LP be wait-free but not obstruction free? ough! I meant it the other way of course: wait-free is a subset of lock-free which is a subset of obstruction-free.
        kragen 11mo ago
        I'm still struggling with it.

Does this avoid the dining philosopher deadlock?

yes, 'synchronize' uses a try_lock/backoff algorithm, same as std::scoped_lock. edit: it could theoretically livelock, but I believe most if not all STM implementations also do not guarantee forward progress.

kragen 11mo ago
Purely optimistic STM implementations that abort transactions early and don't permit other transactions to read uncommitted data can guarantee forward progress, and I believe that both Haskell's STM and Fraser and Harris's STM do, though I could easily be mistaken about that.
- gpderetta 11mo ago
  Probably you are right. I vaguely remembered the "Why Transactional Memory Should Not Be Obstruction-Free" paper, but I might have misunderstood or forgotten what it meant (the implementation can be non obstruction-free, but it doesn't mean it can live-lock).
  - kragen 11mo ago
    You avoid livelock, as I understand the term in an STM, if the only thing that can prevent a transaction from committing when it tries to commit is some other transaction having committed. That way, forward progress is guaranteed; as long as some transaction commits, you're not livelocked, are you? I'm not familiar with "obstruction-free"ness; should I be?
  - kragen 11mo ago
    I'm reading the Kuznetsov and Ravi paper https://www.researchgate.net/publication/272194871_Why_Transactional_Memory_Should_Not_Be_Obstruction-Free https://www.researchgate.net/publication/272194871_Why_Trans... now; I assume that's the one you mean? Its definition of "obstruction-freedom" is that every transaction "not encountering steps of concurrent transactions" must commit. This seems to be neither necessary nor sufficient for avoiding livelock, but certainly very helpful. Their weaker "progressiveness" property seems almost as good. They claim that their STM "LP" is not obstruction-free but is wait-free, which is a very strong claim! WP explains, "A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. ‘Non-blocking’ was used as a synonym for ‘lock-free’ in the literature until the introduction of obstruction-freedom in 2003." Kuznetsov and Ravi say of LP, "every transactional operation completes in a wait-free manner." Its normative force seems to be founded on claims about performance, but it would be very surprising if the performance cost of guaranteed forward progress or obstruction-freedom were too high for me to want to pay it, since what I'm most interested in is latency and fault-tolerance, not parallel speedups.
    - gpderetta 11mo ago
      I need to re-read the paper, but: >"LP" is not obstruction-free but is wait-free As far as I know, wait-free is a superset of lock-free and lock-free is a superset of obstruction-free. How can LP be wait-free but not obstruction free? In any case a wait-free algorithm can't live-lock by definition (progress and fairness of all threads is guaranteed), but the catch is that while the STM runtime itself might have this property, it doesn't necessarily translate to an algorithm implemented in the runtime (which makes sense, you should be able to implement a lock with an STM). So, yes, the paper is interesting, but probably not relevant for this discussion and I shouldn't have brought it up. Now the question again remains, do concrete STM implementations actually provide the guarantee you mentioned earlier, i.e. does a transaction aborting guarantees that another succeeds? I would think it doesn't as I think it would be very costly to implement: both transactions might end up aborting when detecting conflict. Maybe what concrete runtimes actually guarantee is that there is an upper bound on the spurious aborts and restarts as worst case you can fall back on a single global lock for serialization when the upper bound is reached.
      - gpderetta 11mo ago
        > As far as I know, wait-free is a superset of lock-free and lock-free is a superset of obstruction-free. How can LP be wait-free but not obstruction free? ough! I meant it the other way of course: wait-free is a subset of lock-free which is a subset of obstruction-free.
        kragen 11mo ago
        I'm still struggling with it.