logo       

Is enq(Node node) safe?: msg#00008

java.jsr.166-concurrency

Subject: Is enq(Node node) safe?

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;
}
}
}
}


<Prev in Thread] Current Thread [Next in Thread>
Google Custom Search

News | FAQ | advertise