1、簡介

隨著微處理器技術(shù)的發(fā)展,嵌入式系統(tǒng)已經(jīng)成為計(jì)算機(jī)應(yīng)用領(lǐng)域的一個(gè)重要的組成部分。Linux雖然為分時(shí)操作系統(tǒng)，但由于其功能強(qiáng)大、源代碼開放以及可移植性強(qiáng)等優(yōu)勢，已成為日益流行的嵌入式實(shí)時(shí)操作系統(tǒng)的解決方案，然而，在實(shí)時(shí)方面它還不能很好地滿足實(shí)時(shí)系統(tǒng)方面的需要，其本身僅僅提供了一些實(shí)時(shí)處理的支持。為使Linux滿足實(shí)時(shí)應(yīng)用的要求,常用的方法是通過對Linux的內(nèi)核進(jìn)行裁減和修改,使其能夠滿足實(shí)時(shí)性的要求。目前,我們根據(jù)實(shí)際需要對于Linux采用以下方法進(jìn)行改進(jìn)。

2、實(shí)現(xiàn)低延遲

使用兩種方法來實(shí)現(xiàn)低延遲：一種就是鎖分解，即把大循環(huán)中保持的鎖分解為每一輪循環(huán)中都獲得鎖和釋放鎖，典型的代碼結(jié)構(gòu)示例如下：

鎖分解前：

spin_lock(&x_lock);

for (…) {some operations;

…}

spin_unlock(&x_lock);

鎖分解后：

for (…) { spin_lock(&x_lock);

some operations;

…

spin_unlock(&x_lock);}

另一種是增加搶占點(diǎn)，即自愿被搶占。增加搶占點(diǎn)之后：

/* Do the write .. */

for (;;) {

size_t size = count;

if (size > chunk)

size = chunk;

ret = -EFAULT;

if (copy_from_user(tty->write_buf, buf, size))

break;

lock_kernel();

ret = write(tty, file, tty->write_buf, size);

unlock_kernel();

if (ret <= 0)

break;

written += ret;

buf += ret;

count -= ret;

if (!count)

break;

ret = -ERESTARTSYS;

if (signal_pending(current))

break;

cond_resched();

}

語句cond_resched()將判斷是否有進(jìn)程需要搶占當(dāng)前進(jìn)程，如果是將立即發(fā)生調(diào)度，這就是增加的搶占點(diǎn)，它支持四種搶占模式：

(1).No Forced Preemption (Server)，這種模式等同于沒有使能搶占選項(xiàng)的標(biāo)準(zhǔn)內(nèi)核，主要適用于科學(xué)計(jì)算等服務(wù)器環(huán)境。

(2).Voluntary Kernel Preemption (Desktop)，這種模式使能了自愿搶占，但仍然失效搶占內(nèi)核選項(xiàng)，它通過增加搶占點(diǎn)縮減了搶占延遲，因此適用于一些需要較好的響應(yīng)性的環(huán)境，如桌面環(huán)境，當(dāng)然這種好的響應(yīng)性是以犧牲一些吞吐率為代價(jià)的。

(3).Preemptible Kernel (Low-Latency Desktop)，這種模式既包含了自愿搶占，又使能了可搶占內(nèi)核選項(xiàng)，因此有很好的響應(yīng)延遲，實(shí)際上在一定程度上已經(jīng)達(dá)到了軟實(shí)時(shí)性。它主要適用于桌面和一些嵌入式系統(tǒng)，但是吞吐率比模式2更低。

(4).Complete Preemption (Real-Time)，這種模式使能了所有實(shí)時(shí)功能，因此完全能夠滿足軟實(shí)時(shí)需求，它適用于延遲要求為100微秒或稍低的實(shí)時(shí)系統(tǒng)。

實(shí)現(xiàn)實(shí)時(shí)是以犧牲系統(tǒng)的吞吐率為代價(jià)的，因此實(shí)時(shí)性越好，系統(tǒng)吞吐率就越低。

3、中斷線程化

中斷線程化是實(shí)現(xiàn)Linux實(shí)時(shí)性的一個(gè)重要步驟，在Linux標(biāo)準(zhǔn)內(nèi)核中，中斷是最高優(yōu)先級的執(zhí)行單元，不管內(nèi)核當(dāng)時(shí)處理什么，只要有中斷事件，系統(tǒng)將立即響應(yīng)該事件并執(zhí)行相應(yīng)的中斷處理代碼，除非當(dāng)時(shí)中斷關(guān)閉。因此，如果系統(tǒng)有嚴(yán)重的網(wǎng)絡(luò)或I/O負(fù)載，中斷將非常頻繁，后發(fā)生的實(shí)時(shí)任務(wù)將很難有機(jī)會運(yùn)行，也就是說，毫無實(shí)時(shí)性可言。中斷線程化之后，中斷將作為內(nèi)核線程運(yùn)行而且賦予不同的實(shí)時(shí)優(yōu)先級，實(shí)時(shí)任務(wù)可以有比中斷線程更高的優(yōu)先級，這樣，實(shí)時(shí)任務(wù)就可以作為最高優(yōu)先級的執(zhí)行單元來運(yùn)行，即使在嚴(yán)重負(fù)載下仍有實(shí)時(shí)性保證。

中斷線程化的另一個(gè)重要原因是spinlock被mutex取代。中斷處理代碼中大量地使用了spinlock，當(dāng)spinlock被mutex取代之后，中斷處理代碼就有可能因?yàn)榈貌坏芥i而需要被掛到等待隊(duì)列上，但是只有可調(diào)度的進(jìn)程才可以這么做，如果中斷處理代碼仍然使用原來的 spinlock，則spinlock取代mutex的努力將大打折扣，因此為了滿足這一要求，中斷必須被線程化，包括IRQ和softirq。

中斷線程化的實(shí)現(xiàn)方法是：對于IRQ，在內(nèi)核初始化階段init(該函數(shù)在內(nèi)核源碼樹的文件init/main.c中定義)調(diào)用 init_hardirqs(該函數(shù)在內(nèi)核源碼樹的文件kernel/irq/manage.c中定義)來為每一個(gè)IRQ創(chuàng)建一個(gè)內(nèi)核線程，IRQ號為0 的中斷賦予實(shí)時(shí)優(yōu)先級49，IRQ號為1的賦予實(shí)時(shí)優(yōu)先級48，依次類推直到25，因此任何IRQ線程的最低實(shí)時(shí)優(yōu)先級為25。原來的do_IRQ被分解成兩部分，架構(gòu)相關(guān)的放在類似于arch/*/kernel/irq.c的文件中，名稱仍然為do_IRQ，而架構(gòu)獨(dú)立的部分被放在IRQ子系統(tǒng)的位置 kernel/irq/handle.c中，名稱為_do_IRQ。當(dāng)發(fā)生中斷時(shí)，CPU將執(zhí)行do_IRQ來處理相應(yīng)的中斷，do_IRQ將做了必要的架構(gòu)相關(guān)的處理后調(diào)用_do_IRQ。函數(shù)_do_IRQ將判斷該中斷是否已經(jīng)被線程化(如果中斷描述符的狀態(tài)字段不包含SA_NODELAY標(biāo)志說明中斷被線程化了)，如果是將喚醒相應(yīng)的處理線程，否則將直接調(diào)用handle_IRQ_event(在IRQ子系統(tǒng)位置的kernel/irq /handle.c文件中)來處理。對于已經(jīng)線程化的情況，中斷處理線程被喚醒并開始運(yùn)行后，將調(diào)用do_hardirq(在源碼樹的IRQ子系統(tǒng)位置的文件kernel/irq/manage.c中定義)來處理相應(yīng)的中斷，該函數(shù)將判斷是否有中斷需要被處理(中斷描述符的狀態(tài)標(biāo)志 IRQ_INPROGRESS)，如果有就調(diào)用handle_IRQ_event來處理。handle_IRQ_event將直接調(diào)用相應(yīng)的中斷處理句柄來完成中斷處理。

如果某個(gè)中斷需要被實(shí)時(shí)處理，它可以用SA_NODELAY標(biāo)志來聲明自己非線程化，例如：系統(tǒng)的時(shí)鐘中斷就是，因?yàn)樗挥脕砭S護(hù)系統(tǒng)時(shí)間以及定時(shí)器等，所以不應(yīng)當(dāng)被線程化。

static struct irqaction irq0=

{ timer_interrupt, SA_INTERRUPT | SA_NODELAY, CPU_MASK_NONE, "timer", NULL, NULL};

這是在靜態(tài)聲明時(shí)指定不要線程化，也可以在調(diào)用request_irq時(shí)指定，如：

request_irq (HIGHWIRE_SMI_IRQ,highwire_smi_interrupt,SA_NODELAY, "System Management Switch", NULL))

對于softirq，標(biāo)準(zhǔn)Linux內(nèi)核已經(jīng)使用內(nèi)核線程的方式來處理，為了使其易于被搶占，改進(jìn)實(shí)時(shí)性，具體的修改包括：把ksoftirqd的優(yōu)先級設(shè)置為nice值為-10，即它的優(yōu)先級高于普通的用戶態(tài)進(jìn)程和內(nèi)核態(tài)線程，但它不是實(shí)時(shí)線程，因此這樣一來softirq對實(shí)時(shí)性的影響將顯著減小。在處理軟中斷期間，搶占是使能的，這使得實(shí)時(shí)性更進(jìn)一步地增強(qiáng)。在處理軟中斷的函數(shù)_do_softirq中，每次處理完一個(gè)待處理的軟中斷后，都將調(diào)用cond_resched_all()，這顯著地增加了調(diào)度點(diǎn)數(shù)，提高了整個(gè)系統(tǒng)的實(shí)時(shí)性。[!--empirenews.page--]

4、spinlock轉(zhuǎn)換成mutex

spinlock是一個(gè)高效的共享資源同步機(jī)制，在SMP(對稱多處理器Symmetric Multiple Proocessors)的情況下，它用于保護(hù)共享資源，如全局的數(shù)據(jù)結(jié)構(gòu)或一個(gè)只能獨(dú)占的硬件資源。但是spinlock保持期間將使搶占失效，用 spinlock保護(hù)的區(qū)域稱為臨界區(qū)(Critical Section)，在內(nèi)核中大量地使用了spinlock，有大量的臨界區(qū)存在，因此它們將嚴(yán)重地影響著系統(tǒng)的實(shí)時(shí)性。為此使用mutex來替換 spinlock，它的意圖是讓spinlock可搶占，但是可搶占后將產(chǎn)生很多后續(xù)影響。

Spinlock失效搶占的目的是避免死鎖。Spinlock如果可搶占了，一個(gè)spinlock的競爭者將可能搶占該spinlock的保持者來運(yùn)行，但是由于得不到spinlock將自旋在那里，如果競爭者的優(yōu)先級高于保持者的優(yōu)先級，將形成一種死鎖的局面，因?yàn)楸３终邿o法得到運(yùn)行而永遠(yuǎn)不能釋放spinlock，而競爭者由于不能得到一個(gè)不可能釋放的spinlock而永遠(yuǎn)自旋在那里。

由于中斷處理函數(shù)也可以使用spinlock，如果它使用的spinlock已經(jīng)被一個(gè)進(jìn)程保持，中斷處理函數(shù)將無法繼續(xù)進(jìn)行，從而形成死鎖，這樣的spinlock在使用時(shí)應(yīng)當(dāng)中斷失效來避免這種死鎖的情況發(fā)生。標(biāo)準(zhǔn)linux內(nèi)核就是這么做的，中斷線程化之后，中斷失效就沒有必要，因?yàn)橛龅竭@種狀況后，中斷線程將掛在等待隊(duì)列上并放棄CPU讓別的線程或進(jìn)程來運(yùn)行。

等待隊(duì)列就是解決這種死鎖僵局的方法，讓每個(gè)spinlock都有一個(gè)等待隊(duì)列，該等待隊(duì)列是按進(jìn)程或線程的優(yōu)先級排隊(duì)的。如果一個(gè)進(jìn)程或線程競爭的spinlock已經(jīng)被另一個(gè)線程保持，它將把自己掛在該spinlock的優(yōu)先級化的等待隊(duì)列上，然后發(fā)生調(diào)度把CPU讓給別的進(jìn)程或線程。

5、優(yōu)先級繼承和死鎖檢測

spinlock被mutex化后會產(chǎn)生優(yōu)先級逆轉(zhuǎn)(Priority Inversion)現(xiàn)象。所謂優(yōu)先級逆轉(zhuǎn)，就是優(yōu)先級高的進(jìn)程由于優(yōu)先級低的進(jìn)程保持了競爭資源被迫等待，而讓中間優(yōu)先級的進(jìn)程運(yùn)行，優(yōu)先級逆轉(zhuǎn)將導(dǎo)致高優(yōu)先級進(jìn)程的搶占延遲增大，中間優(yōu)先級的進(jìn)程的執(zhí)行時(shí)間的不確定性導(dǎo)致了高優(yōu)先級進(jìn)程搶占延遲的不確定性，因此為了保證實(shí)時(shí)性，必須消除優(yōu)先級逆轉(zhuǎn)現(xiàn)象。

優(yōu)先級繼承協(xié)議(Priority Inheritance Protocol)和優(yōu)先級頂棚協(xié)議(Priority Ceiling Protocol)就是專門針對優(yōu)先級逆轉(zhuǎn)問題提出的解決辦法。

所謂優(yōu)先級繼承，就是spinlock的保持者將繼承高優(yōu)先級的競爭者進(jìn)程的優(yōu)先級，從而能先于中間優(yōu)先級進(jìn)程運(yùn)行，盡可能快地釋放鎖，這樣高優(yōu)先級進(jìn)程就能很快得到競爭的spinlock，使得搶占延遲更確定，更短。

所謂優(yōu)先級頂棚，就是根據(jù)靜態(tài)分析確定一個(gè)spinlock的可能擁有者的最高優(yōu)先級，然后把spinlock的優(yōu)先級頂棚設(shè)置為該確定的值，每次當(dāng)進(jìn)程獲得該spinlock后，就將該進(jìn)程的優(yōu)先級設(shè)置為spinlock的優(yōu)先級頂棚值。

Spinlock被mutex化后引入的另一個(gè)問題就是死鎖，典型的死鎖有兩種：

一種為自鎖，即一個(gè)spinlock保持者試圖獲得它已經(jīng)保持的鎖，很顯然，這會導(dǎo)致該進(jìn)程無法運(yùn)行而死鎖。另一種為非順序鎖而導(dǎo)致的，即進(jìn)程P1 已經(jīng)保持了spinlock LOCKA但是要獲得進(jìn)程P2已經(jīng)保持的spinlock LOCKB，而進(jìn)程P2要獲得進(jìn)程P1已經(jīng)保持的spinlock LOCKA，這樣進(jìn)程P1和P2都將因?yàn)樾枰玫綄Ψ綋碛械牡肋h(yuǎn)不可能釋放的spinlock而死鎖。對這兩種情況都要進(jìn)行檢測，一旦發(fā)生這種死鎖，內(nèi)核將輸出死鎖執(zhí)行路徑并panic。

6、大內(nèi)核鎖可搶占

大內(nèi)核鎖(BKL---Big Kernel Lock)實(shí)質(zhì)上也是spinlock，只是它一般用于保護(hù)整個(gè)內(nèi)核，該鎖的保持時(shí)間比較長，因此它對整個(gè)系統(tǒng)的實(shí)時(shí)性影響是非常大的，大內(nèi)核鎖使用了 semaphore來實(shí)現(xiàn)，如果內(nèi)核配置為前面三種搶占模式，struct semaphore是架構(gòu)相關(guān)的，如對于x86，結(jié)構(gòu)定義如下：

struct semaphore {

atomic_t count;

int sleepers;

wait_queue_head_t wait;

};

但對于第四種搶占模式，其結(jié)構(gòu)為：

struct semaphore {

atomic_t count;

struct rt_mutex lock;

};

注意新的spinlock定義也包含字段struct rt_mutex lock，因此可搶占大內(nèi)核鎖和新的spinlock共用了低層的處理代碼。使用semaphore之后，大內(nèi)核鎖就可搶占了。

7、結(jié)論

Linux實(shí)時(shí)性能的逐步完善，必將大大促進(jìn)嵌入式Linux在工業(yè)控制、后PC時(shí)代信息電器等領(lǐng)域的廣泛應(yīng)用，應(yīng)用的需要也會進(jìn)一步促進(jìn)大量新型實(shí)時(shí)算法的出現(xiàn)。通過對Linux的改動，就可以開發(fā)出一種可靠的且廉價(jià)的硬實(shí)時(shí)操作系統(tǒng)，具有很好的發(fā)展和應(yīng)用前景。本文作者的創(chuàng)新點(diǎn)：通過改進(jìn)延遲，優(yōu)先級繼承并增加搶占機(jī)制，改善了系統(tǒng)的實(shí)時(shí)性，為嵌入式系統(tǒng)開發(fā)打下了基礎(chǔ)。

參考文獻(xiàn)：

[1] 趙炯.Linux內(nèi)核完全注釋[M].北京：機(jī)械工業(yè)出版社 2004.9

[2] 王新政,程小輝,周華茂. 實(shí)時(shí)操作系統(tǒng)任務(wù)調(diào)度策略的研究與設(shè)計(jì)[J]. 微計(jì)算機(jī)信息,2007,11:57-59.

[3] 李善平,劉文峰,王煥龍,等. Linux 與嵌入式系統(tǒng)[M].北京:

清華大學(xué)出版社,2002

[4] 曹計(jì)昌,余雋. 關(guān)于提高Linux 核心實(shí)時(shí)處理能力的討論[J ].計(jì)算機(jī)應(yīng)用,2001 ,21 (1) :75 - 78.

[5] 鄒思軼. 嵌入式Linux 設(shè)計(jì)與應(yīng)用[M] . 北京:清華大學(xué)出版社,1999.