技术标签： C/C++ epoll 定时器 Linux网络编程实践及经典文章收集 Linux网络编程之IOCP/epoll
就是说，有N多个定时器，如何来实现高效到点执行定时函数的问题。
在开发Linux网络程序时，通常需要维护多个定时器，如维护客户端心跳时间、检查多个数据包的超时重传等。
定时器的结构有多钟比如链表式，最小堆，时间轮等。在不同应用场景下使用哪种需要考虑效率和复杂度？
时间轮定时器
1.时间轮定时器有什么好处，或者说这种结构的定时器能决解什么问题？
在升序链表定时器里，可以看到在添加一个定时器的时候，复杂度是O(n)
因为要保持有序性，所以的遍历链表插入到合适的位置。假设系统有大量的定时器(10W个)
使用升序链表型的就会有性能问题。这时时间轮定时器就会比较适合。
2.常用定时器实现算法复杂度
实现方式 StartTimerStopTimerPerTickBookkeeping
基于链表 O(1) O(n) O(n)
基于排序链表 O(n) O(1) O(1)
基于最小堆 O(lgn) O(1) O(1)
基于时间轮 O(1) O(1) O(1)
3.定时器管理：nginx的红黑树和libevent的堆
libevent 发生超时后，while循环一次从堆顶del timer——直到最新调整的最小堆顶不是超时事件为止，（实际是del event），但是会稍后把这个timeout的 event放到active 任务list里，等待处理，event标记为timeout，等处理actvie队列时再由应用层callback函数决定怎么处理标记为timeout的事件。
nginx处理超时时，直接删除红黑树中（ event结构体里的 ）rb node成员，同时调用应用层早已通过add timer注册好的超时handler函数。之所以没有用堆，因为每次直接从内部删除节点，而不是堆顶部。
关键点，采用堆，删除时间是O（1），但是要调整堆，logn。插入时间基本是lgn。
采用红黑树，删除节点是3次旋转，但是，找到最小节点要logn。插入时间基本是lgn。
总体看，都差不多。
堆排序和红黑树性能比较 ：http://blog.sina.com.cn/s/blog_56e6a0750101b0fo.html
不谈内存，从算法上来讲
红黑树插入是最坏情况要比较2logN次(最高的高度）外加不超过两次旋转，最小堆最坏情况是logN次；
红黑树删除不需要比较只需要不超过3旋转，查找最小值需要遍历logN，如果删除最小值树调整一般很小；
最小堆查询顶节点是O(1),而删除顶节点在任何情况下都是个最坏的情况，需要比较2logN次；
红黑树的最坏情况在旋转中不断调整变化，插入性能比最小堆差，但删除最小性能却比最小堆好上几倍；
如果插入+查找最小+删除最小总体来确定红黑树和最小堆，红黑树占优，性能波动相对较小，红黑树不过多的依赖比较，相对最小堆由比较带来的的性能影响较小（如果比较是调用自定义函数、比较的是字符串等，那么性能就牺牲很大）；
最小堆最大的优势在于取最小值性能是O(1),如果插入的数据基本有序，那么最小堆能获得比较好的性能， 在频繁不断地取最小值的是否满足条件的应用中有更加好的性能（如超时队列），红黑树相应就要尽量避免不必要的查询次数才能在超时队列这种应用中获得更好的性能；
从实际出发：
由于最小堆一般是采用堆的方式实现，元素访问速度远高于采用链表方式的红黑树，插入性能快红黑树好几倍，但最小堆的删除性能并不快于红黑树；
最小堆的最大缺点就在于必须是连续的内存。
4. 最近学习libevent，发现libevent1.2版本对Timer事件用的是红黑树，但是libevent2.0版本就放弃了红黑树的使用，使用小根堆。于是搜集了部分资料，
以下内容来自：http://blog.chinaunix.net/xmlrpc.php?r=blog/article&uid=22906954&id=4376535
libevent的最小堆源码路径是：
https://github.com/libevent/libevent/blob/release-2.1.8-stable/minheap-internal.h
首先什么是小根堆：
（1）它是一颗完全二叉树
（2）任意一个节点均小于或等于其左右子节点的关键码（大根堆相反就是了）
因此可以得知，当前树形结构的根节点就是当前整个树形结构最小的节点。。。
至于说这种堆结构有什么作用：
（1）以前本科的时候上数据结构课的时候就有讲过堆排序，好像还不错，O(nlogn)的复杂度
（2）可以用来构造优先权队列。。。。
（3）在libevent库中，定时是采用小根堆来维护（nginx是红黑树）
好了，下面来看看小根堆的插入和删除吧，其实感觉 非常简单诶，比红黑树简单，只需要向上向下浮动就好了，没有红黑树那种左旋右旋，还得染色什么的。。
首先来看节点的插入：
（1）将要插入的节点按照完全二叉树的形式插入到当前树形结构的最末尾
（2）对这个刚刚插入的节点进行向上浮动，浮动的原理是：比较当前的节点和其父节点，如果比父节点小，那么与父节点交换，然后递归的进行，直到浮动不动了或者到了根节点
接下来来看节点的删除：
（1）小根堆的删除是删除当前的根节点，也就是返回当前根节点的值，然后用当前树形结构的最后一个节点来代替根节点
（2）从当前属性结构的最后一个非叶节点开始，向下浮动，浮动的原理是：
如果有比自己小的子节点，那么与这个子节点交换，然后递归的对刚刚交换下去的子节点进行向下浮动，（如果当前两个子节点都比自己小，那么就与最小的那个交换）
5.参考博客
linux网络编程二十一：利用SIGALRM信号，实现一个简单的基于升序链表的定时器 --- 《Linux高性能服务器编程(作者游双) 11.2.1》
linux网络编程二十二：高性能定时器之时间轮 --- 《Linux高性能服务器编程(作者游双) 11.4.1》
linux网络编程二十三：高性能定时器之时间堆 --- 《Linux高性能服务器编程(作者游双) 11.4.2》
文章浏览阅读1.6w次，点赞8次，收藏41次。生活中我们无时不刻不都要在网站搜索资源，但就是缺少一个趁手的资源搜索网站，如果有一个比较好的资源搜索网站可以帮助我们节省一大半时间！今天小编在这里为大家分享5款超厉害的资源搜索网站，每一款都可以让你的资源丰富精彩！网盘传奇一款最有效的网盘资源搜索网站你还在为找网站里面的资源而烦恼找不到什么合适的工具而烦恼吗？这款网站传奇网站汇聚了4853w个资源，并且它每一天都会持续更新资源；..._最全资源搜索引擎
文章浏览阅读4.5k次，点赞5次，收藏18次。阅读测试程序，设计一个Book类。函数接口定义：class Book{}该类有 四个私有属性 分别是 书籍名称、 价格、 作者、 出版年份，以及相应的set 与get方法；该类有一个含有四个参数的构造方法，这四个参数依次是 书籍名称、 价格、 作者、 出版年份 。裁判测试程序样例：import java.util.*;public class Main { public static void main(String[] args) { List <Book>_6-1 book类的设计java
文章浏览阅读613次，点赞28次，收藏27次。相比于以前的传统手工管理方式，智能化的管理方式可以大幅降低学校的运营人员成本，实现了校园导航的标准化、制度化、程序化的管理，有效地防止了校园导航的随意管理，提高了信息的处理速度和精确度，能够及时、准确地查询和修正建筑速看等信息。课题主要采用微信小程序、SpringBoot架构技术，前端以小程序页面呈现给学生，结合后台java语言使页面更加完善，后台使用MySQL数据库进行数据存储。微信小程序主要包括学生信息、校园简介、建筑速看、系统信息等功能，从而实现智能化的管理方式，提高工作效率。
传统上用户登陆状态会以 Session 的形式保存在服务器上，而 Session ID 则保存在前端的 Cookie 中；而使用 JWT 以后，用户的认证信息将会以 Token 的形式保存在前端，服务器不需要保存任何的用户状态，这也就是为什么 JWT 被称为无状态登陆的原因，无状态登陆最大的优势就是完美支持分布式部署，可以使用一个 Token 发送给不同的服务器，而所有的服务器都会返回同样的结果。有状态和无状态最大的区别就是服务端会不会保存客户端的信息。
文章浏览阅读784次。发表于10小时前| 2674次阅读| 来源TechCrunch| 19 条评论| 作者Jon EvansiOSAndroid应用开发产品编程语言JavaObjective-C摘要：即便Android市场份额已经超过80%，对于开发者来说，使用哪一个平台做开发仍然很难选择。本文从开发环境、配置、UX设计、语言、API、网络、分享、碎片化、发布等九个方面把Android和iOS_ios 开发角度
搜索引擎的发展历史可以追溯到20世纪90年代初，随着互联网的快速发展和信息量的急剧增加，人们开始感受到了获取和管理信息的挑战。这些阶段展示了搜索引擎在技术和商业模式上的不断演进，以满足用户对信息获取的不断增长的需求。
文章浏览阅读990次。对象特性是指控制对象的输出参数和输入参数之间的相互作用规律。放大系数K描述控制对象特性的静态特性参数。它的意义是：输出量的变化量和输入量的变化量之比。时间常数T当输入量发生变化后，所引起输出量变化的快慢。（动态参数） ..._控制对象特性
文章浏览阅读5.7w次，点赞50次，收藏276次。FRP搭建内网穿透1.概述：frp可以通过有公网IP的的服务器将内网的主机暴露给互联网，从而实现通过外网能直接访问到内网主机；frp有服务端和客户端，服务端需要装在有公网ip的服务器上，客户端装在内网主机上。2.简单的图解：3.准备工作：1.一个域名（www.test.xyz）2.一台有公网IP的服务器(阿里云、腾讯云等都行)3.一台内网主机4.下载frp，选择适合的版本下载解压如下：我这里服务器端和客户端都放在了/usr/local/frp/目录下4.执行命令# 服务器端给执_locyanfrp
文章浏览阅读687次。题目：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=93745#problem/A题意：给出r*c的01矩阵，可以翻转格子使得0表成1,1变成0，求出最小的步数使得每一行中1的个数相等，每一列中1的个数相等。思路：网络流。容量可以保证每一行和每一列的1的个数相等，费用可以算出最小步数。行向列建边，如果该格子是_uva12534
文章浏览阅读504次。1、Let's Encrypt 90天，支持泛域名2、Buypass：https://www.buypass.com/ssl/resources/go-ssl-technical-specification6个月，单域名3、AlwaysOnSLL：https://alwaysonssl.com/ 1年，单域名 可参考蜗牛（wn789）4、TrustAsia5、Alpha..._csdn alphassl免费申请
文章浏览阅读1.6k次。测试算法的性能 很多时候我们需要对算法的性能进行测试，最简单的方式是看算法在特定的数据集上的执行时间，简单的测试算法性能的函数实现见testSort()。【思想】：用clock_t计算某排序算法所需的时间，（endTime - startTime）/ CLOCKS_PER_SEC来表示执行了多少秒。【关于宏CLOCKS_PER_SEC】：以下摘自百度百科，“CLOCKS_PE_算法性能测试
文章浏览阅读1.2k次。fromhttps://towardsdatascience.com/finding-lane-lines-simple-pipeline-for-lane-detection-d02b62e7572bIdentifying lanes of the road is very common task that human driver performs. This is important ..._lanedetectionlite