喻詩祥,顧乃杰,張 旭,曹 越

(中國科學(xué)技術(shù)大學(xué)a.計(jì)算機(jī)科學(xué)技術(shù)學(xué)院;b.安徽省計(jì)算與通信軟件重點(diǎn)實(shí)驗(yàn)室;c.先進(jìn)技術(shù)研究院,合肥230027)

一種多核ARM平臺下用戶態(tài)定時(shí)器的實(shí)現(xiàn)

喻詩祥a,b,c,顧乃杰a,b,c,張 旭a,b,c,曹 越a,b,c

(中國科學(xué)技術(shù)大學(xué)a.計(jì)算機(jī)科學(xué)技術(shù)學(xué)院;b.安徽省計(jì)算與通信軟件重點(diǎn)實(shí)驗(yàn)室;c.先進(jìn)技術(shù)研究院,合肥230027)

在ARM平臺下,系統(tǒng)提供的posix-timer誤差較大,難以滿足實(shí)時(shí)要求,而且傳統(tǒng)的Linux用戶態(tài)定時(shí)器通過系統(tǒng)調(diào)用及信號傳遞的方式向進(jìn)程提供定時(shí)服務(wù),當(dāng)定時(shí)器使用規(guī)模較大時(shí),進(jìn)程會在內(nèi)核態(tài)用戶態(tài)間頻繁切換。針對上述問題,提出并實(shí)現(xiàn)一種基于多核ARM平臺的新型用戶態(tài)定時(shí)器方案。該方案采用一種新的時(shí)間輪數(shù)據(jù)結(jié)構(gòu),通過內(nèi)核態(tài)與用戶態(tài)共享內(nèi)存等方式向進(jìn)程提供服務(wù),避免不必要的信號傳遞,有效地緩解頻繁狀態(tài)切換問題。實(shí)驗(yàn)結(jié)果表明,該方案保持微秒級的定時(shí)精度,定時(shí)誤差相比posix-timer明顯降低。

Linux用戶態(tài);定時(shí)器;多核;ARM平臺;時(shí)間輪;共享內(nèi)存

1 概述

定時(shí)器作為Linux操作系統(tǒng)提供的一種定時(shí)服務(wù)機(jī)制,被廣泛的應(yīng)用于各種內(nèi)核及用戶應(yīng)用程序中,其主要功能是實(shí)現(xiàn)一個(gè)給定的函數(shù)在給定的定時(shí)時(shí)長用完后被調(diào)用執(zhí)行。在Linux系統(tǒng)中,定時(shí)器分為內(nèi)核態(tài)定時(shí)器和用戶態(tài)定時(shí)器。內(nèi)核態(tài)定時(shí)器在內(nèi)核態(tài)被使用,如早期Linux內(nèi)核提供的低精度經(jīng)典定時(shí)器及后期Linux內(nèi)核提供的高精度定時(shí)器。用戶態(tài)定時(shí)器由進(jìn)程在用戶態(tài)創(chuàng)建使用,一般在內(nèi)核態(tài)定時(shí)器的基礎(chǔ)上實(shí)現(xiàn),Linux用戶態(tài)可以調(diào)用的定時(shí)器接口有setitimer、alARM系統(tǒng)調(diào)用以及posix-timer接口。

衡量一個(gè)定時(shí)器系統(tǒng)好壞的主要標(biāo)準(zhǔn)有定時(shí)精度和定時(shí)誤差,所謂定時(shí)精度是指定時(shí)器所能進(jìn)行最小時(shí)間的定時(shí)操作,定時(shí)誤差指定時(shí)器實(shí)際定時(shí)時(shí)長與預(yù)定定時(shí)時(shí)長之間的時(shí)間差[1-2]。在實(shí)時(shí)操作系統(tǒng)中,要實(shí)現(xiàn)對高精度實(shí)時(shí)任務(wù)的精確控制[3],保證事件在截止時(shí)間之前得到響應(yīng),定時(shí)器精度及定時(shí)誤差顯得尤為重要。由于Linux系統(tǒng)具有功能強(qiáng)大、開源、支持多種硬件平臺等優(yōu)勢,很多實(shí)時(shí)操作系統(tǒng)是在Linux的基礎(chǔ)上改造而來[4-5]。本文針對Linux下定時(shí)器實(shí)現(xiàn)機(jī)制的相關(guān)工作及其優(yōu)缺點(diǎn)進(jìn)行研究,提出并實(shí)現(xiàn)一種基于多核ARM平臺的新型用戶態(tài)定時(shí)器機(jī)制。

2 相關(guān)工作

在早期 Linux內(nèi)核(Linux-2.6.16之前)中, Linux內(nèi)核定時(shí)器的實(shí)現(xiàn)是基于系統(tǒng)周期性時(shí)鐘中斷,系統(tǒng)時(shí)鐘中斷由外部時(shí)鐘源周期性的發(fā)出,時(shí)鐘中斷的頻率由內(nèi)核配置參數(shù)Hz決定。在ARM平臺上,Hz一般被配置為128,即每秒128次時(shí)鐘中斷。針對每個(gè)核上的定時(shí)器,采用經(jīng)典時(shí)間輪數(shù)據(jù)結(jié)構(gòu),即系統(tǒng)根據(jù)其粗略到期時(shí)間(到期時(shí)刻的jiffies)的遠(yuǎn)近分類至5個(gè)不同的組中,在組內(nèi)再根據(jù)定時(shí)器到期的具體到期時(shí)刻將定時(shí)器構(gòu)建為若干個(gè)鏈表,如圖1所示。

圖1 經(jīng)典時(shí)間輪數(shù)據(jù)結(jié)構(gòu)

隨著時(shí)間的推移,當(dāng)?shù)狡跁r(shí)間較近的組中的所有定時(shí)器被處理完之后,再從到期時(shí)間較遠(yuǎn)的組中將定時(shí)器依次前推,重新補(bǔ)足至到期時(shí)間較近的組中。早期內(nèi)核定時(shí)器的精度和誤差都與Hz相關(guān),首先,系統(tǒng)在每次時(shí)鐘中斷中對到期定時(shí)器進(jìn)行處理,即每1/Hz秒處理一次到期定時(shí)器,其次,定時(shí)器計(jì)時(shí)單位基于jiffies變量,定時(shí)器只能處理1/Hz秒整數(shù)倍的定時(shí)操作。如果Hz值設(shè)置較小,定時(shí)精度只能達(dá)到毫秒級別,不能滿足實(shí)時(shí)應(yīng)用需求;如果Hz值過大,將使時(shí)鐘中斷更加頻繁的產(chǎn)生,減少了處理器處理其他工作的時(shí)間,還會頻繁打亂處理器的高速緩存[3]。

隨著實(shí)時(shí)系統(tǒng)的發(fā)展,為了提高定時(shí)器的精度,美國Kansan大學(xué)KURT-linux項(xiàng)目中的UTIME機(jī)制及Monta Vista公司發(fā)起的高精度定時(shí)器開源項(xiàng)目HRT相繼對高精度定時(shí)器的設(shè)計(jì)實(shí)現(xiàn)機(jī)制研究做出了開創(chuàng)性的努力[6-7]。在他們設(shè)計(jì)的高精度定時(shí)器機(jī)制中,對檢測定時(shí)器到期的方式進(jìn)行了創(chuàng)新,早期Linux內(nèi)核通過周期性時(shí)鐘中斷檢測定時(shí)器到期,而新的機(jī)制采用時(shí)鐘源單次觸發(fā)的方式檢測定時(shí)器到期,即每次對時(shí)鐘源編程,設(shè)置其發(fā)出中斷的時(shí)刻為當(dāng)前最早到期的定時(shí)器的到期時(shí)刻,當(dāng)中斷發(fā)生時(shí)(最早到期的定時(shí)器到期時(shí)),在中斷處理函數(shù)中再次對時(shí)鐘源進(jìn)行如上編程,設(shè)置中斷發(fā)生時(shí)刻為下一個(gè)最早到期的定時(shí)器的到期時(shí)刻。通過單次觸發(fā)的方式,定時(shí)器到期事件將不再發(fā)生于周期性的時(shí)鐘中斷中,定時(shí)器精度得到了顯著提高,達(dá)到微秒級別。2006年,Thomas等人提出了Hrtimer高精度定時(shí)器系統(tǒng),并加入到Linux內(nèi)核代碼樹中,其實(shí)現(xiàn)機(jī)制也是基于上述單次觸發(fā)思想[8-10]。Hrtimer系統(tǒng)可以與原有定時(shí)器系統(tǒng)兼容,并實(shí)現(xiàn)了模塊化,在編譯內(nèi)核時(shí)可以進(jìn)行配置選擇。在多核架構(gòu)中,每個(gè)核上的定時(shí)器對象根據(jù)其到期時(shí)刻的遠(yuǎn)近通過紅黑樹的方式進(jìn)行組織,每個(gè)核上的定時(shí)器到期檢測由本地時(shí)鐘源發(fā)出的中斷來驅(qū)動。在一些只有全局時(shí)鐘設(shè)備的SMP系統(tǒng)上,Hrtimer缺乏有效的支持,因?yàn)槿謺r(shí)鐘中斷只能在某一個(gè)核上進(jìn)行處理,無法管理多個(gè)核中的定時(shí)器[2]。

傳統(tǒng)的用戶態(tài)定時(shí)器接口如 setitimer,posixtimer[10]等都是在內(nèi)核態(tài)定時(shí)器的基礎(chǔ)上實(shí)現(xiàn)的,其實(shí)現(xiàn)方式基本是通過系統(tǒng)調(diào)用對內(nèi)核態(tài)定時(shí)器進(jìn)行定時(shí)操作,當(dāng)定時(shí)器到期時(shí),通過信號的方式通知對應(yīng)的進(jìn)程。當(dāng)定時(shí)器使用規(guī)模較大時(shí),進(jìn)程因定時(shí)器操作系統(tǒng)調(diào)用及每個(gè)定時(shí)器的到期信號處理會在內(nèi)核態(tài)和用戶態(tài)之間頻繁切換,導(dǎo)致系統(tǒng)性能降低。在ARM平臺上,除了上述問題,用戶態(tài)定時(shí)器的定時(shí)誤差比較大,難以滿足實(shí)時(shí)要求,尤其當(dāng)定時(shí)器使用規(guī)模較大時(shí),這種狀況更加明顯。針對這些問題,本文設(shè)計(jì)并實(shí)現(xiàn)一種基于多核ARM平臺的新型Linux用戶態(tài)定時(shí)器系統(tǒng)。新的實(shí)現(xiàn)方案在定時(shí)精度上,仍然保持微秒級的定時(shí)精度,在定時(shí)誤差方面,相比posix-timer得到了明顯降低。

3 新型Linux用戶態(tài)定時(shí)器設(shè)計(jì)與實(shí)現(xiàn)

在早期Linux內(nèi)核低精度定時(shí)器的實(shí)現(xiàn)方案中,每個(gè)核都以Hz為頻率周期性地響應(yīng)時(shí)鐘中斷,對核上運(yùn)行的定時(shí)器進(jìn)行到期檢測。為了避免造成系統(tǒng)性能的降低,Hz一般設(shè)置較小,定時(shí)器精度較低。在本文所述定時(shí)器系統(tǒng)中,為了在提高定時(shí)精度,并保持系統(tǒng)性能,僅在一個(gè)處理器核(比如0號核)上周期性進(jìn)行定時(shí)器到期檢測,其他核上的定時(shí)器均通過核間共享內(nèi)存的方式集中于這個(gè)核上進(jìn)行到期檢測,通過對到期檢測的頻率進(jìn)行配置,使定時(shí)精度達(dá)到微秒級別。在運(yùn)行定時(shí)器結(jié)構(gòu)的組織方面,采用一種新的時(shí)間輪數(shù)據(jù)結(jié)構(gòu)。對于相關(guān)數(shù)據(jù)結(jié)構(gòu),通過內(nèi)核態(tài)與用戶態(tài)共享內(nèi)存等方式,避免通過系統(tǒng)調(diào)用進(jìn)行啟動定時(shí)器等操作,在定時(shí)器使用規(guī)模較大時(shí),通過到期定時(shí)器隊(duì)列及共享內(nèi)存的方式,避免不必要的定時(shí)器到期信號導(dǎo)致頻繁的內(nèi)核態(tài)用戶態(tài)切換。

3.1 定時(shí)器到期檢測

在ARM平臺下,定時(shí)器到期檢測通過硬件時(shí)鐘源watch dog的周期性中斷實(shí)現(xiàn),在watch dog對應(yīng)的中斷處理函數(shù)中,檢測用戶態(tài)定時(shí)器是否到期。

watch dog是ARM平臺上一種常見的時(shí)鐘源設(shè)備,它基于一定的工作頻率對計(jì)數(shù)器進(jìn)行遞減操作,當(dāng)計(jì)數(shù)器值變?yōu)?時(shí),向CPU發(fā)出中斷,其工作模式可以設(shè)置為周期觸發(fā)或單次觸發(fā)模式。watch dog中主要包含以下幾個(gè)寄存器:CONTROL寄存器, LOAD寄存器,COUNTER寄存器。CONTROL寄存器用于設(shè)置watch dog是否工作,以及其工作模式為周期觸發(fā)還是單次觸發(fā);COUNTER寄存器是一個(gè)基于一定頻率遞減的計(jì)數(shù)器,當(dāng)其值遞減至0時(shí),會向CPU發(fā)出中斷,若watch dog處于周期觸發(fā)工作模式,則COUNTER值重置為LOAD寄存器的值,并繼續(xù)遞減。

在本文所述定時(shí)器系統(tǒng)中,設(shè)置watch dog工作模式為周期觸發(fā),每隔period微秒發(fā)出一次中斷,假設(shè)watch dog計(jì)數(shù)器遞減的頻率為freq,則LOAD寄存器寫入值的計(jì)算方法如下式:

3.2 新型時(shí)間輪數(shù)據(jù)結(jié)構(gòu)

每發(fā)生一次定時(shí)器到期檢測事件,時(shí)間向前推進(jìn)period微秒,每一次到期檢測事件發(fā)生稱為一個(gè)tick。本文提出的新的時(shí)間輪數(shù)據(jù)結(jié)構(gòu),類似傳統(tǒng)齒輪鐘表的輪式結(jié)構(gòu),在輪上有若干個(gè)刻度,每個(gè)刻度代表一個(gè)tick,時(shí)間輪的指針代表系統(tǒng)當(dāng)前的tick,用current_tick標(biāo)記,如圖2所示。

圖2 新型時(shí)間輪數(shù)據(jù)結(jié)構(gòu)

假設(shè)時(shí)間輪上的刻度個(gè)數(shù)為wheel_ticks,隨著時(shí)間的前進(jìn),時(shí)間輪指針在時(shí)間輪上從0到wheel_ ticks-1不斷循環(huán)變化。在系統(tǒng)初始時(shí)刻,current_tick初始化為0,每經(jīng)歷一個(gè)tick,current_tick的更新公式為:

其中,n表示wheel_ticks。

定時(shí)器在計(jì)時(shí)過程中以tick為單位,當(dāng)定時(shí)器啟動時(shí),對定時(shí)時(shí)長進(jìn)行微秒到tick的轉(zhuǎn)換,根據(jù)系統(tǒng)當(dāng)前tick及定時(shí)時(shí)長的tick數(shù),計(jì)算到期時(shí)刻的目標(biāo)tick及離到期時(shí)刻時(shí)間輪需要運(yùn)行的圈數(shù),假設(shè)定時(shí)時(shí)長為expires微秒,相關(guān)計(jì)算公式如下:

circle作為定時(shí)器的一個(gè)參數(shù),表示其至到期所剩的時(shí)間輪運(yùn)行圈數(shù)。在同一個(gè)tick到期的定時(shí)器通過雙向靜態(tài)鏈表的方式連接起來(如圖2),并且按照circle增序排列,每個(gè)tick上包含鏈表的首結(jié)點(diǎn)序號,啟動定時(shí)器操作即將定時(shí)器插入到到期時(shí)刻目標(biāo)tick對應(yīng)的鏈表中。每經(jīng)歷一個(gè)tick時(shí),對該tick上的定時(shí)器鏈表進(jìn)行檢查,若其中定時(shí)器的circle參數(shù)為0,則表示定時(shí)器在該tick到期,對其進(jìn)行處理,否則,將circle進(jìn)行減1操作。每個(gè)tick上還包含一個(gè)原子鎖變量,0表示未加鎖狀態(tài),1表示加鎖狀態(tài),通過原子語句控制原子鎖以互斥對同一tick上定時(shí)器鏈表的訪問[11-12]。時(shí)間輪由若干個(gè)tick組成,通過一個(gè)tick數(shù)據(jù)結(jié)構(gòu)數(shù)組實(shí)現(xiàn),tick的數(shù)據(jù)結(jié)構(gòu)為:

早期Linux內(nèi)核低精度定時(shí)器的經(jīng)典時(shí)間輪數(shù)據(jù)結(jié)構(gòu)存在一些缺點(diǎn),到期時(shí)間較遠(yuǎn)的定時(shí)器分組粒度較粗,而到期時(shí)間較近的定時(shí)器分組粒度較細(xì),當(dāng)?shù)狡跁r(shí)間較近的分組中的所有定時(shí)器被處理完之后,需要從到期時(shí)間較遠(yuǎn)的各組中將定時(shí)器重新補(bǔ)充至到期時(shí)間較近的組中,對定時(shí)器性能影響較大。

相比早期經(jīng)典時(shí)間輪數(shù)據(jù)結(jié)構(gòu),本文提出的新的時(shí)間輪數(shù)據(jù)結(jié)構(gòu)中,通過tick對定時(shí)器進(jìn)行的分組較為均勻。將時(shí)間輪上的tick個(gè)數(shù)wheel_ticks設(shè)置較大,通過增加時(shí)間輪所占空間的方法,減少不同核操作同一個(gè)tick的可能性,并且避免時(shí)間輪上tick的個(gè)數(shù)較小時(shí)較多的定時(shí)器集中到同一個(gè)tick上從而容易導(dǎo)致該tick上定時(shí)器鏈表較長。

3.3 定時(shí)器池及定時(shí)器到期機(jī)制

在用戶態(tài),進(jìn)程在時(shí)間輪上實(shí)現(xiàn)定時(shí)器啟動等相關(guān)操作,在內(nèi)核態(tài),周期性定時(shí)器到期檢測函數(shù)對時(shí)間輪tick上的定時(shí)器進(jìn)行到期檢測。將定時(shí)器屬性中需要在用戶態(tài)內(nèi)核態(tài)共享的一些屬性(如定時(shí)時(shí)長的tick個(gè)數(shù)、圈數(shù)circle、目標(biāo)tick序號等)單獨(dú)列出,構(gòu)造定時(shí)器共享數(shù)據(jù)結(jié)構(gòu),單獨(dú)分配一段共享內(nèi)存,將定時(shí)器共享數(shù)據(jù)結(jié)構(gòu)以定時(shí)器池的形式組織起來。將定時(shí)器屬性中僅在用戶態(tài)訪問的一些屬性(如定時(shí)器回調(diào)函數(shù)及其參數(shù)等)單獨(dú)列出,構(gòu)造定時(shí)器用戶態(tài)數(shù)據(jù)結(jié)構(gòu)。創(chuàng)建定時(shí)器時(shí),為每個(gè)定時(shí)器用戶態(tài)數(shù)據(jù)結(jié)構(gòu)從定時(shí)器池中分配一個(gè)定時(shí)器共享數(shù)據(jù)結(jié)構(gòu)。

定時(shí)器共享數(shù)據(jù)結(jié)構(gòu)通過兩組雙向靜態(tài)鏈表指針連接,其中一組用于將定時(shí)器連接于時(shí)間輪tick上的定時(shí)器鏈表中,表示定時(shí)器處于運(yùn)行狀態(tài),另一組用于將定時(shí)器連接于定時(shí)器池中的未分配定時(shí)器鏈表中或者進(jìn)程的已分配定時(shí)器鏈表中,表示定時(shí)器未分配或者已分配。

在Linux內(nèi)核定時(shí)器系統(tǒng)中,當(dāng)用戶態(tài)定時(shí)器到期時(shí),內(nèi)核向其所屬進(jìn)程發(fā)送信號,由進(jìn)程在用戶態(tài)捕獲信號,執(zhí)行信號處理函數(shù)。在進(jìn)程中定時(shí)器使用規(guī)模較大的情況下,大量到期信號的捕獲處理導(dǎo)致進(jìn)程進(jìn)行頻繁的內(nèi)核態(tài)用戶態(tài)切換。針對這種情況,本文提出的定時(shí)器系統(tǒng)為進(jìn)程中每個(gè)線程開辟一段共享內(nèi)存,以循環(huán)隊(duì)列的組織方式保存該線程當(dāng)前到期未被處理的定時(shí)器。在內(nèi)核態(tài)定時(shí)器到期檢測函數(shù)中,當(dāng)檢測到屬于某個(gè)線程的定時(shí)器到期時(shí),將該定時(shí)器寫入該線程對應(yīng)隊(duì)列的尾部,僅在該線程對應(yīng)隊(duì)列原來為空的情況下才向該線程發(fā)送信號,并以線程ID作為信號的參數(shù)。在用戶態(tài)信號處理函數(shù)中,通過信號參數(shù)檢測發(fā)生定時(shí)器到期事件對應(yīng)的線程,從該線程到期定時(shí)器隊(duì)列頭部開始,逐個(gè)執(zhí)行每個(gè)定時(shí)器的回調(diào)函數(shù)。定時(shí)器到期處理機(jī)制如圖3所示。

圖3 定時(shí)器到期處理機(jī)制

通過上述到期定時(shí)器隊(duì)列及共享內(nèi)存的方式,在定時(shí)器使用規(guī)模較大時(shí),可以減少信號發(fā)送的次數(shù),避免定時(shí)器密集到期而導(dǎo)致的頻繁內(nèi)核態(tài)用戶態(tài)切換。

3.4 共享內(nèi)存組織結(jié)構(gòu)

共享內(nèi)存作為本文定時(shí)器系統(tǒng)中的一個(gè)重要方法,共享內(nèi)存區(qū)主要包含以下5個(gè)區(qū)域:

(1)時(shí)間輪區(qū):時(shí)間輪由一個(gè)wheeltick結(jié)構(gòu)數(shù)組組成,用戶態(tài)進(jìn)程在時(shí)間輪上實(shí)現(xiàn)定時(shí)器啟動等相關(guān)操作,內(nèi)核態(tài)定時(shí)器到期檢測函數(shù)在時(shí)間輪上進(jìn)行周期性推進(jìn),進(jìn)行定時(shí)器到期檢測。該部分在定時(shí)器系統(tǒng)啟動時(shí)初始化。

(2)定時(shí)器池區(qū):定時(shí)器池區(qū)由定時(shí)器共享數(shù)據(jù)結(jié)構(gòu)數(shù)組構(gòu)成,在邏輯上定時(shí)器共享數(shù)據(jù)結(jié)構(gòu)通過靜態(tài)鏈表的方式連接。在定時(shí)器創(chuàng)建時(shí),若定時(shí)器池空間不足則以內(nèi)存頁為單位實(shí)現(xiàn)動態(tài)擴(kuò)張。

(3)全局參數(shù)區(qū):該區(qū)域用于保存一些全局參數(shù),包括時(shí)間輪上tick個(gè)數(shù)、當(dāng)前tick,定時(shí)器池中定時(shí)器總個(gè)數(shù)、已分配個(gè)數(shù)、空閑定時(shí)器鏈表首結(jié)點(diǎn)等。該部分在定時(shí)器系統(tǒng)啟動時(shí)初始化。

(4)進(jìn)程參數(shù)區(qū):該區(qū)域用于保存一些進(jìn)程參數(shù),包括進(jìn)程從定時(shí)器池中分配的定時(shí)器結(jié)構(gòu)鏈表首結(jié)點(diǎn)、各線程到期定時(shí)器隊(duì)列頭、尾指針等。該部分在進(jìn)程向定時(shí)器系統(tǒng)注冊時(shí)初始化。

(5)到期定時(shí)器隊(duì)列區(qū):該區(qū)域用于為各線程實(shí)現(xiàn)其到期定時(shí)器循環(huán)隊(duì)列。

在系統(tǒng)啟動階段,創(chuàng)建共享內(nèi)存匿名映射設(shè)備,供進(jìn)程進(jìn)行內(nèi)存映射,對共享內(nèi)存中時(shí)間輪區(qū)、定時(shí)器池區(qū)、全局參數(shù)區(qū)進(jìn)行初始化,并設(shè)置時(shí)間輪驅(qū)動源watch dog,使其周期性發(fā)出中斷推動時(shí)間輪。當(dāng)進(jìn)程向定時(shí)器系統(tǒng)注冊之后,為當(dāng)前進(jìn)程對應(yīng)進(jìn)程參數(shù)區(qū)及到期定時(shí)器隊(duì)列區(qū)初始化,將上述5個(gè)共享內(nèi)存區(qū)映射至進(jìn)程地址空間。

共享內(nèi)存區(qū)成功映射并初始化后,定時(shí)器相關(guān)操作均可直接在共享內(nèi)存區(qū)中的數(shù)據(jù)結(jié)構(gòu)上進(jìn)行,避免通過系統(tǒng)調(diào)用方法陷入內(nèi)核態(tài),主要有以下具體操作:創(chuàng)建操作即從定時(shí)器池的未分配定時(shí)器鏈表中分配一個(gè)定時(shí)器結(jié)構(gòu),并連接至進(jìn)程已分配定時(shí)器鏈表中;啟動操作即根據(jù)當(dāng)前tick及定時(shí)時(shí)長,將定時(shí)器插入時(shí)間輪到期目標(biāo)tick的鏈表中;停止操作即將定時(shí)器從時(shí)間輪到期目標(biāo)tick的鏈表中刪除;刪除操作即將定時(shí)器結(jié)構(gòu)回收至定時(shí)器池的未分配定時(shí)器鏈表中。將到期定時(shí)器隊(duì)列放入共享內(nèi)存區(qū),可以避免每次定時(shí)器到期事件都發(fā)送一次信號通知對應(yīng)進(jìn)程,而是僅當(dāng)定時(shí)器隊(duì)列為空時(shí)才發(fā)送信號,當(dāng)定時(shí)器規(guī)模較大時(shí),減少信號發(fā)生的次數(shù),避免不必要的用戶態(tài)與內(nèi)核態(tài)之間的切換。

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)方法及環(huán)境

根據(jù)第3節(jié)所述,本文所述用戶態(tài)定時(shí)器系統(tǒng)精度通過定時(shí)器到期檢測的周期即參數(shù)period配置。下面給出定時(shí)器系統(tǒng)定時(shí)誤差方面的參數(shù)配置及測試方法。首先定時(shí)器系統(tǒng)的相關(guān)參數(shù)配置為:時(shí)間輪上刻度個(gè)數(shù)wheel_ticks配置為217個(gè),定時(shí)到期檢測的周期period參數(shù)配置為20 μs。其次測試方法為:隨機(jī)產(chǎn)生5萬個(gè)2 s內(nèi)的定時(shí)時(shí)長數(shù)據(jù),針對這些數(shù)據(jù),對本文提出的新型用戶態(tài)定時(shí)器系統(tǒng)及Linux內(nèi)核提供的用戶態(tài)posix-timer分別進(jìn)行如下測試,創(chuàng)建5萬個(gè)定時(shí)器,以上述數(shù)據(jù)為定時(shí)時(shí)長,進(jìn)行200輪測試,在每一輪測試中逐個(gè)啟動定時(shí)器,并記錄每個(gè)定時(shí)器的啟動時(shí)間,在定時(shí)器的到期處理函數(shù)中,記錄定時(shí)器到期時(shí)間并計(jì)算定時(shí)誤差,待所有定時(shí)器都到期之后,進(jìn)入下一輪測試。在測試方法中,定時(shí)器啟動時(shí)間及到期時(shí)間,均通過硬件時(shí)間戳計(jì)數(shù)器GLOBAL TIMER讀取。測試平臺環(huán)境為: CPU為ARM cotex-A9 mpcore omap4460 pandaboard @1.2 GHz,內(nèi)存1 GB,操作系統(tǒng)為ubuntu 11.04,內(nèi)核版本為Linux 2.6.38。

4.2 結(jié)果分析

根據(jù)上述測試方法,對每個(gè)定時(shí)器每輪到期的誤差進(jìn)行統(tǒng)計(jì),記錄誤差發(fā)生在各個(gè)區(qū)間內(nèi)發(fā)生的次數(shù),最終計(jì)算誤差在各個(gè)區(qū)間分布的比例及平均誤差。測試結(jié)果如表1、表2及圖4、圖5所示。其中,表 1中平均誤差為 14.0 μs,最大誤差為6 677 μs;表2中平均誤差為24.9 ms,最大誤差為67.0 ms。

表1 本文系統(tǒng)測試結(jié)果

表2 posix-timer測試結(jié)果

圖4 本文系統(tǒng)實(shí)驗(yàn)結(jié)果

圖5 posix-timer實(shí)驗(yàn)結(jié)果

從表1、圖4與表2、圖5的對比看出,在ARM平臺下,本文系統(tǒng)與posix-timer在誤差方面相比取得明顯的改進(jìn),posix-timer的定時(shí)誤差在毫秒級別,本文系統(tǒng)的定時(shí)誤差,被降低到了微秒級別。

5 結(jié)束語

本文針對在ARM平臺下用戶態(tài)定時(shí)器誤差較大,及傳統(tǒng)用戶態(tài)定時(shí)器系統(tǒng)在定時(shí)器使用規(guī)模較大時(shí)導(dǎo)致的內(nèi)核態(tài)用戶態(tài)頻繁切換的問題,設(shè)計(jì)并實(shí)現(xiàn)了一種新型的用戶態(tài)定時(shí)器方案。該方案避免了通過系統(tǒng)調(diào)用進(jìn)行定時(shí)器操作時(shí)不必要的信號傳遞,有效緩解了狀態(tài)頻繁切換問題,保持微秒級別的定時(shí)精度,將定時(shí)誤差降低至微秒級別,并且為其他平臺尤其是只有全局時(shí)鐘設(shè)備的平臺上的定時(shí)器設(shè)計(jì)提供了一種參考方案。

[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的高精度定時(shí)器設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2010,36(16): 267-269.

[3] 王 霞,馬忠梅,何小慶,等.提高嵌入式 Linux時(shí)鐘精度的方法[J].計(jì)算機(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實(shí)時(shí)調(diào)度方案的設(shè)計(jì)與實(shí)現(xiàn) [J].計(jì)算機(jī)研究與發(fā)展,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內(nèi)核新型高精度定時(shí)器的設(shè)計(jì)與實(shí)現(xiàn)[D].成都:電子科技大學(xué),2007.

[10] 周 鵬,周明天.Linux內(nèi)核中一種高精度定時(shí)器的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,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ìn)型鎖無關(guān)雙端隊(duì)列的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,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

“核高基”重大專項(xiàng)(2009ZX01028-002-003-005);高等學(xué)校學(xué)科創(chuàng)新引智計(jì)劃基金資助項(xiàng)目(B07033)。

喻詩祥(1990-),男,碩士研究生,主研方向:程序優(yōu)化技術(shù);顧乃杰(通訊作者),教授、博士生導(dǎo)師;張 旭,博士研究生;曹 越,碩士研究生。

2014-02-21

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

中文引用格式:喻詩祥,顧乃杰,張 旭,等.一種多核ARM平臺下用戶態(tài)定時(shí)器的實(shí)現(xiàn)[J].計(jì)算機(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.