2075. Progress guarantees, lock-free property, and scheduling assumptions

Section: 6.8.2 [intro.multithread], 32.5 [atomics.lockfree], 99 [atomics.types.operations.req] Status: Resolved Submitter: Torvald Riegel Opened: 2011-08-18 Last modified: 2016-02-10

Priority: Not Prioritized

View all other issues in [intro.multithread].

View all issues with Resolved status.

Discussion:

According to 6.8.2 [intro.multithread] p2:

"Implementations should ensure that all unblocked threads eventually make progress."

32.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.

  1. Elaborate on the intentions of the progress guarantee in 6.8.2 [intro.multithread] p2. As I don't know about your intentions, it's hard to suggest a resolution.

  2. Define the lock-free property. The definition should probably include the following points:

  3. Add a note explaining that compare-exchange-weak is not necessarily lock-free (but is nonblocking)? Or is it indeed intended to be lock-free (only allowed to fail spuriously but guaranteed to not fail eventually)? Implementing the latter might be a challenge on LL-SC machines or lead to space overheads I suppose, see the cacheline sharing example above.

[2011-12-01: Hans comments]

6.8.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.

[2012, Kona]

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.8.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 32.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 32.6 [atomics.types.generic] and 32.6.1 [atomics.types.operations] imply that for different instances of pointers of the same type the returned value could be different.

Proposed resolution:

[2014-02-16 Issaquah: Resolved by paper n3927]