--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Parallels/MTQueue.cs	Wed Nov 06 17:49:12 2013 +0400
@@ -0,0 +1,74 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading;
+
+namespace Implab.Parallels {
+    public class MTQueue<T> {
+        class Node {
+            public Node(T value) {
+                this.value = value;
+            }
+            public readonly T value;
+            public Node next;
+        }
+
+        Node m_first;
+        Node m_last;
+
+        public void Enqueue(T value) {
+            var last = m_last;
+            var next = new Node(value);
+
+            while (last != Interlocked.CompareExchange(ref m_last, next, last))
+                last = m_last;
+
+            if (last != null)
+                last.next = next;
+            else
+                m_first = next;
+        }
+
+        public bool TryDequeue(out T value) {
+            Node first;
+            Node next = null;
+            value = default(T);
+
+            do {
+                first = m_first;
+                if (first == null)
+                    return false;
+                next = first.next;
+                if (next == null) {
+                    // this is the last element,
+                    // then try to update tail
+                    if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
+                        // this is inconsistent situation which means that the queue is empty
+                        if (m_last == null)
+                            return false;
+                        // tail has been changed, that means that we need to restart
+                        continue; 
+                    }
+
+                    // tail succesfully updated and first.next will never be changed
+                    // other readers will fail due to inconsistency m_last != m_fist, but m_first.next == null
+                    // but the writer may update the m_first since the m_last is null
+
+                    // so we need to fix inconsistency by setting m_first to null, but if it already has been
+                    // updated by a writer then we should just give up
+                    Interlocked.CompareExchange(ref m_first, null, first);
+                    break;
+
+                } else {
+                        if (first == Interlocked.CompareExchange(ref m_first, next, first))
+                            // head succesfully updated
+                            break;
+                }
+            } while (true);
+
+            value = first.value;
+            return true;
+        }
+    }
+}