嵌入式操作系統調度機制的研究
2009-01-01 00:00:00何福貴侯義斌李輝
計算機應用研究 2009年1期
（北京工業大學 嵌入式軟件與系統研究所， 北京 100022）
摘 要：近年來提出了一些調度機制的實現方案，但這些方案不能實現由用戶來選擇調度算法和多算法集成，不能給用戶提供統一的用戶使用界面。為此，提出了一種新的調度機制，它能夠給用戶提供統一的使用界面，支持所有的調度算法且隱含實現的細節，使用戶更方便地使用各種調度算法。在Linux上進行了實現，給出了主要的數據結構和實現過程，對結果進行了分析。
關鍵詞：調度機制；實時算法；Linux
中圖分類號：TP319 文獻標志碼：A
文章編號：10013695(2009)01016503
Research of embedded operating system scheduling mechanism
HE Fugui，HOU Yibin，LI Hui
(Embedded Software Systems Institute， Beijing University of Technology， Beijing 100022， China)
Abstract:In recent years， some scheduling schemes were presented， but these schemes could not support for user to choose schedulingalgorithm and multialgorithm integration， and could not offer a uniform operatinginterface for users. The paper presented a new scheduling mechanism， it could offer a uniform operatinginterface， and could support available scheduling algorithms， and could hide the implementing details， and let user use all algorithm conveniently. It realized in Linux， presented principal datastructure and realizing procedure，and gave experimental result and analysis.
Key words:scheduling mechanism; realtime algorithms; Linux
0 引言
實時系統的發展已有四十多年的歷史，主要應用于嵌入式領域。運行在這些系統中的操作系統被稱為實時操作系統。實時調度是實時操作系統的核心，它保障實時系統的實時性。實時調度理論在過去的幾十年中進行了廣泛的研究，提出了許多種實時調度算法，如RM[1](ratemonotonic，單調速率)算法、EDF[1](earliest deadline first，截止期最早最優先)算法、DM[2](deadline monotonic)算法、 LFS[3](least slack first，空閑時間最短最優先)算法、HVF[4](highest value first，價值最高最優先)、HVDF[4，5](highest value density first，價值密度最大最優先)、PTS(preemption threshold scheduling)[6]、DS[7](deferrable server)算法、SS[8](sporadic server)算法、DDS[9](deadline deferrable server)算法、DSS[9](deadline sporadic server)算法、 DES[9](deadline exchange server)算法、TBS[10](total bandwidth server)算法和CBS[11](constant bandwidth server) 算法等。
這些算法對周期任務系統和非周期任務系統的調度從理論上進行了分析，得出了相應的可調度的充分條件和必要條件，為實時系統的發展奠定了理論基礎。
近年來對調度機制提出了一些改造的方案，能夠運行一些實時調度算法，以適合實時調度的要求。
1 調度機制簡介
1.1 兩層調度框架
文獻[12]提出了兩層調度框架，它把調度結構分兩部分：調度器(dispatcher)和分配器(allocator)。調度器運行在內核態，分配器可運行在內核態或用戶態。定義了四個通用的調度屬性：優先級(priority)、開始時間(start time)、完成時間(finish time)和預算(budget)，然后靠分配器對四個屬性不同的解釋來實現各種不同的調度算法，取得了很大的靈活性，并在Linux上進行了實現，稱為REDLinux。調度框架如圖1所示。
1.2 開放的實時系統調度框架
文獻[13]提出了一種實時調度框架，如圖2所示。它能夠調度實時和非實時任務，使用一些CPU利用率為常數的服務器來執行硬實時任務，而非實時任務作為背景程序來執行。調度器有一個服務器任務隊列，這個隊列按照EDF調度算法來調度；每個服務器再按照某一種算法調度相應的任務隊列。服務器是動態的，當有相應的任務需執行時，調度器建立一個服務器。當這個任務執行結束時，調度器銷毀這個服務器。所有的非實時任務運行在一個優先級最低的時間共享的服務器上。這種方法實際上將原來的一個調度器分成兩個，以實現不同的調度算法。
1.3 硬實時操作系統RTLinux的調度機制
RTLinux 是在原Linux內核的基礎上增加一個實時內核，形成一個雙內核結構。在實時內核中，RTLinux提供實時調度模塊。它把調度模塊的編寫任務交給系統的使用者，使用者編寫的模塊可以很容易地加入到系統中，這樣，使用者可根據自己的不同需求，采用適宜的調度算法。RTLinux本身提供了兩個實時調度模塊。RTLinux 實現了采用不同的實時調度算法進行調度，但算法的編寫由用戶來完成，這就增加了程序開發的難度。
從以上的分析可以看出，這些調度框架有以下不足之處：a）支持的調度算法很少；b）需要用戶參與實時調度算法的編寫，難度較大；c）對調度參數的解釋沒有統一的規定，容易造成歧義性。為了克服這些不足，本文提出了一種新的調度框架，可以實現對現在所有實時調度算法的支持，對用戶提供了使用的統一接口，使調度規范化。
2 新調度機制
新調度機制的結構如圖3所示，調度模型支持雙層調度。如果采用雙層調度機制，第二層調度器所指向的任務其實是一個服務器，這個服務器去調度它指向的一個任務隊列。
新調度機制的核心是SW，它向用戶提供使用調度算法的統一界面，應用程序通過提供的系統調用使用SW。SW以下對用戶是透明的，具體實現的細節包含在操作系統中，簡化了用戶的操作。用戶通過系統調用選擇單層調度和雙層調度，同時在各層可選擇各種調度算法（包括實時和非實時調度算法），系統可以支持所有的調度算法。
3 新調度機制的實現
由于 Linux源代碼開放，本文選擇Linux為實現目標。
3.1 主要數據結構
核心數據結構為調度節點數據結構，其作用是向上層用戶提供統一的使用界面。此數據結構中包含有各種調度算法的數據結構，這些算法的數據結構作為一個共同體(union)， 每一個調度節點數據結構只能包含各種算法的數據結構中的一個。
調度節點數據結構描述如下：
struct scheduling_inode {
調度公有的屬性;
指向任務結構的指針;
union {
structrm_scheduling_inode rm_inode; //RM 調度節點
struct edf_scheduling_inode edf_inode;// EDF 調度節點
……
} a_inode;
};
每一種調度算法都有其對應的數據結構，以EDF算法結構為例：
structedf _scheduling_inode
{
unsigned long start_time;//開始時間
unsigned long calculate_time;//計算時間
unsigned long finish_time;//完成時間
union {
unsigned long period; //周期
unsigned long internal;//最小間隔
}u
unsigned long deadline;//截止期
unsigned long weight_value; //權值
}
為了能夠操作調度節點，在Linux任務數據結構struct task_struct結構中增加指向調度節點的指針。
3.2 實現過程函數
3.2.1 各種算法的優先級計算函數
每一種實時調度算法都有一個計算優先級的函數，在此函數中可加入接收測試，如果通不過測試，則作為非實時任務來執行。
3.2.2 各種算法的初始化函數和釋放函數
各種算法初始化函數的執行應在進程建立時執行。初始化的功能是首先在內存申請一個調度節點，然后對調度節點相應的成員進行賦值。釋放函數應在進程釋放時執行，釋放函數是釋放調度節點所占用的內存空間，從所在隊列進行脫鏈等相關操作。釋放函數的過程與初始化函數的過程正好相反。
3.2.3 設置調度參數和讀取調度參數
調度參數可以由用戶進行設置。這個函數要解決的關鍵問題是：給定一個參數名和參數的值，如何使這個參數名與scheduling_inode結構的成員名進行比較和匹配。此函數的代碼較長，簡單地描述如下：
首先定義一個結構體struct param{char*name;offset}。 這個結構包含兩個成員：a)Name表示scheduling_inode結構的成員名;b)Offset表示此成員在scheduling_inode結構中的相對位移。然后定義struct param結構的一個數組， 每一個數組成員表示scheduling_inode結構的一個成員名和它的相對位移，數組的大小由用戶可訪問的參數數量決定。最后在設置參數的函數中讓給定的參數名與這個結構數組的每一個name成員相比較，如果出現相同的一對，就以這個數組的位移為相對位移找到對應的scheduling_inode結構的成員名進行賦值，從而修改此成員的值。
讀取scheduling_inode結構成員值的方法與此類似。
3.2.4 對Linux的schedule函數的修改
Linux在schedule[14]函數中實現進程調度的功能。進程優先級的計算是在schedule函數中進行的，在schedule函數調用goodness函數。Goodness函數是Linux計算優先級的函數。新調度機制使用任務所指向的調度節點數據結構來進行計算。為了保持與Linux的兼容性，在新調度的參數沒有定義的情況下，可使用原Linux優先級的計算方法；在新調度的參數存在的情況下，優先使用在新調度的參數計算優先級。
4 結果分析
4.1 調度機制的復雜性分析
Linux進程的優先級計算和從就緒隊列選擇一個優先級最高的進程投入運行都是在schedule()函數中進行的，其中goodness函數計算進程的優先級，其他部分的作用從就緒隊列選擇一個優先級最高的進程。從這一段程序可以看出，每一次調度都要把就緒隊列的所有任務訪問一次，所以Linux調度的復雜性與就緒隊列中任務的個數成正比。本文提出的新調度機制的復雜性與Linux相同，這樣在不增加調度復雜性的前提下，可支持多種調度算法，實現了調度算法的集成。
4.2 實驗測試
本文采用的Linux版本為Linux2.4.20， 在內核修改完成后，設計一組運行時間逐漸增多的程序來進行測試，分別測試在Linux調度機制和新調度機制的程序運行時間，測試運行的平臺為桌面計算機。其配置如下：Celeron 2.00 GHz CPU；內存256 MB；磁盤為ST31640021A。運行的平臺為Red Hat Linux 7.3， 測試結果如圖4所示。從圖中可以看出新調度機制可以有效地減少程序的運行時間。
5 結束語
實時調度是嵌入式操作系統的核心，現在已發展了許多實時調度算法，調度算法是通過調度機制實現的。為了使嵌入式操作系統的調度機制更具有適用性，本文提出了一種新的調度機制，這種調度機制能夠克服現有調度機制存在的缺點，并且選擇Linux為實現目標。測試結果表明，這種調度機制具有很強的實時性和通用性，能夠滿足現有的和未來的實時調度發展的要求。
參考文獻：
［1］
LIU C L，LAYLAND J M.Scheduling algorithms for multiprogramming in a hard realtime environment[J].Journal of the ACM，1973，20(1):4661.
[2]LEUNG J，WHITEHEAD J.On the complexity of fixedpriority scheduling of periodic， realtime tasks[J].Performance Evaluation，1982，2:237250.
[3]DERTOUZOS M L，MOK A K.Multiprocessor online scheduling of hardrealtime tasks[J].IEEE Trans on Software Engineering，1989，15(12):14971506.
[4]JENSEN E D，LOCKE C D，TODUDA H.A timedriven scheduling model for realtime operating systems[C]//Proc of the 6th IEEE Realtime Systems Symposium. San Diego:IEEE Computer Society Press， 1985:112122.
[5]BUTTAZZO G，SPURI M，SENSINI F.Value vs deadline scheduling in overload conditions[C]//Proc of the 19th IEEE Realtime Systems Symposium. Pisa: IEEE Computer Society Press， 1995:9099.
[6]SAKSENA M，WANG Yun.Scalable realtime system design using preemption thresholds[C]//Proc of the 21st IEEE Realtime Systems Symposium. Los Alamitos: IEEE Computer Society Press， 2000:2534.
[7]STROSNIDER J K，LEHOCZKY J P，SHA L. The deferrable server algorithm for enhanced aperiodic responsiveness in hard realtime environments[J].IEEE Trans on Computers，1995，44(1):7391.
[8]SPRUNT B，SHA Lui， LEHOCZKY J.Aperiodic task scheduling for hardrealtime systems[J].Realtime Systems，1989，1(1):2760.
[9]GHAZALIE T M， BAKER T P. Aperiodic servers in a deadline scheduling environment[J].Realtime Systems，1999，9(1):3167.
[10]SPURI M，BUTTAZZO G.Scheduling aperiodic tasks in dynamic priority systems[C]//Proc of the 16th IEEE Realtime Systems Symposium. Pisa， Italy:[s.n.]， 1995:210219.
[11]ABENI L，BUTTAZZO G.Integrating multimedia appplications in hard realtime systems[C]//Proc of IEEE Realtime Systems Symposium. Madrid， Spain:[s.n.]， 1998.
[12]WANG Yuchung.Design and implementation of REDLinux[D].California: University of California，2002.
[13]DENG Z，LIU J W S. Scheduling realtime application in open sysem environment[C]//Proc of the 18th IEEE Realtime Symposium. San Francisco:[s.n.]， 1997:308319.
[14]毛德操，胡希明.Linux情景源代碼分析（上冊）[M].杭州：浙江大學出版社，2001:263398.
