{, Z9 o3 M; d4 @) t
}
; g3 B8 V. E3 N- L- y2 v a7 _3 J void push(Node* val)+ r0 W8 A" G+ s3 l" n$ }- u( U
{
1 R5 ~+ p# Z2 P/ A for (;;)2 N. A% m% a9 I0 l! J& m. x5 m2 u
{# v! e; f, N' ]; s
Node* head = m_head;
* V- q" N, I% ?$ p) P' C val->prev = head;
. j6 X" W! t3 R5 ? if (InterlockedCompareExchangePointer((PVOID*)&m_head, val, head) == head)
1 R5 o* m) q, y return;2 r4 g0 c; M6 j4 e
}
( A. I, g$ \2 x2 ~ }/ G" u3 A3 x7 T5 s k
Node* pop()8 \7 i; ^# w/ l( [! H
{
" d# ]( z$ m+ S* d. S+ ?* O3 f for (;;): ]) \# T; v, a( O
{5 s' j" x y: ?2 v7 J' w
Node* head = m_head;
+ X' c g# a+ y1 H1 m/ ` if (head == NULL)3 Z' z) w6 K0 V, v( {- `
return NULL;$ t& p# F4 w; z' e
if (InterlockedCompareExchangePointer((PVOID*)&m_head, head->prev, head) == head)
5 N, C4 G. W6 O# Y9 `4 W1 y3 i/ x return head;
; f- s: {0 [8 G7 O6 h, F! P }/ e1 i9 s3 o- U9 r' Y2 Q" |/ ]
}, w! U g* Y- Y
};- N f& h+ A# m6 }
嗯,看起来挺不错,代码还算优雅。。。不过遗憾的是,严谨的说其实上面的lockfree算法是有问题的。问题在哪里?在pop算法上。我们看lock范围内的语义:
+ H) F1 u6 w& S* D+ L& U9 | if (InterlockedCompareExchangePointer((PVOID*)&m_head, head->prev, head) == head)4 Y( U1 `: U1 g- u& {, D
return head;$ b2 ^( ]& Q2 D: J; |/ ~8 j5 t% B
这句话用伪代码描述是:/ n4 f. Z3 R; J1 ?. e
lock {3 D, d1 u. }& U" A8 a( \. q+ X
if (m_head == head) {
7 t8 S6 ~* I; o& r m_head = head->prev;5 F% {( |" K/ m, v+ E
return head; |