Chinaunix首页 | 论坛 | 博客
  • 博客访问: 54339
  • 博文数量: 5
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 149
  • 用 户 组: 普通用户
  • 注册时间: 2014-07-30 10:12
个人简介

记录学习、工作的点点滴滴

文章存档

2014年(5)

我的朋友

分类: LINUX

2014-09-06 23:24:58

定时器允许在将来的某一时刻执行我们预先设定的操作。在稍微复杂点的程序中,定时器通常会被广泛使用。

实现一个简单的定时器并不难。每个定时器都包含一个字段,表示定时器需要多长时间到期,当程序检查定时器时,根据时间判断定时器是否到期。如果已到期,则执行相应的操作并删除定时器,否则不做任何处理。

定时器的常见操作有3个:添加定时器, 检查定时器是否到期, 删除定时器。我们来分析下各种常用算法的性能问题。

链表:

将所有的定时器放在一个链表中。这使得每次检查定时器,都得扫描整个链表,当定时器数量非常大时,扫描是很耗时的操作。

维护一个排序的链表,这会提高检查的性能,但插入又会比较耗时。

红黑树:

在分析红黑树之前,我们先从二叉搜索树谈起。不严格的定义就是:左子树上所有结点的值均小于它的点的值,右子树上所有结点的值均大于它的根结点的值,如下图:
                

从上图可知,对于同样的数据集合,可以构造出多种不同的二叉搜索树。根据二叉搜索树的特性,我们很容易分析出各操作的时间复杂度:查找、最大值、最小值、增加结点,删除结点的时间复杂度都是O(h)h为树的深度。显然,为了提高各操作的性能,我们需要尽量降低树的深度。于是平衡二叉搜索树的概念被提出。

平衡二叉搜索树的左右两个子树的高度差不超过1 AVL树是严格的平衡树。红黑树也是众多平衡树中的一种,它会确保没有一条路径会比其它路径长出两倍,因而是近似平衡的。
                                                        
        

在插入和删除结点的时候,为了保持树的平衡性,需要对其它结点做出调整,这是通过“旋转”操作来完成的,因此红黑树的插入和删除操作有些复杂。但红黑树能保证查询、插入、删除操作都能在O(lg2n)内完成,这在数据量很大的时候,性能远好于链表。Linux内核中很多模块都使用了红黑树,具体代码见

小根堆:

小根堆可以近似看成一颗完全二叉树。不严格的定义为:父结点的值小于等于子结点的值,如下图:

                    

堆中的元素存放在数组中,其中第一元素就是最小的,所以找最小值的时间是O(1)

插入结点: 先将数据放到最后一个结点,为了维护堆的性质,将该结点一直往上进行交换即可。时间复杂度为O(lg2n)

删除结点: 取走第一个,将最后一个填写到第一个位置。为了维护堆的性质,将结点一直往下进行交换即可。时间复杂度为O(lg2n)

结论:小根堆的删除操作比红黑树略微慢些,但也在相同数量级O(lg2n)。在定时器这类应用中,由于需要频繁取最小值进行判断,所以用小根堆会更合适些,取最小值时间复杂度为O(1)

内核的定时器实现采用时间轮算法kernel/timer.c):

      直接上数据结构图。

         

      Tv12^8=256个大小的数组,tv2,tv3,tv4,tv5分别是2^6=64个大小的数组,每个元素都是一个链表。

      Tv1是保存0-255 jiffies的。

      Tv2保存2^8-2^(8+6)-1 jiffies的。 

      依次类推。

增加定时器的操作,直接看代码,很简单:
  
 

定时器的迁移:

tv1的定时器全部执行完毕,就将tv2的某一个链表的数据搬移到前255个。当tv2的链表执行完成,将tv3的某一链表搬移到tv264个中,等等。

为了周期性地补充base->tv1.vec, 64次补充当中,63次足以把base->tv2指向的链表分成base->tv1指向的256个链表。依次地,base->tv2.vec数组必须在0.006%的情况下得到补充,即使16.4秒一次。类似地,每1728秒补充一次base->tv3.vec,18小时38分补充一次base->tv4.vec,base->tv5.vec不需要补充。

时间轮算法很好的保证了性能,而且也比较容易理解。

参考资料:

《算法导论》

《深入理解Linux内核》

libevent源代码》

阅读(4224) | 评论(1) | 转发(4) |
0

上一篇:没有了

下一篇:常用排序算法

给主人留下些什么吧!~~

misserwell2014-10-10 16:19:37

这么说 数据结构还是 链表?