网易面试：手撕定时器

概述：

本文使用STL容器-set以及Linux提供的timerfd来实现定时器组件

所谓定时器就是管理大量定时任务，使其能按照超时时间有序地被执行

需求分析：

1.数据结构的选择：存储定时任务

2.驱动方式：如何选择一个任务并执行

一、数据结构的选择：红黑树

红黑树是一种查找、删除、插入时间复杂度为O(logN)的数据结构，性能均衡，STL的set和map就是基于红黑树实现的，与普通的红黑树不同，STL的红黑树设计添加了指向最大节点和最小节点的指针，这一点实现了set和map可以使用O（1）的时间复杂度查找最大值和最小值：

在这里插入图片描述

二、驱动方式：timerfd + epoll

Linux提供了定时机制timerfd，与sockfd一样，内核负责检测该文件描述符的就绪情况，并需要epoll等io多路复用机制向用户层通知

三、代码实现

1.定时任务节点：

struct TimerNodeBase { //  定时器节点基类，用于红黑树（set）存储
    time_t expire;     //  超时时间
    uint64_t id;       //  唯一 id， 用于解决超时时间相同的节点存储问题
};

struct TimerNode : public TimerNodeBase {  // 子类定时器节点， 添加了一个回调函数
    using Callback = function<void(const TimerNode &node)>;
    Callback func;
    TimerNode(int64_t id, time_t expire, Callback func) : func(std::move(func)) { // 使用 move 右值引用，性能高
        this->expire = expire;
        this->id = id;
    }
};

这里设计两个结构体的目的是将回调函数和其它属性（超时时间和id）隔离开

2.运算符重载，用于比较两个节点的大小（超时时间大小）

bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) { // 运算符重载，比较两个节点的大小
    // 先根据超时时间判定大小
    if (lhd.expire < rhd.expire) {
        return true;
    } else if (lhd.expire > rhd.expire) {
        return false;
    } // 超时时间相同时，根据 id 判断大小
    else return lhd.id < rhd.id;
}

3.定时器类：

class Timer {

public:
    static inline time_t GetTick() { // 获取系统当前时间戳
        return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now().time_since_epoch()).count();
    }

    TimerNodeBase AddTimer(int msec, TimerNode::Callback func) {
        time_t expire = GetTick() + msec; // msec是相对超时时间，expire是绝对超时时间（时间戳）
        // 如果待插入节点当前不是红黑树中最大的
        if (timeouts.empty() || expire <= timeouts.crbegin()->expire) { 
            auto pairs = timeouts.emplace(GenID(), expire, std::move(func)); // emplace是在容器内部生成一个对象并插入到红黑树中，性能优于push的copy操作  2.使用move右值引用，避免copy
            // 使用static_cast将子类cast成基类
            return static_cast<TimerNodeBase>(*pairs.first); // emplace的返回值pair包含：1.创建并插入的节点 2.是否成功插入（已存在相同节点则插入失败）
        }
        // 如果待插入节点是最大的，直接插入到最右侧，时间复杂度 O(1) ，优化性能
        auto ele = timeouts.emplace_hint(timeouts.crbegin().base(), GenID(), expire, std::move(func));
       // 返回基类而不是子类
        return static_cast<TimerNodeBase>(*ele);
    }

    void DelTimer(TimerNodeBase &node) { // 从（set）红黑树中删除一个节点
        auto iter = timeouts.find(node); // 找到指定节点
        if (iter != timeouts.end())
            timeouts.erase(iter);       // 移除
    }
    
    void HandleTimer(time_t now) {     // 执行当前已超时的任务
        auto iter = timeouts.begin();
        while (iter != timeouts.end() && iter->expire <= now) {
            iter->func(*iter);
            iter = timeouts.erase(iter); // eraser返回下一个节点
        }
    }

public:
    // 更新 timerfd 的到期时间为 timeouts 集合中最早到期的定时器时间
    virtual void UpdateTimerfd(const int fd) {
        struct timespec abstime;
        auto iter = timeouts.begin();  // 最小超时时间节点
        if (iter != timeouts.end()) {
            abstime.tv_sec = iter->expire / 1000;
            abstime.tv_nsec = (iter->expire % 1000) * 1000000;
        } else {
            abstime.tv_sec = 0;
            abstime.tv_nsec = 0;
        }

        struct itimerspec its;
        its.it_interval = {};
        its.it_value = abstime;

        timerfd_settime(fd, TFD_TIMER_ABSTIME, &its, nullptr);
    }

private:
    static inline uint64_t GenID() { // 生成一个 id
        return gid++;
    }
    static uint64_t gid; // 全局 id 变量

    set<TimerNode, std::less<> > timeouts; // less指定排序方式：从小到大
};

在class timer中实现了

1.创建set容器对象

2.定时任务节点的添加

3.定时任务节点的删除

4.执行已超时任务

四、main函数

int main() {
    int epfd = epoll_create(1);  // epoll

    int timerfd = timerfd_create(CLOCK_MONOTONIC, 0);
    
    struct epoll_event ev = {.events = EPOLLIN | EPOLLET};
    epoll_ctl(epfd, EPOLL_CTL_ADD, timerfd, &ev);

    unique_ptr<Timer> timer = make_unique<Timer>();
    int i = 0;
    timer->AddTimer(1000, [&](const TimerNode &node) {      //   lamda 表达式
        cout << Timer::GetTick() << "node id:" << node.id << "revoked times" << ++i << endl;
    });

    timer->AddTimer(1000, [&](const TimerNode &node) {
        cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;
    });

    timer->AddTimer(3000, [&](const TimerNode &node) {
        cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;
    });

    auto node = timer->AddTimer(2100, [&](const TimerNode &node) {
        cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;
    });
    timer->DelTimer(node);

    cout << "now time:" << Timer::GetTick() << endl;

    struct epoll_event evs[64] = {0};
    while (true) {
        timer->UpdateTimerfd(timerfd);    // epoll中timerfd的到期时间
        int n = epoll_wait(epfd, evs, 64, -1); // 内核检测定时时间timerfd
        time_t now = Timer::GetTick();   // 当前系统时间戳
        
        for (int i = 0; i < n; i++) {     
            // for network event handle
        }
        timer->HandleTimer(now);         // 处理现在到期的定时任务
    }
    epoll_ctl(epfd, EPOLL_CTL_DEL, timerfd, &ev);
    close(timerfd);
    close(epfd);

    return 0;
}

timerfd的使用：

1.将timerfd添加到epoll中

2.使用timerfd_settime()函数更新timerfd的超时时间

3.当超时时间到达时，epoll会通知事件

4.执行完到期的任务后，更新timerfd的超时时间为红黑树中最小节点的超时时间，epoll会再次进行通知

五、完整代码

#include <sys/epoll.h>
#include <sys/timerfd.h>
#include <time.h>
#include <unistd.h>

#include <functional>
#include <chrono>
#include <set>
#include <memory>
#include <iostream>

using namespace std;

struct TimerNodeBase { //  定时器节点基类，用于红黑树（set）存储
    time_t expire;     //  超时时间
    uint64_t id;       //  唯一 id， 用于解决超时时间相同的节点存储问题
};

struct TimerNode : public TimerNodeBase {  // 子类定时器节点， 添加了一个回调函数
    using Callback = function<void(const TimerNode &node)>;
    Callback func;
    TimerNode(int64_t id, time_t expire, Callback func) : func(std::move(func)) { // 使用 move 右值引用，性能高
        this->expire = expire;
        this->id = id;
    }
};

bool operator < (const TimerNodeBase &lhd, const TimerNodeBase &rhd) { // 运算符重载，比较两个节点的大小
    // 先根据超时时间判定大小
    if (lhd.expire < rhd.expire) {
        return true;
    } else if (lhd.expire > rhd.expire) {
        return false;
    } // 超时时间相同时，根据 id 判断大小
    else return lhd.id < rhd.id;
}


class Timer {

public:
    static inline time_t GetTick() { // 获取系统当前时间戳
        return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now().time_since_epoch()).count();
    }

    TimerNodeBase AddTimer(int msec, TimerNode::Callback func) {
        time_t expire = GetTick() + msec; // msec是相对超时时间，expire是绝对超时时间（时间戳）
        // 如果待插入节点当前不是红黑树中最大的
        if (timeouts.empty() || expire <= timeouts.crbegin()->expire) { 
            auto pairs = timeouts.emplace(GenID(), expire, std::move(func)); // emplace是在容器内部生成一个对象并插入到红黑树中，性能优于push的copy操作  2.使用move右值引用，避免copy
            // 使用static_cast将子类cast成基类
            return static_cast<TimerNodeBase>(*pairs.first); // emplace的返回值pair包含：1.创建并插入的节点 2.是否成功插入（已存在相同节点则插入失败）
        }
        // 如果待插入节点是最大的，直接插入到最右侧，时间复杂度 O(1) ，优化性能
        auto ele = timeouts.emplace_hint(timeouts.crbegin().base(), GenID(), expire, std::move(func));
       // 返回基类而不是子类
        return static_cast<TimerNodeBase>(*ele);
    }

    void DelTimer(TimerNodeBase &node) { // 从（set）红黑树中删除一个节点
        auto iter = timeouts.find(node); // 找到指定节点
        if (iter != timeouts.end())
            timeouts.erase(iter);       // 移除
    }
    
    void HandleTimer(time_t now) {     // 执行当前已超时的任务
        auto iter = timeouts.begin();
        while (iter != timeouts.end() && iter->expire <= now) {
            iter->func(*iter);
            iter = timeouts.erase(iter); // eraser返回下一个节点
        }
    }

public:
    // 更新 timerfd 的到期时间为 timeouts 集合中最早到期的定时器时间
    virtual void UpdateTimerfd(const int fd) {
        struct timespec abstime;
        auto iter = timeouts.begin();  // 最小超时时间节点
        if (iter != timeouts.end()) {
            abstime.tv_sec = iter->expire / 1000;
            abstime.tv_nsec = (iter->expire % 1000) * 1000000;
        } else {
            abstime.tv_sec = 0;
            abstime.tv_nsec = 0;
        }

        struct itimerspec its;
        its.it_interval = {};
        its.it_value = abstime;

        timerfd_settime(fd, TFD_TIMER_ABSTIME, &its, nullptr);
    }

private:
    static inline uint64_t GenID() { // 生成一个 id
        return gid++;
    }
    static uint64_t gid; // 全局 id 变量

    set<TimerNode, std::less<> > timeouts; // less指定排序方式：从小到大
};

uint64_t Timer::gid = 0;


int main() {
    int epfd = epoll_create(1);  // epoll

    int timerfd = timerfd_create(CLOCK_MONOTONIC, 0);
    
    struct epoll_event ev = {.events = EPOLLIN | EPOLLET};
    epoll_ctl(epfd, EPOLL_CTL_ADD, timerfd, &ev);

    unique_ptr<Timer> timer = make_unique<Timer>();
    int i = 0;
    timer->AddTimer(1000, [&](const TimerNode &node) {      //   lamda 表达式
        cout << Timer::GetTick() << "node id:" << node.id << "revoked times" << ++i << endl;
    });

    timer->AddTimer(1000, [&](const TimerNode &node) {
        cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;
    });

    timer->AddTimer(3000, [&](const TimerNode &node) {
        cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;
    });

    auto node = timer->AddTimer(2100, [&](const TimerNode &node) {
        cout << Timer::GetTick() << " node id:" << node.id << " revoked times:" << ++i << endl;
    });
    timer->DelTimer(node);

    cout << "now time:" << Timer::GetTick() << endl;

    struct epoll_event evs[64] = {0};
    while (true) {
        timer->UpdateTimerfd(timerfd);    // epoll中timerfd的到期时间
        int n = epoll_wait(epfd, evs, 64, -1); // 内核检测定时时间timerfd
        time_t now = Timer::GetTick();   // 当前系统时间戳
        
        for (int i = 0; i < n; i++) {     
            // for network event handle
        }
        timer->HandleTimer(now);         // 处理现在到期的定时任务
    }
    epoll_ctl(epfd, EPOLL_CTL_DEL, timerfd, &ev);
    close(timerfd);
    close(epfd);

    return 0;
}

推荐学习 https://xxetb.xetslk.com/s/p5Ibb

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/652400.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

CC工具箱使用指南：【淹没区分析(BHM)】

CC工具箱使用指南：【淹没区分析(BHM)】

一、简介 群友定制工具。 这个工具适用面比较小。 工具的应用场景如下&#xff1a; 提供一个淹没区范围&#xff0c;类型是面要素。统计这个范围内的一些线、面要素的面积或长度。 给定的几个数据有&#xff1a;耕地、永久基本农田、房台、道路&#xff08;线&#xff09;…
阅读更多...
LeetCode - 贪心算法 (Greedy Algorithm) 集合 [分配问题、区间问题]

LeetCode - 贪心算法 (Greedy Algorithm) 集合 [分配问题、区间问题]

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/139242199 贪心算法&#xff0c;是在每一步选择中&#xff0c;都采取当前状态下&#xff0c;最好或最优&#xff08;即最有利&#xff09;的选择&…
阅读更多...
【MySQL】库的操作+表的操作

【MySQL】库的操作+表的操作

库的操作表的操作 1.库的操作1.1创建数据库1.2删除数据库1.3查找数据库1.4修改数据库1.5数据库备份和恢复1.6查看连接情况 2.库的操作2.1创建表2.2查看表结构2.3修改表2.4删除表 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; …
阅读更多...
Petalinux 制作ZYNQ镜像文件流程

Petalinux 制作ZYNQ镜像文件流程

1概述 在Zynq-7000 SoC中搭建运行Linux&#xff0c;嵌入式软件栈。 处理器系统引导是一个分两个阶段的过程。第一个阶段是一个内部 BootROM&#xff0c;它存储 stage-0 的引导代码。BootROM 在 CPU 0 上执行&#xff0c;CPU 1 执行等待事件&#xff08;WFE&#xff09;指令。…
阅读更多...
单片机通信协议（1）：SPI简介

单片机通信协议（1）：SPI简介

关于SPI SPI&#xff08;串行外设接口&#xff09;是板载设备间通信接口之一。它是由摩托罗拉公司&#xff08;飞思卡尔半导体&#xff09;推出的。由于其简单性和通用性&#xff0c;它被纳入各种外围设备中&#xff0c;并与飞利浦I2C总线并列。 SPI的三线或四线信号数量比IIC…
阅读更多...
connection problem,giving up

connection problem,giving up

参考&#xff1a; https://zhuanlan.zhihu.com/p/93438433 仅仅安装 sudo apt-get install xrdp 在用RDP远程的时候总是卡在登录界面&#xff0c;connection problem,giving up&#xff0c; some problem… 第一步&#xff1a; sudo apt-get install xserver-xorg-core sudo…
阅读更多...
接口性能测试复盘：解决JMeter超时问题的实践

接口性能测试复盘：解决JMeter超时问题的实践

在优化接口并重新投入市场后&#xff0c;我们面临着一项关键任务&#xff1a;确保其在高压环境下稳定运行。于是&#xff0c;我们启动了一轮针对该接口的性能压力测试&#xff0c;利用JMeter工具模拟高负载场景。然而&#xff0c;在测试进行约一分钟之后&#xff0c;频繁出现了…
阅读更多...
【OpenVINO™】在C#中使用 OpenVINO™ 部署 YOLOv10 模型实现目标

【OpenVINO™】在C#中使用 OpenVINO™ 部署 YOLOv10 模型实现目标

文章目录 1. 前言1.1 OpenVINO™ C# API1.2 YOLOv10 2. 模型获取2.1 源码下载2.2 配置环境2.3 下载模型 3. Yolov10 项目配置3.1 项目创建与环境配置3.2 定义模型预测方法3.2.1 定义目标检测模型方法3.2.2 使用OpenVINO™ 预处理接口编译模型 3.2 模型预测方法调用 4. 项目运行…
阅读更多...
在Linux中 --help 和 -h 的区别

在Linux中 --help 和 -h 的区别

在Linux命令行工具中&#xff0c;--help 和 -h&#xff08;而不是 -help&#xff09;是常见的选项&#xff0c;用于显示工具的帮助信息。 --help&#xff1a; 这是一个长选项&#xff08;long option&#xff09;&#xff0c;用于提供详细的帮助信息。许多工具都支持这个选项。…
阅读更多...
这款信创FTP软件，可实现安全稳定的文件传输

这款信创FTP软件，可实现安全稳定的文件传输

信创&#xff0c;即信息技术应用创新&#xff0c;2018年以来&#xff0c;受“华为、中兴事件”影响&#xff0c;国家将信创产业纳入国家战略&#xff0c;并提出了“28n”发展体系。“8”具体指金融、石油、电力、电信、交通、航空航天、医院、教育等主要行业。目前企业使用比较…
阅读更多...
ElementPlus-日期选择器实现周选择

ElementPlus-日期选择器实现周选择

ElementPlus的日期选择器实现周选择&#xff0c;并且显示的是日期范围&#xff0c;其效果如下&#xff1a; 首先修改中文语言环境&#xff0c;否则日期选择器是从周日开始的。在main.js文件中加上以下代码&#xff1a; import ElementPlus,{dayjs as elDayjs} from element-…
阅读更多...
【包邮送书】你好！C语言

【包邮送书】你好！C语言

欢迎关注博主 Mindtechnist 或加入【智能科技社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;滤波估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能等相关领域的知识和技术。关…
阅读更多...
使用YOLOv9训练和测试自己的数据集

使用YOLOv9训练和测试自己的数据集

任务&#xff1a;检测舌头上的裂纹和齿痕 已经有了labelme标注的数据集&#xff0c;并且转为了coco格式 参考&#xff1a; 详细&#xff01;正确&#xff01;COCO数据集&#xff08;.json&#xff09;训练格式转换成YOLO格式&#xff08;.txt&#xff09;_coco数据集的train…
阅读更多...
【Fiddler抓包工具】第五节.安卓、IOS抓包+fildder插件

【Fiddler抓包工具】第五节.安卓、IOS抓包+fildder插件

文章目录 前言一、HTTPS抓包 1.1 HTTPS与HTTP区别 1.2 HTTPS抓包设置过程 1.3 错误解决方法 1.4 验证证书是否安装成功 1.5 Firefox HTTPS请求捕获二、IOS设备APP抓包 2.1 APP抓包Fiddler设置 2.2 APP抓包IOS设备设置 2.3 And…
阅读更多...
在idea中git add 文件的时候报错 LF would be replaced by CRLF

在idea中git add 文件的时候报错 LF would be replaced by CRLF

把LF改成CRLF 在idea右下角 把这个改成CRLF
阅读更多...
拓展虚拟世界边界，云手机可以做到吗

拓展虚拟世界边界，云手机可以做到吗

虚拟世界&#xff0c;AI&#xff0c;VR等词汇是21世纪最为流行的词汇&#xff0c;在科技背后&#xff0c;这些词汇的影响变得越来越大&#xff0c;已经走进了人们的世界&#xff0c;比如之前APPLE发布的vision pro&#xff0c;使人们能够更加身临其境的体验到原生os系统&#x…
阅读更多...
linux下docker 的使用（2）

linux下docker 的使用（2）

上期我们讲了网络&#xff0c;现在来进行最后的 docker的基础内容 java项目的部署 假如说 我们java 项目已经写好了&#xff0c;现在在maven中打包一下我们的项目&#xff0c;然后会得到一个jar包&#xff0c;把jar包 上传到虚拟机上 点击package 命令&#xff0c;会得到一个…
阅读更多...
js toFixed()四舍五入丢失精度问题处理

js toFixed()四舍五入丢失精度问题处理

js toFixed()四舍五入丢失精度问题处理 错误展示 看了下lodash的代码&#xff0c;大概是通过使用科学计数法扩大10的n次&#xff0c;将操作数化为整数运算&#xff0c;可以避免精度丢失。 /*** Creates a function like _.round.** private* param {string} methodName The …
阅读更多...
艾体宝干货 | 教程：使用ntopng和nProbe监控网络流量

艾体宝干货 | 教程：使用ntopng和nProbe监控网络流量

本教程旨在分享如何通过 ntopng 和 nProbe 这两款工具&#xff0c;深入了解和掌握网络流量监控的艺术。我们将提供从基本概念到高级应用的全面指导&#xff0c;涵盖了在多种平台和设备上的部署和配置步骤。不论您是专业人员还是技术爱好者&#xff0c;跟随本教程&#xff0c;都…
阅读更多...
IPD管理体系指南

IPD管理体系指南

目录 简介 CSDN学院 作者简介 简介 学习任何新的和识或体系&#xff0c;都是需要从这个体影涉及的概念开始的。 IPD 合集也是遵活的这个基础逻辑。 通过 100 例的内容&#xff0c;先将 IPD 涉及到的机含点做了一个统一的梳理。 而本期课程呢&#xff0c;作为IPD 体系的前…
阅读更多...
最新文章

Copyright @ 2022~2023