一种多核ARM平台下用户态定时器的实现

喻诗祥,顾乃杰,张 旭,曹 越

(中国科学技术大学a.计算机科学技术学院;b.安徽省计算与通信软件重点实验室;c.先进技术研究院,合肥230027)

一种多核ARM平台下用户态定时器的实现

喻诗祥a,b,c,顾乃杰a,b,c,张 旭a,b,c,曹 越a,b,c

(中国科学技术大学a.计算机科学技术学院;b.安徽省计算与通信软件重点实验室;c.先进技术研究院,合肥230027)

在ARM平台下,系统提供的posix-timer误差较大,难以满足实时要求,而且传统的Linux用户态定时器通过系统调用及信号传递的方式向进程提供定时服务,当定时器使用规模较大时,进程会在内核态用户态间频繁切换。针对上述问题,提出并实现一种基于多核ARM平台的新型用户态定时器方案。该方案采用一种新的时间轮数据结构,通过内核态与用户态共享内存等方式向进程提供服务,避免不必要的信号传递,有效地缓解频繁状态切换问题。实验结果表明,该方案保持微秒级的定时精度,定时误差相比posix-timer明显降低。

Linux用户态;定时器;多核;ARM平台;时间轮;共享内存

1 概述

定时器作为Linux操作系统提供的一种定时服务机制,被广泛的应用于各种内核及用户应用程序中,其主要功能是实现一个给定的函数在给定的定时时长用完后被调用执行。在Linux系统中,定时器分为内核态定时器和用户态定时器。内核态定时器在内核态被使用,如早期Linux内核提供的低精度经典定时器及后期Linux内核提供的高精度定时器。用户态定时器由进程在用户态创建使用,一般在内核态定时器的基础上实现,Linux用户态可以调用的定时器接口有setitimer、alARM系统调用以及posix-timer接口。

衡量一个定时器系统好坏的主要标准有定时精度和定时误差,所谓定时精度是指定时器所能进行最小时间的定时操作,定时误差指定时器实际定时时长与预定定时时长之间的时间差[1-2]。在实时操作系统中,要实现对高精度实时任务的精确控制[3],保证事件在截止时间之前得到响应,定时器精度及定时误差显得尤为重要。由于Linux系统具有功能强大、开源、支持多种硬件平台等优势,很多实时操作系统是在Linux的基础上改造而来[4-5]。本文针对Linux下定时器实现机制的相关工作及其优缺点进行研究,提出并实现一种基于多核ARM平台的新型用户态定时器机制。

2 相关工作

在早期 Linux内核(Linux-2.6.16之前)中, Linux内核定时器的实现是基于系统周期性时钟中断,系统时钟中断由外部时钟源周期性的发出,时钟中断的频率由内核配置参数Hz决定。在ARM平台上,Hz一般被配置为128,即每秒128次时钟中断。针对每个核上的定时器,采用经典时间轮数据结构,即系统根据其粗略到期时间(到期时刻的jiffies)的远近分类至5个不同的组中,在组内再根据定时器到期的具体到期时刻将定时器构建为若干个链表,如图1所示。

图1 经典时间轮数据结构

随着时间的推移,当到期时间较近的组中的所有定时器被处理完之后,再从到期时间较远的组中将定时器依次前推,重新补足至到期时间较近的组中。早期内核定时器的精度和误差都与Hz相关,首先,系统在每次时钟中断中对到期定时器进行处理,即每1/Hz秒处理一次到期定时器,其次,定时器计时单位基于jiffies变量,定时器只能处理1/Hz秒整数倍的定时操作。如果Hz值设置较小,定时精度只能达到毫秒级别,不能满足实时应用需求;如果Hz值过大,将使时钟中断更加频繁的产生,减少了处理器处理其他工作的时间,还会频繁打乱处理器的高速缓存[3]。

随着实时系统的发展,为了提高定时器的精度,美国Kansan大学KURT-linux项目中的UTIME机制及Monta Vista公司发起的高精度定时器开源项目HRT相继对高精度定时器的设计实现机制研究做出了开创性的努力[6-7]。在他们设计的高精度定时器机制中,对检测定时器到期的方式进行了创新,早期Linux内核通过周期性时钟中断检测定时器到期,而新的机制采用时钟源单次触发的方式检测定时器到期,即每次对时钟源编程,设置其发出中断的时刻为当前最早到期的定时器的到期时刻,当中断发生时(最早到期的定时器到期时),在中断处理函数中再次对时钟源进行如上编程,设置中断发生时刻为下一个最早到期的定时器的到期时刻。通过单次触发的方式,定时器到期事件将不再发生于周期性的时钟中断中,定时器精度得到了显著提高,达到微秒级别。2006年,Thomas等人提出了Hrtimer高精度定时器系统,并加入到Linux内核代码树中,其实现机制也是基于上述单次触发思想[8-10]。Hrtimer系统可以与原有定时器系统兼容,并实现了模块化,在编译内核时可以进行配置选择。在多核架构中,每个核上的定时器对象根据其到期时刻的远近通过红黑树的方式进行组织,每个核上的定时器到期检测由本地时钟源发出的中断来驱动。在一些只有全局时钟设备的SMP系统上,Hrtimer缺乏有效的支持,因为全局时钟中断只能在某一个核上进行处理,无法管理多个核中的定时器[2]。

传统的用户态定时器接口如 setitimer,posixtimer[10]等都是在内核态定时器的基础上实现的,其实现方式基本是通过系统调用对内核态定时器进行定时操作,当定时器到期时,通过信号的方式通知对应的进程。当定时器使用规模较大时,进程因定时器操作系统调用及每个定时器的到期信号处理会在内核态和用户态之间频繁切换,导致系统性能降低。在ARM平台上,除了上述问题,用户态定时器的定时误差比较大,难以满足实时要求,尤其当定时器使用规模较大时,这种状况更加明显。针对这些问题,本文设计并实现一种基于多核ARM平台的新型Linux用户态定时器系统。新的实现方案在定时精度上,仍然保持微秒级的定时精度,在定时误差方面,相比posix-timer得到了明显降低。

3 新型Linux用户态定时器设计与实现

在早期Linux内核低精度定时器的实现方案中,每个核都以Hz为频率周期性地响应时钟中断,对核上运行的定时器进行到期检测。为了避免造成系统性能的降低,Hz一般设置较小,定时器精度较低。在本文所述定时器系统中,为了在提高定时精度,并保持系统性能,仅在一个处理器核(比如0号核)上周期性进行定时器到期检测,其他核上的定时器均通过核间共享内存的方式集中于这个核上进行到期检测,通过对到期检测的频率进行配置,使定时精度达到微秒级别。在运行定时器结构的组织方面,采用一种新的时间轮数据结构。对于相关数据结构,通过内核态与用户态共享内存等方式,避免通过系统调用进行启动定时器等操作,在定时器使用规模较大时,通过到期定时器队列及共享内存的方式,避免不必要的定时器到期信号导致频繁的内核态用户态切换。

3.1 定时器到期检测

在ARM平台下,定时器到期检测通过硬件时钟源watch dog的周期性中断实现,在watch dog对应的中断处理函数中,检测用户态定时器是否到期。

watch dog是ARM平台上一种常见的时钟源设备,它基于一定的工作频率对计数器进行递减操作,当计数器值变为0时,向CPU发出中断,其工作模式可以设置为周期触发或单次触发模式。watch dog中主要包含以下几个寄存器:CONTROL寄存器, LOAD寄存器,COUNTER寄存器。CONTROL寄存器用于设置watch dog是否工作,以及其工作模式为周期触发还是单次触发;COUNTER寄存器是一个基于一定频率递减的计数器,当其值递减至0时,会向CPU发出中断,若watch dog处于周期触发工作模式,则COUNTER值重置为LOAD寄存器的值,并继续递减。

在本文所述定时器系统中,设置watch dog工作模式为周期触发,每隔period微秒发出一次中断,假设watch dog计数器递减的频率为freq,则LOAD寄存器写入值的计算方法如下式:

3.2 新型时间轮数据结构

每发生一次定时器到期检测事件,时间向前推进period微秒,每一次到期检测事件发生称为一个tick。本文提出的新的时间轮数据结构,类似传统齿轮钟表的轮式结构,在轮上有若干个刻度,每个刻度代表一个tick,时间轮的指针代表系统当前的tick,用current_tick标记,如图2所示。

图2 新型时间轮数据结构

假设时间轮上的刻度个数为wheel_ticks,随着时间的前进,时间轮指针在时间轮上从0到wheel_ ticks-1不断循环变化。在系统初始时刻,current_tick初始化为0,每经历一个tick,current_tick的更新公式为:

其中,n表示wheel_ticks。

定时器在计时过程中以tick为单位,当定时器启动时,对定时时长进行微秒到tick的转换,根据系统当前tick及定时时长的tick数,计算到期时刻的目标tick及离到期时刻时间轮需要运行的圈数,假设定时时长为expires微秒,相关计算公式如下:

circle作为定时器的一个参数,表示其至到期所剩的时间轮运行圈数。在同一个tick到期的定时器通过双向静态链表的方式连接起来(如图2),并且按照circle增序排列,每个tick上包含链表的首结点序号,启动定时器操作即将定时器插入到到期时刻目标tick对应的链表中。每经历一个tick时,对该tick上的定时器链表进行检查,若其中定时器的circle参数为0,则表示定时器在该tick到期,对其进行处理,否则,将circle进行减1操作。每个tick上还包含一个原子锁变量,0表示未加锁状态,1表示加锁状态,通过原子语句控制原子锁以互斥对同一tick上定时器链表的访问[11-12]。时间轮由若干个tick组成,通过一个tick数据结构数组实现,tick的数据结构为:

早期Linux内核低精度定时器的经典时间轮数据结构存在一些缺点,到期时间较远的定时器分组粒度较粗,而到期时间较近的定时器分组粒度较细,当到期时间较近的分组中的所有定时器被处理完之后,需要从到期时间较远的各组中将定时器重新补充至到期时间较近的组中,对定时器性能影响较大。

相比早期经典时间轮数据结构,本文提出的新的时间轮数据结构中,通过tick对定时器进行的分组较为均匀。将时间轮上的tick个数wheel_ticks设置较大,通过增加时间轮所占空间的方法,减少不同核操作同一个tick的可能性,并且避免时间轮上tick的个数较小时较多的定时器集中到同一个tick上从而容易导致该tick上定时器链表较长。

3.3 定时器池及定时器到期机制

在用户态,进程在时间轮上实现定时器启动等相关操作,在内核态,周期性定时器到期检测函数对时间轮tick上的定时器进行到期检测。将定时器属性中需要在用户态内核态共享的一些属性(如定时时长的tick个数、圈数circle、目标tick序号等)单独列出,构造定时器共享数据结构,单独分配一段共享内存,将定时器共享数据结构以定时器池的形式组织起来。将定时器属性中仅在用户态访问的一些属性(如定时器回调函数及其参数等)单独列出,构造定时器用户态数据结构。创建定时器时,为每个定时器用户态数据结构从定时器池中分配一个定时器共享数据结构。

定时器共享数据结构通过两组双向静态链表指针连接,其中一组用于将定时器连接于时间轮tick上的定时器链表中,表示定时器处于运行状态,另一组用于将定时器连接于定时器池中的未分配定时器链表中或者进程的已分配定时器链表中,表示定时器未分配或者已分配。

在Linux内核定时器系统中,当用户态定时器到期时,内核向其所属进程发送信号,由进程在用户态捕获信号,执行信号处理函数。在进程中定时器使用规模较大的情况下,大量到期信号的捕获处理导致进程进行频繁的内核态用户态切换。针对这种情况,本文提出的定时器系统为进程中每个线程开辟一段共享内存,以循环队列的组织方式保存该线程当前到期未被处理的定时器。在内核态定时器到期检测函数中,当检测到属于某个线程的定时器到期时,将该定时器写入该线程对应队列的尾部,仅在该线程对应队列原来为空的情况下才向该线程发送信号,并以线程ID作为信号的参数。在用户态信号处理函数中,通过信号参数检测发生定时器到期事件对应的线程,从该线程到期定时器队列头部开始,逐个执行每个定时器的回调函数。定时器到期处理机制如图3所示。

图3 定时器到期处理机制

通过上述到期定时器队列及共享内存的方式,在定时器使用规模较大时,可以减少信号发送的次数,避免定时器密集到期而导致的频繁内核态用户态切换。

3.4 共享内存组织结构

共享内存作为本文定时器系统中的一个重要方法,共享内存区主要包含以下5个区域:

(1)时间轮区:时间轮由一个wheeltick结构数组组成,用户态进程在时间轮上实现定时器启动等相关操作,内核态定时器到期检测函数在时间轮上进行周期性推进,进行定时器到期检测。该部分在定时器系统启动时初始化。

(2)定时器池区:定时器池区由定时器共享数据结构数组构成,在逻辑上定时器共享数据结构通过静态链表的方式连接。在定时器创建时,若定时器池空间不足则以内存页为单位实现动态扩张。

(3)全局参数区:该区域用于保存一些全局参数,包括时间轮上tick个数、当前tick,定时器池中定时器总个数、已分配个数、空闲定时器链表首结点等。该部分在定时器系统启动时初始化。

(4)进程参数区:该区域用于保存一些进程参数,包括进程从定时器池中分配的定时器结构链表首结点、各线程到期定时器队列头、尾指针等。该部分在进程向定时器系统注册时初始化。

(5)到期定时器队列区:该区域用于为各线程实现其到期定时器循环队列。

在系统启动阶段,创建共享内存匿名映射设备,供进程进行内存映射,对共享内存中时间轮区、定时器池区、全局参数区进行初始化,并设置时间轮驱动源watch dog,使其周期性发出中断推动时间轮。当进程向定时器系统注册之后,为当前进程对应进程参数区及到期定时器队列区初始化,将上述5个共享内存区映射至进程地址空间。

共享内存区成功映射并初始化后,定时器相关操作均可直接在共享内存区中的数据结构上进行,避免通过系统调用方法陷入内核态,主要有以下具体操作:创建操作即从定时器池的未分配定时器链表中分配一个定时器结构,并连接至进程已分配定时器链表中;启动操作即根据当前tick及定时时长,将定时器插入时间轮到期目标tick的链表中;停止操作即将定时器从时间轮到期目标tick的链表中删除;删除操作即将定时器结构回收至定时器池的未分配定时器链表中。将到期定时器队列放入共享内存区,可以避免每次定时器到期事件都发送一次信号通知对应进程,而是仅当定时器队列为空时才发送信号,当定时器规模较大时,减少信号发生的次数,避免不必要的用户态与内核态之间的切换。

4 实验结果

4.1 实验方法及环境

根据第3节所述,本文所述用户态定时器系统精度通过定时器到期检测的周期即参数period配置。下面给出定时器系统定时误差方面的参数配置及测试方法。首先定时器系统的相关参数配置为:时间轮上刻度个数wheel_ticks配置为217个,定时到期检测的周期period参数配置为20 μs。其次测试方法为:随机产生5万个2 s内的定时时长数据,针对这些数据,对本文提出的新型用户态定时器系统及Linux内核提供的用户态posix-timer分别进行如下测试,创建5万个定时器,以上述数据为定时时长,进行200轮测试,在每一轮测试中逐个启动定时器,并记录每个定时器的启动时间,在定时器的到期处理函数中,记录定时器到期时间并计算定时误差,待所有定时器都到期之后,进入下一轮测试。在测试方法中,定时器启动时间及到期时间,均通过硬件时间戳计数器GLOBAL TIMER读取。测试平台环境为: CPU为ARM cotex-A9 mpcore omap4460 pandaboard @1.2 GHz,内存1 GB,操作系统为ubuntu 11.04,内核版本为Linux 2.6.38。

4.2 结果分析

根据上述测试方法,对每个定时器每轮到期的误差进行统计,记录误差发生在各个区间内发生的次数,最终计算误差在各个区间分布的比例及平均误差。测试结果如表1、表2及图4、图5所示。其中,表 1中平均误差为 14.0 μs,最大误差为6 677 μs;表2中平均误差为24.9 ms,最大误差为67.0 ms。

表1 本文系统测试结果

表2 posix-timer测试结果

图4 本文系统实验结果

图5 posix-timer实验结果

从表1、图4与表2、图5的对比看出,在ARM平台下,本文系统与posix-timer在误差方面相比取得明显的改进,posix-timer的定时误差在毫秒级别,本文系统的定时误差,被降低到了微秒级别。

5 结束语

本文针对在ARM平台下用户态定时器误差较大,及传统用户态定时器系统在定时器使用规模较大时导致的内核态用户态频繁切换的问题,设计并实现了一种新型的用户态定时器方案。该方案避免了通过系统调用进行定时器操作时不必要的信号传递,有效缓解了状态频繁切换问题,保持微秒级别的定时精度,将定时误差降低至微秒级别,并且为其他平台尤其是只有全局时钟设备的平台上的定时器设计提供了一种参考方案。

[1] Kwon K,SugayaM,NakajimaT.AnalysisofHigh Resolution Timer Latency Using Kernel Analysis System in Embedded System[C]//Proceedingsof2009 IEEE Software Technologies for Future Dependable Distributed Systems.[S.1.]:IEEE Press,2009:122-126.

[2] 王文竹,郭 华,吴庆波.基于PowerPC的高精度定时器设计与实现[J].计算机工程,2010,36(16): 267-269.

[3] 王 霞,马忠梅,何小庆,等.提高嵌入式 Linux时钟精度的方法[J].计算机工程,2006,32(23):70-72.

[4] Hill R,Srinivasan B,Pather S,et al.Temporal Resolution and Real-time Extensions to Linux[R].Information and Telecommunication Technology Center,Electrical Engineering and Computer Science,University of Kansas.Technologies Report:ITTC-FY98-TR-11510-03,1998.

[5] 李小群,赵慧斌,叶以民,等.Linux实时调度方案的设计与实现 [J].计算机研究与发展,2003,40(5): 728-733.

[6] Srinivasan B,Pather S,Hill R,et al.A Firm Real-time System Implementation Using Commercial Off-the-shelf Hardware and Free Software[C]//Proceedings of the 4th IEEE Real-time Technology and Applications Symposium. [S.1.]:IEEE Press,1998:112-119.

[7] Gracioli G,Santos D M,de Matos R,et al.One-shot Time Management Analysis in Epos[C]//Proceedings of IEEE SCCC’08.[S.1.]:IEEE Press,2008:92-99.

[8] Gleixner T,Niehaus D. Hrtimers and Beyond: Transformingthe Linux Time Subsystems[C]// Proceedings of the 8th Linux Symposium.Ottawa, Canada:[s.n.],2006:333-346.

[9] 李 群.Linux2.6内核新型高精度定时器的设计与实现[D].成都:电子科技大学,2007.

[10] 周 鹏,周明天.Linux内核中一种高精度定时器的设计与实现[J].计算机技术与发展,2006,16(4):73-78.

[11] Michael M M.CAS-based Lock-free Algorithm for Shared Deques[C]//Proceedings ofEuro-Par’03.Berlin, Germany:Springer,2003:651-660.

[12] 杨东升,张连法.改进型锁无关双端队列的设计与实现[J].计算机系统应用,2012,21(3):125-129.

编辑 索书志

Implementation of a User-mode Timer in Multi-core ARM Platform

YU Shixianga,b,c,GU Naijiea,b,c,ZHANG Xua,b,c,CAO Yuea,b,c
(a.School of Computer Science and Technology;b.Anhui Province Key Laboratory of Computing and Communication Software; c.Institute of Advanced Technology,University of Science and Technology of China,Hefei 230027,China)

In the ARM platform,the delay of Linux’s posix-timer is big,and can not fit the requirement of real-time system.In addition,traditional Linux user-mode timer provides service to process via system call and signal so that the process switches between kernel-mode and user-mode frequently when the scale of timer being used is very large.To solve these problems,this paper designs and implements a new user-mode timer system in multi-core ARM platform.By using a novel time wheel data structure and providing service to process via sharing memory between kernel-mode and user-mode,the new system avoids the transmission of unnecessary signal,and relives the frequent state switching effectively.Experimental results show that the new system keeps the precision of the timer in micro-second and offers much smaller delay than the posix-timer.

Linux user-mode;timer;multi-core;ARM platform;time wheel;shared memory

1000-3428(2015)01-0019-05

A

TP391

10.3969/j.issn.1000-3428.2015.01.004

“核高基”重大专项(2009ZX01028-002-003-005);高等学校学科创新引智计划基金资助项目(B07033)。

喻诗祥(1990-),男,硕士研究生,主研方向:程序优化技术;顾乃杰(通讯作者),教授、博士生导师;张 旭,博士研究生;曹 越,硕士研究生。

2014-02-21

2014-03-20 E-mail:ysx053@mail.ustc.edu.cn

中文引用格式:喻诗祥,顾乃杰,张 旭,等.一种多核ARM平台下用户态定时器的实现[J].计算机工程,2015, 41(1):19-23.

英文引用格式:Yu Shixiang,Gu Naijie,Zhang Xu,et al.Implementation of a User-mode Timer in Multi-core ARM Platform[J].Computer Engineering,2015,41(1):19-23.