Section: 6.9.2 [intro.multithread], 33.5.5 [atomics.lockfree], 99 [atomics.types.operations.req] Status: Resolved Submitter: Torvald Riegel Opened: 2011-08-18 Last modified: 2016-01-28 10:19:27 UTC
Priority: Not Prioritized
View all other issues in [intro.multithread].
View all issues with Resolved status.
According to 6.9.2 [intro.multithread] p2:
"Implementations should ensure that all unblocked threads eventually make progress."
Which assumptions can an implementation make about the thread scheduling? This is relevant for how implementations implement compare-exchange with load-linked / store conditional (LL-SC), and atomic read-modifiy-write operations with load...compare-exchange-weak loops.
33.5.5 [atomics.lockfree] p2 declares the lock-free property for a particular object. However, "lock-free" is never defined, and in discussions that I had with committee members it seemed as if the standard's lock-free would be different from what lock-free means in other communities (eg, research, text books on concurrent programming, etc.).
Following 99 [atomics.types.operations.req] p7 is_lock_free() returns "true if the object is lock-free". What is returned if the object is only sometimes lock-free?
Basically, I would like to see clarifications for the progress guarantees so that users know what they can expect from implementations (and what they cannot expect!), and to give implementors a clearer understanding of which user expectations they have to implement.
Elaborate on the intentions of the progress guarantee in 6.9.2 [intro.multithread] p2. As I don't know about your intentions, it's hard to suggest a resolution.
Define the lock-free property. The definition should probably include the following points:
[2011-12-01: Hans comments]
6.9.2 [intro.multithread] p2 was an intentional compromise, and it was understood at the time that it was not a precise statement. The wording was introduced by N3209, which discusses some of the issues. There were additional reflector discussions.This is somewhat separable from the question of what lock-free means, which is probably a more promising question to focus on.
General direction: lock-free means obstruction-free. Leave the current "should" recommendation for progress. It would take a lot of effort to try to do better.
[2012, Portland: move to Open]
The current wording of 6.9.2 [intro.multithread] p2 doesn't really say very much. As far as we can tell the term lock-free is nowhere defined in the standard.
James: we would prefer a different way to phrase it.
Hans: the research literature includes the term abstraction-free which might be a better fit.
Detlef: does Posix define a meaning for blocking (or locking) that we could use?
Hans: things like compare-exchange-strong can wait indefinitely.
Niklas: what about spin-locks -- still making no progress.
Hans: suspect we can only give guidance, at best. The lock-free meaning from the theoretical commmunity (forard progress will be made) is probably too strong here.
Atrur: what about livelocks?
Hans: each atomic modification completes, even if the whole thing is blocked.
Moved to open.
[2013-11-06: Jason Hearne-McGuiness comments]
Related to this issue, the wording in 33.5.5 [atomics.lockfree] p2,
In any given program execution, the result of the lock-free query shall be consistent for all pointers of the same type.
should be made clearer, because the object-specific (non-static) nature of the is_lock_free() functions from 33.5.8 [atomics.types.generic] and 126.96.36.199 [atomics.types.operations] imply that for different instances of pointers of the same type the returned value could be different.
[2014-02-16 Issaquah: Resolved by paper n3927]