annotate Implab/Parallels/MTQueue.cs @ 169:54270c2f29f2 ref20160224

DFA refactoring
author cin
date Thu, 03 Mar 2016 08:41:02 +0300
parents 4c945d94b9ab
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
93
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
1 using System.Threading;
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
2 using System.Collections.Generic;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
3 using System;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
4 using System.Collections;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
5
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
6 namespace Implab.Parallels {
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
7 public class MTQueue<T> : IEnumerable<T> {
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
8 class Node {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
9 public Node(T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
10 this.value = value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
11 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
12 public readonly T value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
13 public Node next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
14 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
15
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
16 Node m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
17 Node m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
18
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
19 public void Enqueue(T value) {
80
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
20 Thread.MemoryBarrier();
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
21
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
22 var last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
23 var next = new Node(value);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
24
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
25 // Interlocaked.CompareExchange implies Thread.MemoryBarrier();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
26 // to ensure that the next node is completely constructed
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
27 while (last != Interlocked.CompareExchange(ref m_last, next, last))
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
28 last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
29
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
30 if (last != null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
31 last.next = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
32 else
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
33 m_first = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
34 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
35
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
36 public bool TryDequeue(out T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
37 Node first;
93
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
38 Node next;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
39 value = default(T);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
40
80
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
41 Thread.MemoryBarrier();
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
42 do {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
43 first = m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
44 if (first == null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
45 return false;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
46 next = first.next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
47 if (next == null) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
48 // this is the last element,
19
e3935fdf59a2 Promise is rewritten to use interlocked operations instead of locks
cin
parents: 14
diff changeset
49 // then try to update the tail
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
50 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
51 // this is the race condition
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
52 if (m_last == null)
19
e3935fdf59a2 Promise is rewritten to use interlocked operations instead of locks
cin
parents: 14
diff changeset
53 // the queue is empty
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
54 return false;
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
55 // tail has been changed, we need to restart
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
56 continue;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
57 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
58
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
59 // tail succesfully updated and first.next will never be changed
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
60 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
61 // however the parallel writer may update the m_first since the m_last is null
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
62
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
63 // so we need to fix inconsistency by setting m_first to null or if it has been
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
64 // updated by the writer already then we should just to give up
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
65 Interlocked.CompareExchange(ref m_first, null, first);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
66 break;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
67
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
68 }
93
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
69 if (first == Interlocked.CompareExchange(ref m_first, next, first))
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
70 // head succesfully updated
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
71 break;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
72 } while (true);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
73
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
74 value = first.value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
75 return true;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
76 }
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
77
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
78 #region IEnumerable implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
79
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
80 class Enumerator : IEnumerator<T> {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
81 Node m_current;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
82 Node m_first;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
83
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
84 public Enumerator(Node first) {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
85 m_first = first;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
86 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
87
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
88 #region IEnumerator implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
89
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
90 public bool MoveNext() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
91 m_current = m_current == null ? m_first : m_current.next;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
92 return m_current != null;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
93 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
94
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
95 public void Reset() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
96 m_current = null;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
97 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
98
98
4c945d94b9ab fix MTQueue syntax error
cin
parents: 97
diff changeset
99 object IEnumerator.Current {
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
100 get {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
101 if (m_current == null)
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
102 throw new InvalidOperationException();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
103 return m_current.value;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
104 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
105 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
106
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
107 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
108
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
109 #region IDisposable implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
110
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
111 public void Dispose() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
112 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
113
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
114 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
115
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
116 #region IEnumerator implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
117
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
118 public T Current {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
119 get {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
120 if (m_current == null)
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
121 throw new InvalidOperationException();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
122 return m_current.value;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
123 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
124 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
125
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
126 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
127 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
128
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
129 public IEnumerator<T> GetEnumerator() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
130 return new Enumerator(m_first);
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
131 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
132
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
133 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
134
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
135 #region IEnumerable implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
136
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
137 IEnumerator IEnumerable.GetEnumerator() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
138 return GetEnumerator();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
139 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
140
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
141 #endregion
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
142 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
143 }