多线程应用中的定时器管理算法.pdf

第36卷第2期
计算机工程
2010年1月
VOL36 No2
Computer Engineering
January 2010
软件技术与数据库
文章号:1000-3428(02010)02-007503文标识码:A
中图分类号1P301.5
多线程应用中的定时器管理算法
华,美新红,程凌宇,程永裕
(上海贝尔阿尔卡特股份有限公司,上海200070)
摘:针对高性能电信系统中软定时器效率低下的问题,提出一系列优化方案,采用二次散列的时间轮,并结合免锁算法的低粒度互斥
锁,从理论士把定时器查询和定时器插入等常用操作的复杂度从?m)降至最优情况的O(1)。通过真实高负荷进行测试,采用 Sunstudiol1
性能分析工具对优化前后的性能进行定最分析。实验结果表明,该优化方案能够有提高系统效率。
关词:时间轮;二次散列;粒度;免锁算法
T'imer Management Algorithm in Multi-thread Application
YAO Chong-hua, JIANG Xin-hong, CHENG Ling-yu, CHENG Yong-yu
(Alcatel Shanghai Bell, Ltd. Co., Shanghai 200070
T Abstract Aiming at the problem of low per ormance issue of soft timer manager which is commonly used in high performance telecom system, a
series of optimized algorithm and solution are proposed including double hash time wheel and mutex with small granularity which is inspired by
lock-free theory. It decreases the theoretical complexity from )o (1). Through high load test, and analysis is made with Sunstudioll's
performance analy., and the results show this optimized scheme can promote the system performance effectively
I Key words] time wheel; double hash; granularity; lock-free algorithm
1概述
间片,在每个时间片内检查是否有定时器超时。如果有,则
在通信领域的产品(如大型核心交换网系统)中,有许多触发超时处理,否则终止该定时器。对于需要长期运行的定
定时要求,有些任务需要周期性定时运行,如果主备用之间时器,则不删除,需将其进行重置。
的数据同步,以保证一且发生切换,备用设备能够马上接管
除了以上所描述的操作外,对于一个能够在多线程环境
任务,并且不存在不一致情况;有些任务需要延时,特别是下稳定工作的定时器管理算法来说,还必须解决线程互斥和
在网络中,一方发送消息给另一方,通常需要等待延迟一段工作效率等问题,这些问题会在下文进行讨论。
时间,此时需要定时器来提供定时服务,发送方并不能确定
定时器管理算法的性能指标有2种:(1)空间复杂度:对
能够收到消息,这样就会无限等待下去,造成时间和资源的于该算法用于存储定时器集合的数据结构的内存空间的度
浪费,所以,通过定时器准确定时后,发送方可以进行相应量。(2)时间复杂度:该算法用于管理有限个定时器的最大执
超时处理,如重发或者放弃发送;还有一些任务需要等待其行时间的度量,它是直接反映该算法性能的指标?
他事件或者消息,才能设置超时控制时间,如呼叫转移业务,3定时器管理算法原理
在被叫方无应答一段时间后,呼叫转移处理被触发。总之,3.1基于有序时间表的定时器管理算法
很多情况下都需要软件定时服务
1) addtimer:遍历整个定时器链表,找到合适的插入点,
系统中所需的定时器数最是相当可观的,而且对系统的将新定时器插入到链表中。时间复杂度为O(n)e
性能也有相当大的影响。如果定时器的工作效率较低,将会
(2) )scantier:根据 timerld在链表中查找定时器。时间
消耗大量的CPU资源,不但会影响到定时精度,而且还会复杂度为O(m)。
影响到系统的檠体性能。因此,在系统中实现一个高效的定
(3) otimer'tick:添加定时器时,是按照定时器的超时时间
时器管理算法将对系统的稳定性以及系统的整体性能都有重间隔大小排序,所以,判断是否有超时的定时器只需看当前
要作用。
链表头部的定时器是否超时。时间复杂度为O(1)
2定时器管理算法介绍
图1显示了在当前系统使用的定时器的数据结构。
对于个通用的定时器管理算法来说,以下操作是必须
header
ジ31300
mk?
41700ms
811500
向使用者提供的:
(1)添加定时器
I定时器表结
addtimer( interval, timerld):添加一个指定时长 interval)3.2碁于时间轮的定时器管理算法
的定时器, tiered用于唯一标识一个定时器。
从免锁算法着手,在多线程环境下,众多线程会使用同
(2)查找定时器
scan Timer(timerld):根据 timerld査找一个定时器。
作者介:姚崇华(1978-),男,高级工程师,主研方向:软交换平
(3)超时处理
合;姜新红,高级工程师;程凌字、程水裕,软件工程师
timertick:将定时器的时长划分为若干个时长相等的时收日期:20010-15E-mai:Lingyu.Cheng(@latl-sbellcom.cn
万方数据