How to efficiently handle incoming delayed events on a single timeline?

user_377393 0
Viewed 105

I want to implement the algorithm that awaits for some events and handles them after some delay. Each event has it's own predefined delay. The handler may be executed in a separate thread. The issues with the CPU throttling, the host overload, etc. may be ignored - it's not intended to be a precise real-time system.

Example.

  • At moment N arrives an event with delay 1 second. We want to handle it at moment N + 1 sec.
  • At moment N + 0.5 sec arrives another event with delay 0.3 seconds. We want to handle it at moment N + 0.8 sec.

Approaches.

The only straightforward approach that comes to my mind is to use a loop with minimal possible delay inbetween iterations, like every 10 ms, and check if any event on our timeline should be handled now. But it's not a good idea since the delays may vary on scale from 10 ms to 10 minutes.

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.

Also it's possible to use a thread per event and just sleep, but there may be thousands of simultanious events which effectively may lead to running out of threads.

The solution can be language-agnostic, but I prefer the C++ STD library solution.

c++20 algorithm c++
2 Answers

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.

I suppose solution to these problems are, at least on *nix systems, poll or epoll with some help of timer. It allows you to make the thread sleep until some given event. The given event may be something appearing on stdin or timer timeout. Since the question was about a general algorithm/idea of algorithm and the code would take a lot of space I am giving just pseudocode:

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));
    }
}
user_34149000

Two threads that share a priority queue.

Arrivals thread: Wait for arrival. When event arrives calculate time for handler to run. Add handler to queue with priority of handler time ( the top of the queue will be the next event that is to be handled

Handler thread: Is now equal to time of handler at top of queue then run handler. Sleep for clock resolution.

Note: check if your queue is thread safe. If not, then you will have to use a mutex.

This looks simple, but there a lot of gotchas waiting for the inexperienced. So, I would not recommend coding this from scratch. It is better to use a library. The classic is boost::asio. However, this is beginning to show its age and has way more bells and whistles than are needed. So, personally, I use something more lightweight and coded in C++17 - a non blocking event waiter class I coded that you can get from https://github.com/JamesBremner/await. Notice the sample application using this class which does most of what you require https://github.com/JamesBremner/await/wiki/Event-Server

user_165820
Related