Run Runnables concurrently in order

Question

So here's my situation:

• I got a few Threads that should do background work, ideally with a ThreadPool/ExecutorService and such
• There are a lot of Runnables generated regularly that call one long method. They should be processed by the background workers.
• The runnables have an order they should be executed in (approximately). The interesting thing is: that ordering is dynamic and might change at any time. So which runnable to take next should be decided as late as possible, directly before running it.
• It should be possible to stop all currently working runnables. If this is not possible, they should be notified so that they discard their work once it's finished.

I don't really know how to approach this problem, and I'm not really familiar with multithreading and Java's APIs in that matter.

About the ordering

What I mean with approximately in order: if they get started in order, it will be good enough. Each Runnable does some work on a tile of a map. The idea is to sort the runnables in such a way, that tiles near the position where the used is looking at will be loaded first and then loading the surroundings. Note that therefore the order of execution might change at any time.

Answer 1

So, I finally got a way around this problem. It's not that beautiful and kind of a hack, but it works as intended.

The idea is: if every Runnable is stateless and does only call one method, it does not need to know the tile it should work on on creation. Instead, it will ask for a needed tile once it's started.

public class WorldRendererGL {

    protected Map<Vector2i, RenderedRegion> regions     = new ConcurrentHashMap<>();
    protected Queue<RegionLoader>           running     = new ConcurrentLinkedQueue<>();
    protected Set<RenderedRegion>           todo        = ConcurrentHashMap.newKeySet();

    protected ExecutorService               executor;

    /** Recalculate everything */
    public void invalidateTextures() {
        //Abort current calculations
        running.forEach(f -> f.invalid.set(true));
        running.clear();
        todo.addAll(regions.values());

        for (int i = 0; i < regions.size(); i++) {
            RegionLoader loader = new RegionLoader();
            running.add(loader);
            executor.submit(loader);
        }
    }

    protected class RegionLoader implements Runnable {

        /** Set this to true to nullify all calculations*/
        final AtomicBoolean invalid = new AtomicBoolean(false);

        @Override
        public void run() {
            try {
                if (invalid.get())
                    return;
                RenderedRegion region = null;
                region = nextRegion(); // Get the correct work at runtime
                if (region == null)
                    return;
                BufferedImage texture = renderer.renderRegion(new RegionFile(region.region.regionFile));
                if (!invalid.get()) {
                    region.texture = texture;
                    update.notifyObservers();
                }
            } catch (Throwable e) {
                e.printStackTrace();
            }
        }
    }

    protected RenderedRegion nextRegion() {
        Comparator<RenderedRegion> comp = (a, b) -> /*...*/);
        RenderedRegion min = null;
        for (Iterator<RenderedRegion> it = todo.iterator(); it.hasNext();) {
            RenderedRegion r = it.next();
            if (min == null || comp.compare(min, r) > 0)
                min = r;
        }
        todo.remove(min);
        return min;
    }
}

Answer 2

you could also use a List to emulate a priority queue. For example:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ListEmulateQueueExample {

    public static void main(String[] args) throws InterruptedException {
        ListEmulateQueueExample priorityQueueExample = new ListEmulateQueueExample();
        priorityQueueExample.doTheWork();
    }

    /**
     * uses a list to emulate a queue.
     */
    private void doTheWork() {
        List<Customer> customerList = Collections.synchronizedList(new ArrayList<>());

        Customer johnCustomer = new Customer("John", 5);
        Customer mariaCustomer = new Customer("Maria", 3);
        Customer anaCustomer = new Customer("Ana", 1);

        customerList.add(johnCustomer);
        customerList.add(mariaCustomer);
        customerList.add(anaCustomer);

        CustomerComparator customerComparator = new CustomerComparator();
        synchronized (customerList){
            customerList.sort(customerComparator);
        }


        System.out.println(customerList.remove(0));  // Ana


        johnCustomer.setUrgency(1);
        synchronized (customerList){
            customerList.sort(customerComparator);
        }

        System.out.println(customerList.remove(0));  // John

    }
}

Answer 3

One solution is to put all the jobs that you want to process into a PriorityBlockingQueue. (This queue is automatically sorted either using the natural ordering of the queue items or by providing a Comparator). then the threads running within the ExecutorService should just take elements from the queue.

for example

import java.util.Comparator;
import java.util.concurrent.PriorityBlockingQueue;

public class PriorityQueueExample {

    public static void main(String[] args) throws InterruptedException {
        PriorityQueueExample priorityQueueExample = new PriorityQueueExample();
        priorityQueueExample.doTheWork();

    }

    private void doTheWork() throws InterruptedException {
        PriorityBlockingQueue<Customer> queue = new PriorityBlockingQueue<>(10, new CustomerComparator());
        queue.add(new Customer("John", 5));
        queue.add(new Customer("Maria", 2));
        queue.add(new Customer("Ana", 1));
        queue.add(new Customer("Pedro", 3));


        while(queue.size() > 0){
            System.out.println(queue.take());
        }
    }
}

class CustomerComparator implements Comparator<Customer> {

    @Override
    public int compare(Customer o1, Customer o2) {
        return o1.getUrgency() - o2.getUrgency();
    }
}

class Customer {
    private String name;
    private int urgency;

    public Customer(String name, int urgency) {
        this.name = name;
        this.urgency = urgency;
    }

    public String getName() {
        return name;
    }

    public int getUrgency() {
        return urgency;
    }

    @Override
    public String toString() {
        return "Customer{" +
                "name='" + name + '\'' +
                ", urgency=" + urgency +
                '}';
    }
}

Answer 4

1) Have your tiles implements Callable. You can have them return Callable too.

2) Determine which ones are position to be loaded first.

3) Pass them or their Callables into java.util.concurrent.ExecutorService.invokeAll.

4) Once invokeAll is returned get the next set of tiles adjacent to the previous ones and call java.util.concurrent.ExecutorService.invokeAll again.

5) Repeat step 4 if necessary.