On-the-fly comparator that works correctly with ConcurrentSkipListSet

user_9398584 0
Viewed 106

I'm trying to use

queue = new ConcurrentSkipListSet<Task>(Comparators.comparing(Task::priority))

as a concurrent priority queue with unique elements (see a similar discussion here), but I need to change the priority of tasks from time to time.

Clearly to change the priority of elements while they're in the set is to open a can of worms; fortunately, I only need to change their priority after removing them from queue, and before resubmitting them. More precisely, I use pollFirst() to pop an element from the queue, which I may need to resubmit after updating its priority (with a lower priority).

If this was a serial implementation, there should be no problem with changing the priority of elements while they're outside of the set.

What's a thread-safe way of doing this update with concurrent access? Is it enough to guarantee that

task = queue.pollFirst() happens before task.priorityUpdate(), happens before queue.add(task)?

concurrentskiplistmap happens-before concurrency multithreading java
1 Answers

All concurrent collections establish happen-before relationships between element put and element get.

The problem would be if you need to change priority while they are in the queue, and you take them out and put them back in because that is the only way; then, a concurrent thread may put the same element in the meantime and then you would have lost your modification. In that case, further synchronization would be required.

But if you are taking elements out, changing their priority and only then evaluating whether they should be put back in, happen-before guarantees of concurrent collections are enough to ensure correctness, and you need do nothing else.

From add() to pollFirst() there is a happens-before relationship, so the object created in the thread calling add() is visible to the thread calling pollFirst().

From pollFirst() to add() there is not. However, if you change the priority and then call add() from the same thread, no further memory constraints are needed.
If you later call pollFirst() from another thread, the happens-before relationship between add() and pollFirst() will guarantee the updates to the object before calling add() are visible.

user_34532260
Related