Article index

Lock-Free What is programming ?

When it comes to Lock-Free When programming , We often associate the concept with Mutex or Lock Connect , Describe how to use these lock structures as little as possible in programming , Reduce the chance of threads blocking each other , To improve application performance . The concept of similarity is also  "Lockless" and "Non-Blocking" etc. . actually , This description only covers Lock-Free Programming Part of . In essence ,Lock-Free Programming only describes the nature of the code , There is no limitation or requirement on how to write the code .

Basically , If a part of the program meets the following conditions, determine the description , Then we call this part of the procedure in line with Lock-Free Of . On the other hand , If a part of the program does not meet the following condition description , It is said that this part of the procedure does not conform to Lock-Free Of .

In that sense ,Lock-Free Medium "Lock" It's not directly related to Mutex or Lock And so on , It describes the possibility that the application is locked for some reason , For example, it might be because of a deadlock (DeadLock)、 Live lock (LiveLock) Or thread scheduling (Thread Scheduling) Leading to preemption of priority, etc .

Lock-Free An important effect of programming is , In a series of interviews Lock-Free In the thread of operation , If a thread is suspended , Then it will never stop other threads from running (Non-Blocking).

Here's a simple program fragment , No mutex structure is used , But it doesn't fit Lock-Free The nature of the requirements of . If you use two threads to execute this code at the same time , When a thread is running in a certain schedule , It's very likely that two threads will fall into a dead loop at the same time , It's blocking each other .

 while (x == )
{
x = - x;
}

So ,Lock-Free The challenge of programming comes not only from the complexity of the task itself , And always focus on insight into the nature of things .

Usually , No one should expect a large application to adopt it all Lock-Free technology , They are all used in the design of classes with specific requirements Lock-Free technology . for example , If you need one Stack Class should deal with the scenario of multithreading concurrent access , have access to Lock-Free Related technology implementation ConcurrentStack class , In its Push and Pop Operation of the specific implementation . therefore , In the use of Lock-Free Before technology , Some software engineering costs need to be considered in advance :

  • Lock-Free Technology can easily be misused , It's not easy to realize in the later maintenance of the code , So it's very easy to introduce Bug, And like this Bug It's also very difficult to locate .
  • Lock-Free The details of the technology depend on the memory system model 、 Compiler optimization 、CPU Architecture, etc , And this is using Lock The mechanism is irrelevant , So it also increases the difficulty of understanding and maintenance .

Lock-Free Programming technology

When we're ready to meet Lock-Free Non blocking conditions in programming , There are a number of techniques and methods available , Such as atomic operation (Atomic Operations)、 memory barriers (Memory Barrier)、 avoid ABA problem (Avoiding ABA Problem) etc. . So how do we decide when and which technology to use ? You can judge by the guidance in the figure below .

Read rewrite atomic operation (Atomic Read-Modify-Write Operations)

Atomic manipulation (Atomic Operations) It can be regarded as indivisible when operating memory (Indivisible), Other threads will not interrupt the operation , No operation is only partially completed . In modern times CPU On the processor , Many operations have been designed to be atomic , For example, aligned reading (Aligned Read) And align to write (Aligned Write) etc. .

Read-Modify-Write(RMW) The design of operations makes it atomic to perform more complex transaction operations , When multiple writers want to modify the same memory , Ensure that only one operation is performed at a time .

for example , Common addition operations on integer values RMW operation :

  • stay Win32 There is _InterlockedIncrement
  • stay iOS There is OSAtomicAdd32
  • stay C++11 There is std::atomic<int>::fetch_add

RMW Operate in different CPU The family is supported in different ways .

For example, in x86 Under the architecture , adopt LOCK Instruction prefixes enable many instruction operations (ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, and XCHG) It becomes an atomic operation , among CMPXCHG Instructions can be used to implement CAS operation .

Here's how to use LOCK and CMPXCHG To achieve CAS Code examples of operations .

__inline int CAS(volatile int & destination, int exchange, int comperand)
{
__asm {
MOV eax, comperand
MOV ecx, exchange
MOV edx, destination
LOCK CMPXCHG[edx], ecx /* If eax And edx equal , be ecx send edx And ZF Set up 1;
otherwise edx send ecx, And ZF clear 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;

Compare-And-Swap loop (CAS Loops)

stay Win32 On the platform ,CAS Operations have a set of native implementations , for example _InterlockedCompareExchange etc. . Yes RMW Perhaps the most common discussion of manipulation is , How to use CAS Loops To complete the atomic processing of the transaction .

Usually , The developer will design to execute it repeatedly in a loop CAS Operation to attempt to complete a transaction operation . This process is divided into 3 Step :

  1. Read the original value from the specified memory location ;
  2. Calculate a new value based on the original value read ;
  3. Detect if the memory location is still the original value , Write the new value to the memory location ;

for example , towards LockFreeStack Press in a new node :

 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;
}
}

The loop operation in the above code still conforms to Lock-Free Conditions require , Because if  _InterlockedCompareExchange Condition test failed , This means that another thread has successfully modified the value , The current thread can continue to judge in the next cycle to complete the operation .

ABA problem (ABA Problem)

In the realization of CAS Loops when , When there are multiple threads interleaving the shared memory address , If the implementation design is not correct , It will be possible to encounter  ABA problem .

If a thread reads the same memory address twice , And two reads get the same value , By judgment  " Same value " To determine  " The value has not changed ". However , Within the time interval between these two read operations , Another thread may have modified the value , This is equivalent to cheating the previous thread , Make it think that " The value has not changed ", In fact, the value has been tampered with .

Here is ABA The process of the problem :

  1. T1 The thread reads the value from the shared memory address A;
  2. T1 Threads are preempted , Threads T2 Began to run ;
  3. T2 The value in the shared memory address is determined by the thread A Modified into B, And then revise it back to  A;
  4. T1 The thread continues to execute , Read the shared memory address and the value is still A, Think that there is no change and then continue to carry out ;

because T1 Don't know the value read twice A Has been " Recessive " It's been modified , So it may produce unexpected results .

for example , Use List To hold the Item, If you take a Item from List Removed and released its memory address from , Then recreate a new Item, And add it to List in , Because of optimization and other factors , It's possible to create new Item The memory address of is the same as the one deleted earlier Item The memory address of is the same , Leading to a new Item The pointer to the old is therefore equivalent to pointing to the old Item The pointer to , This will trigger ABA problem .

Take a more life like example :

The local tyrant took one full of money Hermes Black wallet, go to the bar and drink , Put your wallet on the bar , Turn around and chat with your friends , The thief picked up his wallet while the local tyrant turned around , Take the money out of your wallet and put it in a napkin to keep it thick , And put it back in place , Thieves have professional ethics , Only steal money, not ID card , The local tyrant turned his head and found that his wallet was still there , And he's familiar with Hermes Black Wallet , There's no change in thickness , So the local tyrant thinks nothing happened , Keep talking to friends , Until when I checked out, I found that the money in my wallet had been changed into napkins .

therefore , I think ABA Problems can also be called " The problem of subcontracting ". So how to solve " The problem of subcontracting " Well ? Local tyrants began to think of ways .

The first way that local tyrants think about is , Find a rope to tie the wallet to your arm , You have to cut the rope to open the wallet , Cut the rope and you'll find . This is actually Load-Link/Store-Conditional (LL/SC)  The work done in the architecture .

Another way that local tyrants think about is , Put a display on your wallet , Every time I turn on the wallet, the number on the display will +1, In this way, the local tyrant can record the number on the display screen before turning his head , After you turn your head, you can confirm whether the number has changed , I know if the wallet has been opened . This is actually x86/64 Architecture Double-Word CAS Tagging Work done .

Nouveau riche is as like as two peas , Just switch the whole purse , What if I lose my bank card and ID card , The local tyrant decided to buy a unique wallet in the universe , Unless you burn it , Otherwise, there won't be the same wallet again . This is actually Garbage Collection (GC) Work done .

Memory model (Memory Model) The impact on fine-grained locks

In a multithreaded system , When multiple threads access shared memory at the same time , We need a specification to constrain how different threads interact with memory , This specification is called the memory model (Memory Model).

Sequential consistent memory model (Sequential Consistency Memory Model) Is one of the memory model specifications . In this model , Memory remains independent of the thread accessing it , Through a controller (Memory Controller) To keep in touch with threads , To read and write . In the same thread , The order of read and write operations is the order specified by the code . But when there are multiple threads , Read and write operations will be interleaved with read and write operations in other threads .

As shown in the figure above ,Thread 1 In writing Value and Inited Value , and Thread 2 In reading Inited and Value Value to Ri and Rv in . Due to a rearrangement in the memory controller (Memory Reordering), There are many possible outcomes , As shown in the following table .

The sequential consistent memory model is very intuitive , It's easy to understand . But actually , Due to the limitation of the model in memory hardware implementation efficiency , Leading to commercial CPU The architecture basically doesn't follow this model . A more realistic multiprocessor memory model is more similar to the effect shown in the figure below .

in other words , Every CPU Every core has its own cache model , For example, in the figure above Level 1 Cache and Level 2 Cache, To cache recently used data , To improve access efficiency . meanwhile , All written data is buffered to Write Buffer Buffer zone , Before the data is flushed to the cache , The processor can continue to process other instructions . This architecture improves the efficiency of the processor , But it also means that we should not only focus on Memory, At the same time, pay attention to Buffer and Cache, Added complexity .

The above figure shows the cache inconsistency problem (Incoherent Caches), When main memory (Main Memory) There is a store of Value=5,Inited=0 when ,Processor 1 There's new writing Cache The value of was not refreshed in time to Memory The problem of , and  Processor 2 Then there is a read Cache The problem of the old values in .

obviously , As mentioned above, memory rearrangement and caching mechanisms can cause confusion , So the lock mechanism will be introduced into the actual memory model (Locking Protocol). Generally, the memory model follows three rules :

  • Rule 1: When a thread is running in isolation , Its behavior will not change ;
  • Rule 2: The read operation cannot be moved before the get lock operation ;
  • Rule 3: The write operation cannot be moved after the lock release operation ;

Rule 3 Guaranteed before releasing the lock , All write operations have been completed .Rule 2 To ensure that you want to read memory, you must first get the lock , No more threads will modify memory .Rule 1 To ensure that the operation behavior after obtaining the lock is sequential .

In embodying the locking mechanism (Locking Protocol) At the same time , We will also be aware of the limitations it brings , That is, it limits the compiler and CPU Freedom to optimize programs .

We know ,.NET Framework follow ECMA standard , and ECMA The standard defines a relatively loose memory access model , Divide memory access into two categories :

  • Regular memory access (Ordinary Memory Access)
  • Volatile memory access (Volatile Memory Access)

among , Volatile memory access is designed for "volatile" Design , It contains the following two rules :

  1. Read and write operations cannot be moved to volatile-read Before ;
  2. Read and write operations cannot be moved to volatile-write after ;

For those who don't use "lock" and "volatile" Program fragment of , Compilers and hardware can make any reasonable optimization for normal memory access . On the contrary , Memory system only needs to deal with  "lock" and "volatile" Take measures such as cache invalidation and buffer refresh when the system is running , This greatly improves performance .

Sequential consistency (Sequential Consistency) It describes the relationship between the sequence of program code description and the sequence of memory operation execution . Most programming languages provide support for sequence consistency , For example, in C# Variables can be marked as volatile.

A volatile read has "acquire semantics" meaning that the read is guaranteed to occur prior to any references to memory that occur after the read instruction in the CIL instruction sequence.
A volatile write has "release semantics" meaning that the write is guaranteed to happen after any memory references prior to the write instruction in the CIL instruction sequence.

The following list shows .NET Read and write operations in memory The effect of .

Construct

 Refreshes 

Thread

Cache

Before?

 Flushes 

Thread

Cache

After?

Notes

 Ordinary Read

No

No

Read of a non-volatile field

 Ordinary Write 

No

Yes

Write of a non-volatile field

 Volatile Read

Yes

No

Read of volatile field,

or Thread.VolitelRead

 Volatile Write

No

Yes

Write of volatile field

 Thread.MemoryBarrier 

Yes

Yes

Special memory barrier method

 Interlocked Operations

Yes

Yes

Increment, Add, Exchange, etc.

 Lock Acquire

Yes

No

Monitor.Enter

or entering a lock {} region

 Lock Release

No

Yes

Monitor.Exit

or exiting a lock {} region

Code practice

We need to experience in practice Lock-Free Programming , In order to get insight into the nature of the mechanism , Deepen the understanding . Now we use the implementation stack Stack Class Lock-Free The exploration of programming .

The stack structure is actually FILO First in, then out , There are usually two operations :

  • Push: Push an element toward the top of the stack (Item);
  • Pop: Pop an element from the top of the stack (Item);

Here we choose the single linked list structure (Singly Linked List) To achieve FILO Stack , Every time a new chain header is put on the stack , Every time out of the stack is also the chain header .

Implementation of common stack SimpleStack class

Build an inner class Node To hold Item, And includes Next Reference to point to the next node .

 private class Node<TNode>
{
public Node<TNode> Next;
public TNode Item;
public override string ToString()
{
return string.Format("{0}", Item);
}
}

such , Realization Push The operation is to use the newly pressed node as the head of the new list , To achieve Pop The operation is to take out the head of the chain list and take the next node pointed to as the new chain header .

 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;
}
}

Use the following code , First Push Push 1000 Elements , And then in multithreading Pop Elements .

 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();
}
}

The operation effect is shown in the figure below .

It can be seen from the running results in the figure above , When multiple threads are at the same time Pop Data time , It can happen that looks like the same data item Item By Pop Twice .

Realize the common lock stack SimpleLockedStack class

So for consistency and accuracy , The first way to think of it is to lock it .lock Not only can it protect the instructions in the code region from being rearranged , It can also prevent other threads from modifying data after obtaining the lock .

 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;
}
}
}

After lock up , Obviously, the running results will not go wrong .

Realization Lock-Free The stack LockFreeStack class

But obviously we're more focused on performance , When multiple threads are interleaving Push and Pop In operation ,

  • First of all, we don't want to have a wait lock , If a thread gets a lock and is preempted by a higher priority operation schedule , All threads waiting for the lock are blocked ;
  • Second, we don't want threads to wait too long for locks ;

So prepare to use Lock-Free technology , By introducing CAS Operations are implemented through fine-grained locks . here CAS Use C# Medium Interlocked.CompareExchange Method , The operation is atomic , And there are many overload methods to use .

 private static bool CAS(
ref Node<T> location, Node<T> newValue, Node<T> comparand)
{
return comparand ==
Interlocked.CompareExchange<Node<T>>(
ref location, newValue, comparand);
}

In the realization of CAS Loops when , We use do..while.. Grammar to complete .

 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));
}

such , new LockFreeStack Class is born .

 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);
}
}

The test result of this new class is correct as we imagine .

Realization ConcurrentStack class

That's true LockFreeStack After the class , It's actually satisfied Lock-Free Conditional requirements , Can we do better ?

Let's take a look at the implementation above Push Method :

 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));
}

Found that when CAS When the operation fails , Enter the next cycle immediately . In practice , When CAS When judging failure , Because other threads are changing the same memory data , If we do it again immediately CAS If you decide, you have a higher chance of failure , We need to give the threads that are modifying the data time to complete the operation , So it's better for the current thread to " rest " For a while .

" rest " Operation we choose .NET The lightweight available in (4 Bytes) Thread waiting mechanism SpinWait class .

 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();
}
}

actually SpinOnce() Method is called Thread.SpinWait() And so on , So what did these operations do and how long did it take ?

First ,Thread.SpinWait(N) In the current CPU On a compact cycle N A cycle , Every cycle is sent PAUSE Instructions for CPU, tell CPU Currently performing wait , Don't do anything else . therefore , The key is N What's the value of . stay .NET Implemented in SpinOne According to the measurement of statistical significance , Put the N Depending on the number of calls .

  • First call ,N = 4;
  • Second call ,N = 8;
  • ...
  • The tenth call ,N = 2048;

So in 10 After the first call ?

10 After that SpinOnce No more Spin Operation , It chooses to enter different Yield technological process .

  • Thread.Yield: Call static methods Thread.Yield(), If in the same CPU Core There are threads of the same or lower priority waiting to execute on , Then the current thread gives up the time slice . If no such thread is found , Then the current thread continues to run .
  • Thread.Sleep(0): take 0 Pass to Thread.Sleep(), The resulting behavior is related to Thread.Yield() similar , The only difference is in all CPU Core Same or lower priority threads found on , Not just the current CPU Core. If no such thread is found , Then the current thread continues to run .
  • Thread.Sleep(1): The current thread is really sleeping at this time (Sleep State). Although the designation is 1 millisecond , But depending on the time accuracy of different systems , This operation may cost 10-15 millisecond .

The above three situations are SpinOnce According to the following code to determine the execution of .

 int yieldsSoFar = (m_count >= ? m_count - : m_count);
if ((yieldsSoFar % ) == ( - ))
{
Thread.Sleep();
}
else if ((yieldsSoFar % ) == ( - ))
{
Thread.Sleep();
}
else
{
Thread.Yield();
}

such , We can further optimize it by adding a failure wait , New ConcurrentStack class .

 // 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
}

actually , above ConcurrentStack<T> Class is .NET Framework in System.Collections.Concurrent.ConcurrentStack<T> class The basic realization process of .

Reference material

this paper 《Lock Free Programming 》 By author  Dennis Gao  From blog garden blog , Any human or reptilian reprint without the author's permission is a hooligan .

Lock-Free More articles on programming

  1. Concurrent programming 17—— Lock

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  2. Concurrent programming 01—— ThreadLocal

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  3. Concurrent programming 20—— AbstractQueuedSynchronizer In depth analysis

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  4. Concurrent programming 02—— ConcurrentHashMap

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  5. Concurrent programming 04—— atresia CountDownLatch And fence CyclicBarrier

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  6. Concurrent programming 05—— Callable and Future

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  7. Concurrent programming 06—— CompletionService :Executor and BlockingQueue

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  8. Concurrent programming 10—— Task to cancel And close ExecutorService

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

  9. Concurrent programming 12—— Task cancellation and closing And shutdownNow The limitations of

    Java Concurrent programming practice Catalog Concurrent programming 01—— ThreadLocal Concurrent programming 02—— ConcurrentHashMap Concurrent programming 03—— Blocking queues and producers - Consumer model Concurrent programming 04—— close ...

Random recommendation

  1. h5 Drop down the mobile terminal to select the city

    <!doctype html><html>    <head>            <meta http-equiv="Content-Type& ...

  2. C# Import and export data to Excel General class code for

    Excel File import and export , Need to quote Microsoft Excel 11.0 Object Library ///////////////////////////////////////////////// ...

  3. Median of Two Sorted Arrays(Java)

    seek 2 The median of an array There are many ways But the time complexity varies 1 Using the array copy Method merges two arrays first , Then sort , Find the median import java.lang.reflect.Array; import java.u ...

  4. Fedora Next use Iptux, Chinese code scrambling

    Ubuntu/Fedora Next use Iptux And Windows The next big flying pigeon , Chinese code scrambling Problem description : stay Ubuntu/Fedora Under the installation of Iptux after , Go back to Windows When a file or message is sent on the machine , If there is Chinese , ...

  5. Google Map According to the coordinates Get address information

    using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.X ...

  6. .net c# Regular expressions Balance group / Recursive matching

    original text http://www.cnblogs.com/qiantuwuliang/archive/2011/06/11/2078482.html Balance group / Recursive matching The balanced group grammar introduced here is made up of .Net Fr ...

  7. eclipse How to connect to MySQL In the table !!!!!

    brief introduction : use eclipse Write good code , How can we connect to the database ? For starters , In particular, some inexplicable errors often occur when connecting to the database , Generally speaking , In the final analysis, we made mistakes in the process of connecting to the database . How can we solve this problem ? that ...

  8. compile Android All kinds of mistakes

    The first compilation was successful , The second time Value for 'keystore' is not valid. It must resolve to a single path open proj.android\ant. ...

  9. vs Publish the project webconfig Substitution grammar

    About vs When publishing a project webconfig Substitution grammar is something I've just learned , Write this article as a memo , If you can help others, you can learn webconfig How to replace that would be great . 1. Get acquainted. web Under the project of web.D ...

  10. Now the enterprise uses Java What are the mainstream frameworks for developing

    although Java It's been sung down all the time , But until now Java Software development also adheres to the supremacy . without doubt ,Java Is one of the most popular programming languages . With Java The popularity of object-oriented language and the emergence of multi tier architecture applications , So that the reusability of the application is improved ...