Mercurial > pub > ImplabNet
annotate Implab/Parallels/MTQueue.cs @ 80:4f20870d0816 v2
added memory barriers
| author | cin |
|---|---|
| date | Fri, 26 Sep 2014 03:32:34 +0400 |
| parents | 1714fd8678ef |
| children | dc4942d09e74 |
| rev | line source |
|---|---|
| 14 | 1 using System; |
| 2 using System.Collections.Generic; | |
| 3 using System.Linq; | |
| 4 using System.Text; | |
| 5 using System.Threading; | |
| 6 | |
| 7 namespace Implab.Parallels { | |
| 8 public class MTQueue<T> { | |
| 9 class Node { | |
| 10 public Node(T value) { | |
| 11 this.value = value; | |
| 12 } | |
| 13 public readonly T value; | |
| 14 public Node next; | |
| 15 } | |
| 16 | |
| 17 Node m_first; | |
| 18 Node m_last; | |
| 19 | |
| 20 public void Enqueue(T value) { | |
| 80 | 21 Thread.MemoryBarrier(); |
| 22 | |
| 14 | 23 var last = m_last; |
| 24 var next = new Node(value); | |
| 25 | |
| 26 while (last != Interlocked.CompareExchange(ref m_last, next, last)) | |
| 27 last = m_last; | |
| 28 | |
| 29 if (last != null) | |
| 30 last.next = next; | |
| 31 else | |
| 32 m_first = next; | |
| 33 } | |
| 34 | |
| 35 public bool TryDequeue(out T value) { | |
| 36 Node first; | |
| 37 Node next = null; | |
| 38 value = default(T); | |
| 39 | |
| 80 | 40 Thread.MemoryBarrier(); |
| 14 | 41 do { |
| 42 first = m_first; | |
| 43 if (first == null) | |
| 44 return false; | |
| 45 next = first.next; | |
| 46 if (next == null) { | |
| 47 // this is the last element, | |
|
19
e3935fdf59a2
Promise is rewritten to use interlocked operations instead of locks
cin
parents:
14
diff
changeset
|
48 // then try to update the tail |
| 14 | 49 if (first != Interlocked.CompareExchange(ref m_last, null, first)) { |
| 71 | 50 // this is the race condition |
| 14 | 51 if (m_last == null) |
|
19
e3935fdf59a2
Promise is rewritten to use interlocked operations instead of locks
cin
parents:
14
diff
changeset
|
52 // the queue is empty |
| 14 | 53 return false; |
| 71 | 54 // tail has been changed, we need to restart |
| 14 | 55 continue; |
| 56 } | |
| 57 | |
| 58 // tail succesfully updated and first.next will never be changed | |
| 71 | 59 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null |
| 60 // however the parallel writer may update the m_first since the m_last is null | |
| 14 | 61 |
| 71 | 62 // so we need to fix inconsistency by setting m_first to null or if it has been |
| 63 // updated by the writer already then we should just to give up | |
| 14 | 64 Interlocked.CompareExchange(ref m_first, null, first); |
| 65 break; | |
| 66 | |
| 67 } else { | |
| 71 | 68 if (first == Interlocked.CompareExchange(ref m_first, next, first)) |
| 69 // head succesfully updated | |
| 70 break; | |
| 14 | 71 } |
| 72 } while (true); | |
| 73 | |
| 74 value = first.value; | |
| 75 return true; | |
| 76 } | |
| 77 } | |
| 78 } |