Comment by gpderetta
3 months 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.
3 months 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.
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.
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).
I'm reading the Kuznetsov and Ravi paper 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.
3 replies →
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?