今年对内核的slab,timer有了很深入的了解,并且有机会在windows下都重写了一次。slab的文章忘记发了,好像是网络上已经有很全的版本了,想主要说下timer,也就是俗称的定时器。
以前写过一个普通的定时器,简单来说就是串成一个长长的链表,然后分配一定的时间片来扫描。这样做,如果有排序的话还好,可以得知需要扫描的个数,并且有序的执行。快排的效率是是log2n,虽然很不错了,学习学习内核里的方法,开拓下视野也非常的美味。
换个思路来说,时间起于混沌的话(从0开始),并且只有20秒,你要分别在5秒,10秒,15秒做一件事情,你肯定会这样考虑,直接下标啊。简单代码可以写成
int array[20];
array[5]=fn1;
array[10]=fn2;
array[15]=fn3;
array[...]=NULL; //其他的设置为空
oldtime=time();
loop
{
//do other....
//...
nowtime=time();
if(oldtime<=nowtime)
{
array[oldtime].fn();
oldtime++;
}
}
你会很自然的想到,可以把时间当成下标,安排好会发生的事情,然后直接执行,避免了轮询的耗费。那么在32位的机器里,如果以毫秒为单位,可以支持到50年左右。内核里怎么做的具体不详说,列出一些代码片段揣摩:
#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
#define TVN_SIZE (1 << TVN_BITS)
#define TVR_SIZE (1 << TVR_BITS)
#define TVN_MASK (TVN_SIZE - 1)
#define TVR_MASK (TVR_SIZE - 1)
if (idx < TVR_SIZE) {
int i = expires & TVR_MASK;
vec = base->tv1.vec + i;
} else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
int i = (expires >> TVR_BITS) & TVN_MASK;
vec = base->tv2.vec + i;
} else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
vec = base->tv3.vec + i;
} else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
vec = base->tv4.vec + i;
}
else {
i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
vec = base->tv5.vec + i;
}
一堆的宏,定义了分组的大小。分为5层,每层都是一个链表头数组,数组之间的大小也有一定的关系,这里不细展开。每个层关心的定时值也不一样,比如第一层关心0-255毫秒的时间,你可以看成是优先级非常高的时间,越往后时间越松散,比如第二层关系256-10000毫秒的时间,以此类推,有点像盗梦空间的时间观念。简单的结构图如下
兴趣的定时值
层5: ----------- [xxx, 0xffffffff]
层4: ----------- ...
层3: ----------- [1001, 100000]
层2: ----------- [256, 1000]
层1: ------------- [0,255]
想起开头的混沌时间了吗?在时间大值的情况下,如何存入这些小数组?直接用掩码表示:
int i = expires & TVR_MASK;
expires表示一个绝对时间,TVR_MASK表示第一层的掩码。
假设,现在运行了N久时间,毫秒值为12000000,定义一个定时时间为12000100,在进行掩码操作后被存到100的下标。那么来看,是怎么运行第一层的,如果我先插入一个100毫秒值,时间到后,我又插入一个10毫秒的值,这个时候两者之间距离90,如何执行?
//插入
unsigned long expires = timer->expires; //timer->expires,设定的执行时间点
unsigned long idx = expires - base->timer_jiffies;//定时器上一回时间
int i = expires & TVR_MASK;
vec = base->tv1.vec + i;
//执行
int index = base->timer_jiffies & TVR_MASK;
也就是说不管现在时间如何,你什么时候插入,都以当前时间作为一个起始点,后来的时间顺序插入,如果超出则取模。接着刚才,现在时间是12000100,插入一个10毫秒,timer->expires为12000110,对12000110直接取模,得到110,插入在110。 而旧的索引在100,中间刚好10个间隔。
解决完运行的插入后,来看看如果从上层空间取时间。在每次的运行函数里,都有如下代码
#define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)
static int cascade(struct tvec_base *base, struct tvec *tv, int index)
{
struct timer_list *timer, *tmp;
struct list_head tv_list;
list_replace_init(tv->vec + index, &tv_list);
list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
BUG_ON(tbase_get_base(timer->base) != base);
internal_add_timer(base, timer);
}
return index;
}
int index = base->timer_jiffies & TVR_MASK;
if (!index &&
(!cascade(base, &base->tv2, INDEX(0))) &&
(!cascade(base, &base->tv3, INDEX(1))) &&
!cascade(base, &base->tv4, INDEX(2)))
cascade(base, &base->tv5, INDEX(3));
看似每次都执行cascade函数,其实不是。index为刚才说锁的下标掩码,TVR_MASK表示第一个层的长度,也就是说,执行完一遍第一层,才向上层索取。而INDEX这个宏里,根据定时器旧的时间取出一个索引,然后把该索引下链表重新分配。然后返回index,如果是大于0的,则不往下执行了。也就是说,其实只是遍历了一个节点,进行重新分配,而且产生的条件是把第一层都给遍历完了。那么
疑问1:如果其实点不从0开始,而从250开始,隔5个点就要向上层索取一次吗?
疑问2:为什么只取上层的一个节点?
疑问3:上层和下层怎么保持同步的?为什么不从0开始,10开始?
解答疑问1:如果你理解了刚才的10,100毫秒的执行解释,就会发现,这个距离是相对的。如果你也理解了解释2,其实无论如何,第一层只要递增了一步,就可以从第二层取当前下标的数据。情形
如下:
0 (1).....255
0 ......(250) 255
(0) .....255
下回执行的,肯定是在() 的地方,刚好一个周期,所以见0就Cascade吧!
解答疑问2:在时间分层里,其实是有技巧,第一层大小是255, 第二层大小是64,时间范围是N。经过我的验算发现,N/64==253,也就说只要解开一个节点就够了,这里面全都是满足下一回对第一层遍历的定时点。
解答疑问3:代码显示
int i = (expires >> TVR_BITS) & TVN_MASK;
TVR_BITS是第一层(相对来说),取了一个倍数的关系。也就是说,如果第一层走完一圈,倍数+1,走完N圈,+N,而第二层(相对来说)通过插入时的这种取模已经确认的大小和时间关系,因此,第一层执行,相当时一个小齿轮,相对的推动了第二层的下标索引。因此也解释了,为什么第一层大小可以和第二层不一样。更重要的是符合一个进位的关系(N/64==253)
最后串起来:
看似上面讲了很多细节,包括我自己在写的时候,很多东西还要推敲一番。但说到本质,就三条:
1.取模
2.时间组织的相对值,相对位置
3.高层的每个时间刻度对下一层的进位关系
深深觉得,学东西,学得更多,更深,更精粹,越要理解本质的公式推理。细节,是用来验证,但不是用来记忆。
分享到:
相关推荐
linux内核源代码 0.00版本 最适合把玩操作系统的同学 linux最老的源码,只是实现在两个进程间切换。
把玩核桃,不仅能够带来心灵上的愉悦,更能够通过刺激手部穴位,活化血液循环,提升身体健康。特别是对于中老年朋友而言,把玩核桃已成为一种被推崇的养生方式,它不仅能够延缓身体衰老,保持手脑灵活性,还能提升...
滴滴iOS技术专家的分享,滴滴iOS技术专家的分享滴滴iOS技术专家的分享滴滴iOS技术专家的分享滴滴iOS技术专家的分享滴滴iOS技术专家的分享滴滴iOS技术专家的分享滴滴iOS技术专家的分享滴滴iOS技术专家的分享滴滴iOS...
把玩小米路由器AC2100.pdf
【轻松把玩HttpClient-032217531】文档主要介绍了如何使用Apache HttpClient库进行HTTP请求,包括GET和POST方法的实现,以及HTTPS、代理、SSL配置和工具类封装等内容。HttpClient是一个功能丰富的Java库,允许开发者...
林怡在其研究论文《从“把玩”到“虚拟现实”技术——浅谈艺术中的触感表达》中,深刻地探讨了这一主题,从传统的“把玩”文化谈到现代虚拟现实技术,阐述了触感在艺术中的重要性以及科技如何使这种表达方式发生革命...
编译器是现代计算机科学中的一个核心工具,它负责将人类可读的高级编程语言转换为计算机可以理解并执行的机器代码。Clang是一个由Apple公司主导开发的编译器前端,它支持C、C++、Objective-C以及Objective-C++等多种...
10分鐘開始把玩YOLO v4 ~Hands on YOLO v4 in 10 minutes.mp4
标题中的“行业分类-设备装置-一种教学用巧板器具或把玩娱乐玩具”表明了这个压缩包内容属于教育设备或者儿童玩具领域,具体是一种巧板器具,既可以用于教学,也可作为娱乐玩具。巧板,又称拼图玩具,通常由不同形状...
标题中的“UI设计师教你以问答形式来“把玩”APP.pdf”表明这是一份关于UI设计的教程,可能涉及如何通过问答方式理解和优化APP的用户体验。描述中的信息较少,但结合标签“APP应用开发”、“数据分析”、“参考文献...
一:text组件 (此图片来源于网络,如有侵权,请联系删除! ) 通常文本设置要不在wxml中设置,再要不就是通过weml绑定在js中设置文字。 wxml 我是文本组件 <text>{{text}} js ... onReady:fun
华硕Blue Cave无线路由器是一款以智能家居为主打的路由器产品,不仅在外观上具有独特的设计,还在功能上增加了许多创新特性。从提供的文件内容可以整理出以下知识点: 1. 智能家居风:华硕Blue Cave无线路由器以其...
《360°全景图与DroidVR:一个开源项目的深度探索》 全景图技术,作为现代数字图像处理领域的一项重要技术,近年来在娱乐、旅游、房地产、教育等多个领域得到了广泛应用。尤其随着虚拟现实(VR)的发展,360°全景...
(此图片来源于网络,如有侵权,请联系删除! ) 绘图是每个移动应用必备的技术,基本上和Android,IOS,等移动开发都是相同的,创建个上下文,给你个画布再上画,官网给的小例子都比较全了自己去看吧,drawImage时没有...
数据可视化是现代数据分析中的关键步骤,它通过图形的方式将复杂的数据呈现出来,使得非专业人员也能理解其中的模式、趋势和关联。在这个过程中,Python语言的seaborn库扮演着重要角色。seaborn是基于matplotlib构建...
一:checkbox组件 (此图片来源于网络,如有侵权,请联系删除! ) 不得不吐糟下checkbox默认样式真是有点略丑!!!checkbox组件为一个多选框被放到checkbox-group组中,并在checkbox-group(只能包含checkbox)中...