「项目复现」linux并发编程之计时器

服务器程序通常管理着众多定时事件，比如定期检测一个客户连接的活动状态，因此有效地组织这些定时事件，使之能在预期的时间点被触发且不影响服务器的主要逻辑，对于服务器的性能有着至关重要的影响。

为此，程序员通常将每个定时事件分别封装成定时器，并使用某种容器类数据结构（比如链表、排序链表和时间轮），将所有定时器串联起来，以实现对定时事件的统一管理。

设计定时器的一种思路是将所有定时事件放入一个排序容器，主循环以固定的频率调用一个心搏函数tick()，在其中依次检测到期的定时器，然后执行到期定时器上的回调函数。

设计定时器的另一种思路是：使用时间堆，将所有定时事件放在一个最小堆中，将最小堆中的堆顶元素的到期时间最近的时间间隔作为心搏间隔。这样，一旦心搏函数tick()被调用，超时时间最小的定时器必然到期，我们就可以在tick函数中处理该定时器。然后，再次从剩余的定时器中找出超时时间最小的一个，并将这段最小时间设置为下一次心搏间隔。如此反复，就实现了较为精确的定时。

1、计时器的数据结构

#include <chrono>
typedef std::function<void()> TimeoutCallBack;// 返回值为空的对象，定时回调
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::milliseconds MS;// 毫秒级别
typedef Clock::time_point TimeStamp;// 时间点，单位秒数
struct TimerNode {
    int id;// 标识符，该项目中是socket描述符
    TimeStamp expires;// 到期时间点，使用的自1970年开始的绝对时间，单位：秒
    TimeoutCallBack cb;// 定时回调函数，到期时应该执行的操作
    // < 运算符重载函数，用来比较不同的时间点，方便排序
    bool operator<(const TimerNode& t) {
        return expires < t.expires;
    }
};
std::vector<TimerNode> heap_;// 时间堆（最小堆，到期时间最小的在第1个）
std::unordered_map<int, size_t> ref_;// 哈希表<TimerNode.id,>

2、计时器的初始化

HeapTimer() { heap_.reserve(64);// 初始化容量为64 }

3、执行定时事件

int HeapTimer::GetNextTick() {
    tick();// 跳动函数，执行所有到期的定时事件
    size_t res = -1;
    // 如果堆不为空
    if(!heap_.empty()) {
        // 计算堆顶元素的到期间隔
        res = std::chrono::duration_cast<MS>(heap_.front().expires - Clock::now()).count();
        if(res<0) {res=0;}
    }
    return res;
}
// 跳动函数（执行定时事件）
void HeapTimer::tick() {
    if(heap_.empty()) {
        return;
    }
    // 遍历堆，将所有到期的定时事件全部执行
    while(!heap_.empty()) {
        TimerNode node = heap_.front();//取第一个节点
        // 如果还没有到期，跳出循环
        if(std::chrono::duration_cast<MS>(node.expires - Clock::now()).count() > 0) { 
            break; 
        }
        node.cb();// 调用回调函数
        pop();// 去除该节点
    }
}
// 删除最后一个节点
void HeapTimer::pop() {
    assert(!heap_.empty());
    del_(0);
}
void HeapTimer::del_(size_t index) {
    /* 删除指定位置的结点 */
    assert(!heap_.empty() && index >= 0 && index < heap_.size());
    /* 将要删除的结点换到队尾，然后调整堆 */
    size_t i = index;
    size_t n = heap_.size() - 1;
    assert(i <= n);
    if(i < n) {
        SwapNode_(i, n);
        if(!siftdown_(i, n)) {
            siftup_(i);
        }
    }
    /* 队尾元素删除 */
    ref_.erase(heap_.back().id);
    heap_.pop_back();
}

4、添加定时事件

添加一个定时事件

m_pTimer->add(fd, timeoutMS_, bind(&WebServer::CloseConn_, this, &m_UsersDict[fd]));

// 添加一个定时事件，参数分别是socket描述符、时间间隔、回调函数
void HeapTimer::add(int id, int timeout, const TimeoutCallBack& cb) {
    assert(id >= 0);
    size_t i;
    // 如果ref_中不存在id，队尾添加新节点，调整堆
    if(ref_.count(id) == 0) {
        i = heap_.size();// 大小
        ref_[id] = i;
        heap_.push_back({id, Clock::now() + MS(timeout), cb});// 添加一个TimerNode
        siftup_(i);
    } 
    // 如果ref_中不存在id，覆盖原有节点，调整堆
    else {
        i = ref_[id];
        heap_[i].expires = Clock::now() + MS(timeout);
        heap_[i].cb = cb;
        if(!siftdown_(i, heap_.size())) {
            siftup_(i);
        }
    }
}

调整某个定时事件：m_pTimer->adjust(client->GetFd(), timeoutMS_);

void HeapTimer::adjust(int id, int timeout) {
    /* 调整指定id的结点 */
    assert(!heap_.empty() && ref_.count(id) > 0);
    heap_[ref_[id]].expires = Clock::now() + MS(timeout);;
    siftdown_(ref_[id], heap_.size());
}

5、调整堆结构

void HeapTimer::SwapNode_(size_t i, size_t j) {
    assert(i >= 0 && i < heap_.size());
    assert(j >= 0 && j < heap_.size());
    std::swap(heap_[i], heap_[j]);
    ref_[heap_[i].id] = i;
    ref_[heap_[j].id] = j;
} 
void HeapTimer::siftup_(size_t i) {
    assert(i >= 0 && i < heap_.size());// 检查参数是否合法
    size_t j = (i-1) / 2;
    while(j >= 0) {
        if(heap_[j] < heap_[i]) { break; }
        SwapNode_(i, j);
        i=j;// 更新i
        j=(i-1)/2;// 更新j
    }
}
bool HeapTimer::siftdown_(size_t index, size_t n) {
    assert(index >= 0 && index < heap_.size());// 检查参数是否合法
    assert(n >= 0 && n <= heap_.size());// 检查参数是否合法
    size_t i = index;
    size_t j = i * 2 + 1;
    while(j < n) {
        if(j + 1 < n && heap_[j + 1] < heap_[j]) j++;
        if(heap_[i] < heap_[j]) break;
        SwapNode_(i, j);// 交换两个节点
        i = j;
        j = i * 2 + 1;
    }
    return i > index;
}