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

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

關鍵詞：嵌入式系統(tǒng)；實時系統(tǒng)；進程調度；操作系統(tǒng)；優(yōu)先級

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

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

1 實時系統(tǒng)介紹

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

2 普通系統(tǒng)的調度算法

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

2.1 先來先服務調度算法

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

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

2.2 短進程優(yōu)先調度算法

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

2.3 最高響應比優(yōu)先調度算法

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

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

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

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

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

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

3 實時系統(tǒng)的調度算法

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

3.1 基于優(yōu)先級的搶占式的調度算法

實時系統(tǒng)為每一個進程分配一個優(yōu)先級，優(yōu)先級高低反映了進程的重要性和緊迫性，進程按優(yōu)先級別高低排隊?；趦?yōu)先級的搶占式的調度算法，保證了高優(yōu)先級的進程在得到系統(tǒng)資源獲得CPU使用權上比低優(yōu)先級的進程有更好的優(yōu)先權。實時系統(tǒng)都是采用的基于優(yōu)先級的進程調度算法，該算法依據(jù)CPU被搶奪的時間又分為以下兩種：

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

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

3.2 同一優(yōu)先級的時間片輪轉調度算法

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

3.3 單調速率算法

該算法是依據(jù)進程的執(zhí)行頻度來確定其優(yōu)先級，執(zhí)行頻度高的優(yōu)先級高，執(zhí)行頻度低的則優(yōu)先級低，獲得CPU的使用權限低。優(yōu)先級高的可以優(yōu)先獲得CPU的使用權。

4 結論

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

參考文獻：

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

[2] 于玉.操作系統(tǒng)[M] 北京：電子工業(yè)出版社，2003.

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

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

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