嵌入式Linux操作系統實(shí)時(shí)性的分析

一、引言

Linux本身為分時(shí)操作系統，其系統目標為較好的平均響應時(shí)間和較高的吞吐量，而實(shí)時(shí) 系統則主要考慮任務(wù)的按時(shí)完成、盡量減少進(jìn)程運行的不可預測性等。但與商業(yè)嵌入式操作系統相比Linux遵循GPL，具有源代碼開(kāi)放、定制方便、支持廣泛的計算機硬件等優(yōu)點(diǎn)，所以，近年來(lái)嵌入式Linux成為嵌入式系統方向上的一個(gè)研究熱點(diǎn)。本文首先分析了實(shí)時(shí)系統的特點(diǎn)和Linux內核在實(shí)時(shí)應用方面的不足，然后針對影響操作系統實(shí)時(shí)性能的若干方面進(jìn)行研究，提出解決方案，最后總結全文。

二、實(shí)時(shí)系統的分類(lèi)

實(shí)時(shí)系統最重要的特點(diǎn)就是實(shí)時(shí)性，即系統的正確性不僅僅依賴(lài)于計算的邏輯結果的正確性，還取決于輸出結果時(shí)間的及時(shí)性。從這個(gè)角度看，實(shí)時(shí)系統是“一個(gè)能夠在指定或者確定的時(shí)間內完成系統功能和對外部環(huán)境做出響應的系統”。按對實(shí)時(shí)性能要求的程度，實(shí)時(shí)系統可分為兩類(lèi)：

(1) 硬實(shí)時(shí)系統：要求可確定性強，具有明確的實(shí)時(shí)約束，在某個(gè)限定的時(shí)刻之前不能完成任務(wù)將造成災難性的后果。

(2) 軟實(shí)時(shí)系統：也對時(shí)間敏感，但偶爾發(fā)生不能滿(mǎn)足嚴格實(shí)時(shí)要求的情況也是允許的。

三、Linux在實(shí)時(shí)方面存在的不足

Linux雖然符合POSIX1003.1b關(guān)于實(shí)時(shí)擴展部分的標準，例如：支持SCHED_FIFO和SCHED_RR實(shí)時(shí)調度策略，鎖內存機制(memorylocking)，實(shí)時(shí)信號等功能，但是由于其最初的設計目標為通用分時(shí)操作系統，因此作為一個(gè)實(shí)時(shí)操作系統，Linux仍然存在如下缺陷：

(1) Linux的內核本身是非搶占的。Linux下分用戶(hù)態(tài)和核心態(tài)兩種模式，當進(jìn)程運行在用戶(hù)態(tài)時(shí)，可被優(yōu)先級更高的進(jìn)程搶占，但當它進(jìn)入核心態(tài)時(shí)，其他用戶(hù)態(tài)進(jìn)程優(yōu)先級再高也不能搶占它。

(2) Linux雖然給實(shí)時(shí)進(jìn)程提供了較高的優(yōu)先級，但是沒(méi)有加入時(shí)間限制。例如：完成的最后期限、應在多長(cháng)時(shí)間內完成、執行周期等等。同時(shí)，其他大量的非實(shí)時(shí)進(jìn)程也可能對實(shí)時(shí)進(jìn)程造成阻塞，無(wú)法確保實(shí)時(shí)進(jìn)程的響應時(shí)間。

(3) 時(shí)鐘粒度粗糙。時(shí)鐘管理是操作系統的脈搏，任務(wù)的執行和中止在很多情況下都是由時(shí)鐘直接或間接喚起的，它還是進(jìn)程調度的重要依據。Linux的周期模式定時(shí)器頻率僅為100Hz，遠不能滿(mǎn)足實(shí)時(shí)應用的要求。

四、改進(jìn)內核實(shí)時(shí)性的分析與研究

從中斷軟件模擬、可搶占式內核體系結構、實(shí)時(shí)任務(wù)的調度策略這三個(gè)方面對嵌入式Linux內核進(jìn)行研究，并給出了相應的提高實(shí)時(shí)性的方法。

1. 響應時(shí)間的分析及解決方法

任務(wù)的響應時(shí)間被定義為一個(gè)事件的發(fā)生和任務(wù)響應這一事件開(kāi)始執行之間的間隔時(shí)間，通常有以下幾個(gè)因素影響任務(wù)的響應時(shí)間。

(1) 中斷分配時(shí)間IDT（interruptdispatchtime）：當一個(gè)中斷產(chǎn)生時(shí)，在調用中斷處理程序占用CPU以前，操作系統用來(lái)保存所有的寄存器中的內容和系統中其他的關(guān)于這一任務(wù)狀態(tài)的時(shí)間。

(2) 中斷服務(wù)時(shí)間：IST（interruptservicetime）：中斷服務(wù)程序用來(lái)從硬件設備讀取信息或從操作系統收集信息所用的時(shí)間。

(3) 內核搶占時(shí)間KPT（kernelpreemptiontime）：在操作系統意欲搶占當前進(jìn)程與搶占實(shí)際上發(fā)生之間的時(shí)間間隔。

(4) 調度延遲SD（scheduledelay）：調度程序用來(lái)調度另一個(gè)線(xiàn)程投入運行的時(shí)間。

(5) 進(jìn)程切換時(shí)間CST（contestswitchingtime）：當前線(xiàn)程用來(lái)保存寄存器和系統狀態(tài)的時(shí)間與將要運行的線(xiàn)程恢復寄存器中的內容和系統狀態(tài)的時(shí)間總和。

(6) 系統調用返回時(shí)間RST（returnfromsystemcall）：處于內核態(tài)的線(xiàn)程在它返回用戶(hù)態(tài)之前檢查一些狀態(tài)所用的時(shí)間。

以上這些時(shí)間中，SD、CST和RST總是固定不變的，如果Linux內核設計得當的話(huà)，IDT、IST和KPT可以有效的減少。在實(shí)時(shí)應用的環(huán)境中，若干個(gè)中斷同時(shí)發(fā)生的情況是完全可能存在的。這時(shí)任務(wù)的響應時(shí)間最多將包含N(IDT+IST)，N為中斷數。

中斷軟件模擬被用來(lái)解決多個(gè)中斷同時(shí)發(fā)生的情形。當一個(gè)硬件中斷發(fā)生時(shí)，系統只是簡(jiǎn)單的在時(shí)間表中報告這一時(shí)間的發(fā)生，然后立即將CPU的控制權返回給操作系統，完全略過(guò)了查中斷向量表并執行相應的中斷服務(wù)程序。系統在Linux內核之前截獲了所有應中斷信號，并根據當前實(shí)時(shí)任務(wù)的需要，由軟中斷模擬機制處理或掛起該中斷（例如：IBMPC中的8259中斷控制采用這個(gè)方法，可以減少當多個(gè)中斷同時(shí)發(fā)生時(shí)任務(wù)的響應時(shí)間，最長(cháng)的延遲時(shí)間為N*IST’，其中N為中斷數。在這里之所以是IST’，而不是IST，是因為采用軟中斷軟件模擬的方法使得在IST時(shí)間段內只執行一些簡(jiǎn)單的操作。

2. 搶占式內核體系結構的設計

為了解決Linux實(shí)現硬實(shí)時(shí)的最大障礙，使Linux內核成為完全可被搶占實(shí)時(shí)內核，典型的實(shí)現方案是雙核結構。使用實(shí)時(shí)核來(lái)運行實(shí)時(shí)任務(wù)，Linux內核來(lái)運行非實(shí)時(shí)任務(wù)。例如：對于實(shí)時(shí)數據采樣分析而言，利用實(shí)時(shí)內核運行一個(gè)實(shí)時(shí)任務(wù)來(lái)完成數據采集，另一個(gè)實(shí)時(shí)任務(wù)完成數據分析和控制輸出功能；同時(shí)利用Linux內核上運行的界面來(lái)進(jìn)行數據顯示。如圖1所示。

圖1 雙內核結構

在Linux內核和硬件之間加個(gè)小的實(shí)時(shí)核，由它管理中斷，提供一些必要的功能，如底層任務(wù)創(chuàng )建、中斷服務(wù)程序，并且為底層任務(wù)、ISR和Linux進(jìn)程之間進(jìn)行通信排隊；而Linux內核本身則成為優(yōu)先級最低的Idletask。

對實(shí)時(shí)性要求強的應用編寫(xiě)成實(shí)時(shí)任務(wù)，在實(shí)時(shí)內核上直接運行。Linux內核可以被優(yōu)先級更高的實(shí)時(shí)任務(wù)搶占。對于Linux內核的修改主要集中在三方面：(1) 在Linux內核中影響實(shí)時(shí)性的地方增加控制點(diǎn)，使內核在控制點(diǎn)可以被搶占，減少內核搶占延遲；(2) 將執行時(shí)間較長(cháng)的系統劃分為幾個(gè)甚至是十幾個(gè)較小的塊分別執行，使實(shí)時(shí)任務(wù)隨時(shí)中斷非實(shí)時(shí)任務(wù)；(3) 根據實(shí)際需要，增加部分功能。

隨著(zhù)嵌入式應用的深入，特別是在數字通信和網(wǎng)絡(luò )中的應用，多核結構的處理器也陸續上市。如：Motorola公司研發(fā)的MPC8260PowerQUICC||融合了兩個(gè)CPU-嵌入式PowerPC內核和通信處理模塊（CPM）；Infineon公司推出的TC10GP和增強型TC1130都是三核（TriCore）結構的微處理器，這些處理器的產(chǎn)生對于Linux應用中的實(shí)時(shí)性都大有幫助。

3. 實(shí)時(shí)調度的算法研究

常用的實(shí)時(shí)調度算法有：基于優(yōu)先級的調度算法（priority-drivenscheduling，PD）；基于時(shí)間驅動(dòng)的調度算法（time-drivenscheduling，TD）；基于比例共享的調度算法（share-drivensched2uling，SD）?；趦?yōu)先級的調度算法 調度器以?xún)?yōu)先級作為尋求下一個(gè)任務(wù)執行的依據?？煞譃槿缦聝煞N類(lèi)型：

(1) 靜態(tài)優(yōu)先級調度算法：該算法給系統中所有進(jìn)程都靜態(tài)的分配一個(gè)優(yōu)先級。靜態(tài)優(yōu)先級的分配可以根據應用的屬性來(lái)進(jìn)行，例如任務(wù)的周期、用戶(hù)優(yōu)先級或者其他預先確定的策略。RM（RateMonotonic）是一種典型的靜態(tài)優(yōu)先級調度算法，它根據任務(wù)執行周期的長(cháng)短來(lái)決定調度優(yōu)先級，執行周期小的任務(wù)具有較高的優(yōu)先級。

(2) 動(dòng)態(tài)優(yōu)先級調度算法：這種算法根據任務(wù)的資源需求來(lái)動(dòng)態(tài)的分配任務(wù)的優(yōu)先級。EDF（earliestdeadlinefirst）算法是一種典型的動(dòng)態(tài)優(yōu)先級調度算法，該算法根據就緒隊列中各個(gè)任務(wù)的截止期限來(lái)分配優(yōu)先級，具有最近截止期限的任的優(yōu)先級最高。

基于時(shí)間驅動(dòng)的調度算法

該算法本質(zhì)上是一種設計時(shí)就確定下來(lái)的離線(xiàn)的靜態(tài)調度方法。在系統的設計階段，在明確系統中所有處理的情況下，對于各個(gè)任務(wù)的開(kāi)始、切換以及結束時(shí)間等事先組出明確的安排和設計。

基于比例共享的調度算法

這是一種越來(lái)越受到關(guān)注的實(shí)時(shí)調度模式，基于GPS（generalprocessorscheduling）的算法，其基本思想就是按照一定的權重（CPU使用的比例）對一組需要調度的任務(wù)進(jìn)行調度，使其執行時(shí)間與權重完全成正比?？梢酝ㄟ^(guò)兩種方法來(lái)實(shí)現比例共享調度算法：(1)是調節各個(gè)就緒進(jìn)程出現在當前調度隊列隊首的頻率，并調度隊首的進(jìn)程執行；(2)是逐次調度就緒隊列中的各個(gè)進(jìn)程投入運行，但根據分配的權重調節分配給每個(gè)進(jìn)程的運行時(shí)間片。比例共享算法包括輪轉法、公平共享法、公平隊列法和彩票調度法等幾類(lèi)。
每一種調度策略都有自己的優(yōu)越性和不足。在這里我們提出了一種宏觀(guān)調度結構，通過(guò)設計和構造多屬性和多調度器的選擇機制，使三種實(shí)時(shí)調度策略的應用都得到支持，相對于只對單種調度策略提供支持的方案，拓展了系統的可使用范圍。宏觀(guān)調度結構如圖2所示。

圖2 宏觀(guān)調度結構

我們給每一個(gè)實(shí)時(shí)任務(wù)定義了4個(gè)調度屬性：priority（優(yōu)先級：限制該任務(wù)比相關(guān)聯(lián)的其他任務(wù)的優(yōu)先權）、starttime（起始時(shí)間：任務(wù)開(kāi)始執行時(shí)間）、finishtime（截止時(shí)間：任務(wù)停止時(shí)間）和budget（預設值：任務(wù)允許執行時(shí)間），不同屬性的數據對應不同的調度策略。宏觀(guān)調度結構分為兩個(gè)模塊：屬性分配模塊和調度器選擇模塊。屬性分配模塊給每一個(gè)實(shí)時(shí)任務(wù)分配多個(gè)屬性值，并通過(guò)其中的一兩個(gè)屬性值決定哪個(gè)屬性?xún)?yōu)先，這樣調度器選擇模塊就可以根據屬性的優(yōu)先級別選擇不同的調度器。例如：如果優(yōu)先級屬性?xún)?yōu)先，則調度器就變成了一個(gè)純粹的PD調度器；如果截止時(shí)間優(yōu)先，那么調度器就作為EDF調度器來(lái)工作。

實(shí)驗時(shí)采用Pentium-||400處理器，128MB內存，運行環(huán)境Linux2.0.35（以RED-Linux0.5為補?。?，以RM調度策略為例，分別測量每一次系統請求消耗的時(shí)間。數據整理如下：宏觀(guān)調度結構下屬性分配模塊消耗的時(shí)間大部分不到40Ls，平均約35Ls，調度器選擇模塊平均消耗時(shí)間約85Ls，消耗時(shí)間總計為118Ls，約占0.118%的CPU時(shí)間；單一調度策略的情況平均消耗時(shí)間約為25Ls，約占0.025%的CPU時(shí)間。宏觀(guān)調度結構的延遲時(shí)間為傳統調度方式的5倍，對于大多數的嵌入式系統來(lái)講內核的靈活性和可配置性比調度的延時(shí)更為重要，而宏觀(guān)結構和單一調度結構的CPU可用時(shí)間分別為99.88%和99.97%，差別極小，符合嵌入式系統實(shí)時(shí)性要求。

五、結論與展望

Linux雖然為分時(shí)操作系統，但由于其功能強大、源代碼開(kāi)放以及可移植性強等優(yōu)勢，已成為日益流行的嵌入式實(shí)時(shí)操作系統的解決方案。本文從軟中斷模擬技術(shù)、可搶占式內核和實(shí)時(shí)調度策略三個(gè)方面給出了改善系統實(shí)時(shí)性能的方法，并提出了通過(guò)采用宏觀(guān)調度結構實(shí)現的混合調度，拓展了實(shí)時(shí)系統的應用范圍。Linux實(shí)時(shí)性能的逐步完善，必將大大促進(jìn)嵌入式Linux在工業(yè)控制、后PC時(shí)代信息電器等領(lǐng)域的廣泛應用，應用的需要也會(huì )進(jìn)一步促進(jìn)大量新型控制算法的出現。