基于RTEMS嵌入式實時操作系統實現零星服務器調度的方法

楊弋

（中國航空工業集團公司西安航空計算技術研究所，陜西西安，710065）

基于RTEMS嵌入式實時操作系統實現零星服務器調度的方法

楊弋

（中國航空工業集團公司西安航空計算技術研究所，陜西西安，710065）

針對嵌入式實時操作系統在多周期任務及多非周期任務的場景下，既要保證周期任務在截止期內能夠及時響應，又要保證非周期任務能夠即時處理。目前的主流調度算法存在局限性。零星服務器調度算法作為一種指定執行預算及補充周期的非周期任務的調度算法，可以較好的滿足即時響應非周期任務，同時保證系統內其他周期任務的響應。本文簡述了在RTEMS嵌入式實時操作系統下實現零星服務器調度的方法，并對該算法進行測試，看是否達到了預期要求。

RTEMS;調度算法；IEEE；Sporadic Server

0 引言

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

1 調度算法概述

目前嵌入式實時操作系統的調度算法主要有固定優先級和動態優先級調度算法。

1.1 固定優先級調度算法

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

1.2 動態優先級調度算法

動態優先級調度算法主要以截止期最早最優先算法（EDF：Earliest Deadline First）為代表，該算法按照周期任務的截止期（deadline）來分配優先級，截止期越短的周期任務優先級越高。在EDF調度算法中，總是優先響應截止期最低的周期任務。

1.3 非周期任務調度算法

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

背景服務（Background Service）：背景服務算法創建了一個低優先級任務，在CPU空閑時該任務被調度。如果系統中存在多個周期很長的周期任務長期占用CPU，則該低優先級任務有可能一直不參與調度。

輪詢服務器（Polling Server）：輪詢服務器算法創建了一個周期任務來處理非周期請求，該周期任務在周期內處理到達的非周期請求，如果在該周期內無非周期請求，則掛起當前任務直到下一個周期開始解掛該任務。如果在任務掛起后產生非周期請求，則該請求必須在下一個周期開始才會被處理。

延期服務器（Deferrable Server）：延期服務器算法與輪訓服務器（Polling Server）類似，區別在于該算法創建了一個具有執行預算Qs，周期為Ts的周期任務。非周期請求到達后，如果Qs仍有執行預算，則對該請求進行處理，直到Qs耗盡。Qs在每個周期開始時進行補充。

零星服務器（Sporadic Server）：該算法與延期服務器（Deferrable Server）類似，區別在于零星服務器算法相比延期服務器，執行預算Qs的補充方式更加復雜。

2 RTEMS嵌入式實時操作系統的調度策略

RTEMS嵌入式實時操作系統包含兩種調度策略：基于優先級的可搶占調度策略以及時間片輪轉調度策略。

基于優先級的可搶占調度：基于優先級的可搶占調度策略給每個任務分配一個固定的優先級，不同優先級按照優先級的高低順序調度，相同優先級按照先來先服務調度。如果出現有更高優先級任務處于就緒狀態時，則停止當前任務的運行，把CPU控制權交給具有更高優先級的任務。

時間片輪轉調度：時間片輪轉調度策略是指當有兩個或多個就緒任務具有相同優先級，且它們是就緒任務中優先級最高的任務時，調度器按照這組任務的先后順序調度各個任務，并且使每個任務運行一段時間，這段時間稱為時間片（time slicing）。

3 零星服務器調度策略的概念以及實現方法

Sprunt,B.Sha,L.,and Lehoczky在1989年提出了零星服務器調度策略，1999年IEEE將零星服務器調度引入至IEEE1003.1d標準中。在該標準的13.2.4節中詳細說明了零星服務器調度的機制。標準中定義了四種調度策略：SCHED_FIFO（基于優先級搶占），SCHED_RR（時間片輪轉），SCHED_SPORADIC（零星服務器調度），SCHED_OTHER（其他）。

IEEE1003.1d標準中定義了sched_param結構，該參數包含5個參數：sched_priority（優先級），sched_ss_low_ priority（背景優先級），sched_ss_repl_period（補充周期），sched_ss_init_budget（初始預算），sched_ss_max_repl（最大補充事件數）。如果調度策略為SCHED_FIFO或SCHED_RR，則只有sched_priority有效，如果調度策略為SCHED_SPORADIC，則以上5個參數全部有效。

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

圖1 任務處于零星服務器調度策略下的調度方法

◎處于就緒態且優先級為sched_priority的任務開始運行后，該任務的最大運行時間不超過sched_ss_init_budget。

◎任務從阻塞態轉變為就緒態或執行一次補充執行預算的操作后，任務應被插入至sched_priority優先級鏈的鏈尾中，完成以上操作的時間點被稱為啟動時間（activation_time）。

◎當處于sched_priority優先級的任務被高優先級任務搶占，將該任務插入至sched_priority優先級鏈的鏈首，并計算剩余的執行預算，此時執行預算可能會被耗盡。

◎當處于sched_priority優先級的任務被阻塞，計算剩余的執行預算，并執行一次補充執行預算的操作，此時執行預算可能會被耗盡。

◎當處于sched_priority優先級的任務耗盡執行預算時，將任務插入至sched_ss_low_priority優先級鏈的鏈尾，并執行一次補充執行預算的操作。

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

◎實現零星服務器調度雙優先級切換的功能

任務耗盡執行預算或存在超過sched_ss_max_repl個未決補充執行預算事件時，需要降低任務的優先級為sched_ss_low_ priority，任務處于背景優先級時，在系統時鐘到達指定的補充周期后，需要將任務優先級抬升至sched_priority優先級。通過調用RTEMS操作系統提供的_Thread_Change_priority()服務來進行優先級的轉換操作。在任務降低優先級為sched_ss_low_ priority后，使用RTEMS操作系統提供的定時器功能創建定時器，設置定時器觸發時間為補充周期減去當前系統時間，并掛接定時器處理程序，定時器處理程序用于抬升任務的優先級，并計算下一次補充周期及補充任務的執行預算，圖2表示了任務優先級的切換以及定時器操作的流程。

圖2 任務優先級的切換以及定時器操作

◎實現計算零星服務器調度的運行時間及補充事件操作的功能

RTEMS操作系統提供了系統時鐘為應用軟件提供時間服務，每個時鐘周期會產生時鐘中斷，RTEMS操作系統提供了設置和獲取系統時間，通知內核一個tick信號等服務。在觸發時鐘中斷后，需要記錄任務的運行時間及任務剩余的執行預算；如果任務正處于就緒態，還需要記錄任務的啟動時間（activation_time）。任務被更高優先級任務搶占，或被阻塞的情況下，需要生成一個補充事件。利用RTEMS操作系統提供的鏈管理服務，創建一條鏈表，鏈表的每一個結點代表任務的補充事件，補充事件記錄補充的時間點及補充的時間大小。當系統時間到達補充時間點時，從鏈表取出一個結點并對任務的執行預算進行補充，圖3表示任務所需的一些擴展數據，圖4表示在時鐘中斷處理中針對零星服務器調度的擴展操作。

圖3 任務擴展的零星服務器調度數據

圖4 時鐘中斷處理程序中對運行時間及補充事件的操作

4 試驗結果

我們在系統中創建一個具有零星服務器調度的任務和一個非周期任務，給定零星服務器調度的任務的調度參數分別為，優先級=100，背景優先級=50，補充周期=6s，初始預算=4s，最大補充事件數：40，非周期任務優先級為90。任務運行的執行預算變化如圖5所示。

圖5 任務運行的執行預算變化圖

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

5 結束語

本文介紹了一些典型的調度算法，同時闡述了在RTEMS嵌入式實時操作系統中實現零星服務器調度的方法。根據試驗結果，可以看到該實現方法基本滿足了零星服務器調度的功能。

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

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

[3]羅蕾主編.嵌入式實時操作系統及應用開發[M].第2版.北京:航空航天大學出版社, 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

航空科學基金項目資助:工信部民用飛機專項科研項目（MJ-S-2012-05）。