www.cs.umd.edu

www.cs.umd.edu

Improving the Java Memory Model Using CRF Jan-Willem Maessen Arvind Xiaowei Shen [jmaessen,arvind]@lcs.mit.edu, [email protected] J. Maessen, Arvind and X.Shen 1 Java Memory Model: Problems Incomplete - No semantics for final fields Disallows important optimizations - Reordering of loads to same location

- Some reordering are inexpressible in source Difficult to understand - Memory updates not atomic J. Maessen, Arvind and X.Shen 2 Roadmap Examples of JMM problems Desired Programming Discipline Well-behaved programs Source-level algebraic reasoning Translating Java into CRF

Conclusions J. Maessen, Arvind and X.Shen 3 Final fields: The String Example Thread 1 char [ ] a = {H,i}; s = new MyString(a); Thread 2 print(s); Thread 2 should either print Hi or throw an exception class MyString { private final char[ ] theCharacters; public MyString( char[ ] value) { char[ ] internalValue = value.clone(); theCharacters = internalValue;

} ... } J. Maessen, Arvind and X.Shen 4 Enabling Optimizations Thread 1 v = p.f; w = q.f; x = p.f; Thread 2 p.f = 2; Can we replace x = p.f by x = v ? Old JMM: No! What if p==q? Reads must be ordered! Proposed JMM: Yes! Reads can be reordered

J. Maessen, Arvind and X.Shen 5 Confusing Semantics v = q.g; w = p.f; p.f = 42; u = p.f; v = q.g; w = p.f; p.f = 42; X w = p.f; p.f = 42; v = q.g; u = p.f; w = p.f;

p.f = 42; v = q.g; Program behavior is context-sensitive [Pugh99] The old JMM semantics are simply too convoluted! J. Maessen, Arvind and X.Shen 6 The Java Memory Model [Gosling, Joy, Steele, 1st ed., Ch 17] thread thread assign cache cache thread

... cache use store load write read shared memory Seven axioms define permitted reorderings - use and assign occur in program order - store and write to a location occur in order

- read and load from a location occur in order ... J. Maessen, Arvind and X.Shen 7 Solution: Make Reorderings Explicit thread cache thread cache thread ... cache shared memory Reorder at the thread level

Make instructions atomic J. Maessen, Arvind and X.Shen 8 Plan of action Define a desired programming style for Java Give high-level description of program behavior Capture high-level description in a precise semantics J. Maessen, Arvind and X.Shen 9

Java Memory Operations Regular Memory v = LoadR p.f StoreR p.f,v Volatile Memory v = LoadV p.f StoreV p.f,v Final Memory v = LoadF p.f EndCon StoreF p.f,v

Monitors Enter l Exit l J. Maessen, Arvind and X.Shen 10 Regular fields Constrained only by data dependence Load/Store must be protected by monitors If it's shared, it must be locked during access Read-only objects can omit synchronization But only when reached through final fields J. Maessen, Arvind and X.Shen 11

Final Fields and Constructors Allow creation of read-only data An object must not escape its constructor Final fields may be read without synchronization Includes referenced read-only objects J. Maessen, Arvind and X.Shen 12 Volatile Fields Allow free-form data exchange Volatile operations occur in program order

Volatile loads act like Enter Volatile stores act like Exit Any field may safely be made volatile J. Maessen, Arvind and X.Shen 13 Algebraic Rules Source-to-source program manipulation See the effects of reordering Reason about incorrect program behavior

Captures legal static reorderings Easy to reason about interleaved execution Implied by dynamic semantics J. Maessen, Arvind and X.Shen 14 Load/Store Reordering Must respect usual dependencies: Store p.f,4; x = Load p.f; Store p.f,5;

Regular & Final operations reorder freely: StoreR p.f,4; y = LoadF q.g; x = LoadF q.g; x = LoadF q.g; y = LoadF q.g; StoreR p.f,4; Volatile operations do not reorder! J. Maessen, Arvind and X.Shen 15 Synchronization Any Load/Store may enter synchronization LoadR q.f; Enter p.l; LoadR p.f;

Exit p.l; LoadR q.g; Enter p.l; LoadR q.f; LoadR p.f; LoadR q.g; Exit p.l; Non-finals may not escape synchronization Enter must be ordered wrt both Enter and Exit. J. Maessen, Arvind and X.Shen 16 Other Interactions LoadV acts like Enter, StoreV acts like Exit

LoadR q.f; LoadV p.v; LoadV p.v; LoadR q.f; LoadR p.f; LoadR p.f; StoreV p.v; LoadR q.g; LoadR q.g; StoreV p.v; EndCon keeps stores in, non-final stores out: StoreF p.f, 5; StoreF p.f, 5; EndCon; StoreF q.g, p; StoreF q.g, p; EndCon; StoreR r.h, p; StoreR r.h, p;

J. Maessen, Arvind and X.Shen 17 Reordering Around Control Flow Thread 1 Thread 2 int tmp1 = p.flag; if (tmp1==1) { int tmp2 = p.flag; system.out.print("yes"); if (tmp2 == 0) { system.out.print("BAD"); } } p.flag = 1; Consequence of poor synchronization

J. Maessen, Arvind and X.Shen 18 Compilation Dependency Analysis = Reordering Read/write constraints dont capture reorderings Type & alias analyses permit read/write reordering Regular, volatile, and final storage are disjoint! Escape analysis permits local operation reordering Pointer analysis spots fetches via final pointers

J. Maessen, Arvind and X.Shen 19 Roadmap Examples of JMM problems Desired Programming Discipline Well-behaved programs Source-level algebraic reasoning Translating Java into CRF Conclusions J. Maessen, Arvind and X.Shen

20 CRF: A General Representation Java Threads (regular, final, volatile, monitors) Commit-Reconcile & Fences (CRF) X86 Sparc PowerPC Alpha (Shen, Arvind, Rudolph, ISCA99) J. Maessen, Arvind and X.Shen 21 Java to CRF: Regular Memory x = LoadR p.f;

Reconcile p.f; x = LoadL p.f; StoreR p.f, y; StoreL p.f, y; Commit p.f; J. Maessen, Arvind and X.Shen 22 The CRF Model thread cache thread cache

thread ... cache shared memory data caching via semantic caches Cache updates at any time (background) Commit, Reconcile force updates instruction reordering (controllable via Fence) all operations act atomically J. Maessen, Arvind and X.Shen 23 The Fence Operations

Instructions can be reordered except for Data dependence StoreL a,v; Commit a; Reconcile a; LoadL a; StoreL(a1, v); Commit(a1); Fencewr(a1, a2); Reconcile(a2); LoadL(a2); Fencerr; Fencerw; Fenceww; J. Maessen, Arvind and X.Shen 24 Important Properties of CRF Safe to add extra Commits & Reconciles

Safe to add additional Fence operations Extra operations reduce exhibited behaviors, but preserve correctness Can use coarse-grain operations, e.g: Fencerr p.f, *V; Fencerr p.f, *VR; Fenceww l, *VRL; Fenceww *, *VR; J. Maessen, Arvind and X.Shen 25 Java to CRF: Final Memory StoreF p.f, x; y = LoadF p.f;

StoreL p.f, x; Commit p.f; Freeze p.f; Reconcile p.f; y = LoadL p.f; Freeze p.f; J. Maessen, Arvind and X.Shen 26 Java to CRF: Volatile Memory Fencerr *V, p.f; x = LoadV p.f; Fencewr *V, p.f; Reconcile p.f; x = LoadL p.f; Fencerr p.f, *VR;

Fencerw p.f, *VR; Fencerw *VR, p.f; StoreV p.f, y; Fenceww *VR, p.f; StoreL p.f, y; Commit p.f; J. Maessen, Arvind and X.Shen 27 Java to CRF: Synchronization Enter l; Fenceww *L, l; Lock l; Fencewr l, *VR;

Fenceww l, *VRL; Exit l; EndCon; Fenceww *VR, l; Fencerw *VR, l; Unlock l; Fenceww *,*VR; J. Maessen, Arvind and X.Shen 28 Allowing Lock Elimination Enter l;

Fenceww *L, l; r = Lock l; if (r!= currentThread) { Fencewr l, *VR; Fenceww l, *VRL; } Operations move upward out of lock region Including into preceding lock regions Operations cannot move downward J. Maessen, Arvind and X.Shen 29 Limits on Reordering

Some reordering must be dynamic Potential aliasing Some reordering is probably purely static Based on analysis The boundary of static reordering is fuzzy a[x*x*x + y*y*y] a[z*z*z] Solution: Flexible dynamic translation J. Maessen, Arvind and X.Shen 30 Memory Model Issues Remaining

Speculation Arbitrary value speculation is the limit point Reordering around control gives us a lot Points between difficult to formalize Biggest open area in memory models G-CRF allows non-atomic Commit No change in translation needed Is it necessary? Can it be understood J. Maessen, Arvind and X.Shen 31 Other Memory Models Data-Race-Free and Properly Labeled programs [Adve & Gharachorloo, ...]

Define a programming style Appearance of sequential consistency Location consistency [Gao & Sarkar, ...] Order writes per-thread & per-location Set of possible values at each load J. Maessen, Arvind and X.Shen 32 Java Issues Remaining Run-time system memory model issues New threads start with parent's state

GC responsible for its own synchronization EndCon for object pre-initialization Thread-safe Library code Code libraries correctly Clarify finalization Fix native code mutating final fields Establishing thread-safe Patterns Lock-free caching (double-checking breaks) Freezing mutable objects (Java Beans) J. Maessen, Arvind and X.Shen 33 Java Memory Model in CRF Precise and easy to understand - Reason about reordering at instruction level - Intuitive high-level semantics Flexible

- Easy to experiment with possible translations Makes optimizations obvious - Reordering expressible in source Simple mapping to a variety of architectures J. Maessen, Arvind and X.Shen 34 Acknowledgements Bill Pugh

Guy Steele David Detlefs Jeremy Manson Vivek Sarkar & the Jalapeno group The readers of the JMM mailing list J. Maessen, Arvind and X.Shen 35 Question Slides J. Maessen, Arvind and X.Shen 36 Another Try Thread 1 List q = p.next; if (q == p) { List tmp = p.next; system.out.print("y"); List r = tmp.next; if (r == null) {

system.out.print("es"); } } Thread 2 p.next = p; J. Maessen, Arvind and X.Shen 37 Another Try Thread 1 List r = p.next; List q = p.next; if (q == p) { system.out.print("y"); Thread 2 p.next = p; if (r == null) { system.out.print("es");

} } J. Maessen, Arvind and X.Shen 38 CRF: LoadL and StoreL thread LoadL(a) Cell(a,v,-) thread StoreL(a,v) ... Cell(a,v,D) shared memory

LoadL reads from the cache if the address is cached StoreL writes into the cache and sets the state to Dirty J. Maessen, Arvind and X.Shen 39 CRF: Commit and Reconcile proc Commit(a) proc Reconcile(a) ... Cell(a,-,D)? Cell(a,-,C) Cell(a,-,C)? shared memory

Commit completes if the address is not cached in the Dirty state Reconcile Clean completes if the address is not cached in J. Maessen, Arvind and X.Shen 40 CRF: Background Operations proc proc ... Cell(a,5,C) proc

... Cell(b,8,D) Cell(b,8,C) Cell(c,7,C) Cache Writeback Cell(a,5) Cell(b,1) Cell(b,8) Purge Cell(c,7) Cache (retrieve) a copy of an uncached address from memory Writeback

a Dirty copy to memory and set its state Clean Purge a Clean copy J. Maessen, Arvind and X.Shen 41 CRF Extensions: Lock and Unlock thread Lock a thread Unlock a ... Cell(a,v,L) Cell(a,v,L) Cell(a,v,L) Cell(a,v,L)

shared memory Lock atomically increments the monitor count Unlock atomically decrements the monitor count J. Maessen, Arvind and X.Shen 42 CRF: Background Locking thread thread ... Cell(a,0,L) Cell(b,0,L) Locked Unlocked Cell(a,0)

Cell(b,0) Locked: retrieve an exclusive copy of an unheld monitor from memory Unlocked: return an unheld monitor to memory for others to use J. Maessen, Arvind and X.Shen 43 CRF Extensions: Freeze thread Freeze a thread ...

Cell(a,-,F) Cell(a,-,C) shared memory Freeze changes cache state to Frozen Reconcile can ignore Frozen entries J. Maessen, Arvind and X.Shen 44

Recently Viewed Presentations

  • Presentación de PowerPoint

    Presentación de PowerPoint

    Hi ha més riscs financers que els considerats per Basilea II? Presentació Programa: 12-març-2010. Sessió inaugural: taula rodona. Moderat per David Ceballos 19-març-2010. Manuel Miró i David Ceballos: Risc legal 26-març-2010. Samuel Mongrut: working capital management 9-abril-2010.
  • Lab Safety Rules - Richmond County School System

    Lab Safety Rules - Richmond County School System

    Conduct yourself in a responsible manner at all times in the laboratory. This is NOT the playground. Never run, horseplay, play practical jokes or push someone else in the lab.
  • Intro to Apache Spark Paco Nathan http://databricks.com/ 00:

    Intro to Apache Spark Paco Nathan http://databricks.com/ 00:

    Objectives: openaSparkShell. useofsomeMLalgorithms. exploredatasets loadedfromHDFS,etc. reviewSparkSQL,SparkStreaming,Shark. reviewadvancedtopicsandBDASprojects
  • Stitches in Time

    Stitches in Time

    Les gouvernements canadiens ne doivent pas encourager le financement privé et la prestation à but lucratif Institut canadien de la retraite et des avantages sociaux Winnipeg, le 15 juin 2007
  • HT MEDIA LIMITED Results Presentation Q3 & 9M

    HT MEDIA LIMITED Results Presentation Q3 & 9M

    HT MEDIA LIMITED Results Presentation Q3 & 9M FY2011 18 January 2011 Safe Harbour Certain statements in this document may be forward-looking. Such forward-looking statements are subject to certain risks and uncertainties like regulatory changes, local political or economic developments,...
  • Form One Chemistry Lesson Notes - WordPress.com

    Form One Chemistry Lesson Notes - WordPress.com

    Drugs and drug-abuse. A drug is any natural or man made substance which when taken changes in some way the normal working of a body. Drug-abuse is the use of drugs for any other purpose other than for which it...
  • The Limping Child: The good, bad and do not miss

    The Limping Child: The good, bad and do not miss

    Proximal Tibia (Cozen Fracture) slight risk of developing Cozen Deformity (Valgus deformity of the knee 1-2 years after) Toddler's Fractures. Leg-Calve-Perthes. aka . Perthes. Avascular Necrosis of the Femoral Head. Unknown etiology.
  • Decolonizing Museums - sacc.americananthro.org

    Decolonizing Museums - sacc.americananthro.org

    Amy Lonetreea decolonizing museum practice must involve assisting (tribal) communities in addressing the legacies of unresolved grief . Past. Museums have represented frozen static cultures . Held as elite temples. Curatorial control Museums. Present/Future. Inclusivity shift in contemporary museums