小型四轴飞行器系统任务实时调度算法的优化

段天赐++韩晓煜++计诗嫣++王舳

摘要：由于小型四轴飞行器工作资源受限（由电池供电），因此对系统任务的调度会直接影响到整个系统的性能。我们对设计并实现的基于小型四轴飞行器的嵌入式实时操作系统内核的任务调度进行了测试。结果表明由于系统采用EDF（最短截止时间调度算法），在任务的执行过程中会存在多次任务抢占导致任务中断的情况，系统性能不佳。因此对其任务调度算法进行改进，用增加阈值的方法减少作业在开始执行的时候所产生的任务抢占。实验结果表明改进后的任务调度算法，系统整体的性能得到了明显的提升。

关键词：四轴飞行器；EDF；实时调度；算法优化

中图分类号：TP316 文献标识码：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

小型四轴飞行器通常是一个具有四个旋翼，机身采用结构简单的十字支架形式，四个旋翼对称的飞机。小型四轴飞行器以其结构简单、飞行平稳、机动灵活、易于维护，具有能够完成消防安保，无人快递，农药喷洒，海上救援等复杂任务的优点，被广泛应用于很多不同的领域。它具有普通直升机不可替代的优点，例如体积小、造价低，能耗低，易于维护、安全性高，能以各种不同的姿态飞行，如悬停、侧飞、倒飞等。另外，由于小型四轴飞行器是通过平衡四个旋翼产生的力来实现稳定盘旋和精确飞行的，其飞行速度可以很低，能够实现垂直起降和定点悬停，可应适用于封闭的或环境特别复杂的场合。同时，小型四轴飞行器也是嵌入式系统领域研究的热点，吸引了国内外众多的科研机构进行研究[1，2]。

嵌入式系统（Embedded system），是一种完全嵌入受控器件内部，为特定应用而设计的专用计算机系统。由于小型四轴飞行器一般是由机身自带的摄像头采集图形图像信息，飞行器本身要对连续帧图像进行实时性处理，并作出相应的反馈响应和控制，因此研究小型四轴飞行器的嵌入式操作系统就显得十分重要。

最小截止期优先（Earliest Deadline First，EDF）调度算法是实时系统中应用最广泛的调度算法之一，涉及的领域包括工业网络，多媒体传输等众多方面，根据任务的抢占特性不同，EDF算法又分为抢占的EDF调度算法和非抢占的EDF调度算法两种。抢占EDF调度算法已被证实是最优的动态調度算法，但是抢占式DEF虽然调度灵活，CPU利用率高，但内容转换的开销也远远大于非抢占式EDF，对内存的需求也相对较高。

由于任务抢占而引起的额外系统开销对由电池供电的小型四轴飞行器的性能造成很大影响[3]，故此，本文将主要针对EDF调度算法进行优化改进，在满足任务中各个作业均能在截止期完成的前提下，通过合理规划和安排任务间的调度执行，减少任务在执行过程中的抢占次数，降低系统的额外开销，提高飞行器的性能。

1 任务模型

任务集T =（T1，T2，T3，T4）中任务Ti 可用一个二元组（Ci，Di）描述.Ci是任务的周期Di是任务的执行时间。用Wp，q去描述一个特定任务中的作业，即表示任务P一共有q个作业。例如，任务一中有三个作业，则w，1表示第一个作业，依此，第二 个和最后一个作业则可用w1，2和w1，3表示。

现在假设在一个处理器中，存在3个任务，T1（1，0.4），T2（2，06），T3（4，1）。任务组的循环周期为4秒。一个周期内完成4个T1，2个T2，1个T3。结果图1展示了0到3.8秒时间内，任务的EDF调度算法执行情况。

在时刻0，任务1，2，3同时进入，此刻它们的EDF分别是0.6，1.4和3，因此先执行任务1。在时刻0.4，任务1完成，任务2和任务3的EDF分别是1.0和2.6，因此先执行任务2。在时刻1.0，任务2完成，任务1和任务3的EDF分别是0.6和2，因此先执行任务1。在时刻1.4，任务1完成，此时只有任务3需要执行。在时刻2.0，任务1，2，3的EDF分别是0.6，1.4，1.6，因此任务3被打断，先执行任务1。在时刻2.4，任务 1完成，任务2和任务3的EDF分别是1.0和1.2，因此先执行任务2.在时刻2.6，任务2和任务3的EDF相等，为了避免重复循环的抢占，因此任务2不被打断直至完成。在时刻3.0，任务2完成，任务1和任务3的EDF都是0.6，为避免重复循环抢占，因此任务1先执行直至完成。在时刻3.4，此时只有任务3还需执行其剩余额0.4秒。

2 優化后的任务调度算法

为了避免因任务抢占而引起的额外开销，在确保实时性的前提下，我们对EDF算法进行了优化。在以最早截止时间作为评判标准的前提下，设定一个阈值，EDF在此阈值外的时候，以当前执行的任务优先。如遇到任务同时进来并且EDF值相同的情况，再根据静态设定的优先级来判断任务的执行先后顺序。本例中静态优先级为任务1>任务2>任务3，结果图2展示了三个作业使用优化后的EDF调度算法执行情况。

设定阈值为0.1。在时刻0，任务1，2，3同时进入，此刻它们的EDF分别是0.6，1.4和3，因此先执行任务1。在时刻0.4，任务1完成，任务2和任务3的EDF分别是1.0和2.6，因此先执行任务2。在时刻1.0，任务2完成，任务1和任务3的EDF分别是0.6和2，因此先执行任务1。在时刻1.4，任务1完成，此时只有任务3需要执行。在时刻2.0，任务1，2，3的EDF分别是0.6，1.4，1.6，三个任务的EDF都大于阈值，因此，任务3不被抢占，继续执行。在时刻2.4，任务3完成，任务1和任务2的EDF分别为0.2和1.0，因此先执行任务1。在时刻2.8，任务1完成，只有任务2需要执行。在时刻3.0，任务1和任务的EDF分别为0.6和0，6，两个任务的EDF都大于阈值，因此，任务2不被抢占，继续执行。在时刻3.4.只有任务1需要继续执行0.4秒。

对比优化前的EDF算法和优化后的EDF算法，可以对比发现，优化前的EDF算法被打断一次，而优化后的EDF算法因为选择了一个比较好的阈值而没有被打断过。在保证系统实时性的前提下，选择优化后的EDF算法，可以减少因任务抢占而引起的系统额外开销。

3 结语

本文对原有设计的小型四轴飞行器嵌入式实时操作系统内核的任务调度算法进行了优化，提出了一种改进的基于阈值进行任务调度的EDF调度算法，旨在满足所有任务均能在截止时间内完全运行的前提下，即保证实时性的前提下，优化任务内各个作业的开始执行时间，以减少任务的抢占次数，降低小型四周飞行器在运行过程中产生额外的任务抢占开销和I/O延迟，实现小型四轴飞行器的节能，并且提高飞行器的性能。

参考文献：

[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.