0

The use case requires me not to block any thread while retrieving or putting values into a List<V>. I have been looking at compare-and-swap algorithms that require you to implement a datastructure yourself. I would like to use an existing implementation of Collection such as an ArrayList or LinkedList and achieve a lock-free insertion and look up of elements. There is an option to have AtomicReferenceArray<E>. But I was wondering if there was a way to achieve this for a variable-sized list.

user592748
  • 1,194
  • 3
  • 21
  • 45
  • 5
    There is the [`ConcurrentLinkedQueue`](http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html) which is lock free. If you want the full functionality of a `List` then you will need to look at external libraries. – Boris the Spider Feb 17 '15 at 12:22
  • List sinchronizedList = Collections.sinchronizedList(yourList); – Héctor Feb 17 '15 at 12:24
  • Both `ArrayList` and `LinkedList` are not threadsafe and thus lock-free. So you want to have a thread safe implementation, but without locks? Seems a bit contrary to me. – Zhedar Feb 17 '15 at 12:24
  • 1
    @bigdestroyer: The OP wants to avoid synchronized datastructures. Synchronized is simply not *lock-free*. – Willem Van Onsem Feb 17 '15 at 12:25
  • Do you want sincronization without sincronization? – Héctor Feb 17 '15 at 12:28
  • 2
    @bigdestroyer: no, *lock-free* means that there are no locks. The algorithms can run in parallel and perform a *compare-and-swap* in the end, a hardware-based atomic instruction to reduce the overhead. – Willem Van Onsem Feb 17 '15 at 12:30
  • 1
    @Zhedar: see [this](http://en.wikipedia.org/wiki/Compare-and-swap). – Willem Van Onsem Feb 17 '15 at 12:31
  • @BoristheSpider `ConcurrentLinkedQueue` is really interesting. Any similar lock-free collections and pointers to external libraries? – user592748 Feb 17 '15 at 12:37
  • @bigdestroyer Sorry, but you obviously have no clue what the OP is asking for. I would suggest that you do not comment in these cases, it is somewhat unhelpful. – Boris the Spider Feb 17 '15 at 12:40
  • @user592748, this is an extremely complicated problem. I don't know of any more complex lock-free collections apart from Skip Lists. For what the JDK has to offer, examine [`java.util.concurrent`](http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html). – Boris the Spider Feb 17 '15 at 12:42
  • Just because I'm curious: Why do you need lock-free synchronization? Is it a real-time application? Are you working on an embedded system? – slartidan Feb 17 '15 at 12:43
  • @OP Is this question a duplicate of [this](http://stackoverflow.com/questions/4724995/lock-free-concurrent-linked-list-in-java)? – Boris the Spider Feb 17 '15 at 12:45
  • @BoristheSpider Yes, it is a similar question. I need something like `ConcurrentLinkedDeque`. However, the team is using 1.6. I need to get the last element. I am not sure how to do that yet – user592748 Feb 17 '15 at 13:00
  • @slartidan a real-time application. No. not embedded. – user592748 Feb 17 '15 at 13:01
  • The only thing I can suggest is the read the [original paper](http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf) and go from there. – Boris the Spider Feb 17 '15 at 13:06
  • just use volatile keyword – nafas Feb 17 '15 at 13:13
  • What happened to the answer with busy-waiting? I am not sure of the correctness of this because all CAS algorithms I have seen make use of atomic references. Besides, it looks just too simple. There are papers written on CAS-based data structures and I wouldn't believe that would be the case if a simple busy-waiting algorithm would be a substitute. And on these ground, I wouldn't try that approach. – user592748 Feb 17 '15 at 13:32

0 Answers0