Memory Consistency in .NET
by Arch D. Robison

Example 1: 

(a)
// Assume R==0 on entry
// Fill message buffer
for( int i=0; i<n; i++)
   M[i] = ...;
// Signal that message is ready.
R = 1;

(b)
// Assume R==0 on entry
// Wait for signal from sender
while( R==0 )
   continue
// Read the message
for( int i=0; i<n; i++ )
    ... = M[i];


Example 2: 

(a)
// Oops - compiler could reorder 
// writes like this.
R = true;
for( int i=0; i<n; i++ )
   M[i] = ...; 

(b)
// Oops - compiler hoists loop invariant!
int t = R;
while( t==0 )   
   continue;
for( int i=0; i<n; i++ )
   ... = M[i];

Example 3: 

(a)
lock( ... ) 
   if( Z==null )
      Z = new Foo();
 ... = Z;

(b)
// Z must be declared volatile
if( Z==null ) 
   lock( ... ) 
      if( Z==null )
   Z = new Foo();
 ... = Z


Listing One

/// <summary>
/// Mailbox implementation using locks.
/// </summary>
public class LockedMailbox {
	/// <summary>
	/// A letter in the Mailbox
	/// </summary>
	class Letter {
		/// <summary>
		/// Link to next Letter in the mailbox.
		/// </summary>
		public Letter Next;
		/// <summary>
		/// Content of the letter.
		/// </summary>
		public readonly object Content;
		/// <summary>
		/// Construct a letter.
		/// </summary>
		/// <param name="item">content of letter</param>
		public Letter( object item ) {
			Content = item;
		}
	}
	/// <summary>
	/// Root of linked list.
	/// </summary>
	private Letter List;
	/// <summary>
	/// Send an object.
	/// </summary>
	/// <param name="item">object to be sent</param>
	public void Send( object item ) {
		Letter letter = new Letter(item);
		lock( this ) {
			letter.Next = List;
			List = letter;
		}
	}
	/// <summary>
	/// Receive one object.
	/// </summary>
	/// <returns>received object, or null if mailbox was empty</returns>
	public object Receive() {
		Letter letter ;
		lock( this ) {
			letter  = List;
			if( letter !=null ) List=letter.Next;
		}
		return letter .Content;
	}
}


Listing Two


using System.Threading;

/// <summary>
/// Mailbox implementation using CompareExchange
/// </summary>
public class CompareExchangeMailbox {
	/// <summary>
	/// A letter in the Mailbox.
	/// </summary>
	class Letter {
		/// <summary>
		/// Link to next Letter in the mailbox.
		/// </summary>
		public Letter Next;
		/// <summary>
		/// Content of the letter.
		/// </summary>
		public object Content;
		/// <summary>
		/// Construct a letter.
		/// </summary>
		/// <param name="item">content of letter</param>
		public Letter( object item ) {
			Content = item;
		}
	}
	/// <summary>
	/// Root of linked list of Letters.
	/// Conceptually it is a "Letter", but must be declared as "object"
	/// because Interlocked.CompareExchange expects a "ref object".
	/// </summary>
   private object list;
	/// <summary>
	/// Send an object.
	/// </summary>
	public void Send( object item ) {
		Letter letter = new Letter(item);
		object root = list;
		Letter oldRoot;
		do {
			letter.Next = oldRoot = (Letter)root;
		   Thread.MemoryBarrier();
			root = Interlocked.CompareExchange( ref list, letter, oldRoot );
		} while( root!=oldRoot );
	}
	/// <summary>
	/// Receive one object, or null if there were no objects pending.
	/// </summary>
	public object Receive() {
		Letter letter;
		object root = list;
		do {
			if( root==null ) return null;
			letter = (Letter)root;
			Letter next = letter.Next;
			Thread.MemoryBarrier();
			root = Interlocked.CompareExchange( ref list, next, letter );
		} while( letter!=root );
		return letter.Content;
	}
}





