-
Notifications
You must be signed in to change notification settings - Fork 12
/
Copy pathALGORITHMS.txt
144 lines (110 loc) · 6.64 KB
/
ALGORITHMS.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*
Lock free LIFO stack with ABA prevention. a.k.a. "IBM Freelist".
see:
International Business Machines Corporation,
"IBM System/370 Extended Architecture, Principles of Operation,"
Publication Number SA22-7085-0, File Number 5370-01. First Edition, March 1983.
(See Appendix A, pp. A-44 to A-45, "Free-pool Manipulation.")
R.K.Treiber. "Systems Programming: Coping with Parallelism".
RJ 5118, IBM Almaden Research Center, April 1986
Maged M. Michael, Michael L. Scott
"Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors"
Department of Computer Science University of Rochester, Rochester, NY 14627-0226, March 1997.
D. Fober, S. Letz, Y. Orlarey
"Lock-Free Techniques for Concurrent Access to Shared Objects,"
Actes des Journées d'Informatique Musicale JIM2002, Marseille GMEM 2002 Pages 143--150.
NOTE: there is a 2003 revision of this paper.
**The FIFO in this paper is suspect, the paper is mentioned here only for the LIFO.**
See also:
Maged M. Michael
"The Balancing Act of Choosing Nonblocking Features"
ACM Queue vol. 11, no. 7
http://queue.acm.org/detail.cfm?id=2513575
*/
/*
IBM Freelist LIFO Pseudocode from Michael and Scott 1997
Figure 1: Structure and operation of Treiber’s non-blocking concurrent stack algorithm
structure pointer_t { ptr: pointer to node_t, count: unsigned integer}
structure node_t { value: data type, next: pointer_t }
structure stack_t { Top: pointer_t }
INITIALIZE(S: pointer to stack_t)
S->Top.ptr = NULL # Empty stack. Top points to NULL
PUSH(S: pointer to stack_t, value: data type)
node = new node() # Allocate a new node from the free list
node->value = value # Copy stacked value into node
node->next.ptr = NULL # Set next pointer of node to NULL
repeat # Keep trying until Push is done
top = S->Top # Read Top.ptr and Top.count together
node->next.ptr = top.ptr # Link new node to head of list
until CAS(&S->Top, top, [node, top.count+1]) # Try to swing Top to new node
POP(S: pointer to stack_t, pvalue: pointer to data type): boolean
repeat # Keep trying until Pop is done
top = S->Top # Read Top
if top.ptr == NULL # Is the stack empty?
return FALSE # The stack was empty, couldn't pop
endif
until CAS(&S->Top, top, [top.ptr->next.ptr, top.count+1]) # Try to swing Top to the next node
*pvalue = top.ptr->value # Pop is done. Read value
free(top.ptr) # It is safe now to free the old node
return TRUE # The stack was not empty, pop succeeded
In general we use links embedded in the client node structures rather than allocating separate nodes.
*/
/*
Version of IBM Freelist LIFO storing nodes rather than values.
Modified version of Figure 1 pseudocode from Michael and Scott 1997 (see above).
structure pointer_t { ptr: pointer to node_t, count: unsigned integer}
structure node_t { value: data type, next: pointer to node_t }
structure stack_t { Top: pointer_t }
INITIALIZE(S: pointer to stack_t)
S->Top.ptr = NULL # Empty stack. Top points to NULL
PUSH(S: pointer to stack_t, node: pointer to node_t)
node->next = NULL # Set next pointer of node to NULL
repeat # Keep trying until Push is done
top = S->Top # Read Top.ptr and Top.count together
node->next = top.ptr # Link new node to head of list
until CAS(&S->Top, top, [node, top.count+1]) # Try to swing Top to new node
POP(S: pointer to stack_t): pointer to node_t)
repeat # Keep trying until Pop is done
top = S->Top # Read Top
if top.ptr == NULL # Is the stack empty?
return NULL # The stack was empty, couldn't pop
endif
until CAS(&S->Top, top, [top.ptr->next, top.count+1]) # Try to swing Top to the next node (*)
return top # The stack was not empty, pop succeeded
NOTE: at line (*) it is possible that the node pointed to by /top.ptr/
has already been popped by another thread, in which case (*top.ptr).next may
be written by another thread concurrently with the read of top.ptr->next at (*),
Therefore:
(1) to avoid data races node_t::next must be atomic, and
(2) to avoid a strict aliasing violation, the type of node_t::next must
be stable (e.g. no reconstructing the storage of node to a different type).
See also: https://stackoverflow.com/questions/46415027/c-treiber-stack-and-atomic-next-pointers
*/
/*
Reversed IBM Freelist FIFO
I learnt of the reversed IBM Freelist FIFO algorithm from Joe Seigh,
posted to comp.programming.threads, July 1, 2005:
https://groups.google.com/d/msg/comp.programming.threads/D6_l9ShwBAc/h8sHJQjbpUkJ
Joe Seigh wrote:
> Way back, I came up with a scheme where you make the queue a lock-free
> LIFO stack using compare and swap. The single reader just grabbed the
> entire queue using compare and swap, reversed order making it FIFO
> and worked off of that util it was empty and then repeated the whole
> process by grabbing the shared LIFO stack again.
The algorithm was reinvented by Chris Chochran, posted to the
Scalable Sychronisation Algorithms group in on September 17, 2008:
https://groups.google.com/d/msg/lock-free/i0eE2-A7eIA/ha8oHpqKxqAJ
It was at this point that I first saw Dmitry Vyukov call the technique "Reversed IBM Freelist":
https://groups.google.com/d/msg/lock-free/i0eE2-A7eIA/g745KEEx2JIJ
Pop-all LIFO Queue
The part of the Reversed IBM Freelist that handles push and pop-all operations
can be factored as a separate object. (and used as-is if FIFO order is not needed).
The pop-all operation can be implemented using an atomic-swap operation.
No CAS or ABA protection is needed.
In response to Joe Seigh's quote above, Chris M. Thomasson posted
an implementation of the pop-all LIFO using atomic swap:
https://groups.google.com/forum/#!msg/comp.programming.threads/D6_l9ShwBAc/i7loHLS_WaMJ
and more recently, here:
https://groups.google.com/d/msg/comp.arch/RAm2iXLlCu4/ksBWXCJ7D60J
Chris calls the pop_all() operation flush().
*/