# Is Synchronization Order A *Strict* Total Order?

41 messages
123
Open this post in threaded view
|

## Is Synchronization Order A *Strict* Total Order?

 In the JMM documentation, synchronization order is defined as a total order; perhaps it's just semantics, but I've always been curious whether it is intentional that it isn't defined as a *strict* total order. Without getting into arcane mathematics, I guess what I'm asking is: Given a program that contains only synchronization actions, but they are independent, e.g. volatile int x, y Thread A       Thread B x = 1             y = 1 Is the following true? I. *Every* execution of the program has only one and exactly one valid (accurate?) history? [either A(x=1) B(y=1) or B(y=1) A(x=1) ]   II. or is it possible that it can be said that for some theoretical execution, both histories are equally valid? My inference has always been that the JMM prescribes I (which implies strict total order) and proscribes II. Of course, one might say, who cares? or how could you tell the difference? or the "results" of the program are the same . . .
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 The JMM is written to guarantee sequential consistency for data-race-free programs. As I understand it, sequential consistency (SC) requires that every execution *could* be the result of *some* sequential execution. But, in general, multiple possible sequential executions may exist.Do you have a different understanding of SC? Or are you questioning why SC was chosen for JMM?On Mon, May 30, 2016 at 7:40 AM, thurstonn wrote:In the JMM documentation, synchronization order is defined as a total order; perhaps it's just semantics, but I've always been curious whether it is intentional that it isn't defined as a *strict* total order. Without getting into arcane mathematics, I guess what I'm asking is: Given a program that contains only synchronization actions, but they are independent, e.g. volatile int x, y Thread A       Thread B x = 1             y = 1 Is the following true? I. *Every* execution of the program has only one and exactly one valid (accurate?) history? [either A(x=1) B(y=1) or B(y=1) A(x=1) ] II. or is it possible that it can be said that for some theoretical execution, both histories are equally valid? My inference has always been that the JMM prescribes I (which implies strict total order) and proscribes II. Of course, one might say, who cares? or how could you tell the difference? or the "results" of the program are the same . . . -- View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/Is-Synchronization-Order-A-Strict-Total-Order-tp13457.html Sent from the JSR166 Concurrency mailing list archive at Nabble.com. _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 In reply to this post by thurstonn Let me try another way: Imagine we have the previously mentioned program: volatile int x, y Thread A       Thread B x = 1             y = 1 And we have two "observers" Bob and Jill; both of them have the magical ability to observe all hardware state (registers, caches, memory, etc) during the execution of any program *without interfering in said execution* They record each execution of a program by writing down a history of what they observed. The above program is run a 1000 times; after each execution, Bob and Jill compare their two histories; they are always in agreement. For some executions, the history is: A(x=1) B(y=1) for others, it's: B(y=1) A(x=1) Again, Jill's and Bob's histories are always the same. Then the program is executed for the 1001 time. Again they compare histories: Bob: A(x=1) B(y=1) Jill: B(y=1) A(x=1) Bob:  "Hmm, our Java platform is broken; this violates the JMM guarantee of a total order among synchronization actions, i.e. it violates synchronization order" Jill:   "I'm not so sure; a total order (which is just a binary operator) allows for A(x=1) <= B(y=1) AND B(y=1) <= A(x=1). i.e. it allows for A(x=1) = B(y=1). Our Java platform is OK" My question is:  who is right (according to the JMM)?
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 Your hypothetical observers cannot exist in this universe because the two writes can occur concurrently, with true parallelism: each core writes to its cache, there is no synchronization necessary and hence it is not done. Since the difference is not observable (due to special relativity if nothing else) the question is moot as far as I can see. The JMM only regulates observable behavior, and that is hard enough ;-) Is there another question behind the one you are currently asking? Regards, Roland Sent from my iPhone > On 31 May 2016, at 11:52, thurstonn <[hidden email]> wrote: > > Let me try another way: > > Imagine we have the previously mentioned program: > > volatile int x, y > > Thread A       Thread B > x = 1             y = 1 > > And we have two "observers" Bob and Jill; both of them have the magical > ability to observe all hardware state (registers, caches, memory, etc) > during the execution of any program *without interfering in said execution* > > They record each execution of a program by writing down a history of what > they observed. > > The above program is run a 1000 times; after each execution, Bob and Jill > compare their two histories; they are always in agreement. > > For some executions, the history is: > A(x=1) > B(y=1) > > for others, it's: > B(y=1) > A(x=1) > > Again, Jill's and Bob's histories are always the same. > > Then the program is executed for the 1001 time. > Again they compare histories: > Bob: > A(x=1) > B(y=1) > > Jill: > B(y=1) > A(x=1) > > Bob:  "Hmm, our Java platform is broken; this violates the JMM guarantee of > a total order among synchronization actions, i.e. it violates > synchronization order" > > Jill:   "I'm not so sure; a total order (which is just a binary operator) > allows for A(x=1) <= B(y=1) AND B(y=1) <= A(x=1). i.e. it allows for A(x=1) > = B(y=1). Our Java platform is OK" > > My question is:  who is right (according to the JMM)? > > > > > > > > -- > View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/Is-Synchronization-Order-A-Strict-Total-Order-tp13457p13460.html> Sent from the JSR166 Concurrency mailing list archive at Nabble.com. > _______________________________________________ > Concurrency-interest mailing list > [hidden email] > http://cs.oswego.edu/mailman/listinfo/concurrency-interest_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 In reply to this post by thurstonn On 05/31/2016 12:52 PM, thurstonn wrote: > And we have two "observers" Bob and Jill; both of them have the magical > ability to observe all hardware state (registers, caches, memory, etc) > during the execution of any program *without interfering in said execution* Your question boils down to: are Bob and Jill -- the CPU demons -- observe events "x=1" and "y=1" in the same relative order? Since there is communication delay involved, you cannot say they have to observe the events in any particular order. Or, that is to say, the physical universe where machines exist does not force us to detect both events in the same relative order. (Aside: this is similar how introducing the no-faster-than-a-speed-of-light axiom in special relativity gives raise to relativity of simultaneity itself) But the actual question that programmer care of is, are *programs* allowed to observe the different relative order? I.e. if we introduce the actual reads in the program, do we see the different order of x=1 and y=1? IRIW under JMM says "no". And this is a critical thing: model is described as behavior observed by *programs*, not by CPU demons. Now, it is a machine problem how to map the actual physical sequence of events towards the program-observable behaviors. Barriers and other HW synchronization primitives are the ways to communicate where that observable order matters. > My question is:  who is right (according to the JMM)? I think you have to get back to Lamport's definition of sequential consistency and its difference against the strict consistency. Notably, SC definition states "... the result of any execution is the same *as if* [emphasis is mine] the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program." That "as if"-ness is a crucial part here: under SC-DRF, the outcome of the data-race-free program is *as if* there was a total order. The exact order in which the actions were executed is not required to be consistent with that order (_strict_ consistency requires that). Introducing external observers that can magically observe the "blurry" interim state of the system does not violate SC property, because the program outcome still stays the same. Thanks, -Aleksey _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest signature.asc (853 bytes) Download Attachment
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 Quoting from the JLS: 17.4.4. Synchronization Order "Every execution has a synchronization order. A synchronization order is a total order over all of the synchronization actions of an execution. " That seems like a categorical statement; no references to data-races, sequential consistency, observability, program results, nor, God forbid, special relativity (which isn't relevant since CPUs are not in relative motion with each other). So for a program with only synchronization actions, the JMM requires some binary operator (the total order) over each pair of actions in the program (in this case, the set {A(x=1), B(y=1}). What could that binary operator be? In other words, what, within a program execution, does A(x=1) <= B(y=1) mean? Could CPUcost(action-x, action-y) be it?  I don't think so. It seems to me, no matter how hard I might try to avoid it, it means the numerical comparison of time(stamp) of each action, which presents difficulty in precise definition (since, e.g. writes and reads are not instantaneous). The JMM authors had 2 choices (again when it comes to synchronization actions): No execution with simultaneous (A(x=1) = B(y=1)) actions are allowed (Bob's understanding, and implied by a *strict* total order) or Simultaneous (A(x=1) = B(y=1)) actions are allowed (Jill's understanding, and implied by a *non-strict* total order) I'm assuming from your reply that it's the latter (Jill's) meaning, but I fail to see how any reasonable interpretation of the sentence I quoted above could be: "Well, since no threads observe any other thread's actions (true in this case), then scratch the whole requirement about synchronization order" which you also seem to be suggesting
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 The program you are referring to can be obtained by making every field volatile. However, unobservable synchronization actions, including volatile reads and writes, can be optimized and/or elided. On May 31, 2016 11:06 AM, "thurstonn" <[hidden email]> wrote:Quoting from the JLS: 17.4.4. Synchronization Order "Every execution has a synchronization order. A synchronization order is a total order over all of the synchronization actions of an execution. " That seems like a categorical statement; no references to data-races, sequential consistency, observability, program results, nor, God forbid, special relativity (which isn't relevant since CPUs are not in relative motion with each other). So for a program with only synchronization actions, the JMM requires some binary operator (the total order) over each pair of actions in the program (in this case, the set {A(x=1), B(y=1}). What could that binary operator be? In other words, what, within a program execution, does A(x=1) <= B(y=1) mean? Could CPUcost(action-x, action-y) be it?  I don't think so. It seems to me, no matter how hard I might try to avoid it, it means the numerical comparison of time(stamp) of each action, which presents difficulty in precise definition (since, e.g. writes and reads are not instantaneous). The JMM authors had 2 choices (again when it comes to synchronization actions): No execution with simultaneous (A(x=1) = B(y=1)) actions are allowed (Bob's understanding, and implied by a *strict* total order) or Simultaneous (A(x=1) = B(y=1)) actions are allowed (Jill's understanding, and implied by a *non-strict* total order) I'm assuming from your reply that it's the latter (Jill's) meaning, but I fail to see how any reasonable interpretation of the sentence I quoted above could be: "Well, since no threads observe any other thread's actions (true in this case), then scratch the whole requirement about synchronization order" which you also seem to be suggesting -- View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/Is-Synchronization-Order-A-Strict-Total-Order-tp13457p13465.html Sent from the JSR166 Concurrency mailing list archive at Nabble.com. _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 joe.bowbeer wrote The program you are referring to can be obtained by making every field volatile. However, unobservable synchronization actions, including volatile reads and writes, can be optimized and/or elided. On May 31, 2016 11:06 AM, "thurstonn" <[hidden email]> wrote: Of course, hence the program (repeated here) volatile int x, y Thread A       Thread B x = 1             y = 1 Elision is an interesting case;  I interpret that with respect to synchronization order as: "A synchronization order is a total order over all of the synchronization actions of an execution" where the synchronization actions (after elision) is {}. No problem there. Optimization, viz. turning a volatile read/write into a plain one, and therefore not a synchronization action, similarly reduces the execution's SA set.
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 In reply to this post by thurstonn On 05/31/2016 07:55 PM, thurstonn wrote: > "Every execution has a synchronization order. A synchronization order is a > total order over all of the synchronization actions of an execution. " > > That seems like a categorical statement; no references to data-races, > sequential consistency, observability, program results, nor, God forbid, > special relativity (which isn't relevant since CPUs are not in relative > motion with each other). Notice there are also no references as to whether those actions are the actual machine actions that Bob and Jill are supposed to observe. And this is for reason: the program actions in JMM are abstract, and have little connection with what real systems do. As long as runtime/hardware can keep the appearances of satisfying JMM requirements, it can do whatever. The point of my previous note was to highlight that: you are asking the question what could happen on physical level, using the entities (actions) on abstract model level. These have little in common. What happens on physical level is all smoke and mirrors. > So for a program with only synchronization actions, the JMM requires some > binary operator (the total order) over each pair of actions in the program > (in this case, the set {A(x=1), B(y=1}). > > What could that binary operator be? > In other words, what, within a program execution, does A(x=1) <= B(y=1) > mean? > Could CPUcost(action-x, action-y) be it?  I don't think so. > > It seems to me, no matter how hard I might try to avoid it, it means the > numerical comparison of time(stamp) of each action, which presents > difficulty in precise definition (since, e.g. writes and reads are not > instantaneous). I think you are trying to drag the abstract notion of action towards its physical manifestation (e.g. changes in machine state, or associated ticks in a global time) -- a very dangerous and confusing route. > The JMM authors had 2 choices (again when it comes to synchronization > actions): > > No execution with simultaneous (A(x=1) = B(y=1)) actions are allowed (Bob's > understanding, and implied by a *strict* total order) or > > Simultaneous (A(x=1) = B(y=1)) actions are allowed (Jill's understanding, > and implied by a *non-strict* total order) That equality sign is confusing. I am probably forgetting a significant part of my training, but these are the definitions that are consistent with my own memory: (Weak) total order implies that for all A, B, C in set:  a) Reflexive:     (A op A)  b) Antisymmetric: (A op B) and (B op A) => (A = B)  c) Transitive:    (A op B) and (B op C) => (A op C)  d) Totality:      (A op B) or (B op A) Strict total order implies that for all A, B, C in set:  a) Irreflexive:   !(A op A)  b) Asymmetric:    (A op B) => !(B op A)  c) Transitive:    (A op B) and (B op C) => (A op C)  d) Trichotomy:    Exactly one of (A op B), (B op A), (A = B) is true Notice (A = B) reads as "A and B are the *same*", not "simultaneous". The difference is in reflexivity. Does it matter if SO is reflexive or not? I don't think so. What does it mean to be simultaneous in SO? Does it mean there exist two non-equal actions that are *not* ordered by SO relation? This contradicts totality/trichotomy in either. Does it mean two non-equal actions have SO in different orders? This breaks anti/asymmetry in either. Thanks, -Aleksey _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest signature.asc (853 bytes) Download Attachment
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 In reply to this post by Aleksey Shipilev-2 Aleksey Shipilev-2 wrote I am probably forgetting a significant part of my training, but these are the definitions that are consistent with my own memory: (Weak) total order implies that for all A, B, C in set:  a) Reflexive:     (A op A)  b) Antisymmetric: (A op B) and (B op A) => (A = B)  c) Transitive:    (A op B) and (B op C) => (A op C)  d) Totality:      (A op B) or (B op A) Strict total order implies that for all A, B, C in set:  a) Irreflexive:   !(A op A)  b) Asymmetric:    (A op B) => !(B op A)  c) Transitive:    (A op B) and (B op C) => (A op C)  d) Trichotomy:    Exactly one of (A op B), (B op A), (A = B) is true Notice (A = B) reads as "A and B are the *same*", not "simultaneous". Ah, I think that last statement might be the rub; my understanding is that A = B does not mean A and B are the *same*, the irreflexive rule deals with that "=" is defined by the total order. The phraseology is extremely awkward; let's replace total order with "binary operator" (subject to the rules you've enumerated), and let's dispense with (ir)reflexivity, as I agree it's completely unnecessary to speak of ordering a SA with respect to itself. "=" is analogous to equals() vis a vis Java identity (==) (at least as I understand it) Say I have a set of laptops {Laptop-A, Laptop-B}, 2 physically distinct laptops. It is meaningless to speak of a total order over that set. I have to define a binary operator, right? Say, weight-of-laptop. In such a case, I can say weight-of-laptop is a total order over {Laptop-A, Laptop-B}; it's not difficult to interpret "=" in that case. Now my understanding is that weight-of-laptop is *not* a strict total order over say {Laptop-A 1.1kg, Laptop-B 1.1kg} Because in order to be a total order, either Laptop-A :wol: Laptop-B => "<" or Laptop-B :wol: Laptop-A => "<". Similarly, let's define an execution as a set of actions. e.g. {A(x=1), B(y=1)}. What's a total order over it? Meaningless right, i.e. I have to define a binary operator. Now, the JMM doesn't define one; it simply adds that the relations produced by it, must be consistent with (intra-thread) program order; which in the sample trivial program is no restriction at all, since each thread contains a single SA. The only logical binary operator "implementation" I can think of is:  timestamp of action. So, my interpretation of synchronization order has been, every possible legal execution's SAs are ordered by "timestamp of action", with the unsolved question being: does the JMM allow an execution to have a pair of SA's with the same timestamp? Is that thinking too close to the "physical layer"?  Maybe; it only requires that each SA have a timestamp associated with it, and those timestamps be comparable in the common-sense way
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 > 31 maj 2016 kl. 21:37 skrev thurstonn <[hidden email]>: > > Aleksey Shipilev-2 wrote >> >> I am probably forgetting a significant part of my training, but these >> are the definitions that are consistent with my own memory: >> >> (Weak) total order implies that for all A, B, C in set: >> a) Reflexive:     (A op A) >> b) Antisymmetric: (A op B) and (B op A) => (A = B) >> c) Transitive:    (A op B) and (B op C) => (A op C) >> d) Totality:      (A op B) or (B op A) >> >> Strict total order implies that for all A, B, C in set: >> a) Irreflexive:   !(A op A) >> b) Asymmetric:    (A op B) => !(B op A) >> c) Transitive:    (A op B) and (B op C) => (A op C) >> d) Trichotomy:    Exactly one of (A op B), (B op A), (A = B) is true >> >> Notice (A = B) reads as "A and B are the *same*", not "simultaneous". > > Ah, I think that last statement might be the rub; my understanding is that A > = B does not mean A and B are the *same*, the irreflexive rule deals with > that > "=" is defined by the total order. You can’t have it both ways: if you’re talking mathematics, = means “they can be used interchangeably”, they are the same. And that is exactly what antisymmetry gives you for a total order. > The phraseology is extremely awkward; let's replace total order with "binary > operator" (subject to the rules you've enumerated), and let's dispense with > (ir)reflexivity, as I agree it's completely unnecessary to speak of ordering > a SA with respect to itself. > > "=" is analogous to equals() vis a vis Java identity (==) (at least as I > understand it) > > Say I have a set of laptops {Laptop-A, Laptop-B}, 2 physically distinct > laptops. > It is meaningless to speak of a total order over that set. > I have to define a binary operator, right? > > Say, weight-of-laptop. > In such a case, I can say weight-of-laptop is a total order over {Laptop-A, > Laptop-B}; it's not difficult to interpret "=" in that case. > > Now my understanding is that weight-of-laptop is *not* a strict total order > over say {Laptop-A 1.1kg, Laptop-B 1.1kg} > Because in order to be a total order, either Laptop-A :wol: Laptop-B => "<" > or Laptop-B :wol: Laptop-A => "<". > > Similarly, let's define an execution as a set of actions. e.g. {A(x=1), > B(y=1)}. > What's a total order over it? > Meaningless right, i.e. I have to define a binary operator. Nope, not meaningless: for every execution there is at least one total order that results in the observed outcome. That binary operator is defined for you—synchronization order. What is meaningless is to ask how many such orders there can be, given that they all result in the same observed outcome, i.e. they cannot be distinguished by definition. > Now, the JMM doesn't define one; it simply adds that the relations produced > by it, must be consistent with (intra-thread) program order; which in the > sample trivial program is no restriction at all, since each thread contains > a single SA. > > The only logical binary operator "implementation" I can think of is: > timestamp of action. > So, my interpretation of synchronization order has been, every possible > legal execution's SAs are ordered by "timestamp of action", with the > unsolved question being: > does the JMM allow an execution to have a pair of SA's with the same > timestamp? > > Is that thinking too close to the "physical layer"?  Maybe; it only requires > that each SA have a timestamp associated with it, and those timestamps be > comparable in the common-sense way There is no such thing as a common-sense timestamp for these operations. And for timestamps to not be comparable due to special relativity the two devices do not actually have to be in motion relative to each other, the only thing that matters is that the observed order of events is not invariant under Lorentz transformations (i.e. different external observers could see conflicting sequences depending on their movement relative to the devices). If you write timestamps from the CPU cores into memory, you’re adding the synchronization steps needed to collapse those multiple undistinguishable histories into distinct ones. Coming back to your initial question: I don’t think it matters whether synchronization order is described in strict or non-strict form, as one gives rise to the other. Regards, Roland > > > > > > > > > > -- > View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/Is-Synchronization-Order-A-Strict-Total-Order-tp13457p13471.html> Sent from the JSR166 Concurrency mailing list archive at Nabble.com. > _______________________________________________ > Concurrency-interest mailing list > [hidden email] > http://cs.oswego.edu/mailman/listinfo/concurrency-interest-- Simplicity and elegance are unpopular because they require hard work and discipline to achieve and education to be appreciated.   -- Dijkstra _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 Nope, not meaningless: for every execution there is at least one total order that results in the observed outcome. That binary operator is defined for you—synchronization order. What is meaningless is to ask how many such orders there can be, given that they all result in the same observed outcome, i.e. they cannot be distinguished by definition. OK, what's the "observed outcome" of the program? x=1, y=1  ? So then what's  the total order of that execution? Total orders can be enumerated pairwise
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 In reply to this post by thurstonn On 05/31/2016 11:35 PM, thurstonn wrote: > Nope, not meaningless: for every execution there is at least one total order > that results in the observed outcome. That binary operator is defined for > you—synchronization order. What is meaningless is to ask how many such > orders there can be, given that they all result in the same observed > outcome, i.e. they cannot be distinguished by definition. > > > OK, what's the "observed outcome" of the program? > x=1, y=1  ? > So then what's  the total order of that execution? Follow-up question: "If a tree falls in a forest and no one is around to hear it, does it make a sound?" But really, you can observe the finished state is (x = 1, y = 1). Is it relevant which order had produced it? You can justify this outcome with either juxtaposition, and so cannot distinguish which one "really happened". The model does not concern itself with what "really happens", it only cares that outcomes are governed by some abstract rules (that is, "as if" there was a total order indeed). Thanks, -Aleksey _______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest signature.asc (853 bytes) Download Attachment
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 In reply to this post by Justin Sampson "17.4.4. Synchronization Order Every execution has a synchronization order. A synchronization order is a total order over all of the synchronization actions of an execution. For each thread t, the synchronization order of the synchronization actions (§17.4.2) in t is consistent with the program order (§17.4.3) of t. " Every execution (a program without reads falls within "every") Free to do whatever it wants? yes, as long as there is a total order over the set of synchronization actions. My English is pretty good
Open this post in threaded view
|

## Re: Is Synchronization Order A *Strict* Total Order?

 In reply to this post by Aleksey Shipilev-2 Aleksey Shipilev-2 wrote On 05/31/2016 11:35 PM, thurstonn wrote: > Nope, not meaningless: for every execution there is at least one total order > that results in the observed outcome. That binary operator is defined for > you—synchronization order. What is meaningless is to ask how many such > orders there can be, given that they all result in the same observed > outcome, i.e. they cannot be distinguished by definition. > > > OK, what's the "observed outcome" of the program? > x=1, y=1  ? > So then what's  the total order of that execution? Follow-up question: "If a tree falls in a forest and no one is around to hear it, does it make a sound?" But really, you can observe the finished state is (x = 1, y = 1). Is it relevant which order had produced it? You can justify this outcome with either juxtaposition, and so cannot distinguish which one "really happened". The model does not concern itself with what "really happens", it only cares that outcomes are governed by some abstract rules (that is, "as if" there was a total order indeed). Thanks, -Aleksey _______________________________________________ Concurrency-interest mailing list [hidden email]http://cs.oswego.edu/mailman/listinfo/concurrency-interestsignature.asc (853 bytes) Those are perfectly fair questions and I essentially raised them in the OP if you look back. For such a trivial program, I agree it's not an issue; it just seems very difficult to "prove" to myself at least that it doesn't present some issue in some hypothetical "concurrency puzzler" program that I inadvertently write.