annotate Implab/Parallels/MTQueue.cs @ 81:2c5631b43c7d v2

dispatch pool rewritten
author cin
date Fri, 26 Sep 2014 20:44:01 +0400
parents 4f20870d0816
children dc4942d09e74
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
1 using System;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
2 using System.Collections.Generic;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
3 using System.Linq;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
4 using System.Text;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
5 using System.Threading;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
6
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
7 namespace Implab.Parallels {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
8 public class MTQueue<T> {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
9 class Node {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
10 public Node(T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
11 this.value = value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
12 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
13 public readonly T value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
14 public Node next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
15 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
16
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
17 Node m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
18 Node m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
19
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
20 public void Enqueue(T value) {
80
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
21 Thread.MemoryBarrier();
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
22
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
23 var last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
24 var next = new Node(value);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
25
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
26 while (last != Interlocked.CompareExchange(ref m_last, next, last))
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
27 last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
28
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
29 if (last != null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
30 last.next = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
31 else
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
32 m_first = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
33 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
34
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
35 public bool TryDequeue(out T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
36 Node first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
37 Node next = null;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
38 value = default(T);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
39
80
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
40 Thread.MemoryBarrier();
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
41 do {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
42 first = m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
43 if (first == null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
44 return false;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
45 next = first.next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
46 if (next == null) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
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
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
49 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
50 // this is the race condition
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
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
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
53 return false;
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
54 // tail has been changed, we need to restart
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
55 continue;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
56 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
57
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
58 // tail succesfully updated and first.next will never be changed
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
59 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
60 // however the parallel writer may update the m_first since the m_last is null
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
61
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
62 // 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
63 // updated by the writer already then we should just to give up
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
64 Interlocked.CompareExchange(ref m_first, null, first);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
65 break;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
66
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
67 } else {
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
68 if (first == Interlocked.CompareExchange(ref m_first, next, first))
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
69 // head succesfully updated
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
70 break;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
71 }
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 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
77 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
78 }