×

zbMATH — the first resource for mathematics

Generative operational semantics for relaxed memory models. (English) Zbl 1260.68050
Gordon, Andrew D. (ed.), Programming languages and systems. 19th European symposium on programming, ESOP 2010, held as part of the joint European conferences on theory and practice of software, ETAPS 2010, Paphos, Cyprus, March 20–28, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-11956-9/pbk). Lecture Notes in Computer Science 6012, 307-326 (2010).
Summary: The specification of the Java memory model (JMM) is phrased in terms of acceptors of execution sequences rather than the standard generative view of operational semantics. This creates a mismatch with language-based techniques, such as simulation arguments and proofs of type safety.
We describe a semantics for the JMM using standard programming language techniques that captures its full expressivity. For data-race-free programs, our model coincides with the JMM. For lockless programs, our model is more expressive than the JMM. The stratification properties required to avoid causality cycles are derived, rather than mandated in the style of the JMM.
The JMM is arguably non-canonical in its treatment of the interaction of data races and locks as it fails to validate roach-motel reorderings and various peephole optimizations. Our model differs from the JMM in these cases. We develop a theory of simulation and use it to validate the legality of the above optimizations in any program context.
For the entire collection see [Zbl 1182.68003].

MSC:
68N15 Theory of programming languages
68Q55 Semantics in the theory of computing
Software:
Scala; TSOTool
PDF BibTeX XML Cite
Full Text: DOI