Linux實時性研究（1）

sky-walker

Linux Realtime
何謂實時系統(tǒng)：
POSIX 1003.b 定義：系統(tǒng)能夠在限定的響應(yīng)時間內(nèi)提供所需的服務(wù)
Donald Gillies 的定義： 計算的正確性不僅取決于程序的邏輯正確性，也取決于產(chǎn)生結(jié)果的時間快慢。
分類：
【hard realtime(HRT)】在不滿足響應(yīng)時限、響應(yīng)不及時或反應(yīng)過早的情況下都會導(dǎo)致災(zāi)難性的后果
【soft realtime(SRT)】在不滿足響應(yīng)時限時，系統(tǒng)性能退化，但并不會導(dǎo)致災(zāi)難性的后果
【best effort(BE)】工作速度沒有特定限制，快一點更好些
實時指標(biāo)：
】Response time
】Latency
】Deadline
其中
HRT對以上三者都有硬性要求，否則服務(wù)完全失效。如工業(yè)控制，航天航空，軍事應(yīng)用等。
SRT無法提供服務(wù)質(zhì)量。如多媒體實時需求。
BE，如一些字處理器，PC的常規(guī)應(yīng)用。
影響實時的因素：
硬件－－MPU的設(shè)計: Cache結(jié)構(gòu)設(shè)計,上下文切換速度，異常處理，內(nèi)嵌寄存器等。
軟件－－OS設(shè)計理念：kernel的可搶占、重入性，硬件支持程度，實時調(diào)度算法。
Linux的缺陷－－Desktop,Server型OS,實時性有限。主要體現(xiàn)在：內(nèi)核的可重入、可搶占性，系統(tǒng)時鐘粒度，實時調(diào)度算法。
突破Linux缺陷的方法：
1】、增加kernel可搶占性
一般的kernel的不可搶占性使實時任務(wù)無法提供任務(wù)的調(diào)度權(quán)，可以通過修改源碼，縮小禁止中斷、內(nèi)核加鎖的范圍。
2】、細化時鐘粒度
一般的kernel無法提供高精度時鐘，也即無法高精度分辨RT任務(wù)的到來，RTC可提供高精度。
3】、調(diào)度算法
一般的kernel是基于優(yōu)先級的調(diào)度算法，無法滿足HRT、QoS等的任務(wù)需求�？上蛘{(diào)度器增加hook或改造調(diào)度器來改善。
實時調(diào)度算法概覽：
三種模式：
TD－－time driven： 被靜態(tài)精確計算過的運行時任務(wù)計時，適合小型嵌入式系統(tǒng)、自動控制、傳感器領(lǐng)域等。
具有穩(wěn)定、已知輸入的簡單系統(tǒng)，通常提供數(shù)據(jù)處理的預(yù)測性。其本身是一種設(shè)計時就確定下來的離線的靜態(tài)調(diào)度算法。在系統(tǒng)的設(shè)計階段，對于任務(wù)的開始、切換、結(jié)束都事先做好安排。
有良好的任務(wù)可預(yù)測性，但缺乏靈活性，會出現(xiàn)CPU空閑但卻有任務(wù)需要執(zhí)行的情況。
PD－－priority driven：靜態(tài)優(yōu)先級進程調(diào)度算法：靜態(tài)分配給進程優(yōu)先級，根據(jù)應(yīng)用的屬性進行。例如：任務(wù)周期，用戶優(yōu)先級，預(yù)先策略等等。RM(rate-monotonic)－－根據(jù)任務(wù)的執(zhí)行周期長短來決定調(diào)度優(yōu)先級，小周期任務(wù)具有較高優(yōu)先級。
動態(tài)優(yōu)先級進程調(diào)度算法：根據(jù)進程的資源需求動態(tài)分配進程的優(yōu)先級。許多非實時系統(tǒng)采有此種算法，如短作業(yè)優(yōu)先調(diào)度算法。實時算法中EDF(earliest deadline first)較普遍－－給就緒隊列中的各任務(wù)的Deadline來分配優(yōu)先級，Deadline最近的任務(wù)具有最高優(yōu)先級。
基本可以說以上兩類算法提供了硬實時調(diào)度。
SD－－shared driven：基于CPU使用比例的進程調(diào)度算法，讓他們的執(zhí)行時間和他們的權(quán)重成正比。方法有兩種：（1）、調(diào)節(jié)任務(wù)隊列在調(diào)度隊列隊首的頻率，（2）、根據(jù)權(quán)重分配時間片，并逐次調(diào)度隊列中的進程投入運行。
主要類別：輪轉(zhuǎn)法、公平共享、公平隊列、彩票調(diào)度法(Lottery)。
缺點：沒有優(yōu)先級之分，任務(wù)共享資源，系統(tǒng)處于過載狀態(tài)時，所有任務(wù)都按比例變慢，所以一般采用一種動態(tài)調(diào)節(jié)進程權(quán)重的方法。
基礎(chǔ)是GPS(general processor sharing)；算法有WFQ(weighted fair queueing);WF2Q;qlinux使用H-SFQ等。
適合實現(xiàn)資源預(yù)留，保障多媒體等軟實時性能的算法模式，實現(xiàn)的前提要求系統(tǒng)提供某種靜態(tài)優(yōu)先級算法，以實現(xiàn)資源預(yù)留。
其一般內(nèi)容包括：accounting, policing/enforcement,admission control。
linux上的實時多媒體性能
1】、linux－SRT （Cambridge Univ.）
采用高精度時鐘，支持QoS，沒有修改調(diào)度算法，通過在現(xiàn)行kernel中增加調(diào)度類來實現(xiàn)QoS（由于文檔描述粗糙，可靠性收到懷疑）。
2】、Qlinux （Massachusetts Univ. 、Texas Univ. 、Ensim Corp.）
致力于支持高性能多媒體功能的linux，采用H-SFQ（hierachical start-time queueing），提供CPU,network,disk的QoS服務(wù)。
3】、linux/RK（Carnegie-Mellon Univ.、Timesys Corp.）
致力于資源預(yù)留的linux實現(xiàn)，通過實現(xiàn)資源預(yù)留管理模塊、在內(nèi)核調(diào)度相關(guān)代碼中插入hook，達到預(yù)留CPU，network資源，并且向系統(tǒng)特殊任務(wù)實現(xiàn)QoS的目的。
4】、KURT－linux（Kansas Univ.）
提供高精度時鐘&一種特殊的實時任務(wù)保障體制（文檔缺少），提供的實時機制對多媒體性能沒有什么特別。
5】、Red-linux（California Univ.）
整合了三種（TD、PD、SD）實時模式。
【注1】關(guān)于RTlinux/RTAI： 主要用于工控，但缺少學(xué)術(shù)價值，專利許可嚴(yán)密，最重要的是已經(jīng)有理論支持（網(wǎng)上的adeos模型可以取代他）。
【注2】關(guān)于linux內(nèi)核時間粒度：scheduling time slice的最大值為10ms; 時鐘粒度主要取決于RTC。
對于arm來說，提供的high-res clock主要是通過RTC的高精度，而對于MIPS、PPC、x586這樣的處理器還提供了基于總線仲裁的計數(shù)器，通常叫做TSC（timer stamp counter）來提高時鐘精度。
就通常情況，時鐘的頻率是系統(tǒng)總線時鐘頻率的1/4。
【注3】關(guān)于搶占：搶占可以發(fā)生在任何進程的時間片內(nèi)，而不必等到此進程時間片完成。
【注4】關(guān)于MontaVista Corp. : 開發(fā)了用于替換linux標(biāo)準(zhǔn)調(diào)度算法的算法，可以實現(xiàn)SRT ，提供high-res clock 。參見：

http://sourceforge.net/projects/rtsched/
在MontaVista網(wǎng)站上有一個測試系統(tǒng)調(diào)用時間片的Demo，可以試試。
【注5】 the high-res timer Project :

http://sourceforge.net/projects/high-res-timers/




本文來自ChinaUnix博客，如果查看原文請點：http://blog.chinaunix.net/u/8962/showart_100510.html