用一个物理计时器模拟多个虚拟计时器

Question

我正在尝试使用 C 实现选择性重复协议来进行网络分配，但对如何模拟每个单独数据包的计时器感到困惑。我只能访问一个计时器，并且只能调用如下所述的函数。

/* start timer at A or B (int), increment in time*/
extern void starttimer(int, double);       

/* stop timer at A or B (int) */
extern void stoptimer(int);             

Kurose 和 Ross 在他们的网络教科书中提到

可以使用单个硬件定时器来模拟 多个逻辑定时器的操作 [Varghese 1997]。

我发现了以下类似作业的提示

您可以使用单个物理计时器模拟多个虚拟计时器。基本思想是，您保持一系列按到期时间排序的虚拟计时器，并且物理计时器将在第一个虚拟计时器到期时关闭。

但是，我无法访问除 RTT 之外的任何时间变量，因为模拟器位于另一抽象层。在这种情况下，如何实现单个数据包的计时器？

Answer 1

您可以按照在内核级别实现的相同方式来完成此操作。您需要有一个“计时器”链接列表，其中每个计时器都有相对于前一个计时器的超时。它会是这样的： 定时器 1：距 t0 500 毫秒，定时器 2：距 t0 400 毫秒，定时器 3 距 t0 1000 毫秒。

然后你将得到一个链表，其中每个元素都有相对于前一个元素的超时时间，如下所示：

HEAD->定时器2(400ms)->定时器1(100ms)->定时器3(500ms)

每个元素包含最小值：timerID、相对超时、绝对初始化时间（纪元的时间戳）。您可以为每个计时器添加一个回调指针。

您使用唯一的计时器并将超时设置为列表中第一个元素的相对超时：400ms（计时器2）

超时后，您将删除第一个元素，可能会执行与 Timer2 相关的回调，理想情况下该回调是与另一个工作线程一起执行的。然后，您将新的超时设置为下一个元素的相对超时，Timer1：100ms。

现在，当您需要创建一个新计时器时，例如在 t0 300 毫秒后的 3,000 毫秒处，您需要将其插入到导航计时器链接列表的正确位置。 Timer4 中的相对超时将为 2,300。这是通过 (Timer2.RelativeTimeout - (now - Timer2.AbsoluteTimeout)) 计算的，并通过链表查找相应的位置，添加每个先前元素的相对超时。您的链接列表将变成：

HEAD->定时器2(400ms)->定时器1(100ms)->定时器3(500ms)->定时器4(2,300)

通过这种方式，您可以使用一个物理计时器来实现多个逻辑计时器。您的计时器创建和查找时间将为 O(n)，但您可以添加各种改进来提高插入性能。最重要的是定时器超时处理和更新是 O(1)。查找计时器的删除复杂度为 O(n)，删除复杂度为 O(1)。

您必须注意控制计时器的线程与插入或删除计时器的线程之间可能存在的竞争条件。在用户空间中实现此计时器的一种方法是使用条件变量和等待超时。

Answer 2

使用C++向量来实现这个问题：

#include <iostream>
#include <chrono>
#include <functional>
#include <vector>
#include <algorithm>
#include <mutex>
#include <thread>

using Clock = std::chrono::high_resolution_clock;
using TimePoint = Clock::time_point;

struct Timer {
    TimePoint expiration_time;      // time when this timer expires
    int timeout_ms;                 // duration in milliseconds
    std::function<void()> callback; // callback to execute
    bool is_recurring;              // flag to indicate if the timer is recurring

    // overloaded operator to sort timers by expiration time
    bool operator<(const Timer& other) const {
        return expiration_time < other.expiration_time;
    }
};

class Manager {
public:
    Manager() : physical_timer_running(false) {}

    void set_timer(int relative_timeout_ms, std::function<void()> cb, bool recurring = false) {
        std::lock_guard<std::mutex> lock(mutex_);

        // create a new virtual timer
        Timer new_timer;
        new_timer.timeout_ms = relative_timeout_ms;
        // calculate expiration time:
        new_timer.expiration_time = Clock::now() + std::chrono::milliseconds(relative_timeout_ms);
        new_timer.callback = cb;
        new_timer.is_recurring = recurring; // set the recurrence flag

        // add the new timer to the list and sort
        timers_.push_back(new_timer);
        std::sort(timers_.begin(), timers_.end());

        // ff no physical timer is running, start one
        if (!physical_timer_running) {
            set_physical_timer();
        }
    }

    void set_physical_timer() {
        if (timers_.empty()) return;

        // get the next timer
        Timer next_timer = timers_.front();
        auto now = Clock::now();

        // check if the next timer has already expired
        if (now >= next_timer.expiration_time) {
            // immediately execute the callback
            timers_.erase(timers_.begin());

            // execute the callback
            next_timer.callback();

            // if the timer is recurring, reset its expiration time
            if (next_timer.is_recurring) {
                next_timer.expiration_time = Clock::now() + std::chrono::milliseconds(next_timer.timeout_ms);
                timers_.push_back(next_timer);             // re-insert the timer
                std::sort(timers_.begin(), timers_.end()); // re-sort the timer list
            }

            // restart the physical timer if there are more timers left
            if (!timers_.empty()) {
                set_physical_timer();
            }
            return;
        }

        physical_timer_running = true;

        // calculate the wait duration until the next expiration time
        auto wait_duration = std::chrono::duration_cast<std::chrono::milliseconds>(next_timer.expiration_time - now).count();
        physical_timer_thread = std::thread([this, next_timer, wait_duration]() {
            std::this_thread::sleep_for(std::chrono::milliseconds(wait_duration));
            std::lock_guard<std::mutex> lock(mutex_);
            timers_.erase(timers_.begin()); // remove the expired timer
            physical_timer_running = false;
            // execute the callback
            next_timer.callback();
            // if the timer is recurring, reset its expiration time
            if (next_timer.is_recurring) {
                TimePoint t = Clock::now() + std::chrono::milliseconds(next_timer.timeout_ms);
                std::memcpy((void*)&(next_timer.expiration_time), &t, sizeof(next_timer.expiration_time));
                timers_.push_back(next_timer); // reinsert the timer
                std::sort(timers_.begin(), timers_.end()); // re-sort the timer list
            }
            // restart the physical timer if there are still timers left
            if (!timers_.empty()) {
                set_physical_timer();
            }
        });
        physical_timer_thread.detach();
    }

private:
    std::vector<Timer> timers_;        // list of timers
    std::mutex mutex_;                 // mutex for thread safety
    std::thread physical_timer_thread; // thread for the physical timer
    bool physical_timer_running;       // flag to track if the physical timer is running
};

// Test
int main() {
    Manager tm;

    // set a recurring timer for every 1000 ms
    tm.set_timer(1000, []() {
        std::cout << "Recurring timer 1000ms expired!" << std::endl;
    }, true);
    // set a recurring timer for every 1500 ms
    tm.set_timer(1500, []() {
        std::cout << "Recurring timer 1500ms expired!" << std::endl;
    }, true);

    // let the program run for a while to see the timers expire
    std::this_thread::sleep_for(std::chrono::seconds(10));
    
    return 0;
}