1

I know if queue is full the new task will be executed by a newly created thread in priority according to How to guarantee FIFO execution order in a ThreadPoolExecutor

But I have following test code snippets which min core size = max core size.

public class ThreadPoolFifoTest {
    public static void main(String[] args) throws InterruptedException {
        Executor ex = Executors.newFixedThreadPool(10);
        final List<Integer> l = new LinkedList<Integer>();
        final ReentrantLock lock = new ReentrantLock(true);//fair lock
        for(int i=0;i<10000;i++){
            final int num = i ;
            ex.execute(new Runnable() {//FIFO submit 
                @Override
                public void run() {
                    //here since queue is FIFO, it is easy to consider that somebody should be take the task FIFO and let the thread to run this task
                    //so it easy to consider that this should be fifo to go to here. 
                    //But as a result , it is not.
                    lock.lock();
                    l.add(num);
                    lock.unlock();                 
                }
            });
        }

        Thread.sleep(1000);
        System.out.println(l);
        List<Integer> sortedList= new LinkedList<Integer>(l);
        Collections.sort(sortedList);
        System.out.println(sortedList);
        System.out.println(l.equals(sortedList));//not equals here

    }
}

output:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 9, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 85, 84, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
false

Since Queue under the thread pool is FIFO, the task should be poll FIFO and run in the thread, so since I am submiting task folloing order 0.1.2.3.4.....999, my l should looks like sorted, but from the output, it is not, doesn't this mean that the execution order is not FIFO? Why not?

What if I need the task to be executed FIFO?

Community
  • 1
  • 1
JaskeyLam
  • 15,405
  • 21
  • 114
  • 149
  • You haven't sorted `l` but a new list created from `l`!. What execution order are you talking about? – Chetan Kinger Feb 10 '17 at 06:54
  • @CKing , I mean , I am submitting task from 0->999, and in my run() method, I put the number to a FIFO list, if execution is FIFO, my list should be sorted, but from the output, it is not. – JaskeyLam Feb 10 '17 at 06:56
  • But that's what I said. You are not sorting `l` anywhere in your code. You are sorting only the `sortedList`. How do you expect `l` to be sorted? Nevermind. I think I got your question now. – Chetan Kinger Feb 10 '17 at 06:59
  • @CKing , yes, I do not sort it because I need to compare and check if it is FIFO. Since queue in thread pool is FIFO, so if the execution is FIFO, my `l` should be 0.1.2.3.4.....999, but from the output it is not, so dosen't it mean the execution is not FIFO, please correct me if I am wrong. I am trying to figure it out why and how to solve it. – JaskeyLam Feb 10 '17 at 07:02
  • 1
    Yest I get your question now. I misread it earlier. Note that adding the `lock` doesn't ensure that threads will run sequentially. It only ensures what when one thread is writing, the other thread is waiting. – Chetan Kinger Feb 10 '17 at 07:07
  • @CKing, But I make it fair , if the execution is realy FIFO, the `l` should be look sorted since the task who execution first should try lock first(fair) and it should be execution first. But the truth is not, I am wondering why, I guess it could be muticore cpu issue? – JaskeyLam Feb 10 '17 at 07:10
  • http://stackoverflow.com/questions/28545459/looking-for-solution-based-on-threadpoolexecutor-to-ensure-sequential-execution?noredirect=1&lq=1 ? –  Feb 10 '17 at 07:13
  • @RC, this thread does not answer my question : 1. why thread pool execution is not FIFO, and 2. what if I need a simple solution and still use threadpool – JaskeyLam Feb 10 '17 at 07:21
  • 1
    You have ten threads. They will all run at once. No FIFO behaviour here. – user207421 Feb 10 '17 at 07:38
  • I know, but the submiting part shoud be fifo right? Some code under the hood may look like `while(true){ task = q.poll(); putThisTaskToOneThread();}"`, this part should be FIFO. From the result , the execution is not FIFO, I guess it is for os thread scheduling issue? Would you please clarify why and give us a solution? – JaskeyLam Feb 10 '17 at 07:45
  • I have already clarified why. The 'solution' is to create a thread pool containing *one* thread, which of course is completely and utterly pointless. If you want a deterministic order of execution why are you using threads? – user207421 Feb 10 '17 at 08:32
  • @EJP Since queue's order is FIFO, it is easy for user to consider the execution is in order , even the upvoted answer is saying so http://stackoverflow.com/questions/24477316/java-thread-pool-executorservice-threads-execution-order If the queue's order is not repspected when executing tasks, then even thread pool back by PriorityQueue is not fully work as many users' expectation. This should be a nature expection, we don't need to to be complete in order, we just will consider they start in order. – JaskeyLam Feb 10 '17 at 09:05
  • 1
    The user can consider whatever he likes, but threads execute concurrently. That's what they're for. You can start them in any order you like, and you can control that with a queue, but that's the end of your control over it. – user207421 Feb 10 '17 at 09:18
  • I think it's because threads are picked at random by thread scheduler, therefore the glitch of receiving 9 after 10,11... is just because other threads were contending to execute through the lock implementation. – Prashant Nov 23 '18 at 03:26

1 Answers1

1

The problem is that thread only take message off in order, but run independently (as threads should) If you want execution in FIFO you should either

  • use a single thread as you can't run tasks in parallel anyway.
  • use multiple thread but collect the results in the order they were created (not the order they were executed. This is what parallelStream does.

For example

List<Result> results = IntStream.range(0, 10000).parallel()
                                .mapToObject(i -> func(i))
                                .collect(Collector.toList());

This will allow concurrent execution, however the results appear in the original order.

BTW When you sort a LinkedList, it has to turn it into array, sort it and copy it back into the linked list. I suggest using an ArrayList which can be sorted in place.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • Little odd to understand at first look but it seems one thread has independently taken value from the stream and calculated its composed operations, then only next value is supplied to next thread, am I thinking in the right direction clarify? – Prashant Nov 22 '18 at 17:28
  • @Prashant each thread has it's own work queue, but also supports work stealing if they run out of work. The tasks are added to the queues serially but removed concurrently. – Peter Lawrey Nov 22 '18 at 17:32
  • 1
    say T1 has {0,1,2,3} in queue and T2 has{4,5,6,7}, suppose if T2 finishes its set of operations on values in queue and T1 is still in the process, will {3} be taken by T2? should it be always or only in ForkJoinPool or WorkStealingPool? – Prashant Nov 23 '18 at 03:18
  • @Prashant yes, a ThreadExecutorPool has one queue shared across threads, which is simpler when you have fewer, more expensive tasks, WorkStealingPool is better when you have more, smaller tasks. – Peter Lawrey Nov 23 '18 at 07:38