目录
一:前言
二:手撕面试题--set容器--timerfd驱动
1、定时任务存储的结构体
2、Timer类中的私有成员
3、获得当前系统时间
4、任务结点的添加
5、删除任务结点
6、处理超时任务
7、更新时间
8、main函数中的例子
三、set容器--使用epoll_wait的第四个参数超时
一:前言
我之前的文章有过详细的讲解为什么使用红黑树等,讲了很多的理论知识,大家可以先把理论看懂,然后再来看手撕面试题。点我跳转!
二:手撕面试题--set容器--timerfd驱动
1、定时任务存储的结构体
首先定时任务肯定需要时间,由于我们使用的是set容器,不可以插入相同的key值,那么对于同一时间的任务怎么处理呢?我们选择id来区分,我们让id自增长,这样保证id不会重复就可以。
那为什么写了两个结构体呢,因为我们存储在set容器中,其底层是红黑树,当我们插入新的结点的时候,我们需要平衡红黑树,会发生树的旋转操作,旋转操作其实就是结点的复制拷贝,当任务很多的时候,会发生大量的拷贝,降低性能占用内存。因此我们通过使用继承的操作,将子类添加到红黑树中,这样就避免了大量的内存占用。具体去看我的文章哦。
//基类
struct TimerNodeBase
{time_t expire; //时间uint64_t id; //id号,为了区分同一时间插入的任务
};struct TimerNode : public TimerNodeBase
{using CallBack = function<void(const TimerNode & timer)>; //创造一个需要传入自己的回调函数CallBack func;TimerNode (uint64_t id,time_t expire,CallBack func1):func(func1){this->id = id;this->expire = expire;}
};
2、Timer类中的私有成员
这里使用了set容器,其中用子类结点当作key值,使用 less<> 作为结点之间判断的条件。但是我们是使用的结点来当作key值,因此我们需要自己写判断条件。
其中 inline 关键字的作用:用于函数声明或定义中,其作用是将函数指定为内联函数。内联函数的主要目的是解决一些频繁调用的函数大量消耗栈空间(栈内存)的问题,通过在编译时将函数体的代码直接嵌入到每一个调用点处,从而避免函数调用的开销,包括参数传递、栈帧创建与销毁等成本,以提升程序的执行效率。替代宏定义。
private:static uint64_t id; //在这里使用static是为了在类中进行共享,在类外进行初始化,且只有一次。//这意味着无论创建了多少个类的实例,都只有一个static成员变量的副本。这对于需要跟踪类级别信息(如类的实例数量、类的静态配置等)的情况非常有用。set<TimerNode,less<>> timeouts; static inline uint64_t GETID() //这里加入static,只能访问静态成员{return 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;} else return lhd.id < rhd.id;
}
3、获得当前系统时间
static inline time_t GET_TICK() //返回系统的时间{return chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now().time_since_epoch()).count();}
4、任务结点的添加
首先需要传入时间以及回调函数,这个时间是指多少秒后触发的意思。因此我们需要自己去计算这个任务位于整天中的第多少秒。
获得了时间,那么我们就可以通过这个时间去判断这个结点的位置,此时我们需要思考一下,我们都是添加的什么任务结点?是我们需要定时的普通任务呢还是像心跳包一样的规律性任务呢?这两种任务有什么区别?
首先举个例子,如果当前时间是4秒,我要插入第8秒的时间,到了第5秒,我要插入第7秒的时间。我们肯定会碰到这样的插入任务,这样就可以正常插入。但是如果是心跳包这种呢,一直每隔10秒插入一次,我们会发现,当只插入心跳包的时候,只插入到最后,但是红黑树每次都是从中间查找,因此会浪费时间,如果直接插入最后那么时间复杂度不久成O(1)了吗。
//将任务添加到set容器中去TimerNodeBase TimerAdd(int msg,TimerNode::CallBack func) //要执行的时间,以及插入的函数{time_t time = GET_TICK() + msg;//这里是进行了一个小优化,当一直插入的最后一个位置,那么咱们就直接找到那个位置,直接插入,不用从中间进行二分查找,直接将时间变成O(1)if(timeouts.empty() || time <= timeouts.rbegin()->expire){auto ptr = timeouts.emplace(GETID(),time,std::move(func));return static_cast<TimerNodeBase>(*ptr.first); //在编译时进行的显示转换,这里是向上转换,是安全的。}auto ptrt = timeouts.emplace_hint(timeouts.crbegin().base(),GETID(),time,std::move(func)); return static_cast<TimerNodeBase>(*ptrt);}
5、删除任务结点
void DEL(TimerNodeBase & timernode){auto ptr = timeouts.find(timernode);if(ptr != timeouts.end()){timeouts.erase(ptr);}}
6、处理超时任务
void Handle(time_t now){auto ptr = timeouts.begin();while(ptr != timeouts.end() && ptr->expire<=now) //传入时间之后,进行判断,小于这个时间的全部进行执行{ptr->func(*ptr );ptr = timeouts.erase(ptr); //将这个删除之后会赋值一下下一个迭代器}}
7、更新时间
单独看这个函数可能看不懂,只能看懂它将容器中第一个元素的时间给复制了一下,到了一个结构体中,而且这个结构体走了一下这个timerfd_settime函数,其中还包含了epoll的fd。看不懂没事,下面在main中的例子讲解。
virtual void UpdateTimefd(const int fd){struct timespec abstime; auto iter = timeouts.begin();if(iter !=timeouts.end()) //如果在把timefd添加到epoll中之前去的时候,向定时器中添加了一些定时任务的话,走这里,初始化判断的时间{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 ={.it_interval = {},.it_value = abstime};timerfd_settime(fd,TFD_TIMER_ABSTIME,&its,nullptr); //设置定时器fd的时间,每次要执行任务之前要判断fd的时间。}
8、main函数中的例子
首先就是咱们的epollfd,然后通过timerfd_create创建一个定时器的fd,添加到epoll中,然后创建Timer定时器,并添加一些任务。到后面的while循环中去。
到这个时候,我们的timefd和Timer定时器类,并没有任何的交集,此时通过updatetimefd将timefd传入到Timer中去,并且给timefd设置了超时时间,也就是容器中首个位置的时间。这样这个timefd就可以自动超时了。
通过wait函数等待发生事件,无论是网络事件触发,还是定时器的超时触发,我们都进行检查定时器Timer类中是否有任务超时。
cout <<"1"<<endl;int epfd = epoll_create(1);int timefd = timerfd_create(1,0);epoll_event ev ={.events = EPOLLIN | EPOLLET};epoll_ctl(epfd,EPOLL_CTL_ADD,timefd,&ev);//测试用例unique_ptr<Timer> timer = make_unique<Timer>();int i = 0;timer->TimerAdd(1000, [&](const TimerNode &node) {cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->TimerAdd(1000, [&](const TimerNode &node) {cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->TimerAdd(3000, [&](const TimerNode &node) {cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;});auto node = timer->TimerAdd(2100, [&](const TimerNode &node) {cout << Timer::GET_TICK() << " node id:" << node.id << " revoked times:" << ++i << endl;});timer->DEL(node);cout << "now time:" << Timer::GET_TICK() << endl;//将定时器添加完成之后,就进入等待环节epoll_event evs[64]={0};while(1){timer->UpdateTimefd(timefd); //每次等待之前都要将定时器中的代码进行初始化操作,都要复制成容器中第一个的时间,int n = epoll_wait(epfd,evs,64,-1); //设置永远不会超时,当有事件返回,则触发下面判断时间的操作。for(int i=0;i<n;i++){//这里就是正常的接收网络请求的代码}timer->Handle(timer->GET_TICK()); //传入当前时间,将时间之前的任务全部执行。}epoll_ctl(epfd, EPOLL_CTL_DEL, timefd, &ev);close(timefd);close(epfd);return 0;
三、set容器--使用epoll_wait的第四个参数超时
首先我们要知道第四个参数是干什么的,是用来自动超时的,我们可以思考一下怎么将咱们的超时任务连接起来。当我们插入很多任务之后,怎么样才能让他们自动超时呢?
如果我们将每个任务的超时时间添加到这个epoll_wait的参数中去,那么每次超时是不是就成了第一个任务超时的时间了呢。
time_t Timertosleep(){auto iter = timeouts.begin();if(iter == timeouts.end()){return -1; //这里也就是说当没有定时任务的时候}time_t diss = iter->expire - GET_TICK();//每次等待超时的时间return diss >0 ? diss :0; }
每次超时之后处理任务完成,都要重新设置epoll_wait的超时时间,这样就自动超时了。
epoll_event ev[64] = {0};while (true) {int n = epoll_wait(epfd, ev, 64, timer->Timertosleep());time_t now = Timer::GET_TICK();for (int i = 0; i < n; i++) {/**/}/* 处理定时事件*/timer->Handle(now);}
本片讲解完毕啦!
https://xxetb.xetslk.com/s/2D96kH