-1

This question was completely reedited to be fully in line with the SE guidelines and builds on top of already given comments.

I'll try to introduce some vocabulary to better describe the generic terms I use in my concrete problem setting:

Source - A source is basically just a data object with associated jobs. There are many sources (10 to 100 roughly) active, new sources can be added and some sources can be removed. Currently, there is exactly 1 job queued per source, and the job (chain of tasks) is calculated when the last job for a source finishes. I could think of calculating few jobs in advance by another module in the application.

Job - A job is a graph of tasks. Execution of the tasks will in reality be mostly sequential, but some will be able to be executed in parallel. A job has an associated trigger time at which it is scheduled to run. Those times however will be calculated dynamically, based on previous job runs, external data and a pinch of randomness. Without going into too much detail, one could think of a monitoring application that reacts at times rather than to events. Which tasks in which order are selected for a new job is also dynamically calculated.

Task - A task is a processing step which take some time. Most tasks are offloaded to a new process (think of Python/machine learning).

In practice, the times at which jobs get scheduled, are often close together. Some jobs (with a very particular graph of tasks) may only be scheduled once a week or so, others get scheduled twice per day. That together with the fact that the execution of a whole job (wait for all tasks to be completed) can take some time and the fact that there are many sources leads to a lot of overlap.

One idea I haven't explored yet is breaking up the jobs into their individual tasks.

Some pseudocode:

class Job {
    Time runAt;
    Graph<Task> tasks;

    void run() {
        // this can take quite a while
        tasks.executeAll();
    }
}

// keep one thread per source so there is one thread guaranteed to be free for a scheduled job
val scheduler = ScheduledExecutorService.newScheduledThreadpool(sources.size());

// whenever a new job was calculated
scheduler.addOneShotAction(job, job.runAt);

So the current approach comes with the problem that the threadpool is huge (100 threads in some deployments). But it is important to me that a new job once scheduled can immediately start working. Since there is a lot of offloading involved it seems like a really good idea to break the jobs apart to make use of the waiting time in between.

But the tasks itself are not scheduled at a specfic time but should be run as soon as all requirements are met ("parents" in the graph have finished).

Which leads to the question: How could I (optimally) schedule my individual tasks, of which the first task associated with a job has a fixed start time, and the remaining are run in a best effort manner?

8
  • Not sure why you are looking for other approaches, it sounds like your threadpool solution solves your problem. I could imagine scenarios where this solution wouldn't work, but I don't think it would make sense to list them all, since they might not be relevant to your situation. Do you have any other constraints? – Helena Apr 18 at 11:05
  • Finding all the constraints is hard, and they will change over time. This question is not meant to produce the specific solution for a specific problem (that what SO is for), but to get an overview of different approaches so I can hopefully learn and choose the best for any situation I might encounter. – flowit Apr 18 at 11:33
  • 1
    I think this question is too open for that, and I doubt it is a good format for this SE, though I don't know what the rules are (or where to find them). – Helena Apr 18 at 11:36
  • I guess this describes it: softwareengineering.meta.stackexchange.com/questions/7537/… – Helena Apr 18 at 11:39
  • In that case please ignore the above comment. I'd say the question is still valid and follows the rules when interpreted as "Are the given options 1) and 2) valid solutions to this problem? And might there be a better solution for the (more or less) concrete example given?" – flowit Apr 18 at 11:47
0

I would go with a message queue + multiple workers approach.

workers pull jobs from the queue, check the start date of each. if its now() or near enough they run the task. if its not they put it back on the queue.

The fundamental problem you have with a single worker is that if its currently running its max number of tasks, there is no cpu left to start another one on time.

Secondly, if it ever crashes you have lost your "waiting" tasks. Although you can presumably add persistence.

Thirdly! potentially you could run out of memory, having 1000's of pending tasks that don't have to run for days.

The MQ approach allows you to scale up the workers, fixes the persistence problem and the memory issue.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.