Click here to Skip to main content
15,122,379 members
Articles / Programming Languages / C#
Posted 30 Jan 2008

Tagged as


79 bookmarked

Lock Free Queue implementation in C++ and C#

Rate me:
Please Sign up or sign in to vote.
3.15/5 (19 votes)
23 Feb 2008CPOL4 min read
Lock Free Queue implementation in C++ and C#


This article demonstrates implementation of a "lock free" queue in C# and C++. Lock free queues are typically used in multi-threaded architectures to communicate between threads without fear of data corruption or performance loss due to threads waiting to use shared memory. The goal of the article is to familiarize readers with lock free queues and provide a starting point to writing wait-free production architectures. It should be noted that using lock-free queues is only the beginning - a true lock free architecture use a lock free memory allocator. Implementing lock free memory allocators is beyond the scope of this article however.


Recent developments in CPU architecture has necessitated a change in thinking in high performance software architecture - multithreaded software. Communication between threads in multithreaded architecture has traditionally been accomplished using mutexes, critical sections, and locks. Recent research in algorithms and changes in computer architecture has led to the introduction of "wait free", "lock free", or "non-blocking" data structures. The most popular and possibly the most important is the queue, a First In First Out (FIFO) data structure.

The key to the majority of lock free data structures is an instruction known as Compare and Swap (CAS). The flow chart below describes what Compare and Swap does. For the assembler coders out there the instruction is named CMPXCHG on X86 and Itanium architectures. The special thing about this instruction is that it is atomic- meaning that other threads\processes cannot interrupt until it is finished. Operating Systems use atomic operations to implement sychronization - locks, mutexes, semaphores, and critical sections.

Image 1

My code draws on research by Maged M. Michael and Michael L. Scott on non-blocking and blocking concurrent queue algorithms. In fact, an implementation of their queue is now part of the Java concurrency library. Their paper demonstrates why the queue is "linearizable" and "lock free". An implementation of the code in C is available here in tar.gz format. The idea is that pointers are reference counted and checked for consistency in a loop. The reference count is meant to prevent what is referred to the "ABA problem" - if a process or threads reads a value 'A' then attempts a CAS operation, the CAS operation might succeed incorrectly if a second thread or process changes value 'A' to 'B' and then back again to 'A'. If the "ABA" problem never occurs the code is safe because:

  1. The linked list is always connected.
  2. Nodes are only inserted at the end of the linked list and only inserted to a node that has a NULL next pointer.
  3. Nodes are deleted from the beginning of the list because they are only deleted from the head pointer and head always points to the first element of the list.
  4. Head always points to the first element of the list and only changes it's value atomically.

If CAS or similar instructions are not available I suggest using the STL queue or a similar queue with traditional sychronization primitives. Michael and Scott also present a "two lock" queue data structure.

Using the code

UML Diagram of sourceLockFreeQueue.jpg

Using the code provided with this article is simple.

  • C++ class declaration template< class T > class MSQueue
    • Include the "lockfree.h" file. #include <span class="code-string">"LockFreeQ.h"</span>
    • Declare C++ queues like this: MSQueue< int > Q;
    • Add items to the queue: Q.enqueue(i);
    • Remove items from the queue: bool bIsQEmpty = Q.dequeue(i); dequeue returns false if the queue is empty and the value of i would be undefined.
  • C# class declaration namespace Lockfreeq { public class MSQueue<t /> {
    • Include the Lock Free Queue DLL: using Lockfreeq;
    • Declare a C# queue: MSQueue< int > Q = new MSQueue< int >();
    • Add items to the queue: Q.enqueue(i);
    • Remove items from the queue: bool bIsQEmpty = Q.dequeue(ref i); dequeue returns false if the queue is empty and the value of i would be undefined.

Points of Interest

Did you know that Valve Software (makers of Half-Life computer game) have switched to a wait free architecture?


  • This is my first article! (30.1.2008)
  • Revised 21:00 30.1.2008 (Thanks to the early commenters for spotting those mistakes!)
  • Noted need for memory allocator. 31.1.2008
  • Revision to correct inaccuracy with regards to Java Concurrency library.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Idaho Edokpayi
Web Developer EMC Corporation
United States United States
Idaho Edokpayi is a Consultant working in EMC's Microsoft Practice specializing in WSS 3.0, MOSS 07, .NET, and ASP.NET technology. He also likes to write C++, Win32/64 API, and DirectX code in his spare time.

Comments and Discussions

GeneralMy vote of 1 Pin
m1o211-Sep-14 0:29
Memberm1o211-Sep-14 0:29 
Questionbetter than boost spsc_queue? Pin
Oleg Vazhnev29-Aug-14 10:17
MemberOleg Vazhnev29-Aug-14 10:17 
QuestionMSQueue crash problem Pin
adolfsuccess6-Jun-14 4:44
Memberadolfsuccess6-Jun-14 4:44 
GeneralMy vote of 1 Pin
Cygon424-Jun-12 23:26
MemberCygon424-Jun-12 23:26 
GeneralMy vote of 1 Pin
sogard8321-Sep-10 11:03
Membersogard8321-Sep-10 11:03 
GeneralRe: My vote of 1 Pin
wwwllg24-Apr-12 2:52
Memberwwwllg24-Apr-12 2:52 
GeneralMy vote of 1 Pin
MatthysDT19-Jul-10 0:49
MemberMatthysDT19-Jul-10 0:49 
GeneralMy vote of 1 Pin
smek215-May-10 7:19
Membersmek215-May-10 7:19 
QuestionRe: My vote of 1 Pin
LoaderAll14-Jun-10 0:23
MemberLoaderAll14-Jun-10 0:23 
GeneralMy vote of 1 Pin
Bharat Karia5-Feb-10 8:38
MemberBharat Karia5-Feb-10 8:38 
GeneralMy vote of 1 Pin
AAO29-Jul-09 19:10
MemberAAO29-Jul-09 19:10 
Generalstress test core Pin
fly_horse8-May-09 3:21
Memberfly_horse8-May-09 3:21 
GeneralC# Test Crashing Pin
irares16-Apr-09 6:11
Memberirares16-Apr-09 6:11 
Generalstress test not working Pin
hagai_sela28-Jul-08 2:08
Memberhagai_sela28-Jul-08 2:08 
GeneralRe: stress test not working Pin
cool_man_from_Russia23-Mar-09 23:25
Membercool_man_from_Russia23-Mar-09 23:25 
GeneralHello Pin
nidal1020028-Apr-08 7:38
Membernidal1020028-Apr-08 7:38 
GeneralStill a bug. [modified] Pin
Patrick Twohig7-Apr-08 15:25
MemberPatrick Twohig7-Apr-08 15:25 
GeneralRe: Still a bug. Pin
Idaho Edokpayi5-May-08 16:36
MemberIdaho Edokpayi5-May-08 16:36 
QuestionIs there still a chance of bug? Pin
dhbid26-Feb-08 23:00
Memberdhbid26-Feb-08 23:00 
AnswerRe: Is there still a chance of bug? Pin
Idaho Edokpayi27-Feb-08 3:35
MemberIdaho Edokpayi27-Feb-08 3:35 
GeneralRe: Is there still a chance of bug? Pin
LanceDiduck18-Apr-08 10:30
MemberLanceDiduck18-Apr-08 10:30 
GeneralJava Concurrency Library Pin
Mike O'Neill21-Feb-08 15:09
MemberMike O'Neill21-Feb-08 15:09 
GeneralRe: Java Concurrency Library Pin
Idaho Edokpayi23-Feb-08 15:45
MemberIdaho Edokpayi23-Feb-08 15:45 
QuestionCritical Section on the Stack? How Can It Provide Protection/Synchronization? Pin
Mike O'Neill20-Feb-08 16:11
MemberMike O'Neill20-Feb-08 16:11 
AnswerRe: Critical Section on the Stack? How Can It Provide Protection/Synchronization? Pin
Idaho Edokpayi23-Feb-08 15:48
MemberIdaho Edokpayi23-Feb-08 15:48 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.