一種多核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.