Databases
StackOverflow2013
Postsdbo
POWhere is there bug in lock free queue?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhere is there bug in lock free queue?
    primarykey
    data
    text
    <p>I wrote a Java lock free queue implementation. It has a concurrency bug. I cannot find it. This code is not important. I just worry about I cannot explain observed behavior related with volatile variables.</p> <p>The bug is visible by the exception ("null head"). This is impossible state because there is atomic integer holding current queue size. The queue has a stub element. It provides that a reader thread doesn't change tail pointer and a writer thread doesn't change head pointer.</p> <p>Queue length variable guarantee that the linked list will never be empty. It's as a semaphore.</p> <p>The take method behaves like it gets stolen length value.</p> <pre><code>class Node&lt;T&gt; { final AtomicReference&lt;Node&lt;T&gt;&gt; next = new AtomicReference&lt;Node&lt;T&gt;&gt;(); final T ref; Node(T ref) { this.ref = ref; } } public class LockFreeQueue&lt;T&gt; { private final AtomicInteger length = new AtomicInteger(1); private final Node stub = new Node(null); private final AtomicReference&lt;Node&lt;T&gt;&gt; head = new AtomicReference&lt;Node&lt;T&gt;&gt;(stub); private final AtomicReference&lt;Node&lt;T&gt;&gt; tail = new AtomicReference&lt;Node&lt;T&gt;&gt;(stub); public void add(T x) { addNode(new Node&lt;T&gt;(x)); length.incrementAndGet(); } public T takeOrNull() { while (true) { int l = length.get(); if (l == 1) { return null; } if (length.compareAndSet(l, l - 1)) { break; } } while (true) { Node&lt;T&gt; r = head.get(); if (r == null) { throw new IllegalStateException("null head"); } if (head.compareAndSet(r, r.next.get())) { if (r == stub) { stub.next.set(null); addNode(stub); } else { return r.ref; } } } } private void addNode(Node&lt;T&gt; n) { Node&lt;T&gt; t; while (true) { t = tail.get(); if (tail.compareAndSet(t, n)) { break; } } if (t.next.compareAndSet(null, n)) { return; } throw new IllegalStateException("bad tail next"); } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USDaneel S. Yaitskov
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COHow does this code prevents data races, when no locking mechanism is used? Why dont you want to use a lock?
      singulars
      1. POWhere is there bug in lock free queue?
      1. USChriss
    2. COWhen do you see the problem? Do you get it with a single reader thread or do you need multiple readers before you see the problem? I suspect the issue is around multiple reader threads being in the second while loop of takeOrNull.
      singulars
      1. POWhere is there bug in lock free queue?
      1. USmatt helliwell
    3. COThis is not a production code. Treat this an exercise.
      singulars
      1. POWhere is there bug in lock free queue?
      1. USDaneel S. Yaitskov
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload