嵌入式系統中操作系統調度算法講解探討

李秀紅+古麗拉·阿東別克

摘要：嵌入式軟件系統的核心就是嵌入式操作系統，學生在完成嵌入式系統設計過程中，操作系統的選擇和設計至關重要，前提條件是學生對操作系統中進程的調度算法足夠了解，進而進行調度算法的設計以適應嵌入式系統設計的專用性。該文旨在給出操作系統的普通調度算法和嵌入式實時操作系統的不同調度算法，對算法進行講解和區分，以便于學生學習和掌握。

關鍵詞：嵌入式系統；實時系統；進程調度；操作系統；優先級

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2018）01-0013-02

嵌入式系統包括硬件系統和軟件系統。嵌入式軟件系統是由嵌入式操作系統和嵌入式應用程序組成。嵌入式操作系統通常是實時操作系統，盡管不是所有的嵌入式系統都是實時系統，但是實時性是多數嵌入式系統最重要的特性之一。嵌入式系統當中一個很重要的思想就是嵌入式系統當中如果面對的是復雜多任務系統 ，如工業智能控制系統，銀行ATM終端等，這些情況下通常需要安裝嵌入式操作系統，且多數情況下是嵌入式實時操作系統。教學的難點是讓學生理解什么樣的系統需要安裝嵌入式操作系統，不同的應用需要的操作系統差別很大，核心的思想不同的應用會需要特定類型的操作系統，而不同的操作系統會有不同的進程調度算法。實時操作系統中最重要的就是進程調度算法是實時性的，能夠保證較好的響應時間。普通操作系統和實時操作系統的區別就是系統進程調度算法的差別。在課程的講解上，為了增加學生對實時性的認知，需要講解操作系統的調度算法。通過進程調度算法的講解讓學生在完成嵌入式系統設計的過程中，能夠根據實際應用是否實時性進行有效地進行操作系統進程調度算法的選取，進而決定操作系統的類型。

1 實時系統介紹

所謂實時系統就是系統的輸出在時間上至關重要的系統。這樣的系統不但要求系統輸出結果的正確性還要求輸出結果的時間，在給定輸入之后，一定要在有效的時限內產生系統輸出。衡量實時系統很重要的指標是就是響應時間，是指計算機從識別一個外部時間到做出響應的時間。依據輸出結果的時間的長短，實時系統分為強實時系統（響應時間在毫秒或者微秒），弱實時系統（響應時間為數十秒說著更長），一般實時系統（前兩者的折中）。在航空航天，工業控制系統中多要求強實時系統，民用多媒體電子產品對實時性要求一般不高，多數是一般實時系統，比如智能手機。

2 普通系統的調度算法

普通系統和實時系統采用不同的調度算法。不同的算法決定了統實時性能的。調度算法主要是針對系統當中的進程執行的先后順序來進行調度的算法。對于一個普通系統，進程的調度算法常用的主要有：先來先服務，短進程優先，最高響應比優先。三種這三種算法各有優劣，但是這三種算法都不利于系統當中的緊迫性高的實時任務。對于普通系統，這三種調度算法有較好的性能。

2.1 先來先服務調度算法

這是一種最簡單的進程調度算法，在這種進程調度中，進程嚴格依照進入內存的時間先后順序排成一個隊列，處理器每次從就緒隊列中選擇隊首的進程來占據CPU執行，這個隊首的進程一定是系統當前狀態下最先進入內存的進程。

FCFS調度算法屬于不可搶占算法，算法簡單。從表面上看，它對所有進程都是公平的，但若一個長進程先到達系統，就會使后面許多短進程等待很長時間，對長進程比較有利，但會造成短作業等待時間和占據CPU運行的時間比值過大，故而降低系統的吞吐量（系統單位時間內完成的任務總數），導致很多短作業隊系統不滿意。所以可以將這種算法和其他算法結合起來使用。

2.2 短進程優先調度算法

短進程優先調度算法是指對短進程優先調度的算法這是從就緒隊列中選擇一個估計占據CPU執行時間最短的進程，將處理機分配給它，使之立即執行。短進程算法對長進程不利，短作業多的情況下，長進程的等待使用CPU的時間會增加。嚴重的將導致長進程長期不被調度而出現“餓死”，即CPU依照這個算法總是調度短作業運行，長作業始終處于等待狀態而得不到CPU的使用權。該算法會提高系統的吞吐量，因為系統總是調度耗時少的短進程執行，故而吞吐量一定上升，但是整體而言，這個算法對長進程很不公平。

2.3 最高響應比優先調度算法

先來先服務算法會導致系統吞吐量下降，不滿意的短進程數量增加，短進程優先會提高吞吐量但是導致長作業餓死，基于上述兩種算法的綜合，給出了最高響應比優先調度算法。最高響應比優先是響應比高的進程優先調度運行。

該算法需要系統記錄每個進程的等待時間和要求占據CPU的執行時間。進程調度時，先計算后備進程隊列中每個進程的響應比，從中選出響應比最高的進程投入運行。缺點是每一次執行該調度算法時都要重新計算系統當中所有就緒隊列的每一個進程的響應比，這個計算當系統任務量大時候比較消耗系統時間。

通過響應比計算公式我們可以得到以下結論：

· 進程的等待時間相同時，要求CPU執行時間短的響應比高，從而有利于短進程。

· 進程要求CPU執行時間相同，等待時間長的響應比高，此時，該算法是先來先服務。

· 長進程的響應比可以隨其等待時間增長加大，從而得到CPU的使用權。因此該算法不會出現長作業餓死現象?？朔硕套鳂I優先的缺點。

3 實時系統的調度算法

實時內核必須采用基于優先級調度的算法。任務根據重要程度或者緊迫性被賦予一定的優先級，就緒隊列是嚴格按照優先級高低排隊。同一優先級的按照先來先服務的順序排隊。CPU總是調度就緒隊列首位的優先級最高的進程占據CPU執行。這種調度算法一定是支持搶占的，一旦有優先級高的進程就緒，則搶奪當前進程CPU的使用權。實時系統的調度算法主要有三種：基于優先級的搶占式的調度算法，同一優先級的時間片輪轉的調度算法和單調速率算法。endprint

3.1 基于優先級的搶占式的調度算法

實時系統為每一個進程分配一個優先級，優先級高低反映了進程的重要性和緊迫性，進程按優先級別高低排隊?；趦炏燃壍膿屨际降恼{度算法，保證了高優先級的進程在得到系統資源獲得CPU使用權上比低優先級的進程有更好的優先權。實時系統都是采用的基于優先級的進程調度算法，該算法依據CPU被搶奪的時間又分為以下兩種：

· 非搶占式優先級調度算法。高優先級進程一旦就緒，系統會暫停低優先級別的進程，處理高優先級的請求，將其置于當前就緒隊列的首位，然后接著執行低優先級別的進程，直至其結束。之后才調度就緒隊列首位的進程執行，即剛才低優先級別進程執行過程中處于就緒狀態的進程。

· 搶占式調度算法。高優先級進程一旦就緒，低優先級的進程立刻被剝奪CPU的使用權。系統立刻運行高優先級進程。

3.2 同一優先級的時間片輪轉調度算法

在實時系統當中，如果多個任務共享同一個優先級，則統一優先級的進程在就緒隊列當中按照先來先服務的順序排隊，所有進程時間片輪轉的方式獲取CPU的使用權。不同優先級的排成不同的就緒列，這種調度算法，系統當中有多個依據不同優先級而建成的隊列，每個隊列中依據到達的時間先后順序又排隊，系統總是在高優先級隊列為空的情況下調度優先級別低的隊列當中的進程執行。

3.3 單調速率算法

該算法是依據進程的執行頻度來確定其優先級，執行頻度高的優先級高，執行頻度低的則優先級低，獲得CPU的使用權限低。優先級高的可以優先獲得CPU的使用權。

4 結論

課堂教學過程中，嵌入式系統開發的復雜度很高，務必要讓學生理解操作系統選擇的重要性和嵌入式系統當中的軟硬件可裁剪的意義，針對性地選擇合適嵌入式開發合適的環境。操作系統是否需要，需要操作系統的哪些功能，哪些功能是通用操作系統裁剪之后可以得到的，這些講解的過程中最終要的就是操作系統的核心功能：進程調度。不同的進程調度算法決定了系統的實時響應能力。

參考文獻：

[1] 馬忠梅.ARM&LINUX嵌入式系統教程[M] 北京：北京航空航天大學出版社，2014.

[2] 于玉.操作系統[M] 北京：電子工業出版社，2003.

[3] 李善平.LINUX與嵌入式系統[M] 北京：清華大學出版社，2002.

[4] 何小平.選擇適合ARM的嵌入式操作系統[J].BMRfech Inc.2003.

[5] 周立功. ARM嵌入式系統基礎教程[M] 北京：北京航空航天人學出版社，2005.endprint