Re: Is enq(Node node) safe?

Hu, Jinsong 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:

The short answer is that all the other code using nodes is aware of this
possibility and copes. My CSJP workshop paper has a brief explanation.
See http://gee.cs.oswego.edu/dl/papers/aqs.pdf

For the best careful explanation I know on this general technique, see
the DISC'04 paper "An Optimistic Approach to Lock-Free FIFO Queues" Edya 
Ladan-Mozes and Nir Shavit. Google says you can find it at
http://www.springerlink.com/index/H84DFEXJFTDAL4P4.pdf

-Doug