Ordering threads to run in the order they were created/started
Asked Answered
K

11

12

How can i order threads in the order they were instantiated.e.g. how can i make the below program print the numbers 1...10 in order.

public class ThreadOrdering {
    public static void main(String[] args) {

        class MyRunnable implements Runnable{
            private final int threadnumber;

            MyRunnable(int threadnumber){
                this.threadnumber = threadnumber;
            }

            public void run() {
                System.out.println(threadnumber);
            }
        }

        for(int i=1; i<=10; i++){
            new Thread(new MyRunnable(i)).start();
        }
    }
}
Koopman answered 18/9, 2010 at 12:55 Comment(4)
Then what is the purpose of using threads? Use a sequential code insteadDraghound
this was just a simple code for illustration, i actually have some parts that i want to execute in parallel and then once the results are generated i want to merge the results in certain orderKoopman
starting a thread in the way illustrated above is nowhere near readable,try assigning the runnable to a reference variable,that'll make it more readableAlbritton
hi all, the soln from finw does this really nicely, it starts all the tasks together waits for each of the task to complete in order. the merge operation in my case allows this to be optimized futher since the result produced by task 'n' can be merged with result from 'n+1', is it possible to achieve this with callables and futures such that if any one of the callable completes then we can execute the merge step or that the main thread is allowed to execute the merge with task n+1Koopman
G
15

Sounds like you want ExecutorService.invokeAll, which will return results from worker threads in a fixed order, even though they may be scheduled in arbitrary order:

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class ThreadOrdering {

    static int NUM_THREADS = 10;

    public static void main(String[] args) {
        ExecutorService exec = Executors.newFixedThreadPool(NUM_THREADS);
        class MyCallable implements Callable<Integer> {
            private final int threadnumber;

            MyCallable(int threadnumber){
                this.threadnumber = threadnumber;
            }

            public Integer call() {
                System.out.println("Running thread #" + threadnumber);
                return threadnumber;
            }
        }

        List<Callable<Integer>> callables =
            new ArrayList<Callable<Integer>>();
        for(int i=1; i<=NUM_THREADS; i++) {
            callables.add(new MyCallable(i));
        }
        try {
            List<Future<Integer>> results =
                exec.invokeAll(callables);
            for(Future<Integer> result: results) {
                System.out.println("Got result of thread #" + result.get());
            }
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        } catch (ExecutionException ex) {
            ex.printStackTrace();
        } finally {
            exec.shutdownNow();
        }
    }

}
Gossipmonger answered 18/9, 2010 at 14:24 Comment(7)
Nice. A difference between this and Fly's and my solutions is that this produces all the output in one lump at the end, whereas our solutions produce each bit of output as it becomes possible. Depending on what the OP is actually doing, he might prefer one or the other. Or not, of course. It would be nice if there was an invokeAll variant that returned an Iterator rather than a list.Brainwashing
@Tom Anderson, how would you handle interruption in an Iterator?Gossipmonger
superb.. this does the job for me thank u. the merge operation in my case allows this to be optimized futher since the result produced by task 'n' can be merged with result from 'n+1', is it possible to achieve this with callables and futures such that if any one of the callable completes then we can execute the merge step or that the main thread is allowed to execute the merge with task n+1Koopman
Do you want to merge(r(n), r(n+1)) immediately? Can you merge(r(n), merge(r(n), r(n-1))) at some point after that? With invokeAll, the main thread will have to wait for all of the tasks to complete before the list of futures is returned, so you would just merge them by iterating over the results list. Is that not what you want to do?Hairston
@finnw: good question. I assume you mean interruption of the main thread while it's waiting in in Iterator.next()? I think the best option is probably to throw a NoSuchElementException with the InterruptedException as its cause. There's not a lot else you can do with an interface as narrow as Iterator. I suppose you could treat it as cancellation of the Callable being waited for, and return a Future that behaves accordingly. You'd probably also actually cancel the running tasks. It would all be a bit weird, though.Brainwashing
@Fly :: Yes it can be done, but even the merge operation is kind of a heavy operation and so i would like to trigger the merge right after any of the task is processed. It seems that i use countdownlatch to achieve this. once all the tasks are started make the main thread await on countdownlatch, once any of the tasks are completed update the countdownlatch so that main thread can proceed. at this point when main thread is notified i can find if any of the results are available and start the merge operation and then make the main wait until next result is available.Koopman
@finnw: update! ExecutorCompletionService, which i only came across this afternoon, allows you to do more or less exactly what i want, albeit not through an actual Iterator, and with a few more lines of code.Brainwashing
H
10

"I actually have some parts that i want to execute in parallel, and then once the results are generated, I want to merge the results in certain order." Thanks, this clarifies what you're asking.

You can run them all at once, but the important thing is to get their results in order when the threads finish their computation. Either Thread#join() them in the order in which you want to get their results, or just Thread#join() them all and then iterate through them to get their results.

// Joins the threads back to the main thread in the order we want their results.
public class ThreadOrdering {
    private class MyWorker extends Thread {
        final int input;
        int result;
        MyWorker(final int input) {
            this.input = input;
        }
        @Override
        public void run() {
            this.result = input; // Or some other computation.
        }
        int getResult() { return result; }
    }

    public static void main(String[] args) throws InterruptedException {
        MyWorker[] workers = new MyWorker[10];
        for(int i=1; i<=10; i++) {
            workers[i] = new MyWorker(i);
            workers[i].start();
        }

        // Assume it may take a while to do the real computation in the threads.

        for (MyWorker worker : workers) {
            // This can throw InterruptedException, but we're just passing that.
            worker.join();
            System.out.println(worker.getResult());
        }
    }
}
Hairston answered 18/9, 2010 at 13:38 Comment(4)
This way you can't overlap the computation and the results merging (which is done sequentially)Draghound
That could be true if the threads need to keep running---doing more computations after they get their result, but I understood the problem to be needing to do one task in the thread. If the threads need to continue their computations, then the solution would be to use worker.wait() in each loop because you do have to wait() rather than join() for the results in order to be able to print them out.Hairston
Another possibility for getting results from a worker that never finishes would be to have each worker make a callback to some collector object with its result as its result became available, but that seems more complicated than the original question.Hairston
But this solution absolutes does allow computations to overlap. None of the workers wait on any of the other workers.Hairston
I
5

Simply put, the scheduling of threads is indeterminate.

http://www.janeg.ca/scjp/threads/scheduling.html Dead domain - do not click

WaybackMachine version of the above page

The longer answer is that if you want to do this, you'll need to manually wait for each thread to complete its work before you allow another to run. Note that in this fashion, all the threads will still interleave but they won't accomplish any work until you give the go-ahead. Have a look at the synchronize reserved word.

Informal answered 18/9, 2010 at 12:58 Comment(5)
This isn't about having the threads run in a given order (despite what the OP said), but producing output in a given order. You can still run the threads in parallel, as long as there is a way to coordinate their output.Brainwashing
@Tom I answered the question when it looked merely like an academic question. So, thanks for your comment but I answered what he asked :)Informal
No, even in the earliest version of this question, the OP asked "how can i make the below program print the numbers 1...10 in order" which makes it clear he's talking about ordering the output of the threads, not their executions. To me, at least.Brainwashing
@Tom but that would be in willful neglect of the earlier part of the question where he asked how to order the threads, where the common illustration of printing to console is an example of sharing a common resource. You can disagree with me all you want; that's great. I considered the emphasis of the question as scheduling threads (a VERY common novice question), and you considered it to be a problem in data collation. The line is drawn. I understand your point, but nothing will change the fact that I thought he was asking a different question because of his wording.Informal
You're quite right - it's clearly the case that we interpreted the question differently. And, naturally, that we both feel our interpretations are correct. Thus, we have most of human history in a nutshell, sadly.Brainwashing
H
4

You can chain them – that is, have the first one start the second, the second start the third, etc. They won't really be running at the same time except for a bit of overlap when each one is started.

public class ThreadOrdering
{
    public static void main(String[] args)
    {
        MyRunnable[] threads = new MyRunnable[10];//index 0 represents thread 1;
        for(int i=1; i<=10; i++)
            threads[i] = new MyRunnable(i, threads); 
        new Thread(threads[0].start);  
    }
}

public class MyRunnable extends Runnable
{
    int threadNumber;
    MyRunnable[] threads;

    public MyRunnable(int threadNumber, MyRunnable[] threads)
    {
        this.threadnumber = threadnumber;
        this.threads = threads;
    }

    public void run()
    {
        System.out.println(threadnumber);
        if(threadnumber!=10)
            new Thread(threadnumber).start();
    }
}
Harmaning answered 18/9, 2010 at 13:12 Comment(2)
hi peter, i am sorry i should have mentioned this earlier. i dont want the threads to run one after the other i want them to start together, as my goal is to execute some parts in parallel and then i want to end the threads in a certain order. i also added this comment much later just below the questionKoopman
No vote down necessary, to whomever did that. I was working with the original question.Harmaning
B
2

Here's a way to do it without having a master thread that waits for each result. Instead, have the worker threads share an object which orders the results.

import java.util.*;

public class OrderThreads {
    public static void main(String... args) {
        Results results = new Results();
        new Thread(new Task(0, "red", results)).start();
        new Thread(new Task(1, "orange", results)).start();
        new Thread(new Task(2, "yellow", results)).start();
        new Thread(new Task(3, "green", results)).start();
        new Thread(new Task(4, "blue", results)).start();
        new Thread(new Task(5, "indigo", results)).start();
        new Thread(new Task(6, "violet", results)).start();
    }
}

class Results {
    private List<String> results = new ArrayList<String>();
    private int i = 0;

    public synchronized void submit(int order, String result) {
        while (results.size() <= order) results.add(null);
        results.set(order, result);
        while ((i < results.size()) && (results.get(i) != null)) {
            System.out.println("result delivered: " + i + " " + results.get(i));
            ++i;
        }
    }
}


class Task implements Runnable {
    private final int order;
    private final String result;
    private final Results results;

    public Task(int order, String result, Results results) {
        this.order = order;
        this.result = result;
        this.results = results;
    }

    public void run() {
        try {
            Thread.sleep(Math.abs(result.hashCode() % 1000)); // simulate a long-running computation
        }
        catch (InterruptedException e) {} // you'd want to think about what to do if interrupted
        System.out.println("task finished: " + order + " " + result);
        results.submit(order, result);
    }
}
Brainwashing answered 18/9, 2010 at 14:29 Comment(1)
If you have a large number of threads, you might want something a bit cleverer than an arraylist, so you don't have all the old results hanging around. Maybe a heap, ordered by order number, where the root is only popped if it has the next undelivered order number.Brainwashing
N
1

If you need that fine-grained control, you should not use threads but instead look into using a suitable Executor with Callables or Runnables. See the Executors class for a wide selection.

Nectareous answered 18/9, 2010 at 12:59 Comment(1)
Are you referring to Executors.newSingleThreadExecutor()? Based on the OP's response to Peter DeWeese's answer I don't think this is what they want.Gossipmonger
D
1

A simple solution would be to use an array A of locks (one lock per thread). When thread i begins its executions, it acquires its associated lock A[i]. When it's ready to merge its results, it releases its lock A[i] and waits for locks A[0], A[1], ..., A[i - 1] to be released; then it merges the results.

(In this context, thread i means the i-th launched thread)

I don't know what classes to use in Java, but it must be easy to implement. You can begin reading this.

If you have more questions, feel free to ask.

Draghound answered 18/9, 2010 at 13:46 Comment(2)
When the main thread is controlling the collection of results, an idiomatic way to wait for a thread to finish is to call Thread#join(). Your solution to have each result be a "future" that depends on the next future result might be useful in some situations, too, but it seems more complicated than Thread#join().Hairston
If each worker does somehow depend on another worker, one could put the dependencies in the worker threads. It would also work to have the main thread control the interaction of results and do any post/merging computations in order to keep the workers as simple as possible.Hairston
C
1
public static void main(String[] args) throws InterruptedException{
    MyRunnable r = new MyRunnable();
    Thread t1 = new Thread(r,"A");
    Thread t2 = new Thread(r,"B");
    Thread t3 = new Thread(r,"C");

    t1.start();
    Thread.sleep(1000);

    t2.start();
    Thread.sleep(1000);
    t3.start();
}
Cheeky answered 9/12, 2012 at 11:34 Comment(0)
A
0

Control of thread execution order may be implemented quite easily with the semaphores. The code attached is based on the ideas presented in Schildt's book on Java (The complete reference....). // Based on the ideas presented in: // Schildt H.: Java.The.Complete.Reference.9th.Edition.

import java.util.concurrent.Semaphore;

class Manager {
    int n;
// Initially red on semaphores 2&3; green semaphore 1.
    static Semaphore SemFirst = new Semaphore(1);
    static Semaphore SemSecond = new Semaphore(0);
    static Semaphore SemThird = new Semaphore(0);

void firstAction () {
    try {
        SemFirst.acquire();
    } catch(InterruptedException e) {
        System.out.println("Exception InterruptedException catched");
    }
    System.out.println("First: " );
    System.out.println("-----> 111");
    SemSecond.release();
}
void secondAction() {
    try{
        SemSecond.acquire();
    } catch(InterruptedException e) {
        System.out.println("Exception InterruptedException catched");
    }
    System.out.println("Second: ");
    System.out.println("-----> 222");
    SemThird.release();
}
void thirdAction() {
    try{
        SemThird.acquire();
    } catch(InterruptedException e) {
        System.out.println("Exception InterruptedException catched");
    }
    System.out.println("Third: ");
    System.out.println("-----> 333");
    SemFirst.release();
}
}

class Thread1 implements Runnable {
    Manager q;

    Thread1(Manager q) {
    this.q = q;
    new Thread(this, "Thread1").start();
}

public void run() {
    q.firstAction();
}
}

class Thread2 implements Runnable {
    Manager q;

    Thread2(Manager q) {
    this.q = q;
    new Thread(this, "Thread2").start();
}

public void run() {
    q.secondAction();
}
}

class Thread3 implements Runnable {
    Manager q;

    Thread3(Manager q) {
    this.q = q;
    new Thread(this, "Thread3").start();
}

public void run() {
    q.thirdAction();
}
}

class ThreadOrder {
    public static void main(String args[]) {
    Manager q = new Manager();
    new Thread3(q);
    new Thread2(q);
    new Thread1(q);
    }
}
Acevedo answered 10/5, 2017 at 9:51 Comment(0)
E
0

This can be done without using synchronized keyword and with the help of volatile keyword. Following is the code.

package threadOrderingVolatile;

public class Solution {
    static volatile int counter = 0;
    static int print = 1;
    static char c = 'A';

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Thread[] ths = new Thread[4];
        for (int i = 0; i < ths.length; i++) {
            ths[i] = new Thread(new MyRunnable(i, ths.length));
            ths[i].start();
        }
    }

    static class MyRunnable implements Runnable {
        final int thID;
        final int total;

        public MyRunnable(int id, int total) {
            thID = id;
            this.total = total;
        }

        @Override
        public void run() {
            while(true) {
                if (thID == (counter%total)) {
                    System.out.println("thread " + thID + " prints " + c);
                    if(c=='Z'){
                        c='A';
                    }else{
                        c=(char)((int)c+1);
                    }
                    System.out.println("thread " + thID + " prints " + print++);
                    counter++;                  
                } else {
                    try {
                        Thread.sleep(30);
                    } catch (InterruptedException e) {
                        // log it
                    }
                }
            }
        }

    }

}

Following is the github link which has a readme, that gives detailed explanation about how it happens. https://github.com/sankar4git/volatile_thread_ordering

Ep answered 2/6, 2018 at 13:3 Comment(0)
B
0

In case someone needs, this is my take at this problem in Python. My approach is to use a deque. Each instance of the class places itself on the queue, does the working task right at construction, then waits for the previous member of the queue to terminate its output to do his. The trick is that each instance has two locks (aka semaphores) to control printing. One which is copied from the last instance entered in the queue: I wil wait for this lock to print. Another one that is created and locked at construction. The next instance to enter the queue will copy that one and will have to wait for me to release it, which I will do after my printing is done.

import random
from functools import \
    partial  # an object made of a function ready to call with prefilled arguments
import threading, time
from collections import deque

printing_lock = threading.Lock()  # for debuging: avoid threads printing debug infos in the middle of each other


class WorkNowPrintLater:
    def __init__(self, id: int, work_func: partial, print_func: partial, my_queue: deque, queue_lock: threading.Lock):
        """
        Create an instance of this class does the whole thing:
            1/ do some job immediately
            2/ do some other job (usually an output) in the same order as instances were created
        :param id:
            id of this instance. for debug purpose only
        :param work_func:
            the working function.
            Note for non python users: a partial is an object made of a function with its arguments
            already in place, ready to launch
        :param print_func:
            the output function
        :param my_queue:
            a double-end-queue (deque) where each instance of WorkNowPrintLater will put itself on construction
            Must be the same for all instances to synchronize
        :param queue_lock:
            a semaphore to protect access to the queue
            Must be the same for all instances to synchronize
        """
        with printing_lock:
            print(f"{id} being created")
        self.id = id
        self.work_func = work_func
        self.print_func = print_func
        self.my_queue = my_queue
        self.queue_lock = queue_lock
        self.done = False
        self.lock_i_wait_before_i_printing = threading.Lock() if len(my_queue) == 0 else my_queue[
            -1].lock_you_wait_before_you_print
        self.lock_you_wait_before_you_print = threading.Lock()
        self.lock_you_wait_before_you_print.acquire()  # Block access to printer to the next element in the queue until I'm done

        with printing_lock:
            print(f"{self.id} waits for queue lock to put myself in")
        with self.queue_lock:
            self.my_queue.append(self)

        my_worker = threading.Thread(target=self.worker)
        my_worker.start()
        print(f"{id} is alive")

    def worker(self):
        with printing_lock:
            print(f"{self.id} working starts")
        self.work_func()

        with printing_lock:
            print(f"{self.id} working done. wait for printer")
        with self.lock_i_wait_before_i_printing:
            self.print_func()
            self.lock_you_wait_before_you_print.release()
            self.done = True

        with printing_lock:
            print(f"{self.id} waits for queue lock to do housekeeping")
        with self.queue_lock:
            with printing_lock:
                print(f"{self.id} housekeeping starts")
            if len(self.my_queue) <= 1:
                return
            while self.my_queue[0].done and len(self.my_queue) >= 2:
                _ = self.my_queue.popleft()


 """ MAIN PROGRAM """


threads_queue = deque()
semaphore = threading.Lock()


def wait(id):
    t = random.random() * 10
    print(f"{id} is working for {t} seconds")
    time.sleep(t)


def output(id):
    print(f"output {id}")


for i in range(5):
    _ = WorkNowPrintLater(i, partial(wait, i), partial(output, i), threads_queue, semaphore)
Beshore answered 10/4, 2023 at 4:8 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.