Lock-Free 编程

  while (x == )

  {

    x =  - x;

  }

__inline int CAS(volatile int & destination, int exchange, int comperand)

{

  __asm {

    MOV eax, comperand

    MOV ecx, exchange

    MOV edx, destination

    LOCK CMPXCHG[edx], ecx /* 如果eax与edx相等, 则ecx送edx且ZF置1;

                              否则edx送ecx, 且ZF清0.*/

  }

}

/* Accumulator = AL, AX, EAX, or RAX depending on

   whether a byte, word, doubleword, or

   quadword comparison is being performed */

IF accumulator = DEST

  THEN

    ZF ← ;

    DEST ← SRC;

  ELSE

    ZF ← ;

    accumulator ← DEST;

FI;

 void LockFreeStack::Push(Node* newHead)

 {

   for (;;)

   {

     // Read the original value from a memory location.

     // Copy a shared variable (m_Head) to a local.

     Node* oldHead = m_Head;

     // Compute the new value to be set.

     // Do some speculative work, not yet visible to other threads.

     newHead->next = oldHead;

     // Set the new value only if the memory location is still the original value.

     // Next, attempt to publish our changes to the shared variable.

     // If the shared variable hasn't changed, the CAS succeeds and we return.

     // Otherwise, repeat.

     if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)

       return;

   }

 }

     private class Node<TNode>

     {

       public Node<TNode> Next;

       public TNode Item;

       public override string ToString()

       {

         return string.Format("{0}", Item);

       }

     }

   public class SimpleStack<T>

   {

     private class Node<TNode>

     {

       public Node<TNode> Next;

       public TNode Item;

       public override string ToString()

       {

         return string.Format("{0}", Item);

       }

     }

     private Node<T> _head;

     public SimpleStack()

     {

       _head = new Node<T>();

     }

     public void Push(T item)

     {

       Node<T> node = new Node<T>();

       node.Item = item;

       node.Next = _head.Next;

       _head.Next = node;

     }

     public T Pop()

     {

       Node<T> node = _head.Next;

       if (node == null)

         return default(T);

       _head.Next = node.Next;

       return node.Item;

     }

   }

   class Program

   {

     static void Main(string[] args)

     {

       SimpleStack<int> stack = new SimpleStack<int>();

       for (int i = ; i <= ; i++)

       {

         stack.Push(i);

       }

       bool[] poppedItems = new bool[];

       Parallel.For(, , (i) =>

         {

           int item = stack.Pop();

           if (poppedItems[item])

           {

             Console.WriteLine(

               "Thread [{0:00}] : Item [{1:0000}] was popped before!",

               Thread.CurrentThread.ManagedThreadId, item);

           }

           poppedItems[item] = true;

         });

       Console.WriteLine("Done.");

       Console.ReadLine();

     }

   }

   public class SimpleLockedStack<T>

   {

     private class Node<TNode>

     {

       public Node<TNode> Next;

       public TNode Item;

       public override string ToString()

       {

         return string.Format("{0}", Item);

       }

     }

     private Node<T> _head;

     private object _sync = new object();

     public SimpleLockedStack()

     {

       _head = new Node<T>();

     }

     public void Push(T item)

     {

       lock (_sync)

       {

         Node<T> node = new Node<T>();

         node.Item = item;

         node.Next = _head.Next;

         _head.Next = node;

       }

     }

     public T Pop()

     {

       lock (_sync)

       {

         Node<T> node = _head.Next;

         if (node == null)

           return default(T);

         _head.Next = node.Next;

         return node.Item;

       }

     }

   }

     private static bool CAS(

       ref Node<T> location, Node<T> newValue, Node<T> comparand)

     {

       return comparand ==

         Interlocked.CompareExchange<Node<T>>(

           ref location, newValue, comparand);

     }

     public void Push(T item)

     {

       Node<T> node = new Node<T>();

       node.Item = item;

       do

       {

         node.Next = _head.Next;

       }

       while (!CAS(ref _head.Next, node, node.Next));

     }

   public class LockFreeStack<T>

   {

     private class Node<TNode>

     {

       public Node<TNode> Next;

       public TNode Item;

       public override string ToString()

       {

         return string.Format("{0}", Item);

       }

     }

     private Node<T> _head;

     public LockFreeStack()

     {

       _head = new Node<T>();

     }

     public void Push(T item)

     {

       Node<T> node = new Node<T>();

       node.Item = item;

       do

       {

         node.Next = _head.Next;

       }

       while (!CAS(ref _head.Next, node, node.Next));

     }

     public T Pop()

     {

       Node<T> node;

       do

       {

         node = _head.Next;

         if (node == null)

           return default(T);

       }

       while (!CAS(ref _head.Next, node.Next, node));

       return node.Item;

     }

     private static bool CAS(

       ref Node<T> location, Node<T> newValue, Node<T> comparand)

     {

       return comparand ==

         Interlocked.CompareExchange<Node<T>>(

           ref location, newValue, comparand);

     }

   }

     public void Push(T item)

     {

       Node<T> node = new Node<T>();

       node.Item = item;

       do

       {

         node.Next = _head.Next;

       }

       while (!CAS(ref _head.Next, node, node.Next));

     }

     public void Push(T item)

     {

       Node<T> node = new Node<T>();

       node.Item = item;

       SpinWait spin = new SpinWait();

       while (true)

       {

         Node<T> oldHead = _head;

         node.Next = oldHead.Next;

         if (Interlocked.CompareExchange(ref _head, node, oldHead) == oldHead)

           break;

         spin.SpinOnce();

       }

     }

   int yieldsSoFar = (m_count >=  ? m_count -  : m_count);

   if ((yieldsSoFar % ) == ( - ))

   {

     Thread.Sleep();

   }

   else if ((yieldsSoFar % ) == ( - ))

   {

     Thread.Sleep();

   }

   else

   {

     Thread.Yield();

   }

   // A stack that uses CAS operations internally to maintain

   // thread-safety in a lock-free manner. Attempting to push

   // or pop concurrently from the stack will not trigger waiting,

   // although some optimistic concurrency and retry is used,

   // possibly leading to lack of fairness and/or live-lock.

   // The stack uses spinning and back-off to add some randomization,

   // in hopes of statistically decreasing the possibility of live-lock.

   //

   // Note that we currently allocate a new node on every push.

   // This avoids having to worry about potential ABA issues,

   // since the CLR GC ensures that a memory address cannot be

   // reused before all references to it have died.

   /// <summary>

   /// Represents a thread-safe last-in, first-out collection of objects.

   /// </summary>

   public class ConcurrentStack<T>

   {

     // A volatile field should not normally be passed using a ref or out parameter,

     // since it will not be treated as volatile within the scope of the function.

     // There are exceptions to this, such as when calling an interlocked API.

     // As with any warning, you may use the #pragma warning to disable this warning

     // in those rare cases where you are intentionally using a volatile field

     // as a reference parameter.

 #pragma warning disable 420

     /// <summary>

     /// A simple (internal) node type used to store elements

     /// of concurrent stacks and queues.

     /// </summary>

     private class Node

     {

       internal readonly T m_value; // Value of the node.

       internal Node m_next;        // Next pointer.

       /// <summary>

       /// Constructs a new node with the specified value and no next node.

       /// </summary>

       /// <param name="value">The value of the node.</param>

       internal Node(T value)

       {

         m_value = value;

         m_next = null;

       }

     }

     // The stack is a singly linked list, and only remembers the head.

     private volatile Node m_head;

     /// <summary>

     /// Inserts an object at the top of the stack.

     /// </summary>

     /// <param name="item">The object to push onto the stack.

     /// The value can be a null reference for reference types.

     /// </param>

     public void Push(T item)

     {

       // Pushes a node onto the front of the stack thread-safely.

       // Internally, this simply swaps the current head pointer

       // using a (thread safe) CAS operation to accomplish lock freedom.

       // If the CAS fails, we add some back off to statistically

       // decrease contention at the head, and then go back around and retry.

       Node newNode = new Node(item);

       newNode.m_next = m_head;

       if (Interlocked.CompareExchange(

         ref m_head, newNode, newNode.m_next) == newNode.m_next)

       {

         return;

       }

       // If we failed, go to the slow path and loop around until we succeed.

       SpinWait spin = new SpinWait();

       // Keep trying to CAS the existing head with

       // the new node until we succeed.

       do

       {

         spin.SpinOnce();

         // Reread the head and link our new node.

         newNode.m_next = m_head;

       }

       while (Interlocked.CompareExchange(

         ref m_head, newNode, newNode.m_next) != newNode.m_next);

     }

     /// <summary>

     /// Attempts to pop and return the object at the top of the stack.

     /// </summary>

     /// <param name="result">

     /// When this method returns, if the operation was successful,

     /// result contains the object removed.

     /// If no object was available to be removed, the value is unspecified.

     /// </param>

     /// <returns>true if an element was removed and returned

     /// from the top of the stack successfully; otherwise, false.</returns>

     public bool TryPop(out T result)

     {

       // Capture the original value from memory

       Node head = m_head;

       // Is the stack empty?

       if (head == null)

       {

         result = default(T);

         return false;

       }

       if (Interlocked.CompareExchange(

         ref m_head, head.m_next, head) == head)

       {

         result = head.m_value;

         return true;

       }

       // Fall through to the slow path.

       SpinWait spin = new SpinWait();

       // Try to CAS the head with its current next.

       // We stop when we succeed or when we notice that

       // the stack is empty, whichever comes first.

       int backoff = ;

       // avoid the case where TickCount could return Int32.MinValue

       Random r = new Random(Environment.TickCount & Int32.MaxValue);

       while (true)

       {

         // Capture the original value from memory

         head = m_head;

         // Is the stack empty?

         if (head == null)

         {

           result = default(T);

           return false;

         }

         // Try to swap the new head.  If we succeed, break out of the loop.

         if (Interlocked.CompareExchange(

           ref m_head, head.m_next, head) == head)

         {

           result = head.m_value;

           return true;

         }

         // We failed to CAS the new head.  Spin briefly and retry.

         for (int i = ; i < backoff; i++)

         {

           spin.SpinOnce();

         }

         // Arbitrary number to cap back-off.

         backoff = spin.NextSpinWillYield ? r.Next(, ) : backoff * ;

       }

     }

     /// <summary>

     /// Gets a value that indicates whether the stack is empty.

     /// </summary>

     /// <value>true if the stack is empty; otherwise, false.</value>

     public bool IsEmpty

     {

       // Checks whether the stack is empty. Clearly the answer

       // may be out of date even prior to

       // the function returning (i.e. if another thread

       // concurrently adds to the stack). It does

       // guarantee, however, that, if another thread

       // does not mutate the stack, a subsequent call

       // to TryPop will return true

       // -- i.e. it will also read the stack as non-empty.

       get { return m_head == null; }

     }

     /// <summary>

     /// Gets the number of elements contained in the stack.

     /// </summary>

     /// <value>The number of elements contained in the stack.</value>

     public int Count

     {

       // Counts the number of entries in the stack.

       // This is an O(n) operation. The answer may be out of date before

       // returning, but guarantees to return a count that was once valid.

       // Conceptually, the implementation snaps a copy of the list and

       // then counts the entries, though physically this is not

       // what actually happens.

       get

       {

         int count = ;

         // Just whip through the list and tally up the number of nodes.

         // We rely on the fact that

         // node next pointers are immutable after being en-queued

         // for the first time, even as

         // they are being dequeued. If we ever changed this

         // (e.g. to pool nodes somehow),

         // we'd need to revisit this implementation.

         for (Node curr = m_head; curr != null; curr = curr.m_next)

         {

           // we don't handle overflow, to be consistent with existing

           // generic collection types in CLR

           count++;

         }

         return count;

       }

     }

     /// <summary>

     /// Removes all objects from the this stack.

     /// </summary>

     public void Clear()

     {

       // Clear the list by setting the head to null.

       // We don't need to use an atomic operation for this:

       // anybody who is mutating the head by pushing or popping

       // will need to use an atomic operation to guarantee they

       // serialize and don't overwrite our setting of the head to null.

       m_head = null;

     }

 #pragma warning restore 420

   }