Menu
I would like to use a Linked List like the one described in this paper. However, I didn't find any Java implementation in the web.
If no java implementation of the above mentioned Linked List exists, I think, I would use the java.util.concurrent.ConcurrentLinkedQueue<E>. Is this a good choice (it is not really a linked list)?
If it's not a good choice, does anyone know of a reliable concurrent (thread-safe) wait-free(lock-free) Linked List implementation in Java?
775
A data structure provides lock-freedom if, at any time, at least one thread can proceed. All other threads may be starving. The difference to obstruction-freedom is that there is at least one non-starving thread even if no threads are suspended.
Stacks make for a simple case study, since the operations on stacks are very simple. The basic principle behind the implementation is that a thread will create a new version of the top of the stack and if no other thread has modified the stack, the change will be made public.
An unbounded thread-safe queue based on linked nodes. This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time.
7.1. For a data structure to qualify as lock-free, more than one thread must be able to access the data structure concurrently. They don't have to be able to do the same operations; a lock-free queue might allow one thread to push and one to pop but break if two threads try to push new items at the same time.
ConcurrentLinkedQueue is a superb lock free queue and does what a concurrent single linked list can do. A small warning: if you dont use poll or peek and only iterator() (+.remove()) it will leak memory.
It's an outstanding Queue.
54
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
