优先级周期性互换的实时多任务调度方法研究(编辑修改稿)

优先级周期性互换的实时多任务调度方法研究(编辑修改稿)内容摘要：

用的操作系统中所采用的主流多任务调度策略进行了研究与分析，在此基础上提出了优先级周期性互换的多任务调度算法。 时间片轮转法是一种主要用于分时系统中的多任务调度算法，常见于服务器中的多任务调度算法。 该算法是最公平、最简单容易实现的调度算法。 它的工作原理是将系统处理任务的时间分成等长时间片，并且维护一个任务就绪队列表，按照任务的释放时间进行排队。 进入队列最早的任务首先分配时间片执行，如果在给定时间片内任务未执行完，任务就被释放，排列到任务就绪队列表的最后一个位置，原先的第二个任务开始执行，如此往复。 如果给定时间内任务已经执行完毕，处理器马上进行切换下个任务进行执行。 时间片是分时系统中的一个重要的参数，该参数的确定一般依据系统的处理能力、系统对相应时间的要求和就绪队列中进程数目三个方面进行参考。 通常为几十毫秒到几百毫秒数量级，不能取的过大或过小。 对于时间片轮转法，很明显一个问题：假定时间片大小为t，某个任务执行完成所需要的执行时间是T。 当T/t等于整数时，任务执行及时；当T/t大于t/2时，任务执行也算及时；当T/t小于t/2时，此时任务要完成就必须等到下个执行周期分到的时间片进行执行，显然对于任务有效执行很不利。 针对上述问题，显而易见的解决方法就是：当任务的一个时间片用完后，就对该任务的剩余执行时间和时间片进行比较，若任务剩余执行时间大于等于t/2时，就调用下个任务执行；若任务剩余执行时间小于t/2时，就在该时间片后添加和任务剩余执行时间等长的时间段将剩余的任务执行完毕。 这样一来就大大减小了任务执行周期，提高了任务执行效率[32]。 先来先服务调度算法和通常意义上的排队是一样的。 处理器按照任务的释放时间进行排队，建立一个就绪队列表。 最先到达的任务最先占用处理器进行执行，不论该任务的执行时间有多长，直到该任务执行完毕或者挂起才释放处理器。 处理器加载下个任务进行处理，如此一直执行完所有任务。 先来先服务调度算法只需要依赖任务的释放时间进行调度，所以实现比较容易。 先来先服务任务调度算法存在以下问题：从形式上看，它的调度策略符合一般的排队模型，比较公平。 但是，假如最先到的任务是一个需要长响应时间的任务，后面的任务均是响应时间很短的任务。 先来先服务调度算法为了执行一个长响应时间的任务而造成了后面所有短响应时间任务的很大延迟。 在这个意义上讲，先来先服务任务调度算法又是不公平的。 所以，先来先服务任务调度算法在实际系统中很少单独用，通常的做法都是将先来先服务任务调度算法和其他算法相结合。 比如基于优先级任务调度算法中，在相同优先级之间采用先来先服务调度算法。 单调速率调度算法被证明是最优静态实时调度算法。 所谓静态是指实时操作系统为所有任务分配的优先级是根据某种算法得出，在运行过程中任务的优先级不再发生变化。 其后有很多研究人员基于单调速率调度为基础进行算法的改进和优化。 单调速率调度算法是由Liu和Layland在“Scheduling Algorithm for Multiprogramming in a Hard Real Time Environment”提出的。 实时操作系统中所处理的任务优先级是根据任务的周期决定的，任务的周期越短优先级越高。 另外，单调速率调度算法是基于优先级抢占式任务调度算法，低优先级任务在执行过程中允许随时被高优先级任务中断。 单调速率调度算法是在如下条件下提出的：一、在单个处理器中，所有的任务都是周期性运行的。 二、忽略上下文切换时间。 三、任务的执行时间是恒定的。 四、任务之间相互独立，没有数据交换或者资源互斥。 五、任务截止期限都在它们周期的结束点上。 六、抢占式调度算法，优先级最高的就绪任务一定会被选择执行。 单调速率算法的核心是通过周期这个唯一因素来决定优先级高低，任务周期越短相应的优先级就越高。 在单调速率调度中，被调度任务集满足下面的条件，则可调度[33]：这个条件是充分而非必要的，利用单调速率算法调度的必要条件是：。 单调速率调度算法对应的任务数与CPU最高利用率任务数123458，n表示系统中任务个数。 当系统中的任务数趋于无穷时。 该极限值表明，实时操作系统要使用单调速率调度算法进行多任务调度，那么所有任务的执行时间与任务周期比值之和不能超过ln2。 负责，系统采用单调速率调度算法将失效。 如果系统中还有一些任务对时间没有要求，也可能使得处理器的利用率达到100％。 处理器利用率一旦达到100％，就导致系统不能再添加新任务，产品无法升级等问题。 所以，在设计系统和选取任务调度算法时最好对现有资源留有一定的裕量，便于系统的维护和升级。 对于单调速率调度算法，下面进行对一个实例分析：设一个任务用参数表示为P（T，E）。 其中T表示任务周期，E表示任务执行时间，P表示任务。 假设现在某个单处理器系统中有两个周期任务，分别用符号表示为P1(4，2)和P2(6，3)。 任务P1的周期为4，小于任务P2的周期6。 所以根据单调速率唯一因素任务周期来决定任务优先级的原则，任务P1的优先级高于任务P2的优先级。 II仿真软件对任务P1和任务P2进行调度分析的执行情况。 为了便于分析和说明，下图只选取任务P1和任务P2周期值的最小公倍数任务调度时长作为一帧的长度，调度情况如下： 任务P1和任务P2调度仿真图，P1（2，4）是绿色调度线，它的优先级高于P2（3，6）蓝色调度线。 两个任务在0时刻同时到达，由于任务P1的优先级最高，系统又是基于抢占式任务调度的，所以它可以马上执行。 同时任务P2只能处于就绪列表中，等待处理器空闲。 经过两个单位时间后，任务P1执行完毕，释放处理器资源。 任务P2是就立即抢占处理器进行执行，它需要执行四个时间单位才能执行完毕。 但由于在系统时间的第四个单位时间时任务P1触发，并且由于它的优先级高于任务P2，所以任务P2被迫释放处理器资源进入就绪队列，任务P1占用处理器进行执行。 任务P2只能在系统时间的第六个时间单位进行执行1个时间单位的剩余任务。 由于任务的截止期最大不能超过任务的周期，所以任务P2在这段系统调用期间超时完成任务。 接下来的调度可以看到，任务P2在第二个任务周期内按时完成了任务。 系统以后的任务调度就不断重复前十二个时间单位。 根据CPU的利用率：上面的例子中，处理器利用率U=100％，显然处理器的利用率已经满负荷工作。 ，在系统只有两个任务时，%。 很显然，单调速率任务调度算法对该类型的两个任务无法调度。 单调速率任务调度算法在调度任务时对任务有一定的要求，所以它的这个局限性使得该调度算法不能任意运用。 但是它的优势是很明显的，比如系统对任务的调度开销小，针对非周期任务易于扩展调度，具有在系统瞬间过载情况下仍然保持稳定等优点，在相当一部分实际系统中使用[3435]。 期限最近者优先任务调度算法是基于动态优先级调度算法。 同静态调度算法相反，实时操作系统分配给任务的优先级依据某个动态参数算出优先级后赋给任务进行调度。 动态调度算法可以达到比静态调度算法更高的处理器利用率。 期限最近者优先任务调度算法总是调度任务就绪列表中最早达到绝对最后期限的任务。 期限最近者优先调度算法是一种最优的单处理器动态调度算法。 换句话说就是，假如期限最近者优先调度算法在单处理器上对一个任务集不能合理调度，那么其他算法也不能够对该任务集合理调度。 期限最近者优先调度算法的实现步骤：第一、查任务队列中所有就绪任务；第二、比较所有任务最后时间期限；第三、将具有最先时间期限的任务给予最高优先级即最先执行该任务。 期限最近者优先调度算法的优点是任务的优先级容易计算，效率高。 缺点是不能解决系统的过载问题，仅仅能做适当的负载优化。 由于任务的优先级所依赖的最早截止期这个参数是动态变化的，系统中所有任务越是运行到最后计算出的优先级越高，这就会导致系统将花费大量的时间花费在频繁的任务切换上，从而就降低了实时系统处理任务的效率。 为了改掉这个问题，研究人员提出了一种针对该算法的预防措施——设立阈值。 就是当任务的最早截止期小于等于预定的阈值后，系统就不再给该任务重新计算优先级，也就是当任务的最早截止期小于等于阈值后就变成固定优先级了[3637]。 时间片轮转任务调度算法和先来先服务任务调度算法原理简单，便于代码实现。 但这两种算法仅仅适合非实时系统下任务模型简单的情况，对于非实时系统下的非周期任务和实时系统就不适用。 单调速率任务调度算法和期限最近者优先任务调度算法适合于实时系统中多任务调度。 但是。 如果系统中包含了非周期任务，单调速率任务调度算法只能将其转换为周期任务进行调度。 不适合混合任务集的调度，任务调度比较单一，不够灵活处理。 期限最近者优先任务调度算法是动态优先级调度，它可以实现处理器的100%利用率。 但是该调度算法稳定性差，特别是系统中大部分任务都比较靠近最早截止期时，系统会处于频繁的任务切换中，不利于系统的高效要求。 需要加入辅助手段才可以应用到实际系统中。 在实时操作系统中，实时任务的调度算法都是采用优先级驱动。 不论是静态优先级驱动任务调度还是动态优先级驱动调度，优先级就有高低之分。 所以低优先级的响应问题总是比较难以解决。 本文将提出一种新的调度策略针对低优先级任务响应时间长的问题进行改进，并采用Ptolemy II软件进行新算法的仿真和验证。 第三章 基于角色的Ptolemy II实时仿真平台研究Ptolemy II仿真软件是由美国加州伯克利大学电气工程与计算机科学系研制开发的，该开发小组是一个非官方组织，属于复杂嵌入式软件系统中心的一部分。 主要用于研究仿真与设计、并行算法和实时嵌入式系统的建模。 Ptolemy II的基本设计原理为：使用定义明确的计算模型管理组件间的交互机制。 Ptolemy II的设计方法学重点在于通信和并行，并认为时间是最重要的概念。 Ptolemy II的基本组件是带有端口参数的角色，角色是通过端口与参数定义的接口进行通信。 在Ptolemy II中，角色与角色之间的交互是通过计算模型进行控制的，并定义了角色之间的控制流和端口之间的通信语意。 不同的计算模型如连续域、时间多任务域、连续域等等反映了域内系统不同的“动态”行为。 Ptolemy II仿真软件不但可以进行嵌入式异构系统的建模，还能通过部分求值机制[38]和代码生成助手机制[39]可实现设计系统模型到特定平台相关目标代码的自动生成[40]。 Ptolemy II域的研究分析 Ptolemy II仿真软件提供了各种类型的计算域[41]。 在Ptolemy II中，为实现不同的方法处理时间问题和并发性问题的计算模型而定义了计算域的概念。 各个计算域都定义了组件或者角色的交互机制，它是一系列角色的执行规则。 为了便于描述嵌入式系统中多样复杂的不同系统，Ptolemy II定义了如时间多任务域、连续时间域、网络处理域、离散事件域、有限状态机、同步数据流和周期驱动的离散域等几十种计算域。 Ptolemy II中，根据不同计算域的形式进行设计不同的调度策略[4243]。 Ptolemy II中的角色，必须在相应的计算域中进行工程设计，角色之间的通信是在域管理器的控制下完成的。 这样一个工程既能独立执行也可以通过Ptolemy II提供的“复合组件”模块进行封装，形成一个子模块在更高一级的工程中运行。 类似于这样的工程，被称之为域模型。 在Ptolemy II建模环境中。 该模型通过正弦函数执行体产生了正弦波的输出。 图中SDFDirector是域管理器，域模型是通过域管理器来管理模型中执行体间的交互机制，从而实现对整个系统行为的模型化控制。 正弦信号发生模型为了实现多层次的封装设计，Ptolemy II引入了复合执行体构件，用以将其它的执行体或者模型进行封装。 由此，模型设计者可以在不同的域中实现对不同行为的分类建模，再通过执行体的复合机制为模型整合提供实现手段。 高斯信号的封装在离散事件的计算模型中，连接代表的是同一时间链上所发生的事件集合。 一个事件包括数值与时间标志两个参数。 这种计算模型在具体硬件和模拟通信系统上应用广泛，并已实现了大量仿真环境，仿真语言和硬件描述语言。 包括VHDL和Verilog。 与同步/反应模型一样，这里有一个全局一致的时间概念，但离散事件计算模型中事件之间的时间是有意义的。 离散事件域中，事件具有随机性，事件发生的时间是无规律的。 由于事件之间可能是相互独立的，所以可能存在在同一时间触发了多个时间，这类同时触发的事件称之为并发事件[44]。 无论事件的发生是一个一个随机触发还是并发触发，系统都必须在规定时间内及时响应。 所以，事件触发的时间和系统对事件的响应时间是一个至关重要的参数，所以说，离散事件模型的主要任务是在规定时间内对触发的任何形式的事件依据既定规则进行处理。 离散事件域中，由于必须记录时间的触发事件和事件的响应时间，所以它有自身的时间属性。 为了将真实时间和计算模型中的时间相区分，物理世界中的真实时间被称为实时时间[45]，而将计算模型中的时间则称之为模型时间。 离散事件域使用一种全局事件队列对[46]事件进行存储和管理的方法，可以实现一个比较复杂的模型仿真器。 按照时间戳顺序，离散事件模型的调度器每次按照时间戳顺序，由时间戳从小到大排序后依次进行事件处理。 输入到离散事件模型中的初始事件，需要在各级执行体上完成不同的处理流程，最终将正确结果输出后，并予以销毁。 而在不同的处理阶段，执行体对事件的处理将产生新的后续事件，产生的后续事件统称为初始事件的子事件。 所以初始事件和子事件之间就会形成一种类似树形结构的依赖关系。 这类事件称为关联事件[47]，它们必须按照先后关系才能进行正确的处理。 一般不同的初始事件与其自身产生的子事件之间没有关联性，称之为独立事件[48]。 嵌入式系统通常包括例如机械组件，模拟电路和微波电路。 这些外设的特性最好用微分方程建模的组件，然而这些组件与可以作为传感器数据的控制器或接受器的电系统交互。 混合信号建模是典型的连续子系统与数字电信号的联合建模。 连续时间域的。