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

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

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

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

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

1． 中斷延遲

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

2． 搶占延遲

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

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

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

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

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

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

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

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

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

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

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

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

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

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

標(biāo)準(zhǔn)Linux有幾個(gè)機(jī)制嚴(yán)重地影響了實(shí)時(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ù)也不能被搶占。因此那個(gè)緊急任務(wù) 必須等到當(dāng)前任務(wù)執(zhí)行完內(nèi)核態(tài)的操作返回用戶態(tài)后或當(dāng)前任務(wù)因需要等待某些條件滿足而主動(dòng)讓出CPU才能被考慮執(zhí)行，這很明顯嚴(yán)重影響搶占延遲。

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

2．中斷關(guān)閉

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

3．自旋鎖（spinlock）

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

4．大內(nèi)核鎖

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

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

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

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

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

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

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

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

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

1. RTLinux

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

特別是對(duì)中斷的管理，它采用了一種軟件的方式來處理Linux內(nèi)的中斷關(guān)閉，當(dāng)Linux內(nèi)核關(guān)閉中斷后，并不是真正地屏蔽了硬件中斷，相反，它使用了一 個(gè)變量來保存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里，每一個(gè)實(shí)時(shí)任務(wù)都是內(nèi)核線程，運(yùn)行在內(nèi)核空間，RTLinux提供了一套專門的機(jī)制來在實(shí)時(shí)任務(wù)和普通的Linux任務(wù)之間進(jìn)行進(jìn)程間通信。

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

2．TimeSys Linux

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

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

3. Ingo's RT patch

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

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