<p>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.</p>

<p>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.       </p>

<p>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.</p>

<p>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. </p>

<p><code>What is the relation between cache coherence and consistency model?</code></p>

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

<p><code>Do these make consistency model indispensable?</code></p>

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

<p><code>What does it mean for JVM to follow some given consistency model?</code></p>

<blockquote>
  <p>In summary, what are the parts of consistency model playing in hardware, operating system, and programming language? </p>
</blockquote>

<p>I don't understand the whole story and very confused.</p>

<p>Thank you for any suggestions and references.</p>

CC BY-SA 3.0
2012-12-06T15:58:56.610Z
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.
Jukka Suomela
CC BY-SA 3.0
2012-12-06T17:25:55.880Z
@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](http://theory.csail.mit.edu/ftp-data/pub/people/victor_l/Thesis.pdf). Such works had little direct connection with existing processors. Nowadays, [Peter Sewell](http://www.cl.cam.ac.uk/~pes20/) and his team study existing processors and implement their memory models in machine checkable form.
Martin Berger
CC BY-SA 3.0
2012-12-07T01:49:52.330Z
@MartinBerger Thanks for the references, especially the links to Peter Sewell and PhD thesis. They are rich and appear to be very helpful.
hengxin
CC BY-SA 3.0
2012-12-07T03:41:38.753Z
@hengxin Have you tried cs.stackexchange.com ?
AJed
CC BY-SA 3.0
2013-10-02T04:47:44.703Z
@AJed not yet. How can I transfer it to cs.stackexchange.com?
hengxin
CC BY-SA 3.0
2013-10-02T15:43:44.227Z
@hengxin just post it there.
AJed
CC BY-SA 3.0
2015-01-12T10:12:14.730Z
‘JVM satisfies consistency model X’ means that the JVM is an implementation that has the properties listed in the definition of X. As an analogy, suppose someone describes the multiplication algorithm and then says, ‘by the way, this algorithm satisfies commutativity’.
Radu GRIGore
<pl.programming-languages><dc.parallel-comp><concurrency>
What are the parts of consistency model playing in hardware, operating system, and programming language?
hengxin
# What are the parts of consistency model playing in hardware, operating system, and programming language?

(Asked by: username_0 on 2012-12-06)

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.

**Tags:** pl.programming-languages, dc.parallel-comp, concurrency
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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](http://theory.csail.mit.edu/ftp-data/pub/people/victor_l/Thesis.pdf). Such works had little direct connection with existing processors. Nowadays, [Peter Sewell](http://www.cl.cam.ac.uk/~pes20/) and his team study existing processors and implement their memory models in machine checkable form.  
> **username_0**: @MartinBerger Thanks for the references, especially the links to Peter Sewell and PhD thesis. They are rich and appear to be very helpful.  
> **username_3**: @hengxin Have you tried cs.stackexchange.com ?  
> **username_0**: @AJed not yet. How can I transfer it to cs.stackexchange.com?  
> **username_3**: @hengxin just post it there.  
> **username_4**: ‘JVM satisfies consistency model X’ means that the JVM is an implementation that has the properties listed in the definition of X. As an analogy, suppose someone describes the multiplication algorithm and then says, ‘by the way, this algorithm satisfies commutativity’.  

---

## 0 answers

