应用映射与任务调度综述

于千城

摘要：应用映射是CPS系统设计的关键步骤之一，是近年来国内外CPS系统研究、开发和应用的热门课题。应用映射工具的出现简化了CPS系统的设计过程，缩短了设计周期。应用映射理论的研究和任务调度算法的改进，对于提高CPS系统设计非常重要。该文主要关注应用映射中调度和分配两个关键步骤的优化问题。为了适应实时系统具有多种任务类型、约束复杂性的新特点和新要求，该文在分析了传统的常规可调度理论和方法的基础上，以任务特点为横轴，任务调度策略为纵轴讨论了各种任务调度方法（EDD，EDF，LDF，RM）。着重对实时调度理论中的任务调度技术进行了研究，并在此基础上阐述了评价任务调度算法的各种标准，如可行性分析，可调度性分析，资源利用率等。最后对多处理器调度进行了介绍，并从多处理器分组调度及全局调度两方面分析了多处理调度的算法设计及可调度性分析。

关键词：实时调度；可调度性分析；调度算法；多处理器调度

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2015）03-0248-04

Application Mapping and Task Scheduling

YU Qian-cheng

（Beifang University of Nationalities， Yinchuan 750021， China）

Abstract： Application mapping is a key step in CPS system design， and it has been one of the hot research point in the research， development and application of CPS system. The emergence application mapping tool simplifies the CPS system design process and shorten the design cycle. Theoretical research and application mapping task scheduling algorithm for improving the CPS system design is very important. This article focuses on the application mapping scheduling and allocation of two key steps of optimization problems.In order to adapt to new features and requirements of real-time systems with a variety of mission types， constraints and complexity. This article discusses kinds of task scheduling method （EDD，EDF， LDF，RM），base on the analysis of the traditional scheduling theory ， take task characteristics as the horizontal axis， scheduling strategy as the longitudinal axis. Focus on task scheduling techniques in real-time scheduling theory and elaborated evaluation of task scheduling algorithm， such as feasibility analysis， schedulability analysis， and resource utilization. At last it introduces multiprocessor scheduling， and analysis the multiprocessor scheduling algorithms and schedulability from multiprocessor division scheduling and global scheduling.

Key words：real-time scheduling；schedulability analysis；scheduling algorithm；multiprocessor scheduling

实时系统是指必须在精确时间约束内对外部环境事件做出响应的计算系统。因此实时系统的正确性不仅依赖于计算结果的正确性，同时也依赖于产生计算结果的时间。对实时系统的一个普遍的误解是“实时”即“快速”。事实上，快速计算以给定任务集的平均响应时间最小为目标，而实时计算则需要满足每个任务个体的时限需求。例如，文献[1]证明了，提高处理器的计算速度和缩短计算时间并不意味着系统新能的提升，在某些情况下甚至会降低系统的性能。

大多数实时系统都是基于一个实时的内核构建的，而这些内核最核心的功能就是任务管理和任务调度。任务调度作为决定实时系统性能的重要技术，一直被各学科专家广泛的研究。任务调度的分类方法按照其分类依据而有所不同：按照任务实时性要求可分为硬实时调度和软实时调度；根据任务是在一个还是多个处理器上运行可分为单处理器实时调度和多处理器实时调度，其中多处理器实时调度又可分为集中式调度和分布式调度；根据调度算法和可调度性判定是在任务运行时进行的还是任务运行前进行的，又分为静态调度、动态调度和混合调度；根据被调度任务是否可以相互抢占，可分为抢占式调度和非抢占式调度；根据任务请求到达的特性，可分为周期性任务调度和非周期性任务调度。 本文以任务的特点（周期性任务和非周期性任务）为横轴，以任务调度策略（包括时钟驱动的调度，固定优先级调度，动态优先级调度）为纵轴来讨论各种任务调度方法。在此基础上阐述了评价任务调度算法的各种标准，如可行性分析，可调度性分析，资源利用率等等。

1 时钟驱动的调度

时钟驱动的调度（clock-driven）是指在系统开始执行之前，选择一个特定的时刻来决定哪一个作业在何时执行。在一个典型的时钟驱动系统里，所有实时任务的参数都是固定且已知的。作业的调度时间表被脱机计算并保存下来，并在运行时使用[2]。根据该调度算法，调度程序在每一个调度决策时刻调度作业运行。

时钟驱动的调度策略的实现方式是利用一个可编程的时钟发出的周期性时钟中断来控制调度器运行，并且调度器维护一个内部的时间值来计算任务周期和决定何时调用这些任务，这种实现方式可以继续被细分为时钟驱动调度和有计数器的时钟驱动调度。时钟驱动调度使用一个周期时钟发出的中断来中断系统运行并调用调度器来更新系统时间，并在需要时重新调度。有计数器的时钟驱动调度维护一个计数器用来限制调度点的数量。在每一个调度点，计数器的值被初始化为到达下一个任务截止期限的时钟周期数。当每一次时钟中断发生时，计数器的值都会递减；当计数器的值减为[0]时，调度器被触发。

时钟驱动的调度是一种静态调度，其调度开销非常小，概念简单，可预测性好，对于实时任务参数非常清楚且稳定的情况下，时间驱动调度是很好的选择。但也有不足之处，包括：作业的释放时间必须固定，所有周期任务组合必须事先预知，因此缺乏灵活性；另外，如果系统环境在运行时出现一些变化，就可能引起整个系统调度失败。

2 非周期性任务的优先级驱动调度

2.1 最早完成期限算法（Earliest Due Date）

EDD算法针对的是最简单的任务模型，即一个非周期的任务集合在单个处理器上调度，要求让最大延迟最小化。所有的任务都在同一时间到达，但是这些任务所需的CPU时间以及任务期限（deadline）是不相同的。除此以外没有其他的约束，因此任务之间是没有依赖关系的，即任务是各自独立的，并且任务没有互斥访问资源的限制。由于所有的任务都是在同一时刻到达的，因此不存在任务的抢占问题。

Jackson[3]在1955年发明了一个简单的算法，来解决这种任务模型，即最早完成期限算法（EDD算法）：给定一个相互独立的任务集合，从最小化最大延迟的标准来看，只要按照非降序的任务完成期限来执行这些任务，则这种调度必然是最优的。用EDD算法构造最优调度的复杂度在于根据任务的完成期限对任务排序，因此构造包含[n]个任务的EDD算法的复杂度为[O（nlogn）]。

2.2 最早期限优先算法（Earliest Date Frist）

EDD算法解决的是最简单的任务模型的调度，若任务的到达时间不相同，即任务会在执行期的任意时刻到达，则必定会发生抢占的情况。Horn在1974年发明了最早期限优先算法（EDF）来解决包含[n]个相互独立的任务的任务集在单处理器上的调度问题，系统中的任务到达时间是动态的，且任务可被抢占。Dertouzos在1974年证明了EDF算法的最优性[4]。EDF算法的复杂度要根据就绪队列的数据结构来计算：如果就绪队列用列表来实现，则每个任务的复杂度是[O（n）]；若就绪队列使用堆来实现，则每个任务的算法复杂度是[O（nlogn）]。

2.3 不可抢占的调度

在不允许抢占的、有任意到达时间的任务集进行调度时，最小化最大延迟以及找到一个可行调度算法是NP难解的。在这种情况下，EDF算法不再是最优算法，而且就算存在可行的调度，也不可能由EDF算法来生成。但是Martel 证明了在不允许空闲的算法（non-idle algorithm，即当系统中存在活动的任务时就不允许处理器空闲 ）前提下，EDF算法对于非抢占的任务模型是最优的[5]。

若任务到达时间是已知的，则非抢占的调度可用分支限界法来解决，但这种算法只在平均计算时间上较优，而在最坏情况下则为指数复杂度。Bratley等人[6]给出了一个建议的算法，能在非抢占，任意到达的任务集上找到一个可行的调度算法。但前提是必须知道所有的任务参数，包括到达时间。

2.4 带优先约束的调度

对存在优先约束关系的，同一时间到达的任务集，寻找一个最优的调度算法通常是NP难解的。但是对任务做了一定的假设之后，可以找出在多项式时间内解决问题的最优算法。例如最迟期限算法和带优先约束的EDF算法。

2.4.1 最迟期限算法（Latest Deadline First）

LDF是Lawler在1973年发明的算法[7]，其任务模型是任务在相同时间到达，且任务之间存在优先约束。其思路是将所有任务的优先约束关系用有向无环图（DAG）来表示，用尾插队列来对任务排序。从图中的叶子节点（即没有后继的节点或者其后继都已经被选择了的节点）开始搜索，寻找完成期限最迟的任务放入队尾。这个过程一直重复到所有的任务节点都被放入队列。在运行时，任务被从队头取出执行，这样就能保证最早放入队列的任务最后被执行。在同样的优先约束条件下，使用EDF算法所得到的最大任务延迟大于使用LDF算法得到的最大任务延迟。

2.4.2 带优先约束的EDF算法

只有在任务是可抢占的情况下，对带有优先约束关系且动态变化的任务设计多项式时间复杂度的算法才是可能的。1990年，Chetto，Silly，和Bouchentouf设计了一个算法解决了这个问题[8]。其基本思路是将带有优先约束的原始任务集的任务的时间参数进行适当的修改，使这些任务变成相互独立的任务，然后对这些任务使用EDF算法。从原始任务集到新任务集的转换算法能够保证在遵循原始任务集的优先约束关系的基础上，新的任务集与原始任务集在可调度性上保持一致性。一般来说是对任务到达时间和任务完成期限进行修改，以保证每个任务都不可能在它的前驱之前执行，并且不可能抢占它的后继任务。

2.5 非周期性任务调度总结

各种非周期性调度算法的算法复杂度及约束条件如图1所示，EDD算法的约束条件最少，所有任务在同一时间到达，且相互独立，其任务调度算法的设计就相对简单。如果任务到达时间是不同的，则无法采用静态调度，只能在运行时进行调度，EDF算法就是典型的动态调度算法。不可抢占的任务集的调度算法设计要比可抢占的任务集难度大，同时设计出的调度算法复杂度也高于前者。任务间的优先约束关系给任务调度算法的设计带来更大的难度，对于同时到达的任务，可使用LDF算法，而对于不同时间到达的任务，使用带约束的EDF算法也能达到同样的算法复杂度。

[＼&sync ，activation＼&preemptive

async ，activation＼&non- preemptive

async ，activation＼&

Independent＼&EDD（Jackson55）

[O（nlogn）]

Optimal＼&EDF（Horn74）

[O（n2）]

Optimal＼&Tree search

（Bratley71）

[O（nn！）]

Optimal ＼&

Precedence

constraints＼&LDF（Lawler73）

[O（n2）]

Optimal＼&EDF*

（Chetto et al.90）

[O（n2）]

Optimal＼&Spring

（Stankovic&Ramamritham87）

[O（n2）]

Heuristic＼&]

图1 Scheduling algorithms for aperiodic tasks.

3 周期性任务的优先级驱动调度

周期性任务是实时系统中最重要同时也是最常用的任务类型，常用于周期性的采集传感器数据，反馈控制以及系统监控等功能的完成。经典的周期性任务调度算法有速率单调算法（RM算法）和最早期限优先算法（EDF算法）。

3.1单调速率算法（Rate Monotonic）

RM算法使用了一个简单的规则来安排任务的优先级：让使用频率高的任务具有更高的优先级，即周期越短的任务的优先级就越高。由于任务的周期是一个常量，因此RM算法是一个固定优先级的算法：任务的优先级在执行之前就被分配，并且在执行期间不会改变。RM算法本质上是可抢占的：当前执行的任务会被新来的周期更短的任务所抢占。

1973年，Liu和Layland[9]明了RM算法在所有的固定优先级调度算法中是最优的，并且证明了如果一个任务集不能用RM算法调度，则必定不能用其它的固定优先级算法调度。

对于RM算法的可调度性判定，Liu和Layland给出了一个充分条件，即CPU利用率最小上界。随后，Burchard，Bini等人相继提出了改进的CPU最小上界[10]。然而这些最小上界算法都是在最坏情况下考察可调度性，是悲观的考察方法。1997年Han和Tyan提出了时间复杂度为多项式的SR算法和DCT算法[11]，这两种算法基于可调度的充分但不必要条件，其时间复杂度比最小上界算法差，但比确切算法好；使用范围比最小上界法广，但不如确切算法。

3.2 EDF算法

最早期限优先算法选择绝对完成期限最早的任务优先执行，因此它是一个动态调度算法，并且执行在可抢占的模式下。即在当前任务执行期间，只要有一个具有更早的期限的任务被激活，则当前任务会被抢占。由于EDF算法没有对任务的周期性作出任何假设，所以它既可以用于非周期性任务调度，也可以用于周期性任务调度。基于同样的原因，EDF算法的最优性也适用于周期性任务。

3.3 RM算法与EDF算法的比较

对相互独立的任务所构成的可抢占的周期性任务集，固定优先级调度和动态优先级调度都能够产生其解决方案。固定优先级算法的优点在于其实现上的简单性，而动态优先级算法则比较适用于任务量较大的系统或者处理器速度较慢的系统；从可调度性分析的角度来看，对于简单的相互独立的且任务期限等于任务周期的任务集合。在更一般的情况下，如任务期限小于等于任务周期，两种算法的复杂度都是多项式时间。在固定优先级算法情况下，任务集的可行性可以使用响应时间来进行分析，而对于动态优先级调度则可以使用处理器需求标准。从处理器利用率来说，EDF可以最大的利用处理器的带宽，而RM算法的调度在最坏情况下只能保证小于69%的利用率。在平均情况下，Lehoczky， Sha和Ding[12]所做的研究证明了对于随机产生参数的任务集，RM算法能够达到88%的处理器利用率。

4 多处理器调度

多处理器系统已经成为处理复杂实时系统应用的有效手段，实时多处理器系统的调度算法已经成为一个重要研究课题。对于多处理器系统来说，单处理器系统中的任务模型并没有变化，还是可以分为周期性任务和非周期性任务。多处理器系统调度的主要障碍就是其任务调度算法要比单处理器系统复杂，因为在多处理器系统中设计调度算法不仅要对任务集调度排序，还需要确定哪些任务需要使用哪些处理器进行调度。文献[13]指出基于多处理器的调度问题主要是确定任务在哪个处理器上执行，以及何时执行的问题。对于大型周期性的固定优先级任务集在多处理器上的可抢占调度问题认为是NP困难的。因此，需要采用启发式方法解决此类问题。对于周期性任务来说，其各项参数（到达时刻，计算时间、截止期限）具有一定的规律性，因此可以利用单处理器可调度的充分必要条件对多处理器系统中的周期性任务进行调度。而对于动态到达的非周期性任务，只能在运行时决定其处理器分配及调度策略。多处理器系统的调度机制一般可分为两种类型：分组调度和全局调度。

4.1多处理器系统分组调度

多处理器分组调度方案是指系统中的全部任务由任务分配算法预先划分到处理器，每一个处理器可以运行不同或者相同的单处理器调度算法，一个任务的所有出现都在同一个处理器上执行，即不允许任务在多个处理器上迁移。分组调度方案主要用于任务集参数已知的静态优先级调度，对任务集进行脱机分配。分组调度方案的性能由两个因素决定：给处理器分配任务的任务分配算法和每个处理器上决定任务执行顺序的任务调度算法。对于已分配到每个处理器上的任务来说，其可调度性判定及利用率可使用单处理器下的方法来进行研究。因此对于固定优先级的多处理器分组调度方案来说，核心问题就是任务分配算法的设计。这个问题是经典组合优化理论中的装箱问题的变体，即将[N]种尺寸已知的物品装入容量已知的[k]个箱子里。由于装箱前已经获得所有物品的信息，所以可以先按照物品的某个属性排序，按照某种策略装入某个箱子。基于已知条件的装箱策略有下次适合（Next-Fit，NF）算法，最先适合（First-Fit，FF）算法，及任意适合（Any-Fit，AF）算法。基于装箱问题的NF算法和FF分组方法，文献[14]提出了两种多处理器周期性任务分配算法RMNF和RMFF，这两种算法的复杂度都为[O（nlogn）]。

分组调度策略的缺点在于：首先，任务集的特性必须是已知的，而对于很多实时应用来说这是不可能的；其次，任务分配算法复杂度高；最后，会出现某个处理器空闲而另一个处理器的任务来不及处理的情况，造成低的资源利用率。

4.2多处理系统全局调度

全局调度策略是指实时任务的每一次出现都在不同的处理器上执行，所有处理器上只运行同一种调度算法。任务在未执行完之前可以被抢占并且可以在不同的处理器间迁移，同时假定多处理器间共享内存的开销非常低，这种方案的主要目标是为多处理器系统产生一个能够满足它们各自期限的任务分配。

对于变化复杂的动态系统，采用全局调度是一个更好的选择。这种方式下，待处理任务被放入一个全局的队列，被调度器取出并分配给可用的处理器执行。这种方式在本质上保证了处理器的负载均衡，并且只要队列中存在就绪任务，就不会有处理器空闲状态。

5 总结与展望

实时系统的调度理论一直是实时系统的核心研究课题。对实时系统的理论研究集中在如何提高资源利用率，如何设计好的调度算法，如何进行可调度性分析。适用于单处理器调度的某些经典调度算法，如RM算法，EDF算法等也被运用于多处理器调度。但多处理器调度并不是单处理器调度算法的简单扩充。对于动态到达的偶发任务的调度，需要使用各种启发式的方法来设计近似最优的调度算法。本文讨论了几个典型的、经典的单处理器调度算法，并对多处理器调度进行了介绍。认为多处理器的调度算法设计以及可调度性分析方面虽然已经有众多的研究，但也还存在很多未解决的问题。因此多处理器调度是当前实时系统调度的研究热点。

参考文献：

[1] Stankovic J A. Misconceptions about real-time computing[J]. IEEE Computer， 1988，21（10）.

[2] Jane W S.实时系统[M]. 姬孟洛，李军，译.北京：高等教育出版社， 2003：12 .

[3] Jackson J R. Scheduling a production line to minimize maximum tardiness[C]. Management Science Research Project 43， University of California， Los Angeles， USA， 1955.

[4] Dertouzos M L. Control robotics： the procedural control of physical processes. Information Processing， 1974：74.

[5] Bini G， Buttazzo C， Buttazzo G. A hyperbolic bound for the rat e monotonic algorithm[C]// IEEE Proc. 13th Euromicro Conf. Real Time Systems. Oakland： IEEE Computer Society Press， 2011 ：59–68.

[6] Bratley P， Florian M， obillard P R. Scheduling with earliest start and due date constraints. Naval Research Quarterly， 1971， 18（4）.

[7] Lawler E L. Optimal sequencing of a single machine subject to precedence constraints[J]. Managements Science， 1973， 19.

[8] Chetto H， Silly M， Bouchentouf T. Dynamic scheduling of real–time tasks under precedence constraints[J]. Journal of Real–Time Systems， February， 1990.

[9] Liu C L， Layland J W.eduling algorithms for multiprogramming in a hard–real–time environment[J]. Journal of the Association for Computing Machinery， 1973， 20（1）.

[10] Burchard A， Liebeherr J，Oh Y， et al. New strategies f or assigning real time t asks to multiprocessor systems[J]. IEEE Trans. Computers， 1995， 44（12） ： 1429–1442.

[11] Han C C， Tyan H Y. A better polynomial time schedulability test for real time fixed– priority scheduling algorithm .In： Proc[C].18th IEEE Real Time Systems Symposium. Oakland： IEEE Computer Society Press， 1997：36–45.

[12] Lehoczky J P， Sha L， Ding Y. The rate monotonic scheduling algorithm： Exact characterization and average case behavior [C]// Proc. 10th IEEE Real Time Systems Symposium. Oakland： IEEE Computer Society Press， 1989：166–171.

[13] Ramamritham K. Scheduling algorithms and operating systems support for Real Time Systems[C]. Proceeding of IEEE， 1994，82（1）：55–67.

[14] Dhall S K， Liu C L. On a real–time scheduling problem[J].Operations Research， 1978， 26（l）：127–140.