嵌入式系統(tǒng)中操作系統(tǒng)調(diào)度算法講解探討

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

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

關(guān)鍵詞：嵌入式系統(tǒng)；實(shí)時(shí)系統(tǒng)；進(jìn)程調(diào)度；操作系統(tǒng)；優(yōu)先級(jí)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）01-0013-02

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

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

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

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

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

2.1 先來先服務(wù)調(diào)度算法

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

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

2.2 短進(jìn)程優(yōu)先調(diào)度算法

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

2.3 最高響應(yīng)比優(yōu)先調(diào)度算法

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

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

通過響應(yīng)比計(jì)算公式我們可以得到以下結(jié)論：

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

· 進(jìn)程要求CPU執(zhí)行時(shí)間相同，等待時(shí)間長(zhǎng)的響應(yīng)比高，此時(shí)，該算法是先來先服務(wù)。

· 長(zhǎng)進(jìn)程的響應(yīng)比可以隨其等待時(shí)間增長(zhǎng)加大，從而得到CPU的使用權(quán)。因此該算法不會(huì)出現(xiàn)長(zhǎng)作業(yè)餓死現(xiàn)象。克服了短作業(yè)優(yōu)先的缺點(diǎn)。

3 實(shí)時(shí)系統(tǒng)的調(diào)度算法

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

3.1 基于優(yōu)先級(jí)的搶占式的調(diào)度算法

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

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

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

3.2 同一優(yōu)先級(jí)的時(shí)間片輪轉(zhuǎn)調(diào)度算法

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

3.3 單調(diào)速率算法

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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