4
$\begingroup$

In multiprocessor programming, consistency model is the key concept to express the correctness of concurrent objects ranging from simple read/write shared variable to concurrent data structures like FIFO, SkipList, etc.

I think I can understand the principle underlying consistency model when it is treated as an abstract specification of correctness. I am also able to check an execution of some concurrent object against a specific consistency model.

However, when I want to explore more about multiprocessor programming, especially when it comes to the layers of the hardware, operating system, compiler, and virtual machines (JVM, for example), I am totally confused.

At the hardware level, there is only one main memory while each processors holds its own caches. As a consequence, so called cache coherence problem arises and many protocols are proposed to address it.

What is the relation between cache coherence and consistency model?

Up to the operating system and compiler, processes are interleaved and method calls may be reordered for optimization.

Do these make consistency model indispensable?

At the programming language level, I know there is Java Memory Model and it does not enforce Sequential consistency.

What does it mean for JVM to follow some given consistency model?

In summary, what are the parts of consistency model playing in hardware, operating system, and programming language?

I don't understand the whole story and very confused.

Thank you for any suggestions and references.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Before anyone votes to close this question as too elementary: I think this is a very good question. The whole thing is confusing (for example, people commonly mix up specifications and implementations). The state-of-the-art in this area is evolving. Memory models are recent research; they were introduced in major programming languages such as C and C++ as recently as in 2011. Textbooks and lecture notes are not up-to-date. Many TCS researchers should be familiar with these concepts but they are not. I think this question is a very good opportunity for someone to clarify the whole confusion. $\endgroup$ – Jukka Suomela Dec 6 '12 at 15:58
  • 1
    $\begingroup$ @JukkaSuomela Memory models as a research theme are much older. E. Kindler published a big survey in 2000, where he modelled them using Petri nets. This work was in German, hence ignored. A year later, V. Luchangco published similar work in English, using an ad hoc formalism, in his PhD thesis. Such works had little direct connection with existing processors. Nowadays, Peter Sewell and his team study existing processors and implement their memory models in machine checkable form. $\endgroup$ – Martin Berger Dec 6 '12 at 17:25
  • $\begingroup$ @MartinBerger Thanks for the references, especially the links to Peter Sewell and PhD thesis. They are rich and appear to be very helpful. $\endgroup$ – hengxin Dec 7 '12 at 1:49
  • $\begingroup$ @hengxin Have you tried cs.stackexchange.com ? $\endgroup$ – AJed Dec 7 '12 at 3:41
  • $\begingroup$ @AJed not yet. How can I transfer it to cs.stackexchange.com? $\endgroup$ – hengxin Oct 2 '13 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.