When two or more threads are accessing shared object or shared collection which are not thread safe we usually end up with synchronizing the code. The synchronization helps to make it thread safe but has performance drawbacks. Hence we have set of concurrent collections available in java.util.concurrent which are thread safe and does not required (external)synchronization, which makes them extremely fast as compared to their synchronized counterpart.
But how it can be made thread safe without synchronizing. Well answer lies in synchronization itself. Why do we synchronize? Primarily for making a set of statements atomic to ensure thread safety. Well if that atomic nature can be achieved without the synchronization, we don’t need synchronization.
To get a more clear picture, lets take a example of stack. In a stack with have two main operations push() and pop(). The push() adds an item in front/head of the stack and pop remove the item from the front/head. So if we maintain front into some reference, every time a push or pop happens we need to update the front/head. Since there may multiple threads might be accessing the Stack simultaneously we need to update the front/head atomically. Every thread checks the front/head of the stack and sets new value based on value checked. If it finds the value of front/head is changed, this means that some other thread has called push() or pop() on the thread, otherwise it changes the front/head with new value based on operation(push() and pop()) called.
Here comes the AtomicReference which allows to compare and set the references atomically. This means we can create a simple thread safe stack without synchronization.
The following example shows a simple implementation of Concurrent Stack using AtomicReference. The ConcurrentStack<E> class has a private inner class StackNode<E> which is used to represent each node of the stack, which is liked together by StackNode<E> next reference which of type AtomicReference. The ConcurrentStack class maintains is head into head item as of type AtomicReference which is used to push() and pop() elements from it. In this implementation for push() and pop() , I have used a greedy approach where the thread will retry to push() or pop() until it succeeds. But its left up to the use case where it is required to be greedy or time out or fail if not able to push() or pop() in first try.
package com.mylib.concurrent;
public interface Stack <E>{
public void push(E e);
public E pop();
}
package com.mylib.concurrent;
import java.util.concurrent.atomic.AtomicReference;
public class ConcurrentStack<E> implements Stack {
private AtomicReference<StackNode> head;
/**
* Creates a unbounded concurrent queue
*/
public ConcurrentStack() {
head = new AtomicReference();
}
/**
* This method will try to push item into stack until it succeeds
*/
@Override
public void push(E e) {
//Create a new item
StackNode<E> newHead = new StackNode<E>(e);
StackNode<E> headNode = null;
do
{
headNode = head.get();
newHead.next = headNode;
}while(!head.compareAndSet(headNode, newHead));
}
/**
* This method will try to pop item from stack until it succeeds
*/
@Override
public E pop() {
StackNode<E> headNode = head.get();
do
{
headNode = head.get();
if(headNode == null)
return null;
}while(!head.compareAndSet(headNode, headNode.next));
return headNode.item;
}
/**
* Inner class to hold stack items
* @param <E>
*/
private class StackNode<E>{
private E item;
StackNode<E> next;
public StackNode(E item) {
this.item = item;
}
}
}
In above code a thread calls push() method, checks head of the stack and try to set with new head based on the value it had just checked. If the head remains same, it changes head to new item and make new items next to head. Hence new item is pushed. If the value of head is changed since it has checked, this means some other thread has pushed or popped item from it. Hence the thread repeat the same steps checking head and retrying to set until it succeeds.
Same logic is applied to pop() where a thread trying to pop item from the thread checks head and try to set the head with head.next if value is head is not changed. If the value of head is changed this means some other thread has pushed or popped item from the stack, hence the thread has to repeat the same process until it succeeds.
Note : This is sample code, just to understand how AtomicReference can be used to create concurrent data structure. A few corner case might not have covered.
Teknology 