Linux分時(shí)操作系統(tǒng)的實(shí)時(shí)性分析

一、引言

Linux本身為分時(shí)操作系統(tǒng)，其系統(tǒng)目標(biāo)為較好的平均響應(yīng)時(shí)間和較高的吞吐量，而實(shí)時(shí)系統(tǒng)則主要考慮任務(wù)的按時(shí)完成、盡量減少進(jìn)程運(yùn)行的不可預(yù)測(cè)性等。但與商業(yè)嵌入式操作系統(tǒng)相比Linux遵循GPL，具有源代碼開放、定制方便、支持廣泛的計(jì)算機(jī)硬件等優(yōu)點(diǎn)，所以，近年來嵌入式Linux成為嵌入式系統(tǒng)方向上的一個(gè)研究熱點(diǎn)。

本文首先分析了實(shí)時(shí)系統(tǒng)的特點(diǎn)和Linux內(nèi)核在實(shí)時(shí)應(yīng)用方面的不足，然后針對(duì)影響操作系統(tǒng)實(shí)時(shí)性能的若干方面進(jìn)行研究，提出解決方案，最后總結(jié)全文。

二、實(shí)時(shí)系統(tǒng)的分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4) 調(diào)度延遲SD(scheduledelay)：調(diào)度程序用來調(diào)度另一個(gè)線程投入運(yùn)行的時(shí)間。

(5) 進(jìn)程切換時(shí)間CST(contestswitchingtime)：當(dāng)前線程用來保存寄存器和系統(tǒng)狀態(tài)的時(shí)間與將要運(yùn)行的線程恢復(fù)寄存器中的內(nèi)容和系統(tǒng)狀態(tài)的時(shí)間總和。

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

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

中斷軟件模擬被用來解決多個(gè)中斷同時(shí)發(fā)生的情形。當(dāng)一個(gè)硬件中斷發(fā)生時(shí)，系統(tǒng)只是簡單的在時(shí)間表中報(bào)告這一時(shí)間的發(fā)生，然后立即將CPU的控制權(quán)返回給操作系統(tǒng)，完全略過了查中斷向量表并執(zhí)行相應(yīng)的中斷服務(wù)程序。系統(tǒng)在Linux內(nèi)核之前截獲了所有應(yīng)中斷信號(hào)，并根據(jù)當(dāng)前實(shí)時(shí)任務(wù)的需要，由軟中斷模擬機(jī)制處理或掛起該中斷(例如：IBMPC中的8259中斷控制器)。

采用這個(gè)方法，可以減少當(dāng)多個(gè)中斷同時(shí)發(fā)生時(shí)任務(wù)的響應(yīng)時(shí)間，最長的延遲時(shí)間為N*IST’，其中N為中斷數(shù)。在這里之所以是IST’，而不是IST，是因?yàn)椴捎密浿袛嘬浖M的方法使得在IST時(shí)間段內(nèi)只執(zhí)行一些簡單的操作。

2. 搶占式內(nèi)核體系結(jié)構(gòu)的設(shè)計(jì)

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

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

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

隨著嵌入式應(yīng)用的深入，特別是在數(shù)字通信和網(wǎng)絡(luò)中的應(yīng)用，多核結(jié)構(gòu)的處理器也陸續(xù)上市。如：Motorola公司研發(fā)的MPC8260PowerQUICC||融合了兩個(gè)CPU-嵌入式PowerPC內(nèi)核和通信處理模塊(CPM);Infineon公司推出的TC10GP和增強(qiáng)型TC1130都是三核(TriCore)結(jié)構(gòu)的微處理器，這些處理器的產(chǎn)生對(duì)于Linux應(yīng)用中的實(shí)時(shí)性都大有幫助。 3. 實(shí)時(shí)調(diào)度的算法研究

常用的實(shí)時(shí)調(diào)度算法有：基于優(yōu)先級(jí)的調(diào)度算法(priority- drivenscheduling，PD);基于時(shí)間驅(qū)動(dòng)的調(diào)度算法(time-drivenscheduling，TD);基于比例共享的調(diào)度算法(share-drivensched2uling，SD)。基于優(yōu)先級(jí)的調(diào)度算法 調(diào)度器以優(yōu)先級(jí)作為尋求下一個(gè)任務(wù)執(zhí)行的依據(jù)?？煞譃槿缦聝煞N類型：[!--empirenews.page--]

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

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

基于時(shí)間驅(qū)動(dòng)的調(diào)度算法

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

基于比例共享的調(diào)度算法

這是一種越來越受到關(guān)注的實(shí)時(shí)調(diào)度模式，基于 GPS(generalprocessorscheduling)的算法，其基本思想就是按照一定的權(quán)重(CPU使用的比例)對(duì)一組需要調(diào)度的任務(wù)進(jìn)行調(diào)度，使其執(zhí)行時(shí)間與權(quán)重完全成正比。可以通過兩種方法來實(shí)現(xiàn)比例共享調(diào)度算法：(1)是調(diào)節(jié)各個(gè)就緒進(jìn)程出現(xiàn)在當(dāng)前調(diào)度隊(duì)列隊(duì)首的頻率，并調(diào)度隊(duì)首的進(jìn)程執(zhí)行;(2)是逐次調(diào)度就緒隊(duì)列中的各個(gè)進(jìn)程投入運(yùn)行，但根據(jù)分配的權(quán)重調(diào)節(jié)分配給每個(gè)進(jìn)程的運(yùn)行時(shí)間片。比例共享算法包括輪轉(zhuǎn)法、公平共享法、公平隊(duì)列法和彩票調(diào)度法等幾類。

每一種調(diào)度策略都有自己的優(yōu)越性和不足。在這里我們提出了一種宏觀調(diào)度結(jié)構(gòu)，通過設(shè)計(jì)和構(gòu)造多屬性和多調(diào)度器的選擇機(jī)制，使三種實(shí)時(shí)調(diào)度策略的應(yīng)用都得到支持，相對(duì)于只對(duì)單種調(diào)度策略提供支持的方案，拓展了系統(tǒng)的可使用范圍。

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

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

五、結(jié)論與展望

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