Preserving order of add operation encounter Concurrent list/queue insertion-CodePudding

I have multithreaded code where each thread needs to write to a shared list/queue. I want to ensure that multiple add operations can proceed concurrently and that the order in which each thread encounters the add operation is preserved. I do not want to synchronize the add operation if at all possible.

In the above image, green represents the thread that first encountered the add operation, blue represents the thread that encountered it second and red represents the thread that encountered it third. Even if red thread completed insertion before blue thread, I want the order to be effected as depicted.

I'm wondering if there are any existent suitable structures in the java concurrent package (LinkedBlockingQueue perhaps?) and if not, whether someone can offer any tips about what I would need to do in defining my own structure which could fulfill the requirements above.

My best guess at this point is to add a volatile int variable to the multithreaded code that increments immediately before the add operation, which is sent with the Thread.currentThread.getId() value, and can then be used after all write operations are completed, to sort the list/queue structure so that the elements are ordered according to the int variable's value at each element.

Any advice would be appreciated.

EDIT:

It should be noted explicitly that insert operations need to take place in constant time.

CodePudding user response：

Your best bet would be to use ConcurrentHashMap and AtomicInteger as counter.

So every thread right before adding his ID to map calls the

 int id= AtomicInteger.getAndIncrement();

and the you put into ConcurrentHashMap<Integer, Integer> map

map.put(id, threadId);

then after the work is done you can sort entrySet by the key and you get the rigth order

alternatively you can use ConcurrentSkipListMap which will sort by the natural ordering of the keys, or by specified comparator.

But, i think that there is some part of the story that you still need to discover yourself, hard to say what it is now, just the picture you painted has some context and it seems like this context still hides something that you will discover. Just the problem you described comes from somwhere else, and it feel like the solution to it should be differnet than this kind of ordering.

CodePudding user response：

LinkedBlockingQueue uses synchronization internally, in the form of ReentrantLock -- that's how it implements the 'blocking' part.

Something like this should work:

AtomicBoolean busy = new AtomicBoolean(false);

Thread t = new Thread(() -> {
    while (!busy.compareAndSet(false, true)) {
        // busy wait
    }
    try {
        list.add(Thread.currentThread().getId());
    } finally {
        busy.set(false);
    }
};

Here threads compete at the busy flag. One of them wins the right to add to the list, others busy-wait until the winning thread clears the flag.

The two calls to AtomicBoolean methods establish proper 'happens-before' relationship between list.add() calls done on different threads, so each thread should observe actual state of the list.

LinkedList can be used for unbounded queues. For bounded ones, maybe ArrayList with initial capacity set.

CodePudding user response：

When calls are concurrent, by their nature, they are not ordered (that is what the word concurrent implies).

So I would give up this ordering requirement because it really makes no sense. Ordering of requests based on the physical arrival time makes no sense; I do not know of any concurrency model that has this as a requirement.

The simplest solution would be to use a synchronized wrapper around an AtomicList and add the threads to that list.

If you really want to go for a 'non blocking' data-structure, I would have a look at a concurrent ringbuffer like those from JCTools. But before going for such a solution, I would first benchmark your code and figure out where your bottleneck is before just adding random complexity.