linux時鐘淺析

時鐘的作用
盡管與CPU指令執(zhí)行沒有什么直接關(guān)系，時鐘對于操作系統(tǒng)來說還是有著很重要的意義：
1、記錄系統(tǒng)時間。很多應(yīng)用程序需要知道日期和時間、由日期和時間構(gòu)成的時間戳也會被打在文件上面、等等；
2、統(tǒng)計功能。如top之類的用戶程序可以查看一段時間內(nèi)的系統(tǒng)負(fù)載、以及各個進程占用CPU的時間、等等；
3、定時功能。很多用戶程序會使用到定時器，比如sleep一段時間后做某件事情、比如給select設(shè)置一個超時時間、等等；

關(guān)于時鐘硬件
為了實現(xiàn)這些功能，計算機硬件需要提供相應(yīng)的時鐘電路。這些電路大致上分兩類：
1、RTC（實時時鐘），記錄著當(dāng)前的日期和時間（記錄的是自1970-01-01起經(jīng)歷的秒數(shù)），并且自動隨時間增長。
這種硬件是由電池獨立供電的，因為它要保持日期時間的更新，不能因為計算機的斷電而停止工作。
linux內(nèi)核只在啟動時從RTC獲取當(dāng)前時間，用于設(shè)置系統(tǒng)時間。在系統(tǒng)時間被修改時，linux內(nèi)核會相應(yīng)地更新RTC。
而系統(tǒng)時間的自動增長則不依賴于RTC，依賴的是另一種時鐘電路。

2、時鐘振蕩器，可以周期性地發(fā)出中斷。
這種硬件是可編程的，linux內(nèi)核在啟動時可設(shè)置它發(fā)出中斷的周期，一般是1ms。于是每隔1ms，CPU將收到一個時鐘中斷，這個時間間隔稱作一個tick（節(jié)拍）。
利用這種周期性的中斷，linux內(nèi)核在處理時鐘中斷的中斷處理程序（參見《linux內(nèi)核中斷處理淺析》）中，實現(xiàn)了系統(tǒng)時間的自動增長、各種統(tǒng)計和定時器功能。
CPU每ms都要處理一次時鐘中斷，并且還要在中斷處理程序中完成很多功能，那它還有時間干別的事嗎？考慮一個主頻為200MHz的RISC結(jié)構(gòu)的CPU，假設(shè)每個CPU周期能處理一條指令，那么1ms的時間這個CPU能執(zhí)行約20萬條指令。假設(shè)時鐘中斷處理程序能在1萬條指令之內(nèi)完成（一般情況下1萬條指令應(yīng)該足夠了），CPU還是有大部分的時間能干其他事的。

關(guān)于時鐘中斷
在單處理器系統(tǒng)中，每個tick只發(fā)生一次時鐘中斷。在對應(yīng)的中斷處理程序中完成更新系統(tǒng)時間、統(tǒng)計、定時器、等全部功能；
而在多處理器系統(tǒng)下，時鐘中斷實際上是分成兩個部分：
1、全局時鐘中斷，系統(tǒng)中每個tick只發(fā)生一次。對應(yīng)的中斷處理程序用于更新系統(tǒng)時間和統(tǒng)計系統(tǒng)負(fù)載；
2、本地時鐘中斷，系統(tǒng)中每個tick在每個CPU上發(fā)生一次。對應(yīng)的中斷處理程序用于統(tǒng)計對應(yīng)CPU和運行于該CPU上的進程的時間，以及觸發(fā)對應(yīng)CPU上的定時器；
于是，在多處理器系統(tǒng)下，每個tick，每個CPU要處理一次本地時鐘中斷；另外，其中一個CPU還要處理一次全局時鐘中斷。

更新系統(tǒng)時間
在linux內(nèi)核中，全局變量jiffies_64用于記錄系統(tǒng)啟動以來所經(jīng)歷的tick數(shù)。每次進入時鐘中斷處理程序（多處理器系統(tǒng)下對應(yīng)的是全局時鐘中斷）都會更新jiffies_64的值，正常情況下，每次總是給jiffies_64加1。
而時鐘中斷存在丟失的可能。內(nèi)核中的某些臨界區(qū)是不能被中斷的，所以進入臨界區(qū)前需要屏蔽中斷。當(dāng)中斷屏蔽取消的時候，硬件只能告訴內(nèi)核是否曾經(jīng)發(fā)生了時鐘中斷、卻不知道已經(jīng)發(fā)生過多少次。于是，在極端情況下，中斷屏蔽時間可能超過1個tick，從而導(dǎo)致時鐘中斷丟失。
如果計算機上的時鐘振蕩器有很高的精度，linux內(nèi)核可以讀振蕩器中的計數(shù)器，通過比較上一次讀的值與當(dāng)前值，以確定中斷是否丟失。如果發(fā)現(xiàn)中斷丟失，則本次中斷處理程序會給jiffies_64增加相應(yīng)的計數(shù)。但是如果振蕩器硬件不允許（不提供計數(shù)器、或者計數(shù)器不允許讀、或者精度不夠），內(nèi)核也沒法知道時鐘中斷是否丟失了。（不過丟失就丟失吧，也沒什么大不了的。）

內(nèi)核中的全局變量xtime用于記錄當(dāng)前時間（自1970-01-01起經(jīng)歷的秒數(shù)、本秒中經(jīng)歷的納秒數(shù)）。xtime的初始值就是內(nèi)核啟動時從RTC讀出的。
在時鐘中斷處理程序更新jiffies_64的值后，便更新xtime的值。通過比較jiffies_64的當(dāng)前值與上一次的值（上面說到，差值可能大于1），決定xtime應(yīng)該更新多少。

系統(tǒng)調(diào)用gettimeofday（對應(yīng)庫函數(shù)time和gettimeofday）就是用來讀xtime變量的，從而讓用戶程序獲取系統(tǒng)時間。

統(tǒng)計系統(tǒng)負(fù)載
在時鐘中斷處理程序（多處理器系統(tǒng)下對應(yīng)的是全局時鐘）完成對上述jiffies_64和xtime的更新之后，接下來就會對系統(tǒng)負(fù)載進行統(tǒng)計。
所謂系統(tǒng)負(fù)載，是指系統(tǒng)中各個CPU的可執(zhí)行隊列中包含的進程數(shù)目。值為0表示對應(yīng)CPU上沒有可執(zhí)行的進程，CPU空閑；值為1表示對應(yīng)CPU被一個進程獨占，CPU占用率為100%；值大于1表示對應(yīng)CPU被多個進程共享，CPU占用率為100%。
現(xiàn)在，內(nèi)核要在中斷處理程序中統(tǒng)計系統(tǒng)負(fù)載，意味著內(nèi)核每隔一個tick要去查看一下在當(dāng)前時間點上各個CPU的可執(zhí)行隊列中的進程數(shù)目。實際上，孤立地看每個tick對應(yīng)的時間點上的CPU負(fù)載值并沒有太大意義，除非內(nèi)核把從系統(tǒng)啟動以來的所有負(fù)載值都記錄下來，然后再交由關(guān)心系統(tǒng)負(fù)載的用戶進程進行分析。但是這樣做需要花費大量的內(nèi)存空間，并不現(xiàn)實。所以，內(nèi)核最終保留了3個值：最近1分鐘、5分鐘、15分鐘的平均負(fù)載。每次中斷處理程序中獲取到的實時的負(fù)載值只對這3個值產(chǎn)生影響。

在linux系統(tǒng)中，通過top、uptime之類的命令就能看到這3個值，cat /proc/stat也能看到。

統(tǒng)計運行時間
在單處理器系統(tǒng)中，中斷處理程序完成上面的操作后，就到了這一步；在多處理器系統(tǒng)中，每個CPU上的本地時鐘中斷直接進入這一步。
統(tǒng)計運行時間實現(xiàn)起來非常簡單。在中斷處理函數(shù)中，內(nèi)核查看當(dāng)前CPU上正在運行的是哪個進程，然后就給該進程的運行時間增加1ms（一個時鐘周期），除非當(dāng)前進程是0號進程。只要當(dāng)前CPU上正在運行的不是0號進程，就給CPU的運行時間加1ms。因為0號進程是用來讓CPU空轉(zhuǎn)的進程，只在CPU的可執(zhí)行隊列中沒有進程時，才會被調(diào)度執(zhí)行。所以，0號進程正在運行，表明對應(yīng)的CPU空閑。
這樣的統(tǒng)計方法從局部看是很不準(zhǔn)確的，可能出現(xiàn)這樣的情況：進程A運行了0.99ms，然后切換到進程B。進程B只運行了0.01ms，然后中斷就來了。結(jié)果中斷處理程序在計算運行時間只把整個1ms都加到了B進程上。
但是從一段比較長的時間來看（比如幾十秒、幾分鐘），誤差并不會太大，并且就算有誤差也沒什么大問題（并不影響內(nèi)核的穩(wěn)定性，僅僅是展現(xiàn)不夠友好而已）。所以內(nèi)核使用的這種統(tǒng)計方式基本上可以說是非常簡單并且有效的。

在linux系統(tǒng)中，通過cat /proc/$pid/stat就能看到這里的統(tǒng)計值。能看到各個進程運行了多少時間，這個時間還分為用戶態(tài)下的運行時間和內(nèi)核態(tài)下的運行時間。
linux系統(tǒng)中的top命令能夠看到進程的CPU占用率，也是利用了這里的統(tǒng)計結(jié)果。當(dāng)然，top命令還做了很多事情：對所有進程的運行時間進行一遍掃描，然后sleep 1秒（或被用戶的按鍵打斷），然后再掃描一遍。計算在兩次掃描的間隔時間中，各個進程的運行時間都增加了多少，最后得出各個進程在這段時間內(nèi)的CPU占用率、以及總的CPU占用率。

除統(tǒng)計外，更新進程運行時間還有激活間隔定時器的作用。用戶程序通過settimer系統(tǒng)調(diào)用設(shè)置的定時器可以選擇多種定時策略：ITIMER_REAL（真正的時間）、ITIMER_VIRTUAL（進程在用戶態(tài)下運行的時間）、ITIMER_PROF（進程運行的時間，包括用戶態(tài)和內(nèi)核態(tài)）。后兩種定時器稱為間隔定時器。
在中斷處理程序進行進程運行時間統(tǒng)計時會更新進程的運行時間，于是間隔定時器可以在這里被觸發(fā)。如果條件滿足，內(nèi)核會發(fā)送SIGVTALARM或SIGPROF信號給當(dāng)前進程。（為什么只是當(dāng)前進程？因為之前1 個tick的時間將全部增加到當(dāng)前進程上，而其他進程不會得以增加。）

另外，隨著當(dāng)前進程運行時間的增加，當(dāng)前進程可能由于時間片被耗盡而觸發(fā)一次調(diào)度。也有可能因為運行時間達到限制而被內(nèi)核通過發(fā)送SIGKILL信號殺掉（通過ulimit -a命令可以看到“cpu time”這一限制，不過這項限制一般是“unlimited”）。

處理定時器
時鐘中斷處理程序完成上面的操作以后（多處理器系統(tǒng)下對應(yīng)的是本地時鐘），就觸發(fā)一次軟中斷（參見《linux內(nèi)核中斷處理淺析》），由對應(yīng)的軟中斷處理程序來處理定時器。
定時器使用的地方非常多，前面提到的settimer系統(tǒng)調(diào)用在選擇ITIMER_REAL策略時將設(shè)置一個定時器，alarm系統(tǒng)調(diào)用也用于設(shè)置一個類似的定時器。這兩個定時器在觸發(fā)時，內(nèi)核都會發(fā)送SIGALARM信號給定時的進程。另外，nanosleep系統(tǒng)調(diào)用（對應(yīng)庫函數(shù)sleep、usleep等）也使用定時器；select、poll、futex、等允許設(shè)置超時時間系統(tǒng)調(diào)用也使用定時器。這些定時器在觸發(fā)時，對應(yīng)的進程將被喚醒，并且退出系統(tǒng)調(diào)用。

為實現(xiàn)定時器，每個CPU都維護一個定時器隊列。進程在添加定時器時總是添加到正在運行該進程的那個CPU的定時器隊列上。定時器有兩個要素：什么時候觸發(fā)？觸發(fā)后干什么（比如發(fā)送XXX信號、喚醒進程、等等）？
定時器隊列并不是簡單的隊列，否則每個時鐘中斷到來時（多處理器系統(tǒng)下對應(yīng)的是本地時鐘），中斷處理程序都必須遍歷隊列中的所的定時器，以決定需要觸發(fā)其中的哪些。在定時器數(shù)目很多時，這是非常要命的事。
排序的話又如何呢？如果隊列中的定時器按觸發(fā)時間從早到晚排好序，則中斷處理程序只需要關(guān)心隊列頭的若干個觸發(fā)時間與當(dāng)前時間相同的定時器。這將最大限度的降低中斷處理程序?qū)Χ〞r器的處理時間。但是添加定時器時就麻煩了，必須花費一定的時間來尋找合適的位置（復(fù)雜度為O(logn)，二分法）。并且，從尋找到添加完成的過程必須與中斷處理程序處理定時器的過程互斥。添加定時器的時間長了，勢必影響到中斷處理程序。所以這樣的隊列也并不夠理想。
而linux內(nèi)核使用了一種比較巧妙的隊列結(jié)構(gòu)，很好的解決了添加/刪除/處理定時器時的效率問題。下面僅對定時器隊列模型做一些介紹。
linux內(nèi)核將定時器隊列設(shè)計為多個隊列，每個隊列的時間單位不一樣。就像自來水水表一樣，水表上有多個指針，每個指針表示著不同的刻度單位。假設(shè)水表上有1、10、100三個指針，每個1刻度代表一個tick。然后想象水表轉(zhuǎn)動的情景：1指針逐漸增加到9，然后變成0，同時10指針增加1。
添加定時器時，在0~9個tick之內(nèi)將要觸發(fā)的定時器被放在1指針的刻度盤上。隨著1指針的移動，指針指向的刻度上對應(yīng)定時器將被觸發(fā)；
在10~19個tick之內(nèi)將要觸發(fā)的定時器被放在10指針指向的下一個刻度上（在這10個tick之內(nèi)的定時器都放在同一個刻度上）。以此類推，在20~29個tick之內(nèi)將要觸發(fā)的定時器被放在10指針指向的下兩個刻度上……當(dāng)1指針發(fā)生進位時，10指針移動一個刻度。這個刻度上對應(yīng)的定時器將被放入到1指針的刻度盤上（注意，這些定時器的觸發(fā)時間跨越了10個tick）；
以此類推，在100~199個tick之內(nèi)將要觸發(fā)的定時器被放在100指針指向的下一個刻度上。并且當(dāng)10指針進位時，它們被重新放到10指針的刻度盤上……
可見，按照這樣的模型，添加定時器時，只需要計算一下該定時器應(yīng)該放在哪個刻度盤的哪個刻度上即可，復(fù)雜度為O(1)；而時鐘中斷處理程序每次也只需要處理1指針指向的一組定時器即可。然后移動指針，如果發(fā)生進位，則花費一些時間將10指針刻度盤上被指向的一組定時器重新分派到1指針的刻度盤上。10指針進位只也類似地將100指針刻度盤上被指向的一組定時器重新分派到10指針的刻度盤上。平均復(fù)雜度為O(1)。

一些想法
以前接觸過一些用戶態(tài)定時器線程的實現(xiàn)。調(diào)用者將一個定時器結(jié)構(gòu)放入定時器隊列中，由定時器線程在時間到來的時候調(diào)用定時器結(jié)構(gòu)中的回調(diào)函數(shù)。
定時器線程的實現(xiàn)通常有兩種思路：
1、定時線程sleep一小段時間（如1秒），然后處理定時器隊列中已到期的那些定時器（可以通過將定時器排序來優(yōu)化這一處理過程）。
這種方法實現(xiàn)起來非常簡單，調(diào)用者也只需要將定時器添加到定時器隊列即可。
但是效率并不高，定時器線程每隔一定時間輪詢一下定時器隊列，會造成一些不必要的開銷（因為很多時候并沒有定時器需要處理）。并且定時器精度不夠（取決于睡眠時間的長短），要提高精度只能縮短睡眠時間，從而又造成更大的輪詢開銷。
2、定時線程維護一個按觸發(fā)時間排序的定時器隊列，然后總是以當(dāng)前時間到第一個定時器觸發(fā)時間的間隔作為睡眠時間。
這種方法顯然更復(fù)雜一些。最麻煩的是，調(diào)用者添加新定時器的時候，如果新定時器比原有定時器的觸發(fā)時間都早，則需要打斷定時線程的睡眠，并且讓它重新開始一次更短的睡眠。
如果總是不斷的有觸發(fā)時間更早的定時器將定時線程打斷，會對性能有一定的影響。但是總的來說，這種方法避免了大量無用的輪詢，效率會更高一些。并且精度更高（取決于內(nèi)核的定時精度）。

對應(yīng)到linux內(nèi)核，目前對時鐘的處理是以類似第一種方式來實現(xiàn)的。簡單，但效率不高、精度不高。
那么今后linux內(nèi)核是否有可能改用類似第二種方式來處理時鐘呢？拭目以待……