小型四軸飛行器系統(tǒng)任務(wù)實(shí)時調(diào)度算法的優(yōu)化

段天賜++韓曉煜++計詩嫣++王舳

摘要：由于小型四軸飛行器工作資源受限（由電池供電），因此對系統(tǒng)任務(wù)的調(diào)度會直接影響到整個系統(tǒng)的性能。我們對設(shè)計并實(shí)現(xiàn)的基于小型四軸飛行器的嵌入式實(shí)時操作系統(tǒng)內(nèi)核的任務(wù)調(diào)度進(jìn)行了測試。結(jié)果表明由于系統(tǒng)采用EDF（最短截止時間調(diào)度算法），在任務(wù)的執(zhí)行過程中會存在多次任務(wù)搶占導(dǎo)致任務(wù)中斷的情況，系統(tǒng)性能不佳。因此對其任務(wù)調(diào)度算法進(jìn)行改進(jìn)，用增加閾值的方法減少作業(yè)在開始執(zhí)行的時候所產(chǎn)生的任務(wù)搶占。實(shí)驗結(jié)果表明改進(jìn)后的任務(wù)調(diào)度算法，系統(tǒng)整體的性能得到了明顯的提升。

關(guān)鍵詞：四軸飛行器；EDF；實(shí)時調(diào)度；算法優(yōu)化

中圖分類號：TP316 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）32-0229-02

An Improved Task Scheduling Algorithm for small quadcopter

DUAN Tian-ci， HAN Xiao-yu， JI Shi-yan， WANG Zhu

（College of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China）

Abstract： Due to the battery powered，its important for small quadcopter to improve the performance of the system scheduling.We test the task scheduling which designs and implements based on the embedded real-time operating system kernel of small quadcopter. The result show the best real-time ---EDF， the task will be preempted repeatedly during the task execution.We improve the EDF by increasing the threshold for reducing the overhead of task preemption.The results of experimental show the performance of the system scheduling is improved by using the improved method.

Key words： small quadcopter； EDF； real-time scheduling； Algorithm optimization

小型四軸飛行器通常是一個具有四個旋翼，機(jī)身采用結(jié)構(gòu)簡單的十字支架形式，四個旋翼對稱的飛機(jī)。小型四軸飛行器以其結(jié)構(gòu)簡單、飛行平穩(wěn)、機(jī)動靈活、易于維護(hù)，具有能夠完成消防安保，無人快遞，農(nóng)藥噴灑，海上救援等復(fù)雜任務(wù)的優(yōu)點(diǎn)，被廣泛應(yīng)用于很多不同的領(lǐng)域。它具有普通直升機(jī)不可替代的優(yōu)點(diǎn)，例如體積小、造價低，能耗低，易于維護(hù)、安全性高，能以各種不同的姿態(tài)飛行，如懸停、側(cè)飛、倒飛等。另外，由于小型四軸飛行器是通過平衡四個旋翼產(chǎn)生的力來實(shí)現(xiàn)穩(wěn)定盤旋和精確飛行的，其飛行速度可以很低，能夠?qū)崿F(xiàn)垂直起降和定點(diǎn)懸停，可應(yīng)適用于封閉的或環(huán)境特別復(fù)雜的場合。同時，小型四軸飛行器也是嵌入式系統(tǒng)領(lǐng)域研究的熱點(diǎn)，吸引了國內(nèi)外眾多的科研機(jī)構(gòu)進(jìn)行研究[1，2]。

嵌入式系統(tǒng)（Embedded system），是一種完全嵌入受控器件內(nèi)部，為特定應(yīng)用而設(shè)計的專用計算機(jī)系統(tǒng)。由于小型四軸飛行器一般是由機(jī)身自帶的攝像頭采集圖形圖像信息，飛行器本身要對連續(xù)幀圖像進(jìn)行實(shí)時性處理，并作出相應(yīng)的反饋響應(yīng)和控制，因此研究小型四軸飛行器的嵌入式操作系統(tǒng)就顯得十分重要。

最小截止期優(yōu)先（Earliest Deadline First，EDF）調(diào)度算法是實(shí)時系統(tǒng)中應(yīng)用最廣泛的調(diào)度算法之一，涉及的領(lǐng)域包括工業(yè)網(wǎng)絡(luò)，多媒體傳輸?shù)缺姸喾矫妫鶕?jù)任務(wù)的搶占特性不同，EDF算法又分為搶占的EDF調(diào)度算法和非搶占的EDF調(diào)度算法兩種。搶占EDF調(diào)度算法已被證實(shí)是最優(yōu)的動態(tài)調(diào)度算法，但是搶占式DEF雖然調(diào)度靈活，CPU利用率高，但內(nèi)容轉(zhuǎn)換的開銷也遠(yuǎn)遠(yuǎn)大于非搶占式EDF，對內(nèi)存的需求也相對較高。

由于任務(wù)搶占而引起的額外系統(tǒng)開銷對由電池供電的小型四軸飛行器的性能造成很大影響[3]，故此，本文將主要針對EDF調(diào)度算法進(jìn)行優(yōu)化改進(jìn)，在滿足任務(wù)中各個作業(yè)均能在截止期完成的前提下，通過合理規(guī)劃和安排任務(wù)間的調(diào)度執(zhí)行，減少任務(wù)在執(zhí)行過程中的搶占次數(shù)，降低系統(tǒng)的額外開銷，提高飛行器的性能。

1 任務(wù)模型

任務(wù)集T =（T1，T2，T3，T4）中任務(wù)Ti 可用一個二元組（Ci，Di）描述.Ci是任務(wù)的周期Di是任務(wù)的執(zhí)行時間。用Wp，q去描述一個特定任務(wù)中的作業(yè)，即表示任務(wù)P一共有q個作業(yè)。例如，任務(wù)一中有三個作業(yè)，則w，1表示第一個作業(yè)，依此，第二 個和最后一個作業(yè)則可用w1，2和w1，3表示。

現(xiàn)在假設(shè)在一個處理器中，存在3個任務(wù)，T1（1，0.4），T2（2，06），T3（4，1）。任務(wù)組的循環(huán)周期為4秒。一個周期內(nèi)完成4個T1，2個T2，1個T3。結(jié)果圖1展示了0到3.8秒時間內(nèi)，任務(wù)的EDF調(diào)度算法執(zhí)行情況。

在時刻0，任務(wù)1，2，3同時進(jìn)入，此刻它們的EDF分別是0.6，1.4和3，因此先執(zhí)行任務(wù)1。在時刻0.4，任務(wù)1完成，任務(wù)2和任務(wù)3的EDF分別是1.0和2.6，因此先執(zhí)行任務(wù)2。在時刻1.0，任務(wù)2完成，任務(wù)1和任務(wù)3的EDF分別是0.6和2，因此先執(zhí)行任務(wù)1。在時刻1.4，任務(wù)1完成，此時只有任務(wù)3需要執(zhí)行。在時刻2.0，任務(wù)1，2，3的EDF分別是0.6，1.4，1.6，因此任務(wù)3被打斷，先執(zhí)行任務(wù)1。在時刻2.4，任務(wù) 1完成，任務(wù)2和任務(wù)3的EDF分別是1.0和1.2，因此先執(zhí)行任務(wù)2.在時刻2.6，任務(wù)2和任務(wù)3的EDF相等，為了避免重復(fù)循環(huán)的搶占，因此任務(wù)2不被打斷直至完成。在時刻3.0，任務(wù)2完成，任務(wù)1和任務(wù)3的EDF都是0.6，為避免重復(fù)循環(huán)搶占，因此任務(wù)1先執(zhí)行直至完成。在時刻3.4，此時只有任務(wù)3還需執(zhí)行其剩余額0.4秒。

2 優(yōu)化后的任務(wù)調(diào)度算法

為了避免因任務(wù)搶占而引起的額外開銷，在確保實(shí)時性的前提下，我們對EDF算法進(jìn)行了優(yōu)化。在以最早截止時間作為評判標(biāo)準(zhǔn)的前提下，設(shè)定一個閾值，EDF在此閾值外的時候，以當(dāng)前執(zhí)行的任務(wù)優(yōu)先。如遇到任務(wù)同時進(jìn)來并且EDF值相同的情況，再根據(jù)靜態(tài)設(shè)定的優(yōu)先級來判斷任務(wù)的執(zhí)行先后順序。本例中靜態(tài)優(yōu)先級為任務(wù)1>任務(wù)2>任務(wù)3，結(jié)果圖2展示了三個作業(yè)使用優(yōu)化后的EDF調(diào)度算法執(zhí)行情況。

設(shè)定閾值為0.1。在時刻0，任務(wù)1，2，3同時進(jìn)入，此刻它們的EDF分別是0.6，1.4和3，因此先執(zhí)行任務(wù)1。在時刻0.4，任務(wù)1完成，任務(wù)2和任務(wù)3的EDF分別是1.0和2.6，因此先執(zhí)行任務(wù)2。在時刻1.0，任務(wù)2完成，任務(wù)1和任務(wù)3的EDF分別是0.6和2，因此先執(zhí)行任務(wù)1。在時刻1.4，任務(wù)1完成，此時只有任務(wù)3需要執(zhí)行。在時刻2.0，任務(wù)1，2，3的EDF分別是0.6，1.4，1.6，三個任務(wù)的EDF都大于閾值，因此，任務(wù)3不被搶占，繼續(xù)執(zhí)行。在時刻2.4，任務(wù)3完成，任務(wù)1和任務(wù)2的EDF分別為0.2和1.0，因此先執(zhí)行任務(wù)1。在時刻2.8，任務(wù)1完成，只有任務(wù)2需要執(zhí)行。在時刻3.0，任務(wù)1和任務(wù)的EDF分別為0.6和0，6，兩個任務(wù)的EDF都大于閾值，因此，任務(wù)2不被搶占，繼續(xù)執(zhí)行。在時刻3.4.只有任務(wù)1需要繼續(xù)執(zhí)行0.4秒。

對比優(yōu)化前的EDF算法和優(yōu)化后的EDF算法，可以對比發(fā)現(xiàn)，優(yōu)化前的EDF算法被打斷一次，而優(yōu)化后的EDF算法因為選擇了一個比較好的閾值而沒有被打斷過。在保證系統(tǒng)實(shí)時性的前提下，選擇優(yōu)化后的EDF算法，可以減少因任務(wù)搶占而引起的系統(tǒng)額外開銷。

3 結(jié)語

本文對原有設(shè)計的小型四軸飛行器嵌入式實(shí)時操作系統(tǒng)內(nèi)核的任務(wù)調(diào)度算法進(jìn)行了優(yōu)化，提出了一種改進(jìn)的基于閾值進(jìn)行任務(wù)調(diào)度的EDF調(diào)度算法，旨在滿足所有任務(wù)均能在截止時間內(nèi)完全運(yùn)行的前提下，即保證實(shí)時性的前提下，優(yōu)化任務(wù)內(nèi)各個作業(yè)的開始執(zhí)行時間，以減少任務(wù)的搶占次數(shù)，降低小型四周飛行器在運(yùn)行過程中產(chǎn)生額外的任務(wù)搶占開銷和I/O延遲，實(shí)現(xiàn)小型四軸飛行器的節(jié)能，并且提高飛行器的性能。

參考文獻(xiàn)：

[1] Gomez-Balderas J E， Salazar S， Guerrero J A，et al. Vision-based autonomous hovering for a miniature quad-rotor [J]. Robotic， 2014， 32（1）： 43-61.

[2] Ordaz J， Salazar S， Mondie S， et al.Predictor-based position control of a quad-rotor with delays in GPS and vision measurements [J].Journal of intelligent & robotic systems， 2013， 70（1-4）： 13-26. Special Issue： SI.

[3]Jane W.S.Liu. Real-time systems [M]. Beijing ：Higher Education Press， 2003.