楊弋

（中國(guó)航空工業(yè)集團(tuán)公司西安航空計(jì)算技術(shù)研究所，陜西西安，710065）

基于RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)實(shí)現(xiàn)零星服務(wù)器調(diào)度的方法

楊弋

（中國(guó)航空工業(yè)集團(tuán)公司西安航空計(jì)算技術(shù)研究所，陜西西安，710065）

針對(duì)嵌入式實(shí)時(shí)操作系統(tǒng)在多周期任務(wù)及多非周期任務(wù)的場(chǎng)景下，既要保證周期任務(wù)在截止期內(nèi)能夠及時(shí)響應(yīng)，又要保證非周期任務(wù)能夠即時(shí)處理。目前的主流調(diào)度算法存在局限性。零星服務(wù)器調(diào)度算法作為一種指定執(zhí)行預(yù)算及補(bǔ)充周期的非周期任務(wù)的調(diào)度算法，可以較好的滿(mǎn)足即時(shí)響應(yīng)非周期任務(wù)，同時(shí)保證系統(tǒng)內(nèi)其他周期任務(wù)的響應(yīng)。本文簡(jiǎn)述了在RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)下實(shí)現(xiàn)零星服務(wù)器調(diào)度的方法，并對(duì)該算法進(jìn)行測(cè)試，看是否達(dá)到了預(yù)期要求。

RTEMS;調(diào)度算法；IEEE；Sporadic Server

0 引言

嵌入式操作系統(tǒng)產(chǎn)品出現(xiàn)于20世紀(jì)80年代初，經(jīng)過(guò)30多年的發(fā)展，已經(jīng)出現(xiàn)了幾十種嵌入式操作系統(tǒng)。在面向航空，航天，核電等高安全領(lǐng)域，主要采用的是嵌入式實(shí)時(shí)多任務(wù)操作系統(tǒng)。實(shí)時(shí)性是指系統(tǒng)的正確性不僅依賴(lài)于正確的邏輯結(jié)果還要依賴(lài)于結(jié)果產(chǎn)生的時(shí)間，該時(shí)間通常被稱(chēng)為截止期（deadline）。嵌入式實(shí)時(shí)操作系統(tǒng)通常都采用基于優(yōu)先級(jí)搶占的先來(lái)先服務(wù)調(diào)度策略，操作系統(tǒng)內(nèi)核根據(jù)任務(wù)優(yōu)先級(jí)將CPU資源分配給各個(gè)周期任務(wù)使用。然而在嵌入式實(shí)時(shí)操作系統(tǒng)中處理的任務(wù)是多種多樣的，既包含周期性任務(wù)，也包含一些偶發(fā)性的非周期任務(wù)，這些非周期任務(wù)會(huì)處理一些系統(tǒng)產(chǎn)生的偶發(fā)事件，例如I/O操作，外部事件的響應(yīng)等。這些偶發(fā)性的非周期任務(wù)有可能會(huì)導(dǎo)致強(qiáng)調(diào)實(shí)時(shí)性的周期任務(wù)得不到有效地響應(yīng)，抑或是影響了系統(tǒng)的性能，導(dǎo)致CPU吞吐率的下降。為了解決以上問(wèn)題，Sprunt,B.Sha,L., and Lehoczky在1989年提出了零星服務(wù)器調(diào)度（Sporadic Server）策略。本文基于RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)為例，詳細(xì)闡述零星服務(wù)器調(diào)度策略在RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)中的實(shí)現(xiàn)方法并分析該調(diào)度策略的加入對(duì)原有系統(tǒng)的影響。

1 調(diào)度算法概述

目前嵌入式實(shí)時(shí)操作系統(tǒng)的調(diào)度算法主要有固定優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法。

1.1 固定優(yōu)先級(jí)調(diào)度算法

固定優(yōu)先級(jí)調(diào)度算法主要以單調(diào)速率算法（RMS：Rate Monotonic Scheduling）為代表，該算法為每個(gè)周期任務(wù)指定一個(gè)固定不變的優(yōu)先級(jí)Pi，每個(gè)周期任務(wù)的周期為T(mén)i，指定優(yōu)先級(jí)為：Pi=1/Ti，周期越短的任務(wù)優(yōu)先級(jí)越高。

1.2 動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法

動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法主要以截止期最早最優(yōu)先算法（EDF：Earliest Deadline First）為代表，該算法按照周期任務(wù)的截止期（deadline）來(lái)分配優(yōu)先級(jí)，截止期越短的周期任務(wù)優(yōu)先級(jí)越高。在EDF調(diào)度算法中，總是優(yōu)先響應(yīng)截止期最低的周期任務(wù)。

1.3 非周期任務(wù)調(diào)度算法

上述提到的調(diào)度算法的主要應(yīng)用場(chǎng)景為周期任務(wù)。當(dāng)采用RMS或EDF調(diào)度算法的系統(tǒng)中既包含周期性任務(wù)又包含非周期性任務(wù)時(shí)，如果非周期任務(wù)的優(yōu)先級(jí)低于周期任務(wù)，那么非周期任務(wù)有可能永遠(yuǎn)得不到執(zhí)行；如果非周期任務(wù)的優(yōu)先級(jí)高于周期任務(wù)，且非周期任務(wù)如果長(zhǎng)期占用CPU（如I/O操作），則會(huì)影響系統(tǒng)中周期任務(wù)的調(diào)度。為了解決該問(wèn)題，采用了在系統(tǒng)中創(chuàng)建一個(gè)非周期服務(wù)器的方法。該服務(wù)器實(shí)體為一個(gè)任務(wù)，任務(wù)具有一定的執(zhí)行預(yù)算Qs及周期Ts，與周期任務(wù)一起參與調(diào)度。典型的非周期任務(wù)調(diào)度算法包括背景服務(wù)（Background Service），輪詢(xún)服務(wù)器（Polling Server），可延期服務(wù)器（DeferrableServer）和零星服務(wù)器（Sporadic Server）。

背景服務(wù)（Background Service）：背景服務(wù)算法創(chuàng)建了一個(gè)低優(yōu)先級(jí)任務(wù)，在CPU空閑時(shí)該任務(wù)被調(diào)度。如果系統(tǒng)中存在多個(gè)周期很長(zhǎng)的周期任務(wù)長(zhǎng)期占用CPU，則該低優(yōu)先級(jí)任務(wù)有可能一直不參與調(diào)度。

輪詢(xún)服務(wù)器（Polling Server）：輪詢(xún)服務(wù)器算法創(chuàng)建了一個(gè)周期任務(wù)來(lái)處理非周期請(qǐng)求，該周期任務(wù)在周期內(nèi)處理到達(dá)的非周期請(qǐng)求，如果在該周期內(nèi)無(wú)非周期請(qǐng)求，則掛起當(dāng)前任務(wù)直到下一個(gè)周期開(kāi)始解掛該任務(wù)。如果在任務(wù)掛起后產(chǎn)生非周期請(qǐng)求，則該請(qǐng)求必須在下一個(gè)周期開(kāi)始才會(huì)被處理。

延期服務(wù)器（Deferrable Server）：延期服務(wù)器算法與輪訓(xùn)服務(wù)器（Polling Server）類(lèi)似，區(qū)別在于該算法創(chuàng)建了一個(gè)具有執(zhí)行預(yù)算Qs，周期為T(mén)s的周期任務(wù)。非周期請(qǐng)求到達(dá)后，如果Qs仍有執(zhí)行預(yù)算，則對(duì)該請(qǐng)求進(jìn)行處理，直到Qs耗盡。Qs在每個(gè)周期開(kāi)始時(shí)進(jìn)行補(bǔ)充。

零星服務(wù)器（Sporadic Server）：該算法與延期服務(wù)器（Deferrable Server）類(lèi)似，區(qū)別在于零星服務(wù)器算法相比延期服務(wù)器，執(zhí)行預(yù)算Qs的補(bǔ)充方式更加復(fù)雜。

2 RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)的調(diào)度策略

RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)包含兩種調(diào)度策略：基于優(yōu)先級(jí)的可搶占調(diào)度策略以及時(shí)間片輪轉(zhuǎn)調(diào)度策略。

基于優(yōu)先級(jí)的可搶占調(diào)度：基于優(yōu)先級(jí)的可搶占調(diào)度策略給每個(gè)任務(wù)分配一個(gè)固定的優(yōu)先級(jí)，不同優(yōu)先級(jí)按照優(yōu)先級(jí)的高低順序調(diào)度，相同優(yōu)先級(jí)按照先來(lái)先服務(wù)調(diào)度。如果出現(xiàn)有更高優(yōu)先級(jí)任務(wù)處于就緒狀態(tài)時(shí)，則停止當(dāng)前任務(wù)的運(yùn)行，把CPU控制權(quán)交給具有更高優(yōu)先級(jí)的任務(wù)。

時(shí)間片輪轉(zhuǎn)調(diào)度：時(shí)間片輪轉(zhuǎn)調(diào)度策略是指當(dāng)有兩個(gè)或多個(gè)就緒任務(wù)具有相同優(yōu)先級(jí)，且它們是就緒任務(wù)中優(yōu)先級(jí)最高的任務(wù)時(shí)，調(diào)度器按照這組任務(wù)的先后順序調(diào)度各個(gè)任務(wù)，并且使每個(gè)任務(wù)運(yùn)行一段時(shí)間，這段時(shí)間稱(chēng)為時(shí)間片（time slicing）。

3 零星服務(wù)器調(diào)度策略的概念以及實(shí)現(xiàn)方法

Sprunt,B.Sha,L.,and Lehoczky在1989年提出了零星服務(wù)器調(diào)度策略，1999年IEEE將零星服務(wù)器調(diào)度引入至IEEE1003.1d標(biāo)準(zhǔn)中。在該標(biāo)準(zhǔn)的13.2.4節(jié)中詳細(xì)說(shuō)明了零星服務(wù)器調(diào)度的機(jī)制。標(biāo)準(zhǔn)中定義了四種調(diào)度策略：SCHED_FIFO（基于優(yōu)先級(jí)搶占），SCHED_RR（時(shí)間片輪轉(zhuǎn)），SCHED_SPORADIC（零星服務(wù)器調(diào)度），SCHED_OTHER（其他）。

IEEE1003.1d標(biāo)準(zhǔn)中定義了sched_param結(jié)構(gòu)，該參數(shù)包含5個(gè)參數(shù)：sched_priority（優(yōu)先級(jí)），sched_ss_low_ priority（背景優(yōu)先級(jí)），sched_ss_repl_period（補(bǔ)充周期），sched_ss_init_budget（初始預(yù)算），sched_ss_max_repl（最大補(bǔ)充事件數(shù)）。如果調(diào)度策略為SCHED_FIFO或SCHED_RR，則只有sched_priority有效，如果調(diào)度策略為SCHED_SPORADIC，則以上5個(gè)參數(shù)全部有效。

零星服務(wù)器調(diào)度策略主要基于兩個(gè)參數(shù)：補(bǔ)充周期以及執(zhí)行預(yù)算，分別由sched_ss_repl_period以及sched_ss_init_ budget確定。零星服務(wù)器調(diào)度策略基于優(yōu)先級(jí)搶占的調(diào)度算法，采用優(yōu)先級(jí)與背景優(yōu)先級(jí)的雙優(yōu)先級(jí)調(diào)度策略。執(zhí)行預(yù)算決定了任務(wù)的執(zhí)行時(shí)間，如果執(zhí)行預(yù)算大于0，且未決的補(bǔ)充事件數(shù)小于sched_ss_max_repl，任務(wù)在sched_priority優(yōu)先級(jí)下參與調(diào)度；否則，任務(wù)的優(yōu)先級(jí)被降低至sched_ss_low_priority。任務(wù)啟動(dòng)后，任務(wù)被插入sched_priority就緒鏈，執(zhí)行預(yù)算的消耗與補(bǔ)充以及優(yōu)先級(jí)的變化如圖1所示。

圖1 任務(wù)處于零星服務(wù)器調(diào)度策略下的調(diào)度方法

◎處于就緒態(tài)且優(yōu)先級(jí)為sched_priority的任務(wù)開(kāi)始運(yùn)行后，該任務(wù)的最大運(yùn)行時(shí)間不超過(guò)sched_ss_init_budget。

◎任務(wù)從阻塞態(tài)轉(zhuǎn)變?yōu)榫途w態(tài)或執(zhí)行一次補(bǔ)充執(zhí)行預(yù)算的操作后，任務(wù)應(yīng)被插入至sched_priority優(yōu)先級(jí)鏈的鏈尾中，完成以上操作的時(shí)間點(diǎn)被稱(chēng)為啟動(dòng)時(shí)間（activation_time）。

◎當(dāng)處于sched_priority優(yōu)先級(jí)的任務(wù)被高優(yōu)先級(jí)任務(wù)搶占，將該任務(wù)插入至sched_priority優(yōu)先級(jí)鏈的鏈?zhǔn)?，并?jì)算剩余的執(zhí)行預(yù)算，此時(shí)執(zhí)行預(yù)算可能會(huì)被耗盡。

◎當(dāng)處于sched_priority優(yōu)先級(jí)的任務(wù)被阻塞，計(jì)算剩余的執(zhí)行預(yù)算，并執(zhí)行一次補(bǔ)充執(zhí)行預(yù)算的操作，此時(shí)執(zhí)行預(yù)算可能會(huì)被耗盡。

◎當(dāng)處于sched_priority優(yōu)先級(jí)的任務(wù)耗盡執(zhí)行預(yù)算時(shí)，將任務(wù)插入至sched_ss_low_priority優(yōu)先級(jí)鏈的鏈尾，并執(zhí)行一次補(bǔ)充執(zhí)行預(yù)算的操作。

補(bǔ)充執(zhí)行預(yù)算的操作：執(zhí)行預(yù)算補(bǔ)充的大小等于自任務(wù)就緒時(shí)間起（activation_time）至任務(wù)被搶占為止，或自任務(wù)就緒時(shí)間起（activation_time）至任務(wù)被阻塞為止的時(shí)間長(zhǎng)度。補(bǔ)充執(zhí)行預(yù)算的操作在（activation_time+sched_ss_repl_ period）時(shí)執(zhí)行。如果存在多次未決補(bǔ)充執(zhí)行預(yù)算事件，則不得超過(guò)sched_ss_max_repl，否則將該任務(wù)降為sched_ss_low_ priority優(yōu)先級(jí)。如果任務(wù)處于sched_ss_low_priority優(yōu)先級(jí)且處于就緒態(tài)或運(yùn)行態(tài)，則將該任務(wù)插入sched_priority優(yōu)先級(jí)的鏈尾。RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)不支持零星服務(wù)器調(diào)度策略，根據(jù)POSIX標(biāo)準(zhǔn)，零星服務(wù)器調(diào)度類(lèi)似于基于優(yōu)先級(jí)的可搶占調(diào)度，在原有基于優(yōu)先級(jí)的可搶占調(diào)度之上增加雙優(yōu)先級(jí)切換以及計(jì)算任務(wù)的運(yùn)行時(shí)間及補(bǔ)充事件操作的功能即可滿(mǎn)足零星服務(wù)器調(diào)度功能。

◎?qū)崿F(xiàn)零星服務(wù)器調(diào)度雙優(yōu)先級(jí)切換的功能

任務(wù)耗盡執(zhí)行預(yù)算或存在超過(guò)sched_ss_max_repl個(gè)未決補(bǔ)充執(zhí)行預(yù)算事件時(shí)，需要降低任務(wù)的優(yōu)先級(jí)為sched_ss_low_ priority，任務(wù)處于背景優(yōu)先級(jí)時(shí)，在系統(tǒng)時(shí)鐘到達(dá)指定的補(bǔ)充周期后，需要將任務(wù)優(yōu)先級(jí)抬升至sched_priority優(yōu)先級(jí)。通過(guò)調(diào)用RTEMS操作系統(tǒng)提供的_Thread_Change_priority()服務(wù)來(lái)進(jìn)行優(yōu)先級(jí)的轉(zhuǎn)換操作。在任務(wù)降低優(yōu)先級(jí)為sched_ss_low_ priority后，使用RTEMS操作系統(tǒng)提供的定時(shí)器功能創(chuàng)建定時(shí)器，設(shè)置定時(shí)器觸發(fā)時(shí)間為補(bǔ)充周期減去當(dāng)前系統(tǒng)時(shí)間，并掛接定時(shí)器處理程序，定時(shí)器處理程序用于抬升任務(wù)的優(yōu)先級(jí)，并計(jì)算下一次補(bǔ)充周期及補(bǔ)充任務(wù)的執(zhí)行預(yù)算，圖2表示了任務(wù)優(yōu)先級(jí)的切換以及定時(shí)器操作的流程。

圖2 任務(wù)優(yōu)先級(jí)的切換以及定時(shí)器操作

◎?qū)崿F(xiàn)計(jì)算零星服務(wù)器調(diào)度的運(yùn)行時(shí)間及補(bǔ)充事件操作的功能

RTEMS操作系統(tǒng)提供了系統(tǒng)時(shí)鐘為應(yīng)用軟件提供時(shí)間服務(wù)，每個(gè)時(shí)鐘周期會(huì)產(chǎn)生時(shí)鐘中斷，RTEMS操作系統(tǒng)提供了設(shè)置和獲取系統(tǒng)時(shí)間，通知內(nèi)核一個(gè)tick信號(hào)等服務(wù)。在觸發(fā)時(shí)鐘中斷后，需要記錄任務(wù)的運(yùn)行時(shí)間及任務(wù)剩余的執(zhí)行預(yù)算；如果任務(wù)正處于就緒態(tài)，還需要記錄任務(wù)的啟動(dòng)時(shí)間（activation_time）。任務(wù)被更高優(yōu)先級(jí)任務(wù)搶占，或被阻塞的情況下，需要生成一個(gè)補(bǔ)充事件。利用RTEMS操作系統(tǒng)提供的鏈管理服務(wù)，創(chuàng)建一條鏈表，鏈表的每一個(gè)結(jié)點(diǎn)代表任務(wù)的補(bǔ)充事件，補(bǔ)充事件記錄補(bǔ)充的時(shí)間點(diǎn)及補(bǔ)充的時(shí)間大小。當(dāng)系統(tǒng)時(shí)間到達(dá)補(bǔ)充時(shí)間點(diǎn)時(shí)，從鏈表取出一個(gè)結(jié)點(diǎn)并對(duì)任務(wù)的執(zhí)行預(yù)算進(jìn)行補(bǔ)充，圖3表示任務(wù)所需的一些擴(kuò)展數(shù)據(jù)，圖4表示在時(shí)鐘中斷處理中針對(duì)零星服務(wù)器調(diào)度的擴(kuò)展操作。

圖3 任務(wù)擴(kuò)展的零星服務(wù)器調(diào)度數(shù)據(jù)

圖4 時(shí)鐘中斷處理程序中對(duì)運(yùn)行時(shí)間及補(bǔ)充事件的操作

4 試驗(yàn)結(jié)果

我們?cè)谙到y(tǒng)中創(chuàng)建一個(gè)具有零星服務(wù)器調(diào)度的任務(wù)和一個(gè)非周期任務(wù)，給定零星服務(wù)器調(diào)度的任務(wù)的調(diào)度參數(shù)分別為，優(yōu)先級(jí)=100，背景優(yōu)先級(jí)=50，補(bǔ)充周期=6s，初始預(yù)算=4s，最大補(bǔ)充事件數(shù)：40，非周期任務(wù)優(yōu)先級(jí)為90。任務(wù)運(yùn)行的執(zhí)行預(yù)算變化如圖5所示。

圖5 任務(wù)運(yùn)行的執(zhí)行預(yù)算變化圖

零星服務(wù)器調(diào)度任務(wù)在1s，3s，5s，7s，9s時(shí)刻，由于任務(wù)被阻塞讓出CPU給低優(yōu)先級(jí)任務(wù)執(zhí)行，在2s，4s，6s，8s時(shí)任務(wù)解除阻塞，同時(shí)搶占低優(yōu)先級(jí)任務(wù)運(yùn)行。由于任務(wù)被阻塞了5次，產(chǎn)生了5個(gè)補(bǔ)充事件，補(bǔ)充事件以(Es(補(bǔ)充預(yù)算大小)，Ps(補(bǔ)充時(shí)間點(diǎn)))來(lái)表示，則5個(gè)補(bǔ)充事件分別為(1,6)，(1,8)，(1,10)，(1,12)，(1,14)。在途中可看到在6s，8s，10s，12s，14s時(shí)對(duì)執(zhí)行預(yù)算進(jìn)行補(bǔ)充。

5 結(jié)束語(yǔ)

本文介紹了一些典型的調(diào)度算法，同時(shí)闡述了在RTEMS嵌入式實(shí)時(shí)操作系統(tǒng)中實(shí)現(xiàn)零星服務(wù)器調(diào)度的方法。根據(jù)試驗(yàn)結(jié)果，可以看到該實(shí)現(xiàn)方法基本滿(mǎn)足了零星服務(wù)器調(diào)度的功能。

[1]楊麟祥,岳繼光,張曉云.POSIX零星事件調(diào)度策略的研究和實(shí)現(xiàn)[D].同濟(jì)大學(xué)電子與信息工程學(xué)院，上海2009,45(11).

[2]IEEE. Standard for Information Technology— Portable Operating System Interface (POSIX?)[S].IEEE-SA Standards Board:26 September 2008.

[3]羅蕾主編.嵌入式實(shí)時(shí)操作系統(tǒng)及應(yīng)用開(kāi)發(fā)[M].第2版.北京:航空航天大學(xué)出版社, 2007年3月.

Method and Realization of Sporadic Server Scheduling on RTEMS Embedded Real-time Operating System

Yang Yi
(Xi’an Aeronautical Computing Technique Research Institute, AVIC,Xi’an Shaanxi, 710065)

For embedded real-time operating system in periodic tasks and aperiodic tasks,it is necessary to ensure that the periodic tasks is withing the deadline,also the aperiodic tasks should be handled immediately.However the mainstream schedulers have limitation.The sporadic server scheduling algorithm can provide a fast response not only the periodic tasks but aperiodic tasks.This article briefly introduces a method and Realization of Sporadic Server Scheduling on RTEMS Embedded Real-time Operating System,as well as test and verify this algorithm.

RTEMS; scheduling algorithm event; IEEE;Sporadic Server

航空科學(xué)基金項(xiàng)目資助:工信部民用飛機(jī)專(zhuān)項(xiàng)科研項(xiàng)目（MJ-S-2012-05）。