Reordering with two separate Java concurrent structures

Question

I'm starting a long-running process on a queue of items, and while an item is either scheduled to be processed or is being processed, I want to disallow some other operation. My code basically looks like this:

public class LongRunningProcess extends Thread {
    private final ConcurrentLinkedQueue<Item> pending = new ConcurrentLinkedQueue<>();
    private final Set<Item> active = Collections.newSetFromMap(new ConcurrentHashMap<Item, Boolean>());

    public LongRunningProcess() {
        // add items to pending; no more items will ever be added
    }

    @Override
    public void run() {
        while (! pending.isEmpty()) {
            // The peek/add/remove pattern here is important. The number
            // of items that are active or scheduled is always decreasing.
            // Because isScheduled checks pending before checking active,
            // this order of operations ensures that we never miss an item
            // as it is being switched from one collection to the other.
            Item nextItem = pending.peek();
            active.add(nextItem);    // <---Can any of these get reordered?
            pending.remove();        // <---+
            processItem(nextItem);   // <---+
            active.remove(nextItem); // <---+
        }
    }

    public boolean isScheduled(Item item) {
        return pending.contains(item) || active.contains(item);
    }
}

Will this work the way I expect, or is it possible for the highlighted code block above to be reordered? Can you please point me to any relevant specs?

Edit:

@Banthar's helpful comment led me to the java.util.concurrent package documentation, which answers my question definitively:

The methods of all classes in java.util.concurrent and its subpackages extend these guarantees to higher-level synchronization. In particular:

• Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.

Answer 1

Will this work the way I expect, or is it possible for either of the two highlighted items above to be reordered? Can you please point me to any relevant specs?

The short answer is that because both collections are concurrent classes, there is no way that the active.add(...) will happen after the pending.remove().

• The pending.peek(); and pending.remove(); accesses the volatile field head.

  private transient volatile Node<E> head = new Node<E>(null);
  

• The active.add(nextItem); accesses internal locking volatile fields:

  compareAndSetState(0, acquires)) {
  

Because both of your collections are concurrent classes, they both have internal locks or volatile variables so the methods calls have read/write memory barriers which ensure a "happens before" guarantee. This ensures that the operations cannot be reordered because of the Java Memory Model.

However, that doesn't mean that your logic is correct or that there aren't race conditions when you look at how the other threads are consuming those two collections. In addition, those calls are not atomic so you could have 3 threads that do:

1. t1 -- Item nextItem = pending.peek();
2. t2 -- Item nextItem = pending.peek();
3. t1 -- active.add(nextItem);
4. t3 -- removes nextItem from active and processes it or something
5. t2 -- active.add(nextItem);
6. t3 -- removes nextItem from active and processes it again