网易面试：手撕定时器

devtools/2024/9/23 9:22:58/

概述：

本文使用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() { // 生成一个 idreturn 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);  // epollint 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); // 内核检测定时时间timerfdtime_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() { // 生成一个 idreturn gid++;}static uint64_t gid; // 全局 id 变量set<TimerNode, std::less<> > timeouts; // less指定排序方式：从小到大
};uint64_t Timer::gid = 0;int main() {int epfd = epoll_create(1);  // epollint 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); // 内核检测定时时间timerfdtime_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


http://www.ppmy.cn/devtools/44618.html

相关文章

c++中的继承

c++中的继承

一、引言 在面向对象编程&#xff08;OOP&#xff09;的世界中&#xff0c;继承是一个核心概念&#xff0c;它允许我们定义一个类&#xff08;称为基类或父类&#xff09;作为另一个类&#xff08;称为派生类或子类&#xff09;的基础。通过继承&#xff0c;子类可以继承基类的…
阅读更多...
子集和问题（回溯法）

子集和问题（回溯法）

目录 ​​​​ 前言 一、算法思路 二、分析过程 三、代码实现 伪代码&#xff1a; C&#xff1a; 总结 前言 【问题描述】考虑定义如下的PARTITION问题中的一个变型。给定一个n个整数的集合X{x1,x2,…,xn}和整数y&#xff0c;找出和等于y的X的子集Y。 一、算法思路 基本思想&am…
阅读更多...
Vue实现一个动态添加行的表格？

Vue实现一个动态添加行的表格？

在Vue中实现一个动态添加行的表格可以通过以下步骤来完成&#xff0c;如下所示。 步骤 1&#xff1a;设置表格的数据模型 在Vue组件中定义表格的数据模型&#xff0c;通常使用一个数组来存储表格的数据。每一行数据可以是一个对象&#xff0c;对象的属性对应表格的列。 data(…
阅读更多...
LeetCode2336无限集中的最小数字

LeetCode2336无限集中的最小数字

题目描述 现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, …] 。实现 SmallestInfiniteSet 类&#xff1a;SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int num) 如果正整数 …
阅读更多...
使用Java和MyBatis获取表头与数据

使用Java和MyBatis获取表头与数据

使用Java和MyBatis获取表头与数据 在数据处理与展示中&#xff0c;经常需要将数据库查询结果中的表头&#xff08;列名&#xff09;与实际数据提取出来。本文将介绍如何通过Java的JDBC和MyBatis来实现这一需求。 1. 使用JDBC获取表头与数据 在JDBC中&#xff0c;可以使用Res…
阅读更多...
leetcode70-Climbing Stairs

leetcode70-Climbing Stairs

题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;2 解释&#xff1a;有两种方法可以爬到楼顶。 1 阶 1 阶2 阶 分析 爬到顶层n…
阅读更多...
CTF_RE典例

CTF_RE典例

PZCTF Xor 分组异或 0&#xff0c;1&#xff0c;2&#xff0c;3 不变, 4 , 5 &#xff0c;6&#xff0c;7只异或Str[0], 8,9,10,11要先后异或Str[0],Str[1] s [0x50, 0x5a, 0x43, 0x54, 0x16, 0x2b, 0x11, 0xf, 0x3b, 0x63,0x7e, 0x7e, 0x78, 0x2c, 0x16, 0x3a, 0x71, 0x2e…
阅读更多...
日志输出-第四章-接口级（单体应用）前后端数据加解密 Filter 实现

日志输出-第四章-接口级（单体应用）前后端数据加解密 Filter 实现

文章目录 日志输出-第四章-接口级&#xff08;单体应用&#xff09;前后端数据加解密 Filter 实现一、概述二、通过 Filter 的方式实现2.1、加解密工具类2.2、请求包装类2.3、响应包装类2.4、实现加解密2.5、效果展示 三、总结 日志输出-第四章-接口级&#xff08;单体应用&…
阅读更多...
最新文章

Copyright @ 2022~2023