In example 1, we will always print 1 since we can't reorder writes, hence A must be set to 1 when flag is observed to be 1. Reordering reads before writes won't do anything for us.
In example 2, we can observe "0 0", "0 1", and "1 1". "1 0" is impossible in any ordering since we must write 1 to A before writing 1 to B and we can't change the write order.
In example 3, in SC we will observe "1" for the obvious reason. In TSO this doesn't change since there's no reordering of reads and writes, but in PC we can observe "0" by not waiting for the write to A to be observed in P3, hence observing a 0 in A.
In example 4, in SC we can't observe "0 0" but we can in TSO and PC since we can put the two prints before the two writes. Every other ordering is possible.
yangwu
@TomoA i think "1 1" is possible in example 2? simply by executing thread 2 after thread 1 finishs
ppwwyyxx
As a summary, this slide shows that different consistency constraint can indeed lead to different program behavior.
Surprisingly, if all processor do what seems right to itself (reorder the independent instructions), the overall behavior could still be unexpected.
chuangxuean
@TomoA what do you mean in your third paragraph that there is no reordering of reads and writes, aren't we relaxing the write-read ordering?
jsunseri
@chuangxuean We are relaxing W->R but not R->W, so if a read comes before a write this ordering will be observed. Specifically for example 3, if thread 2 could write B=1 before finishing the read of A, it would be possible for thread 3 to print 0 in TSO. However, TSO doesn't allow for R->W to be relaxed, so printing 0 is not a possible result of this program in TSO.
trappedin418
Does anyone have an example where TSO is different than sequential but PC is the same? Is PC always "less strict" than TSO?
totofufu
I understand how "0 0" is possible for TSO in example 4, but can someone explain why "0 0" is possible for PC? In PC, "any processor can read the new value of a variable before a write is observed by all processors", right?
huehue
I think in both TSO and PC, reads can move before writes. But in PC the difference is that writes might not be seen by all processors at the same time. Is that right?
Perpendicular
@trappedin418 I think TSO is always more strciter than PC. If you look at the previous slide there is one important distinction between TSO and PC. In PC all processors (not only processor P) can move their reads before other writes. In TSO only processor P can move its reads before the writes.
randomized
@Perpendicular: I think in both TSO and PC the reads can be moved before writes (see Example 4 for instance). I guess there is no dependency on what other processors are writing. Instead, TSO and PC both place different constraints on what values the other processors can see.
In example 1, we will always print 1 since we can't reorder writes, hence
Amust be set to 1 whenflagis observed to be 1. Reordering reads before writes won't do anything for us.In example 2, we can observe "0 0", "0 1", and "1 1". "1 0" is impossible in any ordering since we must write 1 to
Abefore writing 1 toBand we can't change the write order.In example 3, in SC we will observe "1" for the obvious reason. In TSO this doesn't change since there's no reordering of reads and writes, but in PC we can observe "0" by not waiting for the write to
Ato be observed inP3, hence observing a 0 inA.In example 4, in SC we can't observe "0 0" but we can in TSO and PC since we can put the two prints before the two writes. Every other ordering is possible.
@TomoA i think "1 1" is possible in example 2? simply by executing thread 2 after thread 1 finishs
As a summary, this slide shows that different consistency constraint can indeed lead to different program behavior. Surprisingly, if all processor do what seems right to itself (reorder the independent instructions), the overall behavior could still be unexpected.
@TomoA what do you mean in your third paragraph that there is no reordering of reads and writes, aren't we relaxing the write-read ordering?
@chuangxuean We are relaxing W->R but not R->W, so if a read comes before a write this ordering will be observed. Specifically for example 3, if thread 2 could write B=1 before finishing the read of A, it would be possible for thread 3 to print 0 in TSO. However, TSO doesn't allow for R->W to be relaxed, so printing 0 is not a possible result of this program in TSO.
Does anyone have an example where TSO is different than sequential but PC is the same? Is PC always "less strict" than TSO?
I understand how "0 0" is possible for TSO in example 4, but can someone explain why "0 0" is possible for PC? In PC, "any processor can read the new value of a variable before a write is observed by all processors", right?
I think in both TSO and PC, reads can move before writes. But in PC the difference is that writes might not be seen by all processors at the same time. Is that right?
@trappedin418 I think TSO is always more strciter than PC. If you look at the previous slide there is one important distinction between TSO and PC. In PC all processors (not only processor P) can move their reads before other writes. In TSO only processor P can move its reads before the writes.
@Perpendicular: I think in both TSO and PC the reads can be moved before writes (see Example 4 for instance). I guess there is no dependency on what other processors are writing. Instead, TSO and PC both place different constraints on what values the other processors can see.