aspose file tools*
The moose likes Threads and Synchronization and the fly likes Implement concurrent queue with CAS Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "Implement concurrent queue with CAS" Watch "Implement concurrent queue with CAS" New topic
Author

Implement concurrent queue with CAS

Ranadhir Nag
Ranch Hand

Joined: Mar 09, 2006
Posts: 138
Heres an attempt at writing a concurrent linked implementation using CAS.THe glitch is that the head node moves along with the tail - though I have not done anythig to casue it to do so. It may just be a careless mistake - but would appreciate help in where I am going wrong. As elements are added at the tail and the tail is shifted - so does the head,whereas it is not supposed to do so.

..... .... And the Node member class:
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4174
    
  21

Ranadhir Nag wrote:... though I have not done anythig to casue it to do so....


That isn't true. You should remember that an application will only do what you tell it to. If your code does something it is because you told it to. If you realize that it makes troubleshooting easier (it goes from trying to find some ethereal wrongness to finding the task you wrote incorrectly).



You assign the same Object (AtomicReference) to both head and tail. You then modify the contents of the Object in tail. Since head points to the same Object, head sees the same change.


Steve
Ranadhir Nag
Ranch Hand

Joined: Mar 09, 2006
Posts: 138
Is that a complete explanation of this behaviour?
It is true that I am modifying 'ref' to update its next element.
However,it is only 'tail' which is instructed to refer to a separate element down the chain.
Head should still keep pointing to the same 'ref' - albeit a 'ref' with a modified 'next' element.

And,I get the correct behavior if I use a volatile instead of atomicreference - but it isn't fun till we know why something is not working.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4174
    
  21

Ranadhir Nag wrote:Is that a complete explanation of this behaviour?
It is true that I am modifying 'ref' to update its next element.
However,it is only 'tail' which is instructed to refer to a separate element down the chain.


AtomicReference is an Object. The AtomicReference has a stored value, which is a reference to a Node. When you do

You change the value value stored inside the AtomicReference object so that it points to a different Node. Since both head and tail point to the same AtomicReference they both see the same change in the value stored by that single AtomicReference Object.

Head should still keep pointing to the same 'ref'


It is. It is pointing the same 'ref' it was pointing at the beginning, and the same one tail is pointing at.

albeit a 'ref' with a modified 'next' element.

No, it is pointing at the 'ref' which is pointing at a different Node.

And,I get the correct behavior if I use a volatile instead of atomicreference

Volatile is a modifier for a variable. AtomicReference is an Object. They are two completely different things, there is no comparison or interchanging between them. It is impossible to comment on your 'volatile' code because it would have to be using a completely different bit code for assignment. If you show the code which works, then perhaps we can discuss further.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4174
    
  21

Just to put it a different way. what you are doing with the AtomicReference is equivalent to doing this:

Since both head and tail refer to the same array, changing the value(s) stored in the array means both head and tail see the changes in that array.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Implement concurrent queue with CAS