How is the serial order defined? If we have several threads, how can we justify that which thread should access certain location first and the other threads later?
BestBunny
Correct me if I am wrong, but as we later saw with the MESI invalidation protocol the serial order is a direct result of the serial intercommunication system between processors and main memory. This order is not deterministic, however, since the first processor that is "heard" will get access to the memory location when multiple processors attempt to access the same memory location. So it is not possible to justify that a particular ordering is correct over another, although the overall order of execution will be consistent between the processors.
holard
This definition only requires that such a serial order exists, not that it can be determined beforehand or dictated otherwise.
paramecinm
@chenh1 I have the same question. If two processors try to do X = X + 1 at the same time, they have instructions: load x to r, r = r + 1, store r to x. After they finished add instruction, they will have the X in shared state. Then, one thread tries to store X, it will change X's state to exclusive. But at that time, the other thread's X value in register is obsolete which means the result is wrong.
googlebleh
@paramecinm This slide is before we introduced any coherence/invalidation protocols. First, we just wanted to define coherence, so we just care that all processors will view the same state (as @holard says).
Since you mention "change X's state to exclusive," I assume you meant to examine this problem in the context of MESI. In that case, then before the register increments r, it should broadcast a "Read Exclusive" message saying it has read X with the intent to modify it, and move into the Modified state as it increments X. That way, when the second processor does the same, its write will be flushed and its cache line invalidated, maintaining serial order.
jedi
@paramecinm good point. However, just because the result is wrong, does this mean that the memory system is not coherent? Surely, the memory system should not correct for programmer error (not locking a variable that should be in a critical section).
How is the serial order defined? If we have several threads, how can we justify that which thread should access certain location first and the other threads later?
Correct me if I am wrong, but as we later saw with the MESI invalidation protocol the serial order is a direct result of the serial intercommunication system between processors and main memory. This order is not deterministic, however, since the first processor that is "heard" will get access to the memory location when multiple processors attempt to access the same memory location. So it is not possible to justify that a particular ordering is correct over another, although the overall order of execution will be consistent between the processors.
This definition only requires that such a serial order exists, not that it can be determined beforehand or dictated otherwise.
@chenh1 I have the same question. If two processors try to do X = X + 1 at the same time, they have instructions: load x to r, r = r + 1, store r to x. After they finished add instruction, they will have the X in shared state. Then, one thread tries to store X, it will change X's state to exclusive. But at that time, the other thread's X value in register is obsolete which means the result is wrong.
@paramecinm This slide is before we introduced any coherence/invalidation protocols. First, we just wanted to define coherence, so we just care that all processors will view the same state (as @holard says).
Since you mention "change X's state to exclusive," I assume you meant to examine this problem in the context of MESI. In that case, then before the register increments
r, it should broadcast a "Read Exclusive" message saying it has readXwith the intent to modify it, and move into the Modified state as it incrementsX. That way, when the second processor does the same, its write will be flushed and its cache line invalidated, maintaining serial order.@paramecinm good point. However, just because the result is wrong, does this mean that the memory system is not coherent? Surely, the memory system should not correct for programmer error (not locking a variable that should be in a critical section).