基于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）。