操作系统中的调度问题动画演示系统开发---实时调度算法

摘 要 随着计算机应用范围的日益扩大，实时系统应用越来越广泛。其中，对任务调度的问题是实时系统一个关键的问题。合理的分布式实时系统的任务调度算法对发挥系统的并行性能、保证实时任务的可调度性、以及保持网络的负载平衡都具有非常重要的意义。 调度问题实际上是一个资源分配问题。研究调度问题的根本目的，就是尽可能提高系统有限资源的利用率。操作系统中的调度问题首先是计算机CPU时间的分配，包括调度策略、调度时机和调度算法等。 针对实时任务的多机执行的特点，为了满足任务的合理分配及系统的负载平衡，论文研究了频率单调调度(RMS)、最早截止时间优先调度（EDF）、最低松弛度调度（LLF）算法等三个算法，并基于JAVA平台实现三个算法的演示效果。 关键字：实时调度? 算法 频率单调调度 最早截止时间优先调度 最低松弛度调度 实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。 根据建立调度表和可调度性分析是脱机还是联机实现分为静态调度和动态调度，静态调度无论是单处理器调度还是分布式调度，一般是以RMS算法为基础；而动态调度则以EDF、LLF为主。 按系统分类实时调度可以分为单处理器调度，集中式多处理器调度和分布式处理器调度。 按任务是否可抢占又能分为抢占式调度和不可抢占式调度。 3.1 实时调度-RMS算法 (1) 任务T i (P i, Ci, D i) 模型: 周期为P i,计算时间为Ci, 时限D i 为周期终点。任务在周期起点释放, 高优先级任务可抢占低优先级任务的执行。 (2) 优先级分配方法: 静态固定分配。优先级与周期成反比, 周期越短优先级越高。 (3) 可调度性分析: 如果任务集满足下式, 则该任务集可调度。 定理1：n个独立的周期任务可以被RMPA调度，如果U<=n(2^(1/n)-1)。 一个任务的响应时间(response time)是指一个任务请求, 这个任务实际完成的时间跨度. 在静态调度中, 任务的临界时刻(critical instant)这个概念被首先提出来. 它被定义为一个特定的时刻, 如果在这个时刻有这个任务的请求, 那么这个任务就会需要最大的响应时间。 由此得出。 定理1: 一个任务的临界时间就是比这个任务优先级高的所有任务同时发出请求的时刻。 证明: 由于一个任务的响应时间是它自己的负载时间加上被其它优先级高的任务所打断的时间. 由于自己的负载时间是固定的, 我们考虑在什么时候任一高优先级的任务会有最长的打断时间. 显然, 只有当这一高优先级的任务与该任务同时请求处理时, 才能可能产生最大的打断时间。 定理1的价值在于它找到了一个证明一个调度算法能否调度任一任务集充分必要条件, 那就是所有任务同时请求执行的时的情况下每个任务仍能满足各自的期限, 那么这个任务集就可以被这个调度算法调度。 有了这个推论, 我们就可以证明RM调度的最优性了。 定理2: 如果一个任务集能够被静态调度, 那么RMS算法就能够调度这个任务集. 从这个意义上说, RMS是最优的静态调度算法。 这个定理的证明方法就是有名的交换法. 证明思路如下: 假设一个任务集S采用其他静态优先级算法可以调度,那么总有这样两个优先级相邻的任务i和j, 有Ti>Tj,而Pi≤Pj.把Ti和Tj的优先级Pi和Pj互换,明显可以看出这时S仍然可以调度, 因为在所有任务同时请求的情况下, 交换这两个任务不会影响其它任务的完成时间, 同时这两个任务都可以在各自期限内完成. 按照这样的方法,其他任何静态优先级调度最终都可以转换成RM调度。 RMS已被证明是静态最优调度算法, 开销小, 灵活性好, 是实时调度的基础性理论。即使系统瞬时过载, 也完全可预测哪些任务丢失时限。缺点是处理机利用率较低, 最坏的情况下，当n→∞时, 不超过ln2 (≈ 70%)。另外, RMS是充分但非必要条件。而在一般情况下，对于随机的任务集大约只有88%. 70%或者88%的处理器利用率对于许多实时应用来说是一个严重的限制，动态调度算法如最早截止期最先（earliest deadline first，EDF）或者最少空闲时间最先（least laxity first，LLF）已经被证明是最优的，并且能够实现100% 的处理器利用率. 具有资源同步约束的RMS调 当实时任务间共享资源时, 可能出现低优先级任务不可预测地阻塞高优先级任务执行的情况, 叫优先级倒置。这时RMS 算法不能保证任务集的调度, 必须使用有关协议控制优先级的倒置时间。常用的协议有优先级顶级协议和堆资源协议, 使用这些协议可使优先级的倒置时间最多为一个资源临界段的执行时间, 并且不会发生死锁。 基于RMS 的非周期任务的调度 实时系统中的非周期任务可采用延迟服务器算法或随机服务器算法进行调度。它们的最大特点是可在周期任务的实时调度环境下处理随机请求。两者的基本思想是将非周期任务转化成周期任务, 再利用RMS算法进行调度。前者用一个或几个专用的周期任务执行所有非周期任务, 这种周期任务叫非周期任务服务器。根据周期大小,服务器有固定优先级, 服务器的执行时间被称为预算, 它在每个服务器周期Ts 的起点补充。只要服务器有充足的预算, 就可在其周期内为非周期任务服务。该算法实现简单, 但可调度性分析较难, 有时会出现抖动, 可能发生一个非周期任务在相邻两个服务器周期中连续执行2倍预算的现象, 与RMS理论不符, 需要适当修改RMS算法。随机服务器算法与延迟服务器算法相似, 但预算不是在每个周期起点补充, 而是在预算消耗Ts时间之后再补充。该算法与RMS分析算法一致, 但实现复杂。