Circular message/task queue existing solution

Question

Consider there's a finite set of tasks that must be completed within a certain period of time (being evenly distributed across that period too), and then repeated again and again.

In case of one local worker/thread, we just do something like this (sorry for the pseudocode):

long interval = period / tasks.size

while (true) {
  for (task in tasks) { 
    task.do()
    sleep(interval)
  }
}

Now I want to do this in a distributed manner, with multiple independent workers.

Is there some known best practice solution (preferably from Java world) for a case like this? Circular message queues? Distributed locks on tasks? I've googled quiet a bit, but can't see any elegant out of the box solution.

Answer 1

I don't think there's a single "best" approach for this, as it will be a tradeoff between flexibility and the strength of your evenness guarantees.

At the flexible end of the spectrum, just randomly assign each task to a worker at some time during the period. This will need no communication between workers, so this is scalable and parallelizable. You will have some expectation that things should be fairly even, especially if you have a lot of tasks.

At the strong evenness end of the spectrum, you should divide the tasks by worker and by timeslot as shown by @Lino. This will require you to know in advance how many workers you have etc., and it is not parallelizable.

There are many alternate approaches that fall in between these two extremes, as well as hybrid approaches.

To narrow down the answers, you will need to provide more detail about your constraints and your criteria for success.

Answer 2

Below I just dumped the code I came up with. I tried to comment every step that I did. But in short it just distributes the workLoad of all tasks evenly to all available workers. And calculates the waiting time to fulfill all tasks in the given amount of milliseconds

// the tasks we want to execute
final List<Runnable> tasks = Arrays.asList(
    () -> System.out.println("First"),
    () -> System.out.println("Second"),
    () -> System.out.println("Third"),
    () -> System.out.println("Fourth")
);

// amount of threads
final int amountOfWorkers = 2;

// period in milliseconds
final int period = 1000;

// caching the size for multiple use
final int tasksSize = tasks.size();

// calculating the workload of each worker
final int workLoad = (int) Math.ceil((double) tasksSize / amountOfWorkers);

// interval of sleep for each worker
final int workerPeriod = period / workLoad;

// a list of all workers
final List<Thread> workers = new ArrayList<>();

// in this for loop we create each worker and add it to above list
for(int i = 0; i < amountOfWorkers; i++){
    // calculating the start of the sublist
    final int startIndex = i * workLoad;
    // calculating the end of the sublist
    final int endIndex = (i + 1) * workLoad;
    // here we create the subTasks for each worker, we need to take into account that the tasksList may not 
    // divide fully. e.g. 7 for 4 workers leaves the last worker with only one task
    final List<Runnable> subTasks = tasks.subList(startIndex, endIndex < tasksSize ? endIndex : tasksSize);
    // creating the worker itself
    final Thread worker = new Thread(() -> {
        for(final Runnable subTask : subTasks){
            try{
                subTask.run();
                Thread.sleep(workerPeriod);
            } catch(InterruptedException e){
                throw new IllegalStateException(e);
            }
        }
    });

    // add it to our worker list
    workers.add(worker);
    // and start it
    worker.start();
}

// at last we wait in the main thread for all workers to finish
for(final Thread worker : workers){
    worker.join();
}

This can of course be put into a class, which takes input parameters such as:

• amount of workers
• execution period
• tasks

Which would be more OOP. If requested I could provide that code too, but above should give you a rough idea.