I think the premise that both threads can succeed in setting the head is
false. One will succeed, the other will fail. The compareAndSetHead
call uses an atomic compare-and-set instruction to set the head only if
it is currently null. (Actually, I'm just guessing here -- if I'm wrong
I'm sure someone will correct me.)
Luke
jhu@xxxxxxxx wrote:
Hi,
Can anyone prove that I am wrong? While I review the code for
AbstractQueuedSynchronizer Node's enq method, I have a concern this may mess
up in some multi-thread scenario. Actually, this code logic is used almost
everywhere, I think I do not understand it correctly.
For example, if two threads do the enq at the same time, one thread
reaches line 8 compareAndSetHead(h) and succeeds, while before it reaches
line 9, for whatever reason, CPU decided this thread should sleep for a
while, let other threads to run. Then second thread comes in, since tail is
still null, reaches Line 8, also succeed, reaches line 9, changed tail and
return. Then the first thread wakes up, execute line 9 which changes the
tail, then we can see the tail is not the true tail:
[node0]->[node1]-[node2]
^ ^
| |
head tail
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) { // Must initialize
Node h = new Node(); // Dummy header
h.next = node;
node.prev = h;
if (compareAndSetHead(h)) { // Line 8
tail = node; // Line 9
return h;
}
}
else {
node.prev = t;
if (compareAndSetTail(t, node)) { // line 15
t.next = node; // line 16
return t;
}
}
}
}
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@xxxxxxxxxxxxxxxxxxxx
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
| 