Lecture Notes for Concurrent Programming

5 August 2003 - .NET Memory Consistency

Outline

• .NET and its memory model.

• Memory consistency models.

  • Sequential and release consistency.

• .NET Release Consistency

  • Gates and Fences

  • Locks

  • Sequential Consistency and Volatile Memory

• Using release consistency.

  • Lazy initialization.

  • The double-check idiom.

  • Atomic operations.

What is .NET?

• Damned if I know.

• It's like a language-independent Java.

  • C# (and everything else) is like Java.

  • The Common Language Runtime (CLR) is like the JVM.

  • Everything else is like libraries.

• Microsoft has submitted .NET to the European Computer Manufacturers Association (ECMA) as a standard.

• There is .NET itself from Microsoft, and three "open-source" implementations

  1. Rotor from Microsoft (and it's "shared source"),

  2. Mono from Ximian, and

  3. DotGNU from the FSF.

The .NET Memory Model

• The .NET memory model is similar to the JVM's.

  • Threads don't have local storage.

• A big difference is in the consistency model.

  • .NET's consistency model is stronger than the JVM's.

• See Memory Consistency & .NET by Arch D. Robison, Dr. Dobb's Journal, April, 2003.

Our Ol' Pal

• Consider simple producer-consumer synchronization

  # Inv:  ready -> msg
  
  bool ready = false
  buffer msg
  
  co while ready    msg = data ; ready = true
  || while !ready ; f(msg)     ; ready = false
  

• This synchronization is correct because

  • The producer writes msg and then writes writes.

  • The consumer reads msg and then writes empty.

  • These orderings preserve the invariant for both threads.

Sequential Consistency

• A sequentially consistent system presents one sequence of memory operations to all threads.
  

  • Even when threads are issuing memory operations at the same time.

• A sequential computation is naturally a sequentially consistent system.

  • This is why programmers like sequential consistency.

• A concurrent computation on a uniprocessor is a sequentially consistent system.

  • There's no "at the same time".

Sequential Consistency Problems

• Sequential consistency is good for programmers, but bad for performance.

• Implementing sequential consistency in hardware is hard.

  • It requires too much synchronization, clobbering performance.

  • Intel's Itanium re-orders memory operations in both directions.

    • Most other modern architectures have similar features.

• Common compiler optimizations usually violate sequential consistency.

  while ready          int t = ready
  msg = data           while t
  ready = true         msg = data
                       ready = true
  
  while !ready         while !ready
  f(msg)               ready = false
  ready = false        f(msg)
  

Replacing Sequential Consistency

• Sequential consistency is too strong.

  • Unshared variable accesses can be re-ordered arbitrarily.

  • Shared variable accesses shouldn't wander too far.

    msg3 = data3       msg3 = data3
    msg2 = data2       msg2 = data2
    msg0 = data0       ready = true                  
    msg1 = data1       msg1 = data1
    ready = true       msg0 = data0
    

• The sequential consistency replacement should

  • allow memory operation re-orderings by default, and

  • provide a way to keep memory operations from wandering too far.

• Alternatives to sequential consistency differ in their definition of "wandering too far".

Release Consistency

• Release consistency is a less strict form of memory-operation ordering.

• Acquire and release are the two release-consistency operators.

• Acquire reads a memory location and prevents following memory operations from moving backwards.

  • Previous memory operations can become following memory operations.
  

• Release writes a memory location and prevents previous memory operations from moving forward.

  • Following memory operations can become previous memory operations.
  

• Reordering restrictions apply to all memory accesses, not just the acquired and released ones.

How Release Consistency Works

• Acquire and release prevent shared memory operations from wandering to the wrong side of synchronization operations.
  

• You can think of this as message (or baton) passing.

  • The writer finishes by releasing.

  • The reader starts by acquiring.

• Note this is memory consistency only, not synchronization.

.NET Release Consistency

• .NET Volatile variables are accessed with Release Consistency.

  • This is not the same volatile as in Java (or C++).

• The CLR provides acquire and release operations.

  • Thread.VolatileRead(T &) does an acquire.

  • Thread.VolatileWrite(T &) does a release.

  • T is a primitive type (byte, int, double, or object reference).

• The hardware (may) provide release consistency too.

  • The Itanium does, the current x86 architectures don't.

Gates and Fences

• A volatile write followed by a volatile read forms a fence.
  

  • Memory operations can't traverse the fence.

• Fences are stronger than needed for release consistency.

  • They are sufficient but not necessary.

  • Release consistency doesn't need to prevent bidirectional movement.

• Proper use of acquire and release forms a virtual fence.

  • The producer writes last and the consumer reads first.

• .NET provides barriers with System.Threading.Thread.MemoryBarrier().

Locks

• Consider a fence again.
  

• There are two memory operations that can traverse a fence.
  

• The resulting arrangement is critical section synchronization.

  • Memory operations may migrate into but not out of the critical section.

• Release consistency doesn't provide mutual exclusion.

  • It's the lock protocol on volatile variables that do.

Sequential Consistency and Volatile Memory

• The sliding fence trick tells us one other thing.

  • Volatile memory operations are not sequentially consistent.

  • Two threads can view two volatile memory operations in different orders.

• Java requires that thread-order be preserved for memory operations on volatile fields.

Lazy Initialization

• Suppose a big, expensive object may or may not be read-only accessed.

  BigExpensiveObject beo = new BigExpensiveObject()
  
  // beo may or may not read.
  

  • Can this be handled better?

• Lazy initialization delays object creation until needed.

  BigExpensiveObject beo = null
  
  if beo == null
    beo = new BigExpensiveObject()
  
  // read beo
  

• Lazy initialization avoids unnecessary work, but increases latency.

  • Initial accesses to beo also have to check for initialization.

The Double-Check Idiom

• Suppose beo is shared?

  • beo is (almost) read-only; we (almost) don't care.

  • Initialization's the problem.

• Protect instance creation in a critical section.

  mutex.lock()
  if beo == null
    beo = new BigExpensiveObject()
  mutex.unlock()
  // read beo
  

• Locking the initialization is expensive and mostly useless. Is there a better way?

  • Initialization is stable and beo is atomic.

  if beo == null
    mutex.lock()
    if beo == null
      beo = new BigExpensiveObject()
    mutex.unlock()
  // read beo
  

• This is known as the double-check idiom.

Checking the Double Check

• Does beo need to be volatile?

• It does; otherwise

  • The initializer's write of beo could precede field writes.

  • An reader could find bdo != null with uninitialized fields.

• A volatile beo is an implicit synchronization lock between initializer and reader.

• The Java memory model doesn't support the double-check idiom.

  • This is one of the ways in which the Java memory model is broken.

Atomic Operations

• System.Threading.Interlocked provides four atomic operations:

  T Increment(T & x) 
    < return x++ >
  
  T Decrement(T & x) 
    < return --x >
  
  T Exchange(T & x, T Y) 
    < T t = x ; x = y ; return t >
  
  T CompareExchange(T & x, T y, T z)
    < T t = x ; if (x == z) x = y ; return t >
  

  • Exercise: Lazily initialize beo with one of these operators.

  • Hint: Assume, if you need to, that BigExpensiveObject() is idempotent and side-effect free.

  • Don't peek.

• Atomic operations don't use volatile memory I-O.

  • Atomic operations can be re-arranged for performance.

Points to Remember

• .NET is like Java, only more heavyweight.

• Programmers like sequential consistency; performance hounds don't.

  • Programmers lose.

• Release Consistency allows for more optimizations than does Sequential Consistency.

  • But it's harder to use.

• Gates and fences prevent memory operations from wandering.

  • But they do not provide mutual exclusion.

• Lazy initialization and the double-check idiom is the test.

  • .NET passes, JVM doesn't.

This page last modified on 5 August 2003.