I am trying to create a lock-free queue implementation in Java, mainly for personal learning. The queue should be a general one, allowing any number of readers and/or writers concurrently.
Would you please review it, and suggest any improvements/issues you find?
Thank you.
import java.util.concurrent.atomic.AtomicReference;
public class LockFreeQueue<T> {
private static class Node<E> {
E value;
volatile Node<E> next;
Node(E value) {
this.value = value;
}
}
private AtomicReference<Node<T>> head, tail;
public LockFreeQueue() {
// have both head and tail point to a dummy node
Node<T> dummyNode = new Node<T>(null);
head = new AtomicReference<Node<T>>(dummyNode);
tail = new AtomicReference<Node<T>>(dummyNode);
}
/**
* Puts an object at the end of the queue.
*/
public void putObject(T value) {
Node<T> newNode = new Node<T>(value);
Node<T> prevTailNode = tail.getAndSet(newNode);
prevTailNode.next = newNode;
}
/**
* Gets an object from the beginning of the queue. The object is removed
* from the queue. If there are no objects in the queue, returns null.
*/
public T getObject() {
Node<T> headNode, valueNode;
// move head node to the next node using atomic semantics
// as long as next node is not null
do {
headNode = head.get();
valueNode = headNode.next;
// try until the whole loop executes pseudo-atomically
// (i.e. unaffected by modifications done by other threads)
} while (valueNode != null && !head.compareAndSet(headNode, valueNode));
T value = (valueNode != null ? valueNode.value : null);
// release the value pointed to by head, keeping the head node dummy
if (valueNode != null)
valueNode.value = null;
return value;
}
Lock-free techniques allow multiple threads to work together in a non-blocking way, often achieving incredible performance. As the name suggests, locks are not used. If the idea of a multithreaded program without mutexes makes you uncomfortable, you are quite sane. Yet lock-free systems are pervasive.
A queue, as implemented by Thread::Queue is a thread-safe data structure much like a list. Any number of threads can safely add elements to the end of the list, or remove elements from the head of the list.
The C++ thread safe queue allows to use the queue by multiple thread in multi-threaded code. The thread safe queue is not a built-in method or class in C++; it can be implemented with the help of built-in STL libraries.
Thread safe means that you have to isolate any shared data. Here your shared data is the pointer to the queue.So , in general , any time you have operations on the queue you need to protect queue and prevent multiple threads reach your queue at the same time. One good way is to implement Condition Variables.
The code is not thread-safe. Consider putObject(...)
:
public void putObject(T value) {
Node<T> newNode = new Node<T>(value);
Node<T> prevTailNode = tail.getAndSet(newNode);
prevTailNode.next = newNode;
}
The 2nd statement adds the new node before the previous node's next
pointer has been set. That only happens in the 3rd statement. Thus, there is a window in which the next
is null
; i.e. a race condition.
Even if you fixed that, there is a more insidious problem. A thread reading the next
field for an Node object won't necessarily see the value that a second thread has just written. That's a consequence of the Java memory model. In this case, the way to ensure that the following read always sees the earlier written value is to either:
next
to be volatile
, orEDIT: on reading the code for getObject()
and putObject()
in more detail, I can see that nothing forces the non-null value of next
to be flushed to memory in putObject
, and nothing forces getObject
to read next
from main memory. So the getObject
code could see the wrong value of next
, causing it to return null
when there is really an element in the queue.
I see only two problems with your code:
one is the problem with memory operations ordering Stephen C mentioned (can be solved by declaring next
and value
volatile
) (Node: value has the same problem)
second is a more subtle one, and not concurrency related: after you return an object in getObject
, you still retain its reference from head. This could lead to a memory leak.
Otherwise the algorithm is OK. A vague demonstration (assume the above are fixed):
L1: tail
can never be deleted from the queue. This holds because when something is stored in tail
, it has next == null
. Also, when you assign something to xxx.next
(only in putObject
), it cannot be tail
, because of the getAndSet's atomicity and the ordering between volatile write and subsequent read - assume you read a non-null tail.next
, this value must have been written by putObject
and therefore happens-after the last line of it. This means it happens-after the previous line, which means the value we are reading is not from tail
.
A consequent of it is that every object in putObject
will eventually be reachable from head
. That's because we are connecting after tail
, and this node can be deleted only after we write the new node's reference to its next
, which means the new node is reachable from head
.
The added objects are trivially ordered by the getAndSet
operation in putObject
.
The dequeued objects are ordered according successful compareAndSet
operations in getObject
.
The getObject
/putObject
are ordered according to write/read to volatile field next
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With