Java-高效的调度结构？

Question

我对这个问题的长度表示歉意，但我认为包含足够的细节很重要，因为我正在寻找解决问题的合适方法，而不是简单的代码建议！

---

一般描述：

我正在开发一个项目，该项目需要能够以某个相对重复间隔“安排”任务。

这些间隔以某个内部时间表示，表示为随着程序执行而递增的整数（所以不等于实时）。每次发生这种情况时，都会询问计划以检查是否有在此时间步执行的任何任务。

如果执行了任务，则应重新安排其在相对于当前时间的位置再次运行（例如，以 5 个时间步长）。该相对位置简单地存储为任务对象的整数属性。

问题：

我正在努力决定如何构建它 - 部分原因是它是一组稍微难以查找的搜索词。

就目前情况而言，我认为每次计时器递增时，我都需要：

1. 在计划中的“0”位置执行任务
2. 将这些任务重新添加到计划中的相对位置（例如，每 5 次重复的任务）步骤将返回到位置 5)
3. 计划中的每组任务的“执行时间”都会减一（例如位置 1 的任务将移动到位置 0）

假设：

有几个假设可能会限制可能的我可以使用的解决方案：

• 间隔必须是相对的，而不是特定时间，并且被定义为距离当前时间的整数步数
• 这些间隔可以采用任何整数值，例如不受限制。。
• 多个任务可以安排在同一时间步长，但它们的执行顺序并不重要
• 所有执行都应保留在单个线程中 - 多线程解决方案不适用 由于其他限制而适合

我的主要问题是：

我如何设计此时间表以有效地工作？哪些数据类型/集合可能有用？

我应该考虑另一种结构/方法吗？

我是否错误地放弃了调度框架（例如 Quartz），它似乎在“实时”时域而不是“非实时”时域？

---

非常感谢您提供任何可能的帮助。如果有需要，请随时评论以获取更多信息，我会在需要的地方进行编辑！

Answer 1

嗯，Quartz 是非常强大的工具，但是它的配置可能性有限，因此如果您需要特定功能，您应该编写自己的解决方案。

然而，研究Quartz源代码和数据结构是个好主意，因为它们已经成功地解决了很多问题，你会发现fg数据库级别的进程间同步、运行延迟任务等。

我'我曾经编写过自己的调度程序，该调度程序适用于 Quartz 可能不容易适应的任务，但是一旦我学习了 Quartz，我就了解了我的解决方案可以改进多少，知道它是如何在 Quartz 中完成的。

Answer 2

怎么样，它使用您自己的 Ticks 和 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();
            }
        }
    }
}

您可能想添加一些错误处理，但它应该可以完成您的工作。

这里有一些单元测试:)

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 3

循环链表可能就是您正在寻找的数据结构。您无需递减每个任务元素中的字段，只需递增任务循环列表中“当前”字段的索引即可。伪代码结构可能看起来像这样：

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

任何时候你安排一个新任务，你只需将它添加到当前“tick”前面 N 个刻度的位置

Answer 4

这里有一些想法：

一切保持简单。如果您没有数百万个任务，则不需要优化的数据结构（除了骄傲或过早优化的冲动）。

避免相对时间。使用绝对内部刻度。如果添加任务，请将“下次运行”设置为当前刻度值。将其添加到列表中，按时间对列表进行排序。

查找任务时，从列表的开头开始，选择时间 <= 当前刻度的所有内容，运行该任务。

将所有这些任务收集到另一个列表中。全部运行完毕后，根据当前的刻度和增量计算“下次运行”（这样就不会得到循环的任务），将它们全部添加到列表中，排序。

Answer 5

看一下 DelayQueue 使用 PriorityQueue 来维护此类有序事件列表的方式。 DelayQueue 实时工作，因此可以使用 Condition 和 LockSupport 中提供的可变定时等待方法。您可以实现类似 SyntheticDelayQueue 的功能，其行为方式与 DelayQueue 相同，但使用您自己的合成时间服务。显然，您必须替换 jdk 免费提供的定时等待/信号机制，而这对于高效地完成可能并不简单。

Answer 6

如果我必须这样做，我会创建一个简单的队列（链表变体）。该队列将包含一个动态数据结构（例如简单列表），其中包含需要完成的所有任务。在每个时间间隔（或时间步），进程读取队列的第一个节点，执行它在该节点的列表中找到的指令。在每次执行结束时，它将计算重新调度并将新执行添加到队列中的另一个节点，或者在将指令存储在该节点内之前创建直到该位置的节点。然后删除第一个节点，并在下一个时间步执行第二个节点（现在是第一个）。该系统也不需要跟踪任何整数，并且所需的所有数据结构都可以在 java 语言中找到。这应该可以解决你的问题。

Answer 7

使用 ScheduledExecutorService。它内置了您需要的一切。使用起来非常简单：

// 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