Java efficient schedule structure?

Question

I apologize for the length of this problem, but I thought it was important to include sufficient details, given that I was looking for a suitable approach to my problem, and not just suggesting a code!

---

general description

I am working on a project that requires tasks to be “scheduled” at some relative recurring interval.

These intervals refer to some internal time, which is represented as an integer that increases during program execution (which is not equal to real time). Each time this happens, the schedule will be interogated to check for any tasks that must be performed at this time interval.

If the task is being executed, it should be reconfigured to restart at a position relative to the current time (for example, 5 time stamps). This relative position is simply stored as an integer property of the Task object.

Problem:

I'm struggling a bit to decide how to structure it, partly because it's a bit of a complex set of search queries to search.

Be that as it may, I think that every time the timer increases, I need:

• Performing tasks at position "0" in the schedule
• Re-add these tasks to the schedule again in their relative position (for example, a task repeating every 5 steps will be returned to position 5)
• Each group of tasks in the schedule will have its own "time to completion", reduced (for example, the task in position 1 will move to position 0)

Assumption:

There are several suggestions that may limit the possible solutions that I can use:

• The interval should be relative, not a specific time, and is defined as an integer number of steps from the current time
• These intervals can take any integer value, for example. not limited.
• Several tasks can be scheduled for the same time, but their order of execution is not important.
• All execution should remain in one thread - multithreaded solutions are not suitable due to other restrictions

The main questions that I have are:

How can I design this schedule to work efficiently? What types of data / collections can be useful?

Is there any other structure / approach I should consider?

Am I wrong to reject planning frameworks (like quartz) that seem to work more in the "real" time domain, rather than the "unreal" time domain?

---

Thanks so much for any possible help. Please do not hesitate to comment on additional information, if necessary, I will edit where necessary!

Answer 1

How about this, it uses your own Ticks with executeNextInterval ():

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Scheduler { private LinkedList<Interval> intervals = new LinkedList<Scheduler.Interval>(); public void addTask(Runnable task, int position) { if(position<0){ throw new IllegalArgumentException(); } while(intervals.size() <= position){ intervals.add(new Interval()); } Interval interval = intervals.get(position); interval.add(task); } public void executeNextInterval(){ Interval current = intervals.removeFirst(); current.run(); } private static class Interval { private List<Runnable> tasks = new ArrayList<Runnable>(); public void add(Runnable task) { tasks.add(task); } public void run() { for (Runnable task : tasks) { task.run(); } } } } 

You might want to add some error handling, but it should do your job.

And here are some UnitTests for him :)

 import junit.framework.Assert; import org.junit.Test; public class TestScheduler { private static class Task implements Runnable { public boolean didRun = false; public void run() { didRun = true; } } Runnable fail = new Runnable() { @Override public void run() { Assert.fail(); } }; @Test public void queue() { Scheduler scheduler = new Scheduler(); Task task = new Task(); scheduler.addTask(task, 0); scheduler.addTask(fail, 1); Assert.assertFalse(task.didRun); scheduler.executeNextInterval(); Assert.assertTrue(task.didRun); } @Test public void queueWithGaps() { Scheduler scheduler = new Scheduler(); scheduler.addTask(fail, 1); scheduler.executeNextInterval(); } @Test public void queueLonger() { Scheduler scheduler = new Scheduler(); Task task0 = new Task(); scheduler.addTask(task0, 1); Task task1 = new Task(); scheduler.addTask(task1, 1); scheduler.addTask(fail, 2); scheduler.executeNextInterval(); scheduler.executeNextInterval(); Assert.assertTrue(task0.didRun); Assert.assertTrue(task1.didRun); } } 

Answer 2

Well, Quartz is a pretty powerful tool, but it has limited customization options, so if you need specific features, you have to write your own solution in advance.

However, it is useful to study the Quartz source code and data structures because they have successfully dealt with many problems that you will find, for example. interprocess synchronization at the database level, triggering delays, etc.

I wrote once my own scheduler, which was adapted to tasks in which, perhaps, Quartz could be easily adapted, but as soon as I learned Quartz, I realized how much I could improve my decisions, knowing how to do it was done in Quartz.

Answer 3

A circular linked list may be the data structure you are looking for. Instead of decreasing the fields in each element of the task, you simply increase the index of the current field in the circular list of tasks. The structure of the pseudocode might look something like this:

 tick(): current = current.next() for task : current.tasklist(): task.execute() 

anytime you are planning a new task, you simply add it to position N, pointing forward from the current “tick”

Answer 4

Here are a few thoughts:

Keep it simple. If you do not have millions of tasks, there is no need for an optimized data structure (other than pride or the desire for premature optimization).

Avoid relative times. Use an absolute inner tick. If you add a task, set "run next time" to the current checkmark value. Add it to the list, sort the list by time.

When searching for tasks, run at the head of the list and select everything that has time <= current tick, run the task.

Collect all these tasks in a different list. After everything is started, calculate "run next time" based on the current tick and increment (so that you do not get tasks that performed the cycle), add all of them to the list, sort.

Answer 5

See how DelayQueue uses PriorityQueue to maintain such an ordered list of events. DelayQueue works in real time and therefore can use the time-based wait methods available in Condition and LockSupport . You can implement something like SyntheticDelayQueue , which behaves the same as DelayQueue , but uses your own synthetic time service. You will obviously have to replace the synchronized wait / signaling mechanisms that are provided for free with jdk, although this may not be trivial for efficient execution.

Answer 6

If I had to do this, I would create a simple queue (a variant of a linked list). This queue will contain a dynamic data structure (for example, a simple list) containing all the tasks that need to be performed. At each time interval (or time step), the process reads the first node of the queue, executes the commands that it finds in the list of this node. At the end of each execution, he would compute the redistribution and add a new execution to another node in the queue or create nodes to this position before storing the instruction in that node. The first node is then deleted, and the second node (now the first) is executed in the next step. This system would also not require tracking integers, and all the necessary data structures were found in the Java language. This should solve your problem.

Answer 7

Use ScheduledExecutorService . It has everything you need built in. Here's how simple it is:

 // Create a single-threaded ScheduledExecutorService ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1); // 1 thread // Schedule something to run in 10 seconds time scheduler.schedule(new Runnable() { public void run() { // Do something }}, 10, TimeUnit.SECONDS); // Schedule something to run in 2 hours time scheduler.schedule(new Runnable() { public void run() { // Do something else }}, 2, TimeUnit.HOURS); // etc as you need