Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am having a hard time understanding the SC memory model properly. The sentence "the result of any execution is the same as if 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." is very ambiguous for me.

Does: "having the operations in each processor appear in the sequence specified by the program" mean that all memory operations are updated system wide exactly after being run? Or can they reside in the cache, not known to the processors by the new value for a while.

Does the sentence also infer that no matter what sequential order i decide to order my commands between the threads (not order differently the commands in each individual thread), I will always get the same read's for all of my writes?

Lets take for example this:

Thread 0         Thread 1           Thread 2
X=1              EAX=X              Y=1
                 EBX=Y              ECX = X

Thread 1: EAX=1
Thread 1: EBX=0
Thread 2: ECX=0

It is easily seen that Y=1 MUST be before EBX=Y, because otherwise, EAX cannot be 1 if ECX is 0 or vice versa. But is this still SC? because even though Y=1 was issued before EBX=Y, it could of updated all the threads only after EBX polled Y.

share|cite|improve this question
You could look at Lamport's How to make a multiprocessor computer that correctly executes multiprocess programs or at Luchangco's dissertation which develops a general framework for memory models and around Page 81 specialises it to sequential consistency. – Martin Berger Dec 22 '12 at 17:17
Thanks Martin, I will have a look – Yarneo Dec 24 '12 at 0:02
@Yarneo As for your example, it is impossible to schedule the instructions to get the output as you given, still satisfying the Sequential consistency. For a unified theory of memory models, you can check Unified Theory of Shared Memory Consistency. With the formal definition, you can verify whether an execution (including an output) satisfies a specific memory model systematically. – hengxin Dec 25 '12 at 10:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.