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

楊弋

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

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

楊弋

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

時間片輪轉(zhuǎn)調(diào)度：時間片輪轉(zhuǎn)調(diào)度策略是指當(dāng)有兩個或多個就緒任務(wù)具有相同優(yōu)先級，且它們是就緒任務(wù)中優(yōu)先級最高的任務(wù)時，調(diào)度器按照這組任務(wù)的先后順序調(diào)度各個任務(wù)，并且使每個任務(wù)運(yùn)行一段時間，這段時間稱為時間片（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ì)說明了零星服務(wù)器調(diào)度的機(jī)制。標(biāo)準(zhǔn)中定義了四種調(diào)度策略：SCHED_FIFO（基于優(yōu)先級搶占），SCHED_RR（時間片輪轉(zhuǎn)），SCHED_SPORADIC（零星服務(wù)器調(diào)度），SCHED_OTHER（其他）。

IEEE1003.1d標(biāo)準(zhǔn)中定義了sched_param結(jié)構(gòu)，該參數(shù)包含5個參數(shù)：sched_priority（優(yōu)先級），sched_ss_low_ priority（背景優(yōu)先級），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個參數(shù)全部有效。

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

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

◎處于就緒態(tài)且優(yōu)先級為sched_priority的任務(wù)開始運(yùn)行后，該任務(wù)的最大運(yùn)行時間不超過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)先級鏈的鏈尾中，完成以上操作的時間點(diǎn)被稱為啟動時間（activation_time）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

本文介紹了一些典型的調(diào)度算法，同時闡述了在RTEMS嵌入式實(shí)時操作系統(tǒng)中實(shí)現(xiàn)零星服務(wù)器調(diào)度的方法。根據(jù)試驗(yàn)結(jié)果，可以看到該實(shí)現(xià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í)時操作系統(tǒng)及應(yīng)用開發(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ī)專項(xiàng)科研項(xiàng)目（MJ-S-2012-05）。