c++ - 如何有效地处理单个时间线上传入的延迟事件？

Question

我想实现等待某些事件并在延迟一段时间后处理它们的算法。每个事件都有其自己的预定义延迟。该处理程序可以在单独的线程中执行。 CPU 节流、主机过载等问题可能会被忽略 - 它并不是一个精确的实时系统。

示例。

• 在时刻 N 到达一个延迟 1 秒的事件。我们希望在 N + 1 秒的时刻处理它。
• 在 N + 0.5 秒的时刻，另一个事件到达，延迟了 0.3 秒。我们希望在 N + 0.8 秒的时刻处理它。

方法。

我想到的唯一直接的方法是在迭代之间使用一个尽可能最小延迟的循环(例如每 10 毫秒)，并检查现在是否应该处理时间线上的任何事件。但这不是一个好主意，因为延迟可能会从 10 毫秒到 10 分钟不等。

另一种方法是让单个线程在事件之间休眠。但是，当从现在到下一次计划的唤醒之间有一个应该处理的新事件时，我不知道如何强制“唤醒”它。

此外，还可以为每个事件使用一个线程并只是休眠，但是可能有数千个同时发生的事件，这实际上可能会导致线程耗尽。

该解决方案可以与语言无关，但我更喜欢 C++ STD 库解决方案。

Answer 1

Another approach is to have a single thread that sleeps between events. But I can't figure out how to forcefully "wake" it when there is a new event that should be handled between now and the next scheduled wake up.

我认为这些问题的解决方案是，至少在 *nix 系统上，poll或epoll在 timer 的帮助下。它允许您让线程休眠，直到发生某个给定事件。给定事件可能是 stdin 上出现的事件或计时器超时。由于问题是关于通用算法/算法思想，并且代码会占用大量空间，因此我仅给出伪代码:

epoll = create_epoll();
timers = vector<timer>{};

while(true) {
    event = epoll.wait_for_event(timers);

    if (event.is_timer_timeout()) {
        t = timers.find_timed_out();
        t.handle_event();
        timers.erase(t);
    } else if (event.is_incoming_stdin_data()) {
        data = stdin.read();
        timers.push_back(create_timer(data));
    }
}