Linux實(shí)時技術(shù)與典型實(shí)現(xiàn)分析－第 1 部分

本系列文章分兩部分，第 1 部分闡述了實(shí)時的概念、衡量實(shí)時性的指標(biāo)，詳細(xì)地分析了嵌入式系統(tǒng)對 Linux 實(shí)時性的需求以及 Linux 在實(shí)時性方面的不足，然后簡單地描述了三個著名的 Linux 實(shí)時實(shí)現(xiàn)，第 2 部分對一個典型的實(shí)時實(shí)現(xiàn)（Ingo's RT patch）做了詳盡的分析。
一、實(shí)時的概念

所謂實(shí)時，就是一個特定任務(wù)的執(zhí)行時間必須是確定的，可預(yù)測的，并且在任何情況下都能保證任務(wù)的時限（最大執(zhí)行時間限制）。實(shí)時又分軟實(shí)時和硬實(shí)時，所謂 軟實(shí)時，就是對任務(wù)執(zhí)行時限的要求不那么嚴(yán)苛，即使在一些情況下不能滿足時限要求，也不會對系統(tǒng)本身產(chǎn)生致命影響，例如，媒體播放系統(tǒng)就是軟實(shí)時的，它需 要系統(tǒng)能夠在1秒鐘播放24幀，但是即使在一些嚴(yán)重負(fù)載的情況下不能在1秒鐘內(nèi)處理24幀，也是可以接受的。所謂硬實(shí)時，就是對任務(wù)的執(zhí)行時限的要求非常 嚴(yán)格，無論在什么情況下，任務(wù)的執(zhí)行實(shí)現(xiàn)必須得到絕對保證，否則將產(chǎn)生災(zāi)難性后果，例如，飛行器自動駕駛和導(dǎo)航系統(tǒng)就是硬實(shí)時的，它必須要求系統(tǒng)能在限定 的時限內(nèi)完成特定的任務(wù)，否則將導(dǎo)致重大事故，如碰撞或爆炸等。

二、衡量實(shí)時性的指標(biāo)

那么，如何判斷一個系統(tǒng)是否是實(shí)時的呢？主要有以下兩個指標(biāo)：

1． 中斷延遲

中斷延遲就是從一個外部事件發(fā)生到相應(yīng)的中斷處理函數(shù)的第一條指令開始執(zhí)行所需要的時間。很多實(shí)時任務(wù)是靠中斷驅(qū)動的，而且中斷事件必須在限定的時限內(nèi)處理，否則將產(chǎn)生災(zāi)難性后果，因此中斷延遲對于實(shí)時系統(tǒng)來說，是一個非常重要的指標(biāo)。

2． 搶占延遲

有時也稱調(diào)度延遲，搶占延遲就是從一個外部事件發(fā)生到相應(yīng)的處理該事件的任務(wù)的第一條命令開始執(zhí)行的時間。大多數(shù)實(shí)時系統(tǒng)都是處理一些周期性的或非周期性 的重復(fù)事件，事件產(chǎn)生的頻度就確定了任務(wù)的執(zhí)行時限，因此每次事件發(fā)生時，相應(yīng)的處理任務(wù)必須及時響應(yīng)處理，否則將無法滿足時限。搶占延遲就反映了系統(tǒng)的 響應(yīng)及時程度。

如果以上兩個指標(biāo)是確定的，可預(yù)測的，那么就可以說系統(tǒng)是實(shí)時的。

三、影響系統(tǒng)實(shí)時性的因素

對系統(tǒng)實(shí)時性的影響因素既有硬件方面的，也有軟件方面的。

現(xiàn)代的高性能的硬件都使用了cache技術(shù)來彌補(bǔ)CPU和內(nèi)存間的性能差距，但是cache卻嚴(yán)重地影響著實(shí)時性，指令或數(shù)據(jù)在cache中的執(zhí)行時間和 指令或數(shù)據(jù)不在cache中的執(zhí)行時間差距是非常巨大的，可能差幾個數(shù)量級，因此為了保證執(zhí)行時間的確定性和可預(yù)測性，來滿足實(shí)時需要，一些系統(tǒng)就失效了 cache或使用沒有cache的CPU。

另一個硬件方面的影響因素就是虛存管理，對于多用戶多任務(wù)的操作系統(tǒng)，它確實(shí)非常有用，它使得系統(tǒng)能夠執(zhí)行比物理內(nèi)存更大的任務(wù)，而且各任務(wù)互不影響，完 全有自己的獨(dú)立的地址空間。但是虛存管理的缺頁機(jī)制嚴(yán)重地影響了任務(wù)執(zhí)行時間的可預(yù)測性和確定性，任務(wù)執(zhí)行時使用缺頁機(jī)制調(diào)入訪問的指令或數(shù)據(jù)和被執(zhí)行的 指令和數(shù)據(jù)已經(jīng)在內(nèi)存中需要的執(zhí)行時間的差距是非常大的。因此一些實(shí)時系統(tǒng)就不使用虛存技術(shù)，例如 Wind River的VxWorks。

在軟件方面，影響因素包括關(guān)中斷、不可搶占、一些O(n)的算法。

前面已經(jīng)提到，中斷延遲是衡量系統(tǒng)實(shí)時性的一個重要指標(biāo)。關(guān)中斷就導(dǎo)致了中斷無法被響應(yīng)，增加了中斷延遲。

前面提到的搶占延遲也是衡量系統(tǒng)實(shí)時性的重要指標(biāo)。如果發(fā)生實(shí)時事件時系統(tǒng)是不可搶占的，搶占延遲就會增加。

還有就是一些時間復(fù)雜度為O(n)的算法也影響了執(zhí)行時間的不確定性，例如任務(wù)調(diào)度算法，要想執(zhí)行實(shí)時任務(wù)必須進(jìn)行調(diào)度，如果調(diào)度算法的執(zhí)行時間取決于當(dāng) 前系統(tǒng)運(yùn)行的任務(wù)數(shù)，那么調(diào)度實(shí)時任務(wù)所花費(fèi)的時間就是不確定的，因為它是與系統(tǒng)運(yùn)行的任務(wù)數(shù)呈線性關(guān)系的函數(shù)，運(yùn)行的任務(wù)越多，時間就越長。

四、嵌入式系統(tǒng)需要實(shí)時Linux

Linux在設(shè)計之初沒有對實(shí)時性進(jìn)行任何考慮，因此非實(shí)時性絕非偶然。Linus考慮的是資源共享，吞吐率最大化。但是隨著Linux的快速發(fā)展，它的 應(yīng)用已經(jīng)遠(yuǎn)遠(yuǎn)超出了Linus自己的想象。Linux的開放性已經(jīng)對很多種架構(gòu)的支持使得它在嵌入式系統(tǒng)中得到了廣泛的應(yīng)用，但是許多嵌入式系統(tǒng)的實(shí)時性 要求使得Linux在嵌入式領(lǐng)域的應(yīng)用受到了一定的障礙，因此人們要求Linux需要實(shí)時性的呼聲越來越高。

Linux的開放性和低成本是實(shí)時Linux發(fā)展的優(yōu)勢，越來越多的研究機(jī)構(gòu)和商業(yè)團(tuán)體開展了實(shí)時Linux的研究與開發(fā)，其中最著名的就是FSMLab的Rtlinux和TimeSys Linux。還有一個就是Ingo's RT patch。

五、標(biāo)準(zhǔn)Linux內(nèi)核制約實(shí)時性的因素

標(biāo)準(zhǔn)Linux有幾個機(jī)制嚴(yán)重地影響了實(shí)時性。

1．內(nèi)核不可搶占

在Linux 2.4和以前的版本，內(nèi)核是不可搶占的，也就是說，如果當(dāng)前任務(wù)運(yùn)行在內(nèi)核態(tài)，即使當(dāng)前有更緊急的任務(wù)需要運(yùn)行，當(dāng)前任務(wù)也不能被搶占。因此那個緊急任務(wù) 必須等到當(dāng)前任務(wù)執(zhí)行完內(nèi)核態(tài)的操作返回用戶態(tài)后或當(dāng)前任務(wù)因需要等待某些條件滿足而主動讓出CPU才能被考慮執(zhí)行，這很明顯嚴(yán)重影響搶占延遲。

在Linux 2.6中，內(nèi)核已經(jīng)可以搶占，因而實(shí)時性得到了加強(qiáng)。但是內(nèi)核中仍有大量的不可搶占區(qū)域， 如由自旋鎖 （spinlock）保護(hù)的臨界區(qū)，以及一些顯式使用preempt_disable失效搶占的臨界區(qū)。

2．中斷關(guān)閉

Linux在一些同步操作中使用了中斷關(guān)閉指令，中斷關(guān)閉將增大中斷延遲，降低系統(tǒng)的實(shí)時性。

3．自旋鎖（spinlock）

自旋鎖是在可搶占內(nèi)核和SMP情況下對共享資源的一種同步機(jī)制，一般地一個任務(wù)對共享資源的訪問是非常短暫的，如果兩個任務(wù)競爭一個共享的資源時，沒有得 到資源的任務(wù)將自旋以等待另一個任務(wù)使用完該共享資源。這種鎖機(jī)制是非常高效的，但是在保持自旋鎖期間將失效搶占，這意味著搶占延遲將增加。在 2.6內(nèi)核中，自旋鎖的使用非常普遍，有的甚至對整個一個數(shù)組或鏈表的便歷過程都使用自旋鎖。因此搶占延遲非常不確定。

4．大內(nèi)核鎖

由于歷史原因，內(nèi)核一直保留有幾個大內(nèi)核鎖，大內(nèi)核鎖實(shí)質(zhì)上也是一種自旋鎖，但是它與一般的自旋鎖的區(qū)別是，它是用于同步整個內(nèi)核的，而且一般該鎖的保持時間較長，也即搶占失效時間長，因此它的使用將嚴(yán)重地影響搶占延遲。

5．中斷總是最高優(yōu)先級的

在Linux中，中斷（包括軟中斷）是最高優(yōu)先級的，不論在任何時刻，只要產(chǎn)生中斷事件，內(nèi)核將立即執(zhí)行相應(yīng)的中斷處理函數(shù)以及軟中斷，等到所有掛起的中 斷和軟中斷處理完畢有才執(zhí)行正常的任務(wù)。因此在標(biāo)準(zhǔn)的Linux系統(tǒng)上，實(shí)時任務(wù)根本不可能得到實(shí)時性保證。例如，假設(shè)在一個標(biāo)準(zhǔn)Linux系統(tǒng)上運(yùn)行了 一個實(shí)時任務(wù)（即使用了SCHED_FIFO調(diào)度策略并且設(shè)定了最高的實(shí)時優(yōu)先級），但是該系統(tǒng)有非常繁重的網(wǎng)絡(luò)負(fù)載和I/O負(fù)載，那么系統(tǒng)可能一直處在 中斷處理狀態(tài)而沒有機(jī)會運(yùn)行任何任務(wù)，這樣實(shí)時任務(wù)將永遠(yuǎn)無法運(yùn)行，搶占延遲將是無窮大。因此，如果這種機(jī)制不改，實(shí)時Linux將永遠(yuǎn)無法實(shí)現(xiàn)。

6．調(diào)度算法和調(diào)度點(diǎn)

在Linux 2.4和以前的版本，調(diào)度器的時間復(fù)雜度是O(n)的，而且在SMP的情況下性能低，因為所有的CPU共享一個任務(wù)鏈表，任何時刻只能有一個調(diào)度器運(yùn)行。因此，搶占延遲很大程度上以來于當(dāng)前系統(tǒng)的任務(wù)數(shù)，具有非常大的不確定性和不可預(yù)測性。

在2.6內(nèi)核中引入的O(1)調(diào)度器很好地解決了這些問題。

此外，即使內(nèi)核是可搶占的，也不是在任何地方可以發(fā)生調(diào)度，例如在中斷上下文，一個中斷處理函數(shù)可能喚醒了某一高優(yōu)先級進(jìn)程，但是該進(jìn)程并不能立即運(yùn)行， 因為在中斷上下文不能發(fā)生調(diào)度，中斷處理完了之后內(nèi)核還要執(zhí)行掛起的軟中斷，等它們處理完之后才有機(jī)會調(diào)度剛才喚醒的進(jìn)程。在標(biāo)準(zhǔn)Linux內(nèi)核中，調(diào)度 點(diǎn)（有意安排的執(zhí)行任務(wù)調(diào)度的點(diǎn)）并不多，對2.4和2.6內(nèi)核測試的結(jié)果表明，缺乏調(diào)度點(diǎn)是影響Linux實(shí)時性的一個因素。

六、現(xiàn)存的Linux實(shí)時技術(shù)

現(xiàn)有的著名的實(shí)時Linux實(shí)現(xiàn)包括RTLinux、RTAI和TimeSys。

1. RTLinux

RTLinux是著名的研究機(jī)構(gòu)FSMLab研發(fā)的一款實(shí)時Linux，既有GPL和Free版本，又有商業(yè)版本。它使用的實(shí)現(xiàn)方式是子內(nèi)核方法，即把 Linux內(nèi)核作為一個新實(shí)現(xiàn)的子內(nèi)核的閑暇任務(wù)，子內(nèi)核位于Linux內(nèi)核和硬件抽象層之間，實(shí)時任務(wù)運(yùn)行于子內(nèi)核之上，只有當(dāng)沒有實(shí)時任務(wù)需要運(yùn)行 時，Linux內(nèi)核才有機(jī)會運(yùn)行。

特別是對中斷的管理，它采用了一種軟件的方式來處理Linux內(nèi)的中斷關(guān)閉，當(dāng)Linux內(nèi)核關(guān)閉中斷后，并不是真正地屏蔽了硬件中斷，相反，它使用了一 個變量來保存Linux內(nèi)核的中斷標(biāo)志位，Linux內(nèi)核的開關(guān)中斷只是影響了該變量，硬件的中斷由子內(nèi)核來接管，當(dāng)Linux內(nèi)核關(guān)閉了中斷，子內(nèi)核仍 然可以響應(yīng)任何中斷，只是如果子內(nèi)核不需要處理的中斷才交給Linux內(nèi)核來處理，如果Linux內(nèi)核關(guān)閉了中斷，子內(nèi)核將記錄該中斷并在 Linux內(nèi)核打開中斷后提交它處理。

在RTLinux里，每一個實(shí)時任務(wù)都是內(nèi)核線程，運(yùn)行在內(nèi)核空間，RTLinux提供了一套專門的機(jī)制來在實(shí)時任務(wù)和普通的Linux任務(wù)之間進(jìn)行進(jìn)程間通信。

這種子內(nèi)核的實(shí)現(xiàn)提供了非常好的實(shí)時性，完全是一個硬實(shí)時的Linux。

2．TimeSys Linux

Timesys很早就發(fā)布了實(shí)時Linux的商業(yè)版以及GPL版，它采用了與RTLinux完全不同的實(shí)現(xiàn)方式。前面已經(jīng)提到了標(biāo)準(zhǔn)Linux內(nèi)核的實(shí)時 限制，TimeSys Linux就是通過消除這些限制來達(dá)到實(shí)時性的。它把中斷(IRQ)和軟中斷(softIRQ)全部線程化并賦予不同的優(yōu)先級，實(shí)時任務(wù)可以有比中斷線程 更高的優(yōu)先級，它使用Mutex替代spinlock來使得自旋鎖完全可搶占。它也對調(diào)度器做了優(yōu)化使它是O(1)的（注：因為使用2.4內(nèi)核）。由于中 斷已經(jīng)線程化了，很多中斷關(guān)閉就沒必要了，因而消除了很多中斷關(guān)閉區(qū)域。它還實(shí)現(xiàn)了對CPU和網(wǎng)絡(luò)資源的預(yù)定來改善實(shí)時性。后面將說的Ingo's RT patch就是借鑒這些思路來實(shí)現(xiàn)實(shí)時性的。

這種實(shí)現(xiàn)方式保持了全部的Linux應(yīng)用編程模式，實(shí)時應(yīng)用和普通的應(yīng)用采用同樣的編程方式，使用同樣的API，只是實(shí)時任務(wù)需要明確指定自己的優(yōu)先級與 調(diào)度策略。但是這種實(shí)現(xiàn)方式也有弊病，那就是它滿足硬實(shí)時性有一定的困難，因為即使中斷關(guān)閉和不可搶占區(qū)大為減少，但是還是存在，一些中斷還是無法線程 化，如時鐘中斷等。

3. Ingo's RT patch

Ingo's RT patch是又一個Linux實(shí)時實(shí)現(xiàn)，它采用了與TimeSys完全相同的技術(shù)路線，而且有一些實(shí)現(xiàn)是基于TimeSys的源代碼的，如IRQ和 softirq線程化。但是它與前面提到的兩個實(shí)時實(shí)現(xiàn)不同的地方是，它可能并入到標(biāo)準(zhǔn)Linux內(nèi)核（作者預(yù)見，可能并入到2.6.13或以后的某個版 本中）。在最新的標(biāo)準(zhǔn)內(nèi)核Linux 2.6.11中，已經(jīng)出現(xiàn)了這個補(bǔ)丁曾經(jīng)包含的部分代碼，如IRQ子系統(tǒng)，那是IRQ和softirq線程化的基礎(chǔ)，已經(jīng)隱含了一些線程化的代碼，如自愿 搶占代碼，那是2.4的低延遲補(bǔ)?。╨ow latency patch）和Ingo的一些自愿搶占代碼以及Robert Love的鎖分解補(bǔ)丁的集合，還有可搶占的大內(nèi)核鎖。

本系列第 2 部分將專門對Ingo's RT patch進(jìn)行詳細(xì)的解讀。