《Linux原理與結(jié)構(gòu)》課件第5章

第五章時鐘管理5.1時鐘管理系統(tǒng)組成結(jié)構(gòu) 5.2時鐘設(shè)備管理5.3計時器管理5.4周期性時鐘中斷5.5單發(fā)式時鐘中斷5.6變頻式周期性時鐘中斷在所有的外部中斷中，時鐘中斷是最特別、最重要的一種。時鐘中斷驅(qū)動著操作系統(tǒng)中的時間與定時器，是系統(tǒng)中與時間相關(guān)的所有操作的基礎(chǔ)，是必須由操作系統(tǒng)內(nèi)核處理的最基本的外部中斷。

時鐘中斷來源于計算機系統(tǒng)中的時鐘設(shè)備。時鐘設(shè)備是一種特殊的外部設(shè)備，其主要作用是產(chǎn)生時鐘中斷。傳統(tǒng)的時鐘設(shè)備常用于產(chǎn)生周期性的時鐘中斷，被看作是計算機系統(tǒng)的心跳與脈搏。老版本的Linux在時鐘中斷處理中完成所有與時間相關(guān)的管理工作，包括計時與定時，未形成獨立的時鐘管理系統(tǒng)。這種嵌入在中斷處理中的時鐘管理方案雖然簡單，但卻存在一些問題，如與時鐘設(shè)備硬件綁定過緊，難以維護；增加新的時鐘設(shè)備時需重寫管理程序，代碼重復(fù)量大；難以提供高精度定時、周期性時鐘中斷暫停等新型服務(wù)等，因而有必要對系統(tǒng)中的時鐘管理部分進行重新設(shè)計。

2005年以后，隨著高精度時鐘設(shè)備的引入，出現(xiàn)了多種時鐘管理改進方案，這些方案被逐漸集成到了新的Linux版本中，逐步形成了獨立的時鐘管理系統(tǒng)。以時鐘管理系統(tǒng)為基礎(chǔ)，當前的Linux已可提供多種優(yōu)質(zhì)的計時與定時服務(wù)。

時鐘管理系統(tǒng)負責(zé)管理時鐘設(shè)備和計時器，處理系統(tǒng)中與時間相關(guān)的工作。Linux中的時鐘管理系統(tǒng)由兩大部分組成，其基礎(chǔ)是時鐘設(shè)備管理和計時器管理，建立在該基礎(chǔ)上的是基于時間的服務(wù)，其組織結(jié)構(gòu)如圖5.1所示。5.1時鐘管理系統(tǒng)組成結(jié)構(gòu)圖5.1時鐘管理系統(tǒng)的組織結(jié)構(gòu)時鐘設(shè)備管理子系統(tǒng)負責(zé)管理系統(tǒng)中的時鐘設(shè)備，其中包含一個管理框架和一組通用操作，支持時鐘設(shè)備的注冊、選用、模式設(shè)置及時鐘中斷的處理。每一個時鐘設(shè)備都需要向該子系統(tǒng)注冊一個管理結(jié)構(gòu)。時鐘設(shè)備可工作在周期中斷模式、高精度單發(fā)中斷模式或低精度單發(fā)中斷模式。但在一個特定的時間點上，一個時鐘設(shè)備只能工作一種中斷模式。

計時器管理子系統(tǒng)負責(zé)管理系統(tǒng)中的計時器設(shè)備。系統(tǒng)中可能同時存在多種計時器設(shè)備，每一種計時器都需要注冊一個管理結(jié)構(gòu)。以高精度計時器和時鐘設(shè)備為基礎(chǔ)，可為用戶提供更加精確、平滑的時間服務(wù)。時鐘管理系統(tǒng)提供的服務(wù)包括時間管理(更新墻上時間并為用戶提供時間服務(wù))、定時管理(管理各類定時器并為用戶提供定時服務(wù))、進程賬務(wù)管理(統(tǒng)計進程的時間消耗信息并在需要時啟動進程調(diào)度)、負載管理(統(tǒng)計系統(tǒng)負載并進行必要的平衡)等。

老版本的Linux僅提供了兩種定時器，即核心定時器和時間間隔定時器。新版本的Linux增加了一個管理框架，專門用于管理系統(tǒng)中的高精度定時器。核心定時器和時間間隔定時器可建立在周期性時鐘中斷之上，但高精度定時器只能建立在高精度單發(fā)式時鐘中斷之上。單發(fā)式時鐘中斷僅在需要時產(chǎn)生，不需要時可以暫停。通過暫停空閑處理器上的周期性時鐘中斷，可極大地減少時鐘中斷的次數(shù)，改善系統(tǒng)的節(jié)能效果。

早期的系統(tǒng)中只有一個時鐘設(shè)備，即PIT(ProgrammableIntervalTimer)。目前的系統(tǒng)中通常配置有多種時鐘設(shè)備，如LocalAPICTimer、HPET(HighPrecisionEventTimer)、ACPI的電源管理定時器(PowerManagementTimer)等。5.2時鐘設(shè)備管理其中的PIT和HPET屬于全局時鐘設(shè)備，LocalAPICTimer屬于局部時鐘設(shè)備。每類全局時鐘設(shè)備的配置量一般不會超過1個，但每個處理器都可能配置有自己的局部時鐘設(shè)備。全局時鐘設(shè)備所產(chǎn)生的時鐘中斷可以被遞交給系統(tǒng)中任意一個處理器，局部時鐘設(shè)備所產(chǎn)生的時鐘中斷僅會遞交給與之相連的處理器。

時鐘設(shè)備通常支持兩種中斷模式。工作在周期(Period)模式的時鐘設(shè)備會產(chǎn)生周期性的時鐘中斷，工作在單發(fā)(Oneshot)模式的時鐘設(shè)備每啟動一次僅會產(chǎn)生一個時鐘中斷。5.2.1時鐘設(shè)備管理結(jié)構(gòu)

顯然，不同的時鐘設(shè)備具有不同的特性、不同的狀態(tài)和不同的操作方法。為了統(tǒng)一管理，Linux定義了結(jié)構(gòu)clock_event_device用來描述時鐘設(shè)備，每種時鐘設(shè)備一個。

結(jié)構(gòu)clock_event_device中包含以下一些屬性域：

(1)時鐘設(shè)備特性features，如是否支持周期中斷模式、是否支持單發(fā)中斷模式、是否會在處理器睡眠(C3狀態(tài))時停止產(chǎn)生中斷、是否為啞設(shè)備等。

(2)設(shè)備當前中斷模式mode，如未用、已關(guān)閉、周期模式、單發(fā)模式等。

(3)下一次時鐘中斷發(fā)生時間next_event，僅用于單發(fā)中斷模式。next_event的取值范圍在min_delta_ns和max_delta_ns之間，單位為納秒。

(4)轉(zhuǎn)換關(guān)系mult和shift，用于時鐘中斷周期(納秒)和輸入脈沖數(shù)之間的相互轉(zhuǎn)換。通常情況下，時鐘設(shè)備在收到多個輸入脈沖后會產(chǎn)生1個時鐘中斷。

(5)時鐘設(shè)備優(yōu)先級rating，值越大表示時鐘設(shè)備的優(yōu)先級越高。

(6)中斷請求號irq，是時鐘設(shè)備所產(chǎn)生的IRQ號。

(7)處理器位圖cpumask，描述該時鐘設(shè)備所服務(wù)的處理器集合。

結(jié)構(gòu)clock_event_device中還包含四個操作函數(shù)，用于實現(xiàn)時鐘設(shè)備的管理操作，其中set_mode用于設(shè)置時鐘設(shè)備的中斷模式，set_next_event用于設(shè)置時鐘設(shè)備的下一次中斷時間，broadcast用于將設(shè)備產(chǎn)生的時鐘中斷廣播給其它處理器，event_handler用于處理時鐘中斷。

Linux提供了兩個全局隊列用于管理時鐘設(shè)備，其中隊列clockevent_devices中包含所有已注冊且已被選用的時鐘設(shè)備，隊列clockevents_released中包含已注冊但未被選用的時鐘設(shè)備。指針global_clock_event指向當前使用的全局時鐘設(shè)備。

傳統(tǒng)的時鐘設(shè)備通常工作在周期中斷模式，用以產(chǎn)生周期性的時鐘中斷。周期性時鐘中斷的頻率是操作系統(tǒng)中的一個重要參數(shù)，稱為HZ。兩次時鐘中斷之間的時間間隔稱為1個滴答(tick)。在早期的版本中，HZ被設(shè)為100，即1秒鐘產(chǎn)生100次時鐘中斷，滴答值是10ms。在新版本中，HZ被設(shè)為1000，即1秒鐘產(chǎn)生1000次時鐘中斷，滴答值是1ms。新式的時鐘設(shè)備通常工作在單發(fā)中斷模式，不再依賴于周期性時鐘中斷，因而可以將HZ取消掉。5.2.2PIT設(shè)備

傳統(tǒng)的PIT由三個計數(shù)器組成，各計數(shù)器的初值由操作系統(tǒng)設(shè)定，并隨PIT的輸入脈沖而遞減，如圖5.2所示。PIT的三個計數(shù)器可獨立配置、獨立工作，支持周期和單發(fā)兩種中斷模式。若計數(shù)器工作在周期中斷模式，那么每當它的計數(shù)值減到0時，就會輸出一個脈沖，而后計數(shù)器會恢復(fù)初值，重新開始計數(shù)，因而會產(chǎn)生周期性的輸出脈沖。缺省情況下，第0號計數(shù)器工作在周期中斷模式，它的輸出脈沖會周期性地中斷處理器，因而常被稱為周期性時鐘中斷。

圖5.2基于PIT的時鐘中斷在計算機系統(tǒng)中，PIT設(shè)備的輸入頻率是1193182Hz，即每秒1193182個輸入脈沖。當PIT工作在周期中斷模式時，它產(chǎn)生周期性時鐘中斷的頻率略大于Hz。當PIT工作

在單發(fā)中斷模式時，可為它設(shè)定的下一次中斷時間應(yīng)在12

571

ns(0xF個輸入脈沖)到

27461862ns(0x7FFF個輸入脈沖)之間。PIT是最基本的時鐘設(shè)備，其clock_event_device結(jié)構(gòu)已被注冊到clockevent_devices隊列中。

PIT內(nèi)部有4個寄存器，分別是計數(shù)器0、計數(shù)器1、計數(shù)器2和控制寄存器，其I/O端口號分別是0x40、0x41、0x42、0x43。通過操作PIT的I/O端口可以改變其中斷模式，如將PIT設(shè)為周期中斷模式并將第0號計數(shù)器的初值設(shè)為(1

193

182+Hz/2)/Hz、將PIT設(shè)為未用或關(guān)閉模式以禁止它繼續(xù)產(chǎn)生時鐘中斷等。若PIT工作在單發(fā)中斷模式，通過設(shè)置它的第0號計數(shù)器的計數(shù)值可以設(shè)定它的下一次中斷時間。

PIT的輸入頻率較低，且不夠規(guī)整，滴答值難以算得十分精確(略小)。在目前的計算機系統(tǒng)中，只有當HPET不可用時才會選用PIT。5.2.3HPET設(shè)備

HPET是一種高精度時鐘設(shè)備，其輸入時鐘的頻率不低于10MHz。一個HPET由一個主計數(shù)器和最多32個Timer組成，每個Timer中又包含一個比較器和一個匹配寄存器，如圖5.3所示。HPET的主計數(shù)器單調(diào)增長，每個輸入時鐘周期加1。比較器隨時比較主計數(shù)器的當前值與自己匹配寄存器的預(yù)定值，當發(fā)現(xiàn)兩者匹配時即請求產(chǎn)生中斷。如果Timer工作在周期中斷模式，那么每次中斷之后其匹配寄存器的值都會自動累加一個周期數(shù)(記錄在周期寄存器中)，因而可產(chǎn)生周期性的時鐘中斷。如果Timer工作在單發(fā)中斷模式，在產(chǎn)生中斷之后其匹配器的值不會自動調(diào)整，因而僅能產(chǎn)生一次性的時鐘中斷。HPET的每個Timer都可以獨立地產(chǎn)生中斷，其中的第0號Timer可用于替代PIT(連接到PIC的第0號管腳或I/OAPIC的第2號管腳)，第1號Timer可用于替代RTC的定時器(連接到PIC或I/OAPIC的第8號管腳)。圖5.3HPET組成結(jié)構(gòu)如果系統(tǒng)支持HPET，那么在ACPI的描述表中一定包含著有關(guān)HPET的描述信息，如其寄存器的物理基地址等。Linux在初始化時已經(jīng)對HPET做了如下設(shè)置工作：

(1)已將HPET的寄存器映射到了內(nèi)核的線性地址空間。與PIT相比，HPET內(nèi)部有更多的寄存器，如用于整體管理的能力與ID寄存器、配置寄存器、中斷狀態(tài)寄存器、主計數(shù)寄存器等，用于各Timer自身管理的配置寄存器、匹配寄存器和中斷路由寄存器等。Linux用內(nèi)存映射方式訪問HPET的寄存器。

(2)已對HPET的配置信息進行了合法性檢查。讀HPET的寄存器可獲得它的配置信息，如其中的計數(shù)器個數(shù)、主計數(shù)器的計數(shù)周期(以10-15s為單位)等。Linux假定HPET的主計數(shù)周期(輸入時鐘周期)應(yīng)在0.1ns～100ns之間。

(3)已注冊了HPET的clock_event_device結(jié)構(gòu)。當HPET工作在單發(fā)中斷模式時，可為它設(shè)定的下一次中斷時間應(yīng)不小于5000ns且不大于0x7FFFFFFF個主計數(shù)周期。

(4)已在數(shù)組hpet_devs中記錄了HPET中所有Timer的配置信息。除第0和第1號Timer之外，HPET的其它Timer可動態(tài)分配，用做其它目的。

通過讀寫HPET的寄存器，可以對其進行以下操作：

(1)啟/停HPET。整體配置寄存器的第0位是啟/停位，將其清0，可使整個HPET停止工作，將其置1，可使整個HPET重新工作。

(2)讀/寫主計數(shù)器。讀主計數(shù)器可獲得它的當前值，寫主計數(shù)器可以設(shè)置它的計數(shù)初值，如0。

(3)改變各Timer的中斷模式。如將某個Timer設(shè)為周期中斷模式并設(shè)置它的計數(shù)周期(頻率也是Hz)、將某Timer設(shè)為單發(fā)中斷模式并通過匹配寄存器設(shè)定它的下次中斷時間、將某個Timer設(shè)為未用或關(guān)閉模式以禁止它繼續(xù)產(chǎn)生中斷等。5.2.4LocalAPIC設(shè)備

LocalAPICTimer位于LocalAPIC內(nèi)部，是一種局部時鐘設(shè)備。與PIT和HPET不同，LocalAPICTimer沒有自己獨立的時鐘源，它的定時依據(jù)是處理器的總線時鐘。

每個LocalAPICTimer內(nèi)部至少包含三個寄存器，其中分頻寄存器用于設(shè)置Timer的計數(shù)頻率，實際是對處理器總線頻率的分頻。LocalAPICTimer的實際計數(shù)頻率為總線頻率的1/2i(i

=

0～7)，i由分頻寄存器指定。初始計數(shù)器用于設(shè)置計數(shù)初值。當前計數(shù)器的初值來源于初始計數(shù)器，并按計數(shù)頻率遞減。當當前計數(shù)器的值遞減到0時，LocalAPICTimer產(chǎn)生中斷，并被遞交給與之相連的處理器，其中斷向量號為0xef。

LocalAPICTimer可工作在單發(fā)中斷模式和周期中斷模式中。當工作在單發(fā)模式時，當前計數(shù)器從初始計數(shù)器中獲得初值并開始遞減，當遞減到0時產(chǎn)生中斷，而后停止，等待下一次設(shè)置。當工作在周期模式時，當前計數(shù)器會自動從初始計數(shù)器重裝初值，反復(fù)計數(shù)，從而產(chǎn)生周期性的中斷。

LocalAPICTimer可以被關(guān)閉，此時處理器僅能使用全局時鐘設(shè)備。LocalAPICTimer也可以被啟用，此時處理器通常使用自己的局部時鐘設(shè)備。每個LocalAPICTimer都要注冊自己的clock_event_device結(jié)構(gòu)，注冊工作由處理器自己完成。

Linux按16分頻設(shè)置LocalAPICTimer，即每過16個總線時鐘周期LocalAPICTimer的當前計數(shù)值才會減1。由于處理器的總線時鐘不是固定的，因而必須預(yù)先估算總線時鐘頻率或LocalAPICTimer的計數(shù)頻率。估算的依據(jù)是全局時鐘中斷，方法是讓系統(tǒng)延時100個滴答(100ms)，記下其間當前計數(shù)器的計數(shù)差，從而估算出LocalAPIC計數(shù)器的計數(shù)頻率和處理器的總線時鐘頻率。

當LocalAPICTimer工作在單發(fā)中斷模式時，可為它設(shè)定的下一次中斷時間，即LocalAPIC的計數(shù)初值，應(yīng)在0xF到0x7FFFFF之間。改變LocalAPICTimer的中斷模式需要設(shè)置LocalAPIC局部中斷向量表中的LVTT和Timer的初始計數(shù)器，LVTT控制Timer的中斷模式(周期模式、單發(fā)模式)、中斷向量和中斷屏蔽等，初始計數(shù)器控制Timer的中斷頻率(周期模式)或下一次中斷時間(單發(fā)模式)。關(guān)閉LocalAPICTimer的方法十分簡單，屏蔽它的中斷即可。

特殊情況下，可以廣播一個LocalAPICTimer的時鐘中斷，從而將其轉(zhuǎn)化成全局時鐘設(shè)備。方法是在局部時鐘中斷處理中，讓當前處理器通過IPI機制向其它處理器發(fā)送處理器間中斷，中斷向量號也是0xef。5.2.5當前時鐘設(shè)備

由于系統(tǒng)中同時存在多種時鐘設(shè)備，因而不同的處理器可能選用不同的時鐘設(shè)備。Linux在PERCPU數(shù)據(jù)區(qū)中為每個處理器定義了一個結(jié)構(gòu)變量tick_cpu_device(類型為tick_device)，用于記錄處理器當前使用的時鐘設(shè)備。每個處理器都需要選用一個時鐘設(shè)備，一個時鐘設(shè)備只能被一個處理器選用。

structtick_device{

structclock_event_device *evtdev; //時鐘設(shè)備

enumtick_device_mode mode; //中斷模式

};

DEFINE_PER_CPU(structtick_device,tick_cpu_device);

每當有新的時鐘設(shè)備注冊時，當前處理器都會進行檢查比對，決定是否需要更新自己的時鐘設(shè)備。檢查的范圍包括新注冊的時鐘設(shè)備和clockevents_released隊列中的所有空閑的時鐘設(shè)備。在下列條件下，處理器將更換時鐘設(shè)備：

(1)新設(shè)備能為本處理器提供時鐘中斷。

(2)處理器還未選用時鐘設(shè)備，或新時鐘設(shè)備的優(yōu)先級比已選用設(shè)備的優(yōu)先級高。

如果處理器已經(jīng)選用了時鐘設(shè)備，那么在下列情況下不用再進行更換：

(1)新設(shè)備不能為本處理器提供時鐘中斷。

(2)處理器已選用了自己的局部時鐘設(shè)備。

(3)處理器已選用的時鐘設(shè)備支持單發(fā)中斷模式，但新時鐘設(shè)備不支持。

(4)處理器已選時鐘設(shè)備的優(yōu)先級比新設(shè)備的優(yōu)先級高。

如果處理器決定選用或更換時鐘設(shè)備，它要進行如下處理：

(1)如果處理器還未選用時鐘設(shè)備，則將新注冊的設(shè)備選為自己的周期性時鐘設(shè)備，即讓tick_cpu_device中的evtdev指向新設(shè)備；如果處理器已選用過時鐘設(shè)備，則將老的時鐘設(shè)備設(shè)為未用模式，將其轉(zhuǎn)到clockevents_released隊列中，而后將新設(shè)備設(shè)為自己的時鐘設(shè)備，中斷模式與處理函數(shù)保持不變。

(2)如果選用的新設(shè)備不是當前處理器的局部時鐘設(shè)備(全局時鐘設(shè)備)，則需要設(shè)置中斷控制器，讓其將新時鐘設(shè)備的中斷遞交給當前處理器。事實上，每個時鐘設(shè)備的中斷僅會遞交給一個處理器。

(3)如果還未為時鐘中斷全局部分的處理工作指定處理器，則指定當前處理器。時鐘中斷的處理工作分成兩部分：全局部分負責(zé)處理影響系統(tǒng)全局的工作(如更新系統(tǒng)時間)，本地部分負責(zé)處理單個處理器內(nèi)部的工作(如更新當前進程的時間片)。系統(tǒng)中只能有一個處理器負責(zé)全局部分的處理工作。

(4)設(shè)置時鐘設(shè)備的中斷處理函數(shù)。初始情況下，時鐘設(shè)備工作在周期中斷模式，其處理函數(shù)是tick_handle_periodic。如果該時鐘設(shè)備同時還是時鐘中斷的廣播設(shè)備，它的處理函數(shù)應(yīng)是tick_handle_periodic_broadcast。

(5)啟用新選用的時鐘設(shè)備。如果新選用的時鐘設(shè)備工作在周期中斷模式，還要設(shè)置它的中斷頻率，否則要設(shè)置它的下一次中斷時間。

在系統(tǒng)初始化時，BSP負責(zé)注冊全局時鐘設(shè)備PIT和HPET，同時也會注冊自己的LocalAPICTimer。由于LocalAPICTimer的優(yōu)先級比全局設(shè)備的優(yōu)先級高，因而只要BSP未禁用LocalAPIC，它肯定會選用自己的局部時鐘設(shè)備。在AP啟動過程中，它們也會注冊自己的LocalAPICTimer，且會選用自己的局部時鐘設(shè)備。所以，正常情況下，處理器都會選用自己的局部時鐘設(shè)備，除非它的LocalAPIC被禁用。

如果處理器選用的是啞時鐘設(shè)備(不會產(chǎn)生時鐘中斷)，則要啟用廣播設(shè)備(HPET或PIT)。指針tick_broadcast_device指向廣播設(shè)備，位圖tick_broadcast_mask記錄需要接收時鐘中斷廣播的處理器。初始情況下，廣播設(shè)備也工作在周期中斷模式，其處理函數(shù)是tick_handle_periodic_broadcast。當廣播設(shè)備產(chǎn)生中斷時，其處理函數(shù)會將該中斷轉(zhuǎn)發(fā)給選用啞設(shè)備的處理器，所轉(zhuǎn)發(fā)的中斷號就是啞設(shè)備注冊的中斷向量號，如0xef。

傳統(tǒng)的計算機系統(tǒng)中僅有一個RTC和一個PIT，因而只能以滴答為基礎(chǔ)建立其時間管理系統(tǒng)。在新的計算機系統(tǒng)中，除PIT之外，還配置有其它的計時設(shè)備，如HPET、TSC等，它們可以提供更小的計時單位、更高的計時精度和更新的計時方法。然而，多種共存的計時設(shè)備也增加了管理的復(fù)雜性。5.3計?時?器?管?理為了統(tǒng)一起見，Linux將可以用來計時的設(shè)備抽象成計時器，并專門定義了結(jié)構(gòu)clocksource(也叫timesource)來描述計時器。每個計時器都有定義自己的clocksource結(jié)構(gòu)，其中包含如下一些屬性域：

(1)優(yōu)先級rating，值越大表示計時器的優(yōu)先級越高。

(2)轉(zhuǎn)換關(guān)系mult和shift，用于計時單位數(shù)與納秒數(shù)之間的互換，兩者之間的關(guān)系是mult=1個計時單位的長度(納秒)*2shift。對jiffies計時器，1個計時單位就是1個滴答。對HPET計時器，1個計時單位就是一個輸入脈沖周期。

(3)操作函數(shù)，其中read和vread用于獲得計時器的當前值，resume用于恢復(fù)計時器的運行，enable和disable用于開、關(guān)計時器等。

計時器可動態(tài)地注冊、注銷，并可暫停、恢復(fù)。

系統(tǒng)中所有已注冊的clocksource結(jié)構(gòu)都被組織在鏈表clocksource_list中，高優(yōu)先級的在前，低優(yōu)先級的在后。指針curr_clocksource指向當前使用的計時器，通常是已注冊且優(yōu)先級最高的計時器。在系統(tǒng)運行過程中，當前計時器可以被改變。

在目前的Linux版本中，可用的計時器已有多種，包括基于jiffies的計時器、基于TSC的計時器、基于HPET的計時器等。

基于jiffies的計時器是最傳統(tǒng)的計時器，它所計的是相對時間。Jiffies計時器建立在變量jiffies之上，或者說就是jiffies變量，其計時單位是滴答。如果系統(tǒng)使用的時鐘設(shè)備是PIT，時鐘中斷的頻率Hz是1000，那么一個滴答的長度約為999847ns，略小于106ns(1毫秒的納秒數(shù))。Jiffies計時器的read操作所讀出的是jiffies變量的當前值。

基于jiffies的計時器誤差較大，精度較低，而且會受時鐘中斷丟失的影響，因而其優(yōu)先級最低(為1)，通常僅用做備用計時器。

如果系統(tǒng)中配置有HPET，系統(tǒng)會在使能它時注冊基于HPET的計時器。HPET的計時頻率是其主計數(shù)器的增長頻率，計時單位即是其輸入時鐘的周期(可以從HPET的寄存器中讀出)，不大于100ns。因而HPET計時器的精度遠高于jiffies計時器，優(yōu)先級為250，也遠高于jiffies計時器。

HPET計時器建立在其主計數(shù)器之上，或者說就是HPET的主計數(shù)器。在啟用HPET時，其主計數(shù)器被清0，所以HPET計時器所計的也是相對時間。HPET計時器的read操作所讀出的是主計數(shù)器的當前值。

TSC(TimeStampCounter)是Intel處理器提供的一個時間戳計數(shù)器，該計數(shù)器在開機或RESET時清0，在處理器運行過程中單調(diào)增長。在較老的處理器上，每個內(nèi)部處理器時鐘周期都會使TSC遞增；在新的處理器上，TSC可按固定速率遞增。Intel提供了專門的指令RDTSC用于讀取TSC的當前值。

TSC的計時單位取決于處理器的時鐘周期，需要估算。Linux初始化時已利用PIT的第2個計數(shù)器(用于揚聲器)估算出了TSC的計數(shù)頻率，估算的方法很直觀，如下：

(1)讀出TSC的當前計數(shù)值tsc1。

(2)等待PIT第2個計數(shù)器的值減少i個，即延時(i

×

1000/1193182)ms。

(3)再讀出TSC的當前計數(shù)值tsc2。

(4)

TSC的計數(shù)頻率tsc_khz=((tsc2-tsc1)

×

1193182)/(i

×

1000)kHz。

當然，當處理器調(diào)整時鐘頻率時，其TSC的計數(shù)頻率還需要重新估算。TSC計時器的read操作所讀出的是TSC計數(shù)器的當前值。

由于目前處理器的時鐘頻率都比較高(1GHz以上)，因而TSC的計時精度很高。TSC計時器的優(yōu)先級為300，是最佳的計時器。

時鐘設(shè)備的原始設(shè)計目標是產(chǎn)生周期性的時鐘中斷。初始情況下，時鐘設(shè)備也被設(shè)定在周期中斷模式，用于產(chǎn)生周期性時鐘中斷。操作系統(tǒng)在周期性時鐘中斷處理中完成與時間相關(guān)的所有管理工作，如時間管理(更新當前時間)、定時管理(處理各類到期的定時器)、進程時間片管理、系統(tǒng)負載統(tǒng)計等。5.4周期性時鐘中斷5.4.1周期性時鐘中斷處理

在早期的版本中，Linux將周期性時鐘中斷的處理過程分成上下兩部分。上部處理在關(guān)中斷狀態(tài)下執(zhí)行，僅僅累計變量jiffies。底半處理在開中斷狀態(tài)下執(zhí)行，完成與時間相關(guān)的管理工作。由于時鐘中斷可能丟失、底半處理可能被推遲，因而上述處理過程可能導(dǎo)致較大的時間誤差。在新的Linux版本中，時鐘中斷的大部分處理工作被移到了硬處理部分，其處理流程依賴于處理器當前選用的時鐘設(shè)備。處理器可能選用全局時鐘設(shè)備。全局時鐘設(shè)備產(chǎn)生的中斷屬于設(shè)備中斷，使用的IRQ號是0，中斷控制器為它遞交的中斷向量號是0x30。在系統(tǒng)初始化時，已在IRQ0對應(yīng)的irq_desc結(jié)構(gòu)中注冊了處理程序timer_interrupt。每當全局時鐘設(shè)備產(chǎn)生中斷時，按照正常的設(shè)備中斷處理流程，函數(shù)timer_interrupt都會被執(zhí)行一次，該函數(shù)直接調(diào)用全局時鐘設(shè)備的處理函數(shù)global_clock_event->event_handler完成中斷處理。初始情況下，全局時鐘設(shè)備的處理函數(shù)是tick_handle_periodic。然而在目前的計算機系統(tǒng)中，處理器通常都會選用自己的LocalAPICTimer作為時鐘設(shè)備。LocalAPICTimer產(chǎn)生的時鐘中斷屬于局部中斷，中斷向量號是0xef，中斷處理函數(shù)是apic_timer_interrupt。局部時鐘中斷的處理流程如下：

(1)向LocalAPIC的EOI寄存器寫0，應(yīng)答此次時鐘中斷。

(2)增加preempt_count中的硬處理計數(shù)，表示進入硬中斷處理程序。

(3)累計當前處理器的統(tǒng)計信息，表示新收到一次局部時鐘中斷。

(4)執(zhí)行本地clock_event_device結(jié)構(gòu)中的event_handler操作，處理中斷。

(5)減少preempt_count中的硬處理計數(shù)，表示已退出硬中斷處理程序。

由此可見，局部時鐘中斷實際是由局部時鐘設(shè)備的event_handler操作處理的。處理器在選用局部時鐘設(shè)備時為它指定的event_handler操作也是tick_handle_periodic。

因此，不管處理器選用的是全局時鐘設(shè)備還是局部時鐘設(shè)備，最終完成周期性時鐘中斷處理的都是函數(shù)tick_handle_periodic，該函數(shù)完成的主要處理工作如下：

(1)如果當前處理器負責(zé)全局部分的處理工作，則更新系統(tǒng)時間、統(tǒng)計系統(tǒng)負載。

(2)統(tǒng)計當前進程的賬務(wù)信息，如累計進程消耗的時間等。

(3)處理高精度定時器隊列，執(zhí)行其中已到期的各高精度定時器上的處理函數(shù)。

(4)激活軟中斷TIMER_SOFTIRQ，請求處理核心定時器，并試圖將時鐘設(shè)備切換到單發(fā)中斷模式。

(5)如果當前處理器上有待處理器的RCU工作，則激活軟中斷RCU_SOFTIRQ。

(6)如果有待處理的日志寫操作，則處理它們。

(7)更新當前進程的調(diào)度信息(參見7.3.5)，如更新當前進程的虛擬計時器或時間片，觸發(fā)處理器間的負載平衡等。

(8)處理符合POSIX標準的時間間隔定時器。

(9)統(tǒng)計系統(tǒng)的Profile數(shù)據(jù)，以便進行性能分析。

注意：在切換到單發(fā)中斷模式之后，時鐘設(shè)備即不再產(chǎn)生周期性的時鐘中斷，其處理程序也就不會再被執(zhí)行，周期性時鐘中斷的處理工作將被設(shè)法仿真。5.4.2時間管理

時間管理子系統(tǒng)的主要工作是向用戶提供單調(diào)且平滑增長的、符合人類閱讀習(xí)慣的墻上時間(WallTimeorTimeofDay)，并能自動對時鐘的漂移進行微調(diào)。傳統(tǒng)的時間管理機制建立在周期性時鐘中斷之上，簡單但不準確，且可能違犯單調(diào)增長的原則。新的時間管理機制建立在高精度計時器之上，能夠提供單調(diào)、平滑、精確的時間服務(wù)。

在早期的版本中，Linux定義了兩個時間變量，其中jiffies的單位為滴答，內(nèi)容是從開機到當前時刻所過去的滴答總數(shù)，稱為相對時間；xtime的單位是微秒，內(nèi)容是從1970-01-0100:00:00到當前時刻所過去的微秒數(shù)，稱為墻上時間。變量jiffies的類型是32位的無符號整數(shù)，變量xtime的類型是一個結(jié)構(gòu)，其中包含兩個32位的整數(shù)，分別表示秒和微秒數(shù)，兩者之和為真正的墻上時間。

在隨后的發(fā)展中，時鐘中斷的頻率(Hz)提高了(jiffies更易溢出)，對時間精度的要求也提高了(納秒)，因而Linux調(diào)整了上述兩個變量的定義，如下：

u64 jiffies_64 _

_cacheline_aligned_in_smp=INITIAL_JIFFIES;

structtimespec{

_kernel_time_t tv_sec; //秒數(shù)，_

_kernel_time_t等價于long

long tv_nsec; //納秒數(shù)

};

structtimespec xtime _

_attribute_

_((aligned(16)));

structtimespec wall_to_monotonic _

_attribute_

_((aligned(16)));

staticstructtimespec xtime_cache _

_attribute_

_((aligned(16)));

重新定義以后，相對時間的類型改成了64位無符號整數(shù)，擁有了足夠大的容量，基本不會再溢出。為了與老版本兼容，jiffies仍被保留，但已不再是獨立的變量，而是變量jiffies_64中低32位的別名。墻上時間的基本單位改成了納秒。在系統(tǒng)初始化時，已經(jīng)從RTC中取出了當前時間(分別為year、mon、day、hour、min、sec)，并已將它們轉(zhuǎn)化成了相當于1970-01-0100:00:00的秒數(shù)。轉(zhuǎn)化算法如下：

(1)將mon提前2月。將mon減2，如果mon<=0，則將year減1，mon加12。

(2)轉(zhuǎn)換后的秒數(shù)= ((((year/4-year/100+year/400+367

×

mon/12+day)

+year

×

365-719499)

×

24+hour)

×

60+min)

×

60+sec。

在變量xtime中，域tv_sec的初值就是這一轉(zhuǎn)化后的秒數(shù)，域tv_nsec的初值是0。傳統(tǒng)的計時方法是：每收到一個時鐘中斷就在jiffies上加1，同時在xtime上累加1個滴答的時間量(如1ms)。

變量wall_to_monotonic用于計算開機以來新流逝的時間量(相對時間)，其初值與xtime相反，且在時鐘中斷處理中保持不變。因而wall_to_monotonic與xtime的和就是開機后新流逝是時間量。這種計算方法比jiffies更準確。

在系統(tǒng)初始化時，Linux還定義了一個timekeeper結(jié)構(gòu)，用于記錄系統(tǒng)當前選用的計時器和一些計時參數(shù)，如cycle_last是上一次更新墻上時間的時刻，xtime_nsec是累計的計時誤差，cycle_interval是一個時間更新周期(1個滴答或1個NTP校驗周期)所對應(yīng)的計時單位數(shù)，xtime_interval和raw_interval都是一個時間更新周期的長度(納秒數(shù))，前者經(jīng)過了NTP(NetworkTimeProtocol)校準，后者未經(jīng)過校準。

NTP是一種常用的時間校準機制，用于校正墻上時間。

負責(zé)全局工作的處理器會在自己的周期性時鐘中斷處理中更新系統(tǒng)時間，時間更新的依據(jù)是當前使用的計時器。時間更新的處理流程如下：

(1)將jiffies_64加1，因而jiffies也被自動加1。

(2)從timekeeper中取出上次進行時間更新的時間cycle_last，從系統(tǒng)當前選用的計時器中取出當前時間，算出兩者之間的時間差offset。

(3)根據(jù)offset和時間更新周期(cycle_interval)算出自上次時間更新以來新流逝的滴答數(shù)。由于時鐘中斷可能丟失，因而新流逝的滴答數(shù)可能大于1。根據(jù)新流逝的滴答數(shù)調(diào)整xtime中的tv_sec和tv_nsec，同時調(diào)整timekeeper中的累計誤差，并將cycle_last更新成最近一個時鐘中斷產(chǎn)生的時刻。

(4)根據(jù)timekeeper中的累計計時誤差微調(diào)它的mult、xtime_interval、xtime_nsec等參數(shù)，從而校準計時器。

(5)減去已累加到xtime中的時間量之后，offset中可能還有部分剩余，剩余量肯定小于1個滴答。將剩余的時間量累計到變量xtime_cache中。變量xtime_cache與xtime的類型相同，初值也相同，唯一的差別就是這不到1個滴答的時間量。

(6)將xtime中的時間值拷貝到vsyscall頁中。vsyscall頁已被映射到所有進程的虛擬地址空間中，用戶進程可以直接訪問其中的內(nèi)容，因而可直接獲得當前時間，從而減少系統(tǒng)調(diào)用的次數(shù)，加快進程運行速度。

由此可見，xtime和xtime_cache中記錄的都是截止到上次時鐘中斷時的系統(tǒng)時間，但xtime中的時間已按滴答值取整。以xtime為基礎(chǔ)可以向用戶提供時間服務(wù)，如獲取當前時間gettimeofday、設(shè)置當前時間settimeofday等。服務(wù)gettimeofday所獲得的當前時間就是xtime，但加上了新流逝的時間量。服務(wù)settimeofday則直接根據(jù)用戶提供的墻上時間設(shè)置xtime_cache、xtime、vsyscall頁中的時間及當前計時器的參數(shù)，還要根據(jù)新設(shè)置時間修正wall_to_monotonic。與傳統(tǒng)計時方法相比，上述計時方法已不再依賴于jiffies，因而更加精確。雖然時鐘中斷可能丟失，jiffies可能不準確，但只要收到時鐘中斷，xtime就會被更新成準確的當前時間，因為xtime的更新依據(jù)是高精度計時器，如TSC、HPET等，而高精度計時器的更新是由硬件自動實現(xiàn)的，不會受關(guān)中斷的影響，也不會丟失。即使出現(xiàn)xtime被延遲更新的現(xiàn)象，用戶通過gettimeofday獲得的當前時間也是精確的，因為它在xtime上加入了新流逝的時間量，而新流逝的時間量也取自高精度計時器。在新的計時方法中，系統(tǒng)開機時間(相對時間)由wall_to_monotonic和xtime計算得來，也不再依賴于jiffies，因而更加精確且保證會單調(diào)增長。事實上，新的時間管理子系統(tǒng)已擺脫了對jiffies的依賴，可以在單發(fā)式時鐘中斷驅(qū)動下很好地工作。5.4.3定時管理

以周期性時鐘中斷為基礎(chǔ)，可以提供多種定時器。使用定時器的目的有兩種，一是超時，目的是監(jiān)測某事件是否會在預(yù)定的時間內(nèi)發(fā)生，一旦事件發(fā)生，定時器將被關(guān)閉，定時器到期表示事件未發(fā)生；二是定時，目的是預(yù)定某項工作的停止或開始時間，一旦到期，工作必須立刻停止或開始。用做超時的定時器幾乎都會在到期前被關(guān)閉，且不需要很高的精度。用做定時的定時器通常會運行到預(yù)定的時間，且需要較高的精度。

早期的Linux提供了兩類定時器，一類是內(nèi)核自己使用的，稱核心定時器或低精度定時器；另一類是給用戶進程使用的，稱時間間隔定時器。兩類定時器都建立在jiffies基礎(chǔ)之上，由周期性時鐘中斷驅(qū)動，定時精度較低。在新版本中，Linux又提供了第三類定時器，稱為高精度定時器。高精度定時器的基礎(chǔ)是高精度時鐘設(shè)備。

1.核心定時器管理

核心定時器是最基本的一類定時器，它所定的是相對于jiffies的時間，單位為滴答。當jiffies的值達到或超過某核心定時器的到期時間時，該定時器到期，它的處理函數(shù)會被執(zhí)行一次。在高精度定時機制被啟用之前，核心定時器由周期性時鐘中斷驅(qū)動；在高精度定時機制被啟用之后，核心定時器由高精度定時器驅(qū)動。

一個核心定時器由一個結(jié)構(gòu)timer_list描述，其主要內(nèi)容如下：

structtimer_list{

structlist_head entry;

unsignedlong expires; //預(yù)定的到期時間

void(*function)(unsignedlong); //到期處理函數(shù)

unsignedlong data; //給處理函數(shù)的參數(shù)

structtvec_base *base; //定時器當前所屬的隊列組集合

};

Linux定義了512個隊列用于組織單個處理器中的核心定時器，這些隊列被分成5組，其中tv1組中有256個隊列，tv2、tv3、tv4、tv5組中各有64個隊列。

structtvec{

structlist_head vec[TVN_SIZE]; //TVN_SIZE=64

};

structtvec_root{

structlist_head vec[TVR_SIZE];

//TVR_SIZE=256

};

structtvec_base{

spinlock_t lock; //保護隊列組的自旋鎖

structtimer_list *running_timer; //正在被處理的定時器

unsignedlong timer_jiffies; //下一次處理時間

structtvec_root tv1;

structtvec tv2;

structtvec tv3;

structtvec tv4;

structtvec tv5;

}_cacheline_aligned;

DEFINE_PER_CPU(structtvec_base*,tvec_bases);

由定義可見，結(jié)構(gòu)tvec和tvec_root就是簡單的隊列數(shù)組，而結(jié)構(gòu)tvec_base則是隊列組的集合，其中的timer_jiffies是下一次應(yīng)進行核心定時處理的時間，也就是上次進行核心定時處理的時間(jiffies)加1。早期的Linux僅定義了一個核心定時器隊列組集合。新版本的Linux為每個處理器都定義了一個核心定時器隊列組集合。一個定時器僅能加入到一個隊列中，因而僅能屬于一個處理器。指針tvec_bases指向各處理器自己的定時器隊列組集合，如圖5.4所示。

圖5.4核心定時器的隊列組集合結(jié)構(gòu)在一個核心定時器的隊列組集合中，不同隊列組的定時范圍不同，相鄰隊列間的時間差(粒度)也不同。這一組織方式在保證管理效率的前提下有效地減少了定時器隊列的數(shù)量。表5.1列出了各隊列組的定時范圍及隊列組中相鄰隊列間的時間差。

表5.1隊列組的定時范圍及相鄰隊列間的時間差在一個核心定時器定時期間，它所處的隊列組(tvi)會逐漸變化。定時器當前所處的隊列組取決于它的定時間隔，即與當前時刻的距離，也就是預(yù)定的到期時間(expires)與隊列組集合中timer_jiffies的差值，該差值落在哪個隊列組的定時范圍，定時器就應(yīng)該進入哪個隊列組。隨著時間的流逝，定時器的到期時間越來越近，它所處的隊列組也會越來越小。到期的定時器永遠都在tv1中。

核心定時器在一個隊列組中的位置(隊列)僅取決于它的到期時間(expires)而與它的定時間隔無關(guān)。定時器的到期時間是一個32位的無符號整數(shù)，被分成5段，分別對應(yīng)5個隊列組，如圖5.5所示。

圖5.5定時器到期時間(expires)的劃分如一個核心定時器應(yīng)進入第i

(i在1到5之間)個隊列組，其expires的tvi段的值是j，那么該定時器應(yīng)被插入在第i個隊列組的第j個隊列中。由于定時器的expires不會改變，它在隊列組內(nèi)部的位置就不會隨著時間的流逝而變動。也就是說，核心定時器僅會在隊列組間移動，不需要在隊列組內(nèi)移動。最壞情況下，一個定時器會被移動4次，從tv5到tv4、tv4到tv3、tv3到tv2、tv2到tv1，形成了一個逐級下降的瀑布，因而這種管理模型又稱為瀑布模型。瀑布模型極大地減少了核心定時器管理的工作量。瀑布模型與人類的計時習(xí)慣完全吻合。定時距離越近，定時粒度應(yīng)該越小，對它的管理應(yīng)越細致；定時距離越遠，定時粒度應(yīng)該越大，對它的管理可以更粗放。

啟動一個核心定時器的工作包括設(shè)置好它的處理函數(shù)和到期時間，確定它所在的定時隊列，而后將它的timer_list結(jié)構(gòu)插入到隊列(隊頭或隊尾)中。停止一個核心定時器就是將其timer_list結(jié)構(gòu)從隊列中摘下。在隊列間移動核心定時器的工作包括兩步，即先將其從老隊列中摘下(刪除)，再根據(jù)它的expires將其插入到新隊列中。通過刪除和再插入，可以在同一個隊列組集合內(nèi)移動定時器，也可以在不同隊列組集合間移動定時器，即在不同的處理器間移動定時器，從而實現(xiàn)定時器的負載平衡。當然，移動定時器的過程需要鎖(tvec_base中的lock)的保護。

在核心定時器定時期間，可以改變它的到期時間。定時器的到期時間被改變之后，它所在的隊列也應(yīng)隨之改變。

核心定時器由周期性時鐘中斷驅(qū)動。處理器每收到一次時鐘中斷，不管它來自全局還是局部時鐘設(shè)備，都會在硬處理程序中激活一次軟中斷TIMER_SOFTIRQ。在系統(tǒng)初始化時，為該軟中斷注冊的處理程序是run_timer_softirq。因而，只要處理器處理軟中斷TIMER_SOFTIRQ，函數(shù)run_timer_softirq就會被執(zhí)行。只要jiffies的當前值達到或超過了隊列組集合中的timer_jiffies，其上的核心定時器就會被檢查并被處理。

早期的Linux為核心定時器的每個隊列組都定義了一個index，用來指示該隊列組中下一個待處理的隊列。當index所指隊列被處理完后，index加1，指向下一個隊列。新版本的Linux去掉了各隊列組中的index，改用隊列組集合中的timer_jiffies統(tǒng)一指示各隊列組中的下一個待處理隊列，如圖5.6所示。

圖5.6timer_jiffies與定時器隊列的關(guān)系與expires一樣，timer_jiffies也被劃分成了5個部分，分別用于指示5個的隊列組中的待處理隊列。域timer_jiffies的初值是隊列組集合初始化時的jiffies，在隨后的處理中，timer_jiffies的值會不斷遞增，與jiffies基本保持一致，從而使各組中的隊列被輪流處理，因此核心定時機制又被稱為時間輪(Timing-Wheel)。核心定時器的處理流程如下：

(1)取出timer_jiffies中的tv1部分，暫記在index中。

(2)如果index是0，說明tv1的所有隊列已被處理過一遍，時間又過去了256個滴答，tv2的待處理隊列上的定時器距離到期時間已不足256個滴答，應(yīng)該將它們下移到tv1中。

(3)如果timer_jiffies中的tv2部分是0，說明tv2的所有隊列已被處理過一遍，時間又過去了256

×

64個滴答，tv3的待處理隊列上的定時器距離到期時間已不足256

×

64個滴答，應(yīng)該將它們下移到tv2中。

(4)如果timer_jiffies中的tv3部分是0，說明tv3的所有隊列已被處理過一遍，時間又過去了256

×

64

×

64個滴答，tv4的待處理隊列上的定時器距離到期時間已不足256

×

64

×

64個滴答，應(yīng)該將它們下移到tv3中。

(5)如果timer_jiffies中的tv4部分是0，說明tv4的所有隊列已被處理過一遍，時間又過去了256

×

64

×

64

×

64個滴答，tv5的待處理隊列上的定時器距離到期時間已不足256

×

64

×

64

×

64個滴答，應(yīng)該將它們下移到tv4中。

(6)將timer_jiffies加1。

(7)在tv1中，index所指的是已到期的定時器隊列。摘下該隊列中的所有定時器，將隊列清空，而后逐個執(zhí)行各到期定時器上的處理函數(shù)function。

(8)如果timer_jiffies仍然未超過jiffies的當前值，說明還有到期的定時器，轉(zhuǎn)(1)進行新一輪的處理。正常情況下，當處理核心定時器時，隊列組集合中的timer_jiffies應(yīng)等于jiffies。但由于軟中斷可能被延遲，jiffies有可能超過timer_jiffies。這也說明核心定時器的定時不是十分精確。

綜上所述，核心定時器的插入、刪除操作都很快，與系統(tǒng)中的定時器數(shù)量無關(guān)，算法的時間復(fù)雜度是O(1)。核心定時器下移的平均時間復(fù)雜度很好，但最壞時間復(fù)雜度較差，為O(n)，可能會增加定時處理的延遲時間。因而，核心定時器比較適合較近的定時(小于256滴答)、在到期或被下移之前就被刪除的定時，如網(wǎng)絡(luò)的超時定時等。

2.高精度定時器管理

建立在周期性時鐘中斷基礎(chǔ)上的核心定時器所實現(xiàn)的定時粒度為滴答(毫秒級)，且最壞時間復(fù)雜性較差，無法提供更精確的定時服務(wù)。1998年以來，人們嘗試了多種方法，試圖在核心定時器的管理框架中集成高精度定時器，但都沒有達到理想的效果。直到2006年，在Linux2.6.16中，以高精度時鐘設(shè)備為基礎(chǔ)，新設(shè)計了一種高精度定時器的管理框架，才解決了高精度定時器的管理問題。

與核心定時器相似，一個高精度定時器也需要一個描述結(jié)構(gòu)，用于記錄它的到期時間(_expires)、到期處理函數(shù)(function)、定時器狀態(tài)等，該結(jié)構(gòu)為hrtimer，定義如下：

structhrtimer{

structrb_node node;

ktime_t _expires;

ktime_t _softexpires;

enumhrtimer_restart(*function)(structhrtimer*);

structhrtimer_clock_base *base;

unsignedlong state;

};可以為高精度定時器預(yù)定一個到期時間范圍，從_softexpires到_expires，但定時仍以_expires為準。定時器的狀態(tài)包括未啟動、已入隊、正在處理、正在遷移等。

由于系統(tǒng)中可能同時啟動多個高精度定時器，因而需要另外一種結(jié)構(gòu)來組織、管理它們的hrtimer結(jié)構(gòu)。根據(jù)高精度定時器的管理要求，所有的hrtimer結(jié)構(gòu)應(yīng)該組成一個有序隊列，隊頭的定時器最早到期，隊尾的定時器最遲到期。雖然可以用鏈表實現(xiàn)有序隊列，但有序鏈表的插入時間較長，最壞時間復(fù)雜度為O(n)。為改善有序隊列的管理性能，Linux引入了紅黑樹，將已啟動的高精度定時器組織在紅黑樹中，從而使插入、刪除和查找的時間復(fù)雜度都縮減到了O(log(n))。結(jié)構(gòu)hrtimer中的node用于將高精度定時器鏈接到紅黑樹中。一棵紅黑樹由一個hrtimer_clock_base結(jié)構(gòu)描述，其定義如下：

structhrtimer_clock_base{

structhrtimer_cpu_base *cpu_base;

clockid_t index;

structrb_root active;

structrb_node *first;

ktime_t resolution;

ktime_t(*get_time)(void);

ktime_t softirq_time;

ktime_t offset;

};其中的active是紅黑樹的根，first是紅黑樹中最左邊的節(jié)點，也就是最早到期的高精度定時器，resolution是定時精度(未啟用高精度定時機制時的精度是1個滴答、啟用后的精度為1ns)，offset是定時的基準時間，softirq_time是系統(tǒng)當前時間，get_time是從計時器中讀取當前時間的操作函數(shù)。高精度定時器對到期時間的表示方法有兩種，一種是絕對時間(指定一個絕對的到期時刻)，即定時到某年某月某日的某時某分某秒某納秒為止；另一種是相對時間(指定一個定時間隔)，即從當前時間開始定時，在某納秒之后到期。采用絕對時間的定時器稱為絕對時間定時器，采用相對時間的定時器稱為相對時間定時器。雖然可以用統(tǒng)一的方式表示它們，但Linux提供了兩棵紅黑樹，分別用于組織兩類不同的高精度定時器。結(jié)構(gòu)hrtimer_cpu_base用于描述這兩棵紅黑樹，其定義如下：

structhrtimer_cpu_base{

spinlock_t lock; //保護鎖

structhrtimer_clock_base clock_base[2]; //兩棵紅黑樹

ktime_t expires_next; //時鐘設(shè)備下次產(chǎn)生中斷的時間

int hres_active; //是否已被啟用

unsignedlong nr_events; //累計到期次數(shù)

};在實現(xiàn)時，時鐘設(shè)備下次產(chǎn)生中斷的時間expires_next被統(tǒng)一成了相對于開機時刻的偏移量，單位為ns。與核心定時器不同，高精度定時機制必須顯式地啟用。域hres_active記錄一個處理器上的高精度定時機制是否已被啟用。

與核心定時器相似，為了避免沖突，Linux在PERCPU數(shù)據(jù)區(qū)中為每個處理器定義了一個紅黑樹管理結(jié)構(gòu)，稱為hrtimer_bases，其中的第0棵樹為絕對時間紅黑樹，讀取當前時間的操作函數(shù)為ktime_get_real；第1棵樹為相對時間紅黑樹，讀取當前時間的操作函數(shù)為ktime_get。兩棵樹中的初始定時精度resolution都是1個滴答。管理結(jié)構(gòu)如圖5.7所示。

圖5.7高精度定時器的管理結(jié)構(gòu)不管是否已啟用高精度定時機制，都可以啟動高精度定時器。

在啟動一個高精度定時器之前，需要先初始化它的hrtimer結(jié)構(gòu)，設(shè)置好它的到期時間(_expires)、到期處理函數(shù)、類型(絕對或相對)等，而后按到期時間的先后順序?qū)⑵洳迦氲脚c定時器類型匹配的紅黑樹中。如果高精度定時機制已被啟用，且新啟動定時器的相對到期時間(_expires與offset的差)比預(yù)定的下一次中斷時間expires_next更早，則要對時鐘設(shè)備進行重新編程，以調(diào)整它的下一次中斷時間。如果高精度定時機制未被啟用，則不需要對時鐘設(shè)備進行重新編程。如果在此期間新啟動的定時器已經(jīng)到期，則要激活軟中斷HRTIMER_SOFTIRQ，檢查并處理已到期的高精度定時器。

在高精度定時器到期之前可以將其停止。停止一個高精度定時器的主要工作是將其從紅黑樹中摘除。如果高精度定時機制已被啟用，且被停止的定時器位于紅黑樹的最左邊，則要對時鐘設(shè)備進行重新編程，以調(diào)整它的下一次中斷時間。最左邊的定時器被摘除后，它的下一個定時器會變成最左邊的定時器。在一個高精度定時器定時期間，可以改變它的到期時間。定時器的到期時間被改變之后，它在紅黑樹中的位置也要隨之調(diào)整(先摘下、再插入)。

在一個高精度定時器定時期間，可以將其從一個處理器遷移到另一個處理器(平衡負載)。遷移一個定時器的工作包括將其從老紅黑樹中摘下，再插入到新的紅黑樹中。

在初始情況下，高精度定時機制都未被啟用(hres_active是0)，各時鐘設(shè)備都工作在周期中斷模式中。在周期性時鐘中斷驅(qū)動下，高精度定時器的處理流程如下：

(1)更新兩棵紅黑樹中的當前時間softirq_time。在絕對定時器樹中，softirq_time被更新為xtime_cache，即當前的絕對時間；在相對定時器樹中，softirq_time被更新為xtime_cache與wall_to_monotonic的和，即當前的相對時間。

(2)以softirq_time為基準，按從左到右的順序檢查兩棵紅黑樹。如果某定時器已到期，則將其從紅黑樹中摘下，執(zhí)行其上的處理函數(shù)。如果在處理函數(shù)中又重新啟動了該定時器，則將其再次插入到紅黑樹中。由此可見，雖然高精度定時器可以提供更高精度的定時服務(wù)，但在真正啟用高精度定時機制之前，其優(yōu)勢并未發(fā)揮出來。在處理之時，有的高精度定時器可能已經(jīng)過期了較長時間。此時的高精度定時器基本等價于核心定時器，有著較大的定時誤差。

3.時間間隔定時器管理

用戶進程的運行也需要定時器，內(nèi)核應(yīng)該為用戶進程提供這類定時服務(wù)。與核心定時器和高精度定時器不同，時間間隔定時器是由用戶進程在用戶空間啟動的(當然需要通過系統(tǒng)調(diào)用)，它們運行在內(nèi)核空間，但需要將到期信息及時地通知用戶進程。通知的手段是信號(Signal)。

傳統(tǒng)的Linux提供三類時間間隔定時器，分別是實時(Real)、虛擬(Virtual)和概略(Profile)定時器。三類定時器所定的都是相對時間。實時定時器根據(jù)系統(tǒng)實際時間定時，定的是流逝的時間量，定時到期時進程會收到SIGALRM信號。虛擬定時器根據(jù)進程消耗的用戶態(tài)時間定時，定的是進程在用戶態(tài)消耗的時間量，定時到期時進程會收到SIGVTALRM信號。概略定時器根據(jù)進程消耗的時間(不管是用戶態(tài)時間還是核心態(tài)時間)定時，定的是進程消耗的時間量，定時到期時進程會收到SIGPROF信號。虛擬與概略定時器的定時單位是滴答。Linux統(tǒng)一管理三類時間間隔定時器。用戶進程不會啟動太多的時間間隔定時器。事實上，一個用戶進程最多能夠啟動三個時間間隔定時器，每類定時器一個。由于這一限制，時間間隔定時器的管理結(jié)構(gòu)就不需要特別復(fù)雜，僅需要在進程管理結(jié)構(gòu)中為時間間隔定時器增加幾個域變量即可。

時間間隔定時器可以工作在單發(fā)模式，也可以工作在周期模式。既然間隔定時器可工作在周期模式，就需要為它們分別準備一個變量來記錄周期長度或時間間隔；既然實時定時器按系統(tǒng)時間定時，就需要為它準備一個高精度定時器或核心定時器；既然虛擬和概略定時器按進程消耗的時間定時，就需要為它們分別準備變量來記錄進程消耗的時間量和到期的時間量。早期的Linux將上述信息直接記錄在task_struct結(jié)構(gòu)中，新版本的Linux將這些信息記錄在信號管理結(jié)構(gòu)signal_struct中。結(jié)構(gòu)signal_struct中包含很多內(nèi)容，與時間間隔定時器相關(guān)的有如下幾個：

(1)

real_timer是為實時定時器準備的高精度定時器。

(2)

it_real_incr、it_virt_incr、it_prof_incr是實時、虛擬、概略定時器的定時間隔。

(3)

it_virt_expires和it_prof_expires是虛擬和概略定時器的當前值。

(4)

utime是進程消耗的用戶態(tài)時間，stime是進程消耗的核心態(tài)時間，utime+stime是進程消耗的時間。

定時器的當前值與定時間隔可以取不同的值，其組合意義如表5.2所示。

表5.2時間間隔定時器各參數(shù)的組合意義三類時間間隔定時器的啟動與處理方式如下：

(1)實時定時器。在進程創(chuàng)建時，已設(shè)置了它的高精度定時器real_timer，該定時器將采用相對時間定時，其到期處理函數(shù)是it_real_fn。在用戶進程請求啟動實時定時器時，請求的時間間隔被記錄在進程的it_real_incr中，定時器real_timer被同時設(shè)置并啟動。當定時器到期時，向進程發(fā)送信號SIGALRM。如果it_real_incr非0，則real_timer的到期時間會被加上it_real_incr，該定時器也會被重新啟動。

(2)虛擬定時器。在進程創(chuàng)建時，虛擬定時器的當前值與定時間隔都是0。在用戶進程請求啟動虛擬定時器時，it_virt_expires被設(shè)為初始定時間隔與進程已消耗的用戶態(tài)時間之和，it_virt_incr被設(shè)為定時間隔。在時鐘中斷處理中，當前進程消耗的用戶態(tài)時間量被累計在utime中。如果utime大于或等于it_virt_expires，則向進程發(fā)送信號SIGVTALRM。如果it_virt_incr為0，則將it_virt_expires清0，停止定時，否則將it_virt_expires設(shè)為utime+it_virt_incr，重新啟動定時器，如圖5.8所示。圖5.8周期性虛擬定時器

(3)概略定時器。在進程創(chuàng)建時，概略定時器的當前值與定時間隔都是0。在用戶進程請求啟動概略定時器時，it_prof_expires被設(shè)為初始時間間隔與進程已消耗時間的和，it_prof_incr被設(shè)為定時間隔。在時鐘中斷處理中，當前進程消耗的時間量被累計在utime和stime中。如果utime+stime大于或等于it_prof_expires，則向進程發(fā)送信號SIGPROF。如果it_prof_incr為0，則將it_prof_expires清0，停止定時，否則將it_prof_expires設(shè)為utime+stime+it_prof_incr，重啟定時器。在早期的系統(tǒng)中，如果啟動了虛擬或概略定時器，那么每次時鐘中斷都會向下遞減it_virt_expires和it_prof_expires，減到0時發(fā)送信號，而后用it_virt_incr和it_prof_incr恢復(fù)初值。在時鐘中斷丟失的情況下，這種定時方法有較大的誤差。新的定時方法不再依賴于滴答，而且對進程消耗時間的統(tǒng)計也比較準確，因而定時的誤差較小。

周期性時鐘中斷是簡單的，也是盲目的、傻瓜的。不管系統(tǒng)是否需要，周期性時鐘中斷都會如期產(chǎn)生，其時機不受外界干擾，也無法動態(tài)調(diào)整。將系統(tǒng)建立在周期性時鐘中斷之上會帶來以下問題：

(1)中斷過多。很多的周期性時鐘中斷都沒有太多用處，它們給系統(tǒng)帶來的純粹是一種噪聲(Jitter)，既浪費處理器時間，又浪費電力資源。5.5單發(fā)式時鐘中斷

(2)誤差過大。周期性時鐘中斷往往不能在真正需要的時間點上及時產(chǎn)生，導(dǎo)致了較大的計時誤差，如圖5.9所示。圖5.9周期性時鐘中斷與單發(fā)式時鐘中斷更為嚴重的是，上述兩個問題的解決方法是相互矛盾的。解決第一個問題的方法是降低中斷頻率，但頻率過低會帶來更大的誤差；解決第二個問題的方法是提高中斷頻率，但頻率過高又會帶來更多的噪聲。因而，只要有可能，Linux都試圖拋棄傳統(tǒng)的周期性時鐘中斷，改用更加智能、準確的單發(fā)式時鐘中斷。

目前的時鐘設(shè)備大都能夠支持單發(fā)中斷模式，即可以根據(jù)設(shè)定在準確的時間點上產(chǎn)生單發(fā)式時鐘中斷。與周期性時鐘中斷不同，單發(fā)式時鐘中斷通常是不連續(xù)的，時間間隔不等，甚至可以暫停。工作在單發(fā)中斷模式的時鐘設(shè)備更加智能，它產(chǎn)生時鐘中斷的時機更加準確，目的性也更加明確。單發(fā)中斷模式是對周期中斷模式的一種顛覆，它打破了周期性時鐘中斷的設(shè)計定式，為時鐘管理帶來了革命性的變革。以單發(fā)式時鐘中斷為基礎(chǔ)，可以設(shè)計出更高精度的定時器從而提供更高精度的定時服務(wù)，可以在系統(tǒng)空閑時停止時鐘中斷從而減少對系統(tǒng)的干擾，節(jié)約能源。當然，以單發(fā)式時鐘中斷為基礎(chǔ)，也可以完成時間管理、進程調(diào)度和系統(tǒng)負載統(tǒng)計等工作。與周期中斷模式不同，當時鐘設(shè)備工作在單發(fā)中斷模式時，它產(chǎn)生時鐘中斷的每一個時間點都必須明確地、顯式地設(shè)定。按照允許設(shè)定的時間點精度，可以將單發(fā)中斷模式細分為高精度單發(fā)中斷模式和低精度單發(fā)中斷模式。5.5.1高精度單發(fā)中斷模式

如果處理器選用的時鐘設(shè)備是高精度的，而且支持單發(fā)中斷模式，那么Linux會將其切換到高精度單發(fā)中斷模式。當時鐘設(shè)備工作在高精度單發(fā)中斷模式時，它的中斷時間點由高精度定時器管理，所產(chǎn)生的時鐘中斷也由高精度定時器處理，因而高精度定時器是高精度單發(fā)式時鐘中斷處理的核心。事實上，在進入高精度單發(fā)中斷模式后，系統(tǒng)的時間管理、定時管理等子系統(tǒng)都建立在高精度定時器之上(如圖5.1所示)。

高精度定時器的定時思路是：將高精度時鐘設(shè)備切換到單發(fā)中斷模式，將它的下一次中斷時間設(shè)為到期時間最近的某個定時器的到期時間，從而啟動定時；當定時到期時，高精度時鐘設(shè)備產(chǎn)生中斷；在時鐘中斷處理中執(zhí)行已到期定時器的處理函數(shù)，完成定時處理工作，而后重新選擇到期時間最近