Unable to maintain order of producer tasks in java

Question

I am writing a multithreaded application where there a n producers who tries to add an element to the shared resource. I want to maintain the order in which producer produces the element in the shared resource.

For example my shared resource is a SynchronizedQueue and P1, P2, P3, P4 are going to produce a new elements in the order p1, p2, p3, p4 and during that time P5 producer is adding its element to the queue, so P1, P2, P3, P4 will be waiting for the lock. Once P5 releases the lock any one of the P1-4 will acquire the lock, so we loose the order of elements.

Is there a way to maintain the order of elements who wait for a lock ? From my understanding it is not possible but I would like to check whether this can be achieved programmatically.

Answer 1

Sure it's possible :) Generally this class of problems are solved by adding sequence numbers where the sequence is known. In your case, your producers can produce products with sequence numbers like "P1-1", "P1-2", "P2-1" etc. which can then be used to restore order after some processing.

This is preferable to maintaining order as some optimisations are not possible this way (search for "Java reordering" for example).

You could do something like this:

PriorityQueue priorityQueue = // give suitable comparator
int seq = 0;

void synchronized add(E e){
    priorityQueue.add(e);
}

E synchronized poll(){
    E candidate = priorityQueue.peek();
    if(candidate.getSeq() == seq){
        seq++;
        return priorityQueue.poll();
    }else{
        log.debug("{} hasn't arrived yet", seq);
        return null;
    }
}

Answer 2

This is a false goal. I assume your producers are threads. Threads execution order is not strictly defined - one time thread A can run faster than thread B, another time B runs faster, so the order you want to preserve is random itself and is not worth to care. Besides, the time spend to add an element to a queue is so small that even two or more threads do it simultaneously, you can consider it as happening at the very same moment of time.

Multithreading resembles relativistic physics - there is no universal time, only happens-before relations. If there are such relations between produced events, then that relations should be used. The time when an element is added to common queue cannot serve as such a relation.

Answer 3

You did not supply any code to see how the locks are obtained/released on the shared resource, but you maybe interested in the java.util.concurrent.locks.ReentrantLock class.

The constructor for this class accepts an optional fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread.

So if P1,P2,P3 tried to obtain the re-entrant lock in that order and the shared resource is locked, the thread waiting the longest (in this case P1) will obtain the lock first, then P2, then P3, then any other threads after that.

Answer 4

The problem is that the order in which the lock is acquired can be arbitrarily different from the order in which elements are produced and this can even be arbitrarily different from the order in which producers enqueue themselves for acquiring a lock in a multi threaded environment. So you are ending up with the same problem you were trying to solve. (See recursion)

Not all problems can be solved by another level of indirection ;-)

Answer 5

One way I could think of would be to create a wrapper class, PriorityP which has the fields int priority and P value.

Then you assign each thread a priority (int) and the thread gives as result a PriorityP with the appropriate priority and value.

Now, you can use a PriorityBlockingQueue instead of your SynchronizedQueue, and implement the Comparator interface in the PriorityP class.

When you do it like this, then whenever a thread enters his value into the queue, it is automatically put in the correct position.

Answer 6

If you have a way of assigning values to elements stored in queue, which can be used for their ordering than you can use a PriorityBlockingQueue instead of the SynchronizedQueue. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time.

For example, you can store the id of the producer in the element and have a Comparator which knows how to compare between the producer ids.