CODEWITHSUNDEEP
c++multithreadingc++11atomic
itaj
itaj

Reputation: 133

c++11 atomic ordering: extended total order memory_order_seq_cst for locks

from c++11 29.3-p3:

There shall be a single total order S on all memory_order_seq_cst operations, consistent with the "happens before" order and modification orders for all affected locations, such that each memory_order_seq_cst operation B that loads a value from an atomic object M observes either one of the following values:

-- the result of the last modification A of M that precedes B in S, if it exists, or

-- if A exists, the result of some modification of M in the visible sequence of side effects with respect to B that is not memory_order_seq_cst and that does not happen before A, or

-- if A does not exist, the result of some modification of M in the visible sequence of side effects with respect to B that is not memory_order_seq_cst.

[ Note: Although it is not explicitly required that S include locks, it can always be extended to an order that does include lock and unlock operations, since the ordering between those is already included in the "happens before" ordering. --end note ]

In the last note, what does it mean by "always"? I can understand that any certain implementation can be designed to support such an extended S. But in some general implementation that wasn't designed for it, I don't see that S can be extended with the described properties.

Does it mean an extended order that also satisfies the same visibility properties here?

I had sent this question to comp.std.c++ but got no answers there. http://groups.google.com/group/comp.std.c++/browse_frm/thread/5242fa70d0594d1b#

Upvotes: 5

Views: 674

Answers (1)

jpalecek
jpalecek

Reputation: 47762

What does it mean by "always"?

Always means that there exists a total order S+l on seq_cst ops U lock ops that is consistent with happens-before and S.

Why is that

Fact 1: S is a total order consistent with HB.

Fact 2: Lock operations are ordered in the HB partial order, because they are acquire/release operations.

Fact 3: There are no cycles in HB.

Lemma 1: There are no cycles in S' = S union HB.

Proof: If there were any cycles in S', they would be in the form Aop1 <S Aop2 <HB Aop1, because any two atomic operations are comparable in S and happens-before is transitive. That would contradict with Fact 1. QED

Conclusion: Because for each partial order (= without cycles) there exists its extension to total order (cf. topological sorting), there is a total order extending S'. So you just pick atomics and lock operations from it and get S+l.

But in some general implementation that wasn't designed for it, I don't see that S can be extended so.

Such an implementation would not satisfy mem_order_seq_cst requirements.

Upvotes: 3

Related Questions