OS-03中断与处理机调度.ppt

操作系统原理 金海溶blue1879 办公室 JK329 第3章处理器调度 处理器调度的类型调度算法Linux进程调度Windows2000 xp线程调度 中断 中断 在进程运行过程中出现某种紧急情况 必须中止当前正在运行的程序 转去处理其它事件 处理完毕后恢复原来程序的运行 中断系统 中断装置 中断处理程序中断分类 内中断和外中断 硬中断和软中断 可屏蔽中断和不可屏蔽中断 强迫性中断和自愿性中断P49 59 选择性自学 第3章处理器调度 操作系统必须为多个进程可能有竞争的请求分配计算机资源 对处理器而言 可分配的资源是在处理器上的执行时间 分配途径是调度处理器调度 指采用合理的策略和方法在多个可运行实体间分配CPU资源 处理器调度算法 按照什么原则和方法分配处理器资源处理机调度必须设计成可以满足多个目标 例如公平 任何进程都不会饿死 有效地使用处理器时间和低开销等 调度算法设计指标 面向用户准则所关心的性能指标周转时间T 指一个进程从提交到完成之间的时间间隔 包括实际执行时间加上等待时间 等待 就绪 带权的周转时间W 周转时间与执行时间的比值响应时间从提交一个请求到开始处理的时间间隔 最后期限当可以指定进程完成的最后期限时 调度原则将服从于其他目标 使得距最后期限最近平均周转时间 p61平均带权周转时间 p61 面向系统准则所关心的性能指标吞吐量单位时间内完成的任务数 调度策略将试图使得每个时间单位完成的进程数目最大 处理器使用率处理器忙的时间百分比 尽量是CPU处于繁忙状态 公平进程应该被平等对待 没有一个进程会被饿死强制优先级当进程被指定了优先级 调度策略会先选择高优先级的进程平衡资源保持系统中所有资源忙 这个准则也可用于中程调度和长程调度 调度算法设计指标 处理器调度的类型 级别 多道程序的关键是调度 典型的调度类型有 长程调度 作业调度 高级调度 决定加入到待执行的进程池中中程调度 交换调度 中级调度 将进程调入内存 或者将进程交换到硬盘短程调度 进程调度 低级调度 决定哪一个就绪进程将被处理器执行线程调度 决定哪一个线程被处理器执行 就绪 挂起 新建 就绪 运行 退出 阻塞 短程调度 阻塞 挂起 中程调度 长程调度 长程调度 中程调度 下一次允许哪一个进程进入的决策可以基于简单的先来先服务原则 或者也可以基于管理系统性能的工具使用的原则包括优先级 期待执行时间和I O需求同样 可以根据请求哪个I O资源和试图平衡I O使用的目的进行决策 长程调度 中程调度的目标有2个 解决内存资源紧张的矛盾减小并发度以降低系统开销中程调度算法将结合存储管理来设计 中程调度 从执行的频率看长程调度程序的执行频率相对低些 并且仅仅是粗略地决定是否接受新进程以及接受哪一个为进行交换决策 中程调度程序执行得略微频繁一些短程调度程序 即分派程序执行得最频繁 并且精确地决定下一次执行哪一个进程 短程调度 根据已占有处理机的进程是否可被剥夺这一原则 调度方式 策略 可分为 非剥夺方式 一旦某个就绪进程分得处理机之后 只要不是其自身的原因被阻塞 如要求I O操作 而不能继续运行时 就一直运行下去 直至运行结束缺点 紧急进程无法立即运行 实时性差 短进程周转时间长 公平性差 进程调度方式 剥夺方式 当一个正在运行的进程没有运行完时 系统采取某种手段强行剥夺已分配给该进程的处理器资源 而被剥夺的进程重新回到就绪队列中等待在剥夺方式下 可以通过剥夺处理器所有权的方式 暂停当前进程的运行 已满足更紧急进程的处理要求 进程调度方式 进程调度方式 有三个进程p1 p2 p3到达时间为 0 3 4 优先级依次增高 运行所需的时间分别为20 4 2 假设现按优先级策略调度执行 并且不采用时间片原则 请分别求出非剥夺方式和剥夺方式下各个进程的周转时间 周转时间 p1 20 p2 23 p3 18 周转时间 p1 26 p2 6 p3 2 当时间片为5时 采用优先级策略 问非剥夺和剥夺方式下 求各进程的周转时间和响应时间 先来先服务 FCFS FirstComeFirstService 按照进程就绪的先后顺序来调度进程 到达的越早 其优先级越高获得处理机的进程 在未遇到其他情况时一直运行下去 采用的是非剥夺方式FCFS算法具有公平的特点 不会发生饿死 但短进程的等待时间长 平均周转时间长 调度算法 p61 最短进程SPN 短进程优先调度算法 减少FCFS固有的对长进程的偏爱的另一种方法是最短进程 SPN 策略 这是一种非剥夺的策略 其原则是下一次选择所需处理时间最短的进程 因此 短进程将会越过长进程 得到优先运行SPN策略的难点在于需要知道或至少需要估计每个进程所需要的处理时间长进程可能被 饿死 调度算法 最短剩余时间优先调度算法 SRTN 对SPN增加剥夺机制 当一个时钟中断周期到后 调度程序总是选择预期剩余时间最短的进程当一个新进程加入就绪队列时 它可能比当前运行的进程具有更短的剩余时间 因此 调度程序将剥夺当前程序 将处理器分配给新进程 和SPN一样 调度程序必须有关于处理时间的估计 并且存在长进程被饿死的危险 调度算法 最高响应比优先调度算法 HRRN 响应比 R w s s 1 w sw表示等待时间 s表示执行所需时间最高响应比也是对最短进程法的一种改进 当当前进程完成或被阻塞时 选择响应比最大的进程先执行 是一种非剥夺的策略 响应比R 代表了进程的年龄 算法在保证短进程优先的同时又兼顾了长进程 折中 调度算法 最高响应比优先调度算法 HRRN R w s s 1 w s当一系列进程同时进入系统时 由于短作业s值小 R值就大 因此短作业得到了优先执行 但随着长作业等待的时间 w 增长 R值不断增大 到达一定的等待时间 长进程最终将凭借年龄的增长战胜短进程 从而获得处理器 可见 在HRRN算法中 长作业不会被饿死 调度算法 优先级调度算法 按进程的优先级调度 选择就绪队列中优先级最高的进程到处理机上运行 优先数确定方式 静态优先级 每个进程创建时被赋予一个优先数 该优先数在进程整个生命周期都是固定不变的 动态优先级 每个进程被创建时被赋予一个优先数 该优先数在进程的生命周期内是可以动态变化的 调度算法 大多数动态优先级设计方案把交互式和I O频繁的进程移到优先级队列的顶端 而让计算量大的进程移到较低的优先级上对与优先级相同的进程 按先来先服务或轮转法则分配处理机对于一给定时间周期 一个正在运行的进程 每请求一次I O操作后其优先级就自动加1 直接反映出I O请求的频率 从而使I O设备具有很高的利用率 调度算法 优先级调度算法分类 非抢占的优先级调度法 一旦一个高优先级的进程占有了处理器 就一直运行下去 直到因等待某事被阻塞或执行结束 才选择就绪队列中优先级最高的进程来执行 可抢占的优先级调度法 任何时刻都按照高优先级进程在处理器上运行的原则进行进程调度 当一高优先级进程运行时 若有一更高优先级进程到达就绪队列 则当前运行进程立刻将处理器让给更高优先级的进程 即使未处理完 也无遇到阻塞情况 调度算法 最高优先数算法 可抢占CPUProcessArrivaltimePriorityBursttimeP1008P2215P3437P4023P5572GanttChart 最高优先数算法 轮转调度 简单轮转法RR 系统把所有就绪进程按先后次序排队 处理机总是优先分配给就绪队列中的第一个就绪进程 并分配它一个固定的时间片 如50毫秒 当该运行进程用完规定的时间片时 被迫释放处理机给下一个处于就绪队列中的第一个进程 自己回到就绪队列的尾部 并等待下次调度当某个正在运行的进程的时间片尚未用完 但进程需要I O时 该进程被送到相应阻塞队列 等I O完成重新返回到就绪队列尾部 等待调度 调度算法 简单轮转法RR 处理器 就绪队列 阻塞队列 分派 释放 超时 等待事件 事件发生 轮转调度简单轮转法是以就绪队列中的所有进程均以相同的速度往前推进为其特征 其时间片的长短 影响着进程的进展速度当就绪进程很多时 如果时间片很长 就会影响一些需要 紧急 运行的作业 同样这对短作业和要求I O操作多的作业显然是不利的因而 在简单轮转法的基础上又提出了分级轮转法 调度算法 分级轮转法将一个就绪队列根据进程的优先级不同 划分二个或二个以上的就绪队列 并赋给每个队列不同的优先级 甚至可以分配不同的时间片一般情况下 调度算法把相同的时间片分配给优先级高的就绪队列中的队首进程只有当优先级高的就绪队列中的所有进程全部运行完毕或等待I O操作而没有进程运行时 才把处理机分配给低优先级就绪队列中的进程 调度算法 高优先级就绪队列 低优先级就绪队列 处理器 分级轮转调度 分派 超时 阻塞队列 释放 调度算法 分级轮转法为了公平性 低优先级就绪队列的进程如果获得调度 将得到比高优先级就绪队列进程更多的时间片 加以弥补这样能大大降低长作业的交换频率 减少系统在交换作业时的时间消耗 又给了短作业较高的优先级 反馈FB 多级反馈队列调度算法 分级轮转调度和动态优先级算法的结合 采用剥夺策略划分多个就绪队列 优先级逐步降低 新建进程进入优先级最高的队列中 每当进程规定的时间片用完 被剥夺时 就送往低一级的就绪队列 进程调度时总是先执行高优先级队列中的进程 高优先级队列为空后 才转去处理低一级优先级队列中的进程 同一优先级队列 除最低 的进程 按FIFO机制调度 最低优先级队列 按时间片轮转调度算法执行 调度算法 允许进入 CPU RQ0 RQ1 RQ2 RQn 释放 CPU 释放 CPU 释放 CPU 释放 反馈调度 不同优先级的就绪队列可以给予相同的时间片 也可以不同 调度算法 反馈FB在反馈调度算法中 长进程也存在饿死的现象当比运行进程更高优先级队列到来一个新进程时 则应该处理高优先级队列的进程 有两种方案 抢占方式 即当高优先级进程到来时 立即抢占处理进程的处理器 被抢占进程回到原来就绪队列的末尾 没有特殊说明时 认为是抢占方式 非抢占方式 当前进程用完规定的时间片后 再调度高优先级的进程 调度算法 反馈FB对于被阻塞的进程 当阻塞取消后的处理方法 进入低一级的就绪队列回到原就绪队列放入高一级的就绪队列中 进入最高级的就绪队列 时间片的长短由如下四个因素决定 系统的响应时间当进程数目一定时 时间片的长短直接影响系统的响应时间就绪队列中进程的数目当系统对响应时间要求一定时 就绪队列中进程数少则时间片长 反之亦然进程状态转换 即进程由就绪态到运行 或反之 的时间开销计算机本身的处理能力执行速度和可运行作业的道数 调度算法 调度算法例题 现有5各进程 到达就绪队列的时间和所需的服务时间如下表所示求 FCFS RR q 1 4 SPN SRTN HRRN FB q 1 2i 先来先服务 FCFS 调度算法例题 循环 RR q 1 调度算法例题 循环 RR q 4 调度算法例题 最短进程 SPN 调度算法例题 最短剩余时间 SPTN 调度算法例题 最高响应比 HRRN 调度算法例题 反馈 队列有2个 q 1 调度算法例题 反馈 采用剥夺方式 q 2i 调度算法例题 各种调度算法各有其特点 但分级轮转法和反馈法较为理想除了从就绪进程中选取一合理的进程投入运行外 进程调度程序还必须给该进程分配运行时间片为了保证终端用户提供服务请求之后 能及时得到响应 一般规定的时间片在几十毫秒到几百毫秒之间不等 调度算法 可以有针对性地确定时间片的长短 让运行时间长的进程在不太频繁的时间间隔里获得较大的时间片让经常相互制约的进程有更多的机会获得处理机 但每次获得的时间片应较短系统优先考虑那些短的 相互制约的进程 而要求时间片长的进程虽然不经常运行 但其运行周期较长 能减少处理机分配所造成的开销进程调度算法有许多种 在具体实施中 是将几种算法结合起来使用 这样效率更高 选择调度策略 因等待I O而堵塞 运行 高优先级就绪 低优先级就绪 调度时的进程状态变迁图 分析其使用的调度策略与调度算法分析这一调度策略的设计出发点 调度算法分析 将就绪进程分成高和低优先级两个队列 如果进程运行中超过了规定的时间片就进入低优先级队列 而I O操作完成的进程 即由阻塞状态进入高优先级就绪队列调度算法是 首先从高优先就绪队列中选择一个进程来运行 如果在高优先级就绪队列中没有进程 则从低优先级就绪队列中选择一个进程运行 调度时的进程状态图 此算法对于要求I O量大的就绪进程有利 高优先级 而对于那些计算量大的就绪进程不利 未计算完毕就进入低优先级就绪队列 由于外部设备的运行速度大大低于主机的运行速度 所以为了保持I O通道和设备处于忙碌状态 受I O限制的进程优先于受CPU限制的进程运行 只有当所有的受I O限制的进程全部被阻塞 才选取某个受CPU限制的低优先级就绪进程在处理机上运行对交互式用户来说 这个策略提供了良好的响应 也保持了I O和中央处理机之间的高度并行 调度时的进程状态图 4传统的UNIX调度 传统的UNIX调度的基本目标是分时交互环境调度算法设计成为交互用户提供好的响应时间 同时保证低优先级的后台作业不会饿死 是分时调度算法的代表传统的UNIX调度程序在每个优先级队列中采用使用循环法的多级反馈 该系统使用1秒剥夺 也就是说 如果一个正在运行的进程在1秒内没有阻塞或完成 它将被剥夺 优先级基于进程类型和执行历史 4传统的UNIX调度 每秒都重新计算每个进程的优先级 并进行一次新的调度决策基本优先级的目的是把所有的进程划分成固定的优先级 这些区用于优化访问块设备 如磁盘 和允许操作系统迅速响应系统调用按优先级的顺序 这些区如下交换程序块I O设备控制文件操作 字符I O设备控制用户进程 4多处理器调度 当系统包含多个处理器时 在设计调度功能时就会产生一些新问题多处理器系统可以划分为以下几类松耦合 分布式多处理器 集群 由一组相对自治的系统组成 每个处理器有自己的主存和I O通道专门功能的处理器 例如I O处理器 在这种情况下 有一个通用的主处理器 专用处理器受主处理器的控制 并给主处理器提供服务紧耦合多处理器 由一组共享同一个主存并在操作系统完全控制下的处理器组成关注最后一类系统 特别是与调度有关的问题 粒度刻画多处理器的一种比较好的方法 是考虑系统中进程之间的同步粒度 或者说同步频率可以根据粒度区分5类并行度独立 多个无关进程非常粗 在网络节点上进行分布处理 以形成一个计算环境粗 在多道程序环境中并发进程的多处理中等 在一个应用程序中的并行处理或多任务处理 线程 细 指令流中固有的并行 4多处理器调度 独立并行度进程间没有显式的同步 每个进程都代表各自独立的应用或作业 这类并行度的一个典型应用是分时系统 每个用户都执行一个特定的应用 如字处理或使用电子表格 多处理器和多道程序单处理器一样提供相同的服务 由于有多个处理器可用 因而用户的平均响应时间非常短有可能达到这样的性能 每个用户都如同在使用个人计算机或工作站 如果任何一个文件或信息被共享 则单个系统必须连接在一个有网络支持的分布式系统中在许多实例中 多处理器共享系统比分布式系统的成本效益更合算 它允许节约使用磁盘和其他外围设备 粒度 粗粒度和非常粗粒度的并行度是指进程之间在一个非常粗的级别上存在着同步 这种情况可以简单地处理成一组运行在多道程序单处理器上的并发进程 在多处理器上对用户软件进行很少的改动或者不进行改动就可以提供支持一般来说 使用多处理器体系结构 对所有需要通信或同步的并发进程集合都有好处 当进程间存在非常频繁的交互时 分布式系统可以提供好的支持 但是 当交互更加频繁时 分布式系统中的网络通信开销会抵消一部分潜在的加速 在这种情况下 多处理器组织能提供最有效的支持 粒度 中等粒度的并行度应用程序可以作为进程中的一组线程被有效地实现 在这种情况下 可以由程序员显式地指定应用程序潜在的并行性 典型地 在应用程序的线程之间 需要更高程度的合作与交互 从而导致中等粒度级的同步尽管多处理器和多道程序单处理器都支持独立 非常粗和粗粒度的并行度 并对调度功能产生少许影响或没有影响 但是在处理线程调度时 我们仍然需要重新分析调度 由于应用程序中各个线程间的交互是如此地频繁 关于线程调度的决策可能会影响整个应用的性能 粒度 细粒度的并行度代表着比线程中的并行更加复杂的使用 尽管在高度并行的应用中已经完成了大量的工作 迄今为止 这仍然是一个特殊的 被分割的领域 粒度 多处理器中的调度涉及到以下三个相关问题把进程分配到处理器在单个处理器上使用多道程序一个进程的实际分派在讨论这三个问题时 必须记住所采用的方法通常取决于应用程序的粒度等级和可用的处理器的数目 设计问题 把进程分配到处理器假设多处理器结构中各个处理器在访问主存和I O设备时没有特别优势 那么最简单的调度方法是把处理器看作是一个资源池 并按照要求把进程分配到相应的处理器 带来的问题是 分配应该是静态的还是动态的 设计问题 静态 一个进程从被激活到完成 被永久地分配到一个处理器 则需要为每个处理器维护一个专门的短程队列 其优点是调度的开销比较小 因为所有进程关于处理器的分配只进行一次静态分配的缺点是某个处理器可能空闲 这时它的队列为空 而另一个处理器却积压了许多工作 设计问题 设计问题 动态 为防止静态分配浪费CPU资源的情况 需要使用一个公共队列 所有进程都进入一个全局队列 然后调度到任何一个可用的处理器中 这样 在一个进程的生命周期中 它可以在不同的时间在不同的处理器上执行 把进程分配到处理器 处理器结构主从式结构 操作系统的主要核心功能总是在某个特定的处理器上运行 其他处理器可能仅用于执行用户程序主处理器负责调度作业 当一个进程被激活时 如果从处理器需要服务 例如一次I O调用 它必须给主处理器发送一个请求 然后等待服务的执行这种方法简单 由于处理器拥有对所有存储器和I O资源的控制 因而可以简化冲突解决方案缺点是 主处理器的失败导致整个系统失败 主处理器可能成为性能瓶颈 设计问题 把进程分配到处理器 处理器结构对等式结构 操作系统可以在任何一个处理器中执行 每个处理器从可用进程池中进行自调度 这种方法增加了操作系统的复杂性 必须确保两个处理器不会选择同一个进程 进程也不会从队列中丢失也可以提供一个处理器子集专门用于内核处理 或者是基于优先级和执行历史来管理内核进程和其他进程之间的差别等 设计问题 在单个处理器上使用多道程序传统的多处理器处理是粗粒度或独立同步粒度 显然单个处理器能够在许多进程间切换 以达到较高的使用率和更好的性能 但是 对于运行在有许多处理器的多处理器系统中的中等粒度 线程 应用程序 当多个处理器可用时 要求每个处理器尽可能地忙就不再那么重要了 相反 我们更加关注如何能为应用提供最好的平均性能 设计问题 进程分派选择哪一个进程运行 在多道程序单处理器上 与简单的先来先服务策略相比较 使用优先级或者基于过去的使用历史的高级调度算法可以提高性能当考虑多处理器时 这些复杂性是不必要的 不然可能反而达不到预期的目标 对于多处理器 相对比较简单的方法会更有效 而且开销也比较低 设计问题 在大多数传统的多处理器系统中 进程并不是被指定到一个专门的处理器 不是所有处理器只有一个队列而是有多条基于优先级的队列 并且都送进相同的处理器池中 在任何情况下 我们都可以把系统看作是多服务器排队结构对各种情况进行分析 对于多处理器 调度原则的选择没有在单处理器中显得重要 因此 在多处理器系统中使用简单的FCFS 先来先服务 原则或者在静态化先级方案中使用FCFS就足够了 多处理器进程调度 CPU 就绪队列n 释放 CPU 释放 CPU 释放 CPU 释放 多处理器调度 就绪队列3 就绪队列2 就绪队列1 分派 CPU池 在单处理器中 线程可以用作辅助构造程序 并在处理过程中重叠执行I O 由于在进行线程切换时的性能损失远远小于进程切换的开销 因此可以用很少的代价实现这些优点在多处理器系统中 线程的全部能力得到了更好的展现 线程可以用于开发应用程序中真正的并行性 如果一个应用程序的各个线程同时在各个独立的处理器中执行 其性能就会得到显著的提高 线程调度 在多处理器线程调度和处理器分配的各种方案中 比较突出的方法是 负载分配 进程不是分配到一个特定的处理器 而是维护一个就绪进程的全局队列 每个处理器只要空闲就从队列中选择一个线程 负载平衡是基于一种比较永久的分配方案配工作的成组调度 一组相关的线程基于一对一的原则 同时调度到一组处理器上运行专用处理器分配 这种方法与负载分配的方法相反 它通过把线程指定到处理器来定义隐式的调度 在程序执行过程中 每个程序被分配给一组处理器 处理器的数目与程序线程的数目相等 当程序终止时 处理器返回到总的处理器池中 可供分配给另一个程序动态调度 在执行期间 进程中线程的数目可以改变 线程调度 Windows2000调度 Windows2000的设计目标是在高度交互的环境中或者作为服务器尽可能地响应单个用户的需求Windows2000实现了剥夺式调度程序 它具有灵活的优先级系统 在每一级上都包括了循环调度方法 在某些级上 优先级可以基于它们当前的线程活动而动态变化 Windows2000中的优先级被组织成两段 两类 实时和可变 每一段包括16种优先级 需要立即关注的线程在实时类中 它包括诸如通信之类的功能和实时任务Windows2000使用一种优先级驱动的剥夺式调度程序 具有实时优先级的线程优先于其他线程在单处理器中 当一个线程就绪时 如果它的优先级高于当前正在执行的线程 那么低优先级的线程被剥夺 具有更高优先级的进程占用处理器 进程和线程优先级 两类优先级的处理方式有一定的不同在实时优先级类中 所有线程具有固定的优先级 并且它们的优先级永远不会改变 某一给定优先级的所有活动线程在一个循环队列中在可变优先级类中 一个线程的优先级在开始时是最初指定的值 但在它的生命周期中可能会发生变化 上升或者下降 因此 在每个优先级上都有一个FIFO队列 一个进程可能在可变优先级类中从一个队列迁移到另一个队列 但是 优先级为15的线程不能升到16级 也就是说不能升到实时类的任何级中 进程和线程优先级 最低 0 最高 15 最低 16 最高 31 实时优先级类 可变优先级类 WindowsNT线程调度优先级 当Windows2000运行在一个处理器上时 优先级最高的线程总是活跃的 除非它正在等待一个事件如果有多个线程具有最高的优先级 则处理器在这一级的所有线程间被循环共享在一个具有N个处理器的多处理器系统中 N 1 个最高优先级的线程总是活跃的 在 N 1 个处理器上独占运行 剩下的低优先级线程共享剩下的一个处理器 多处理器调度 3 4实时调度 real timescheduling 实时任务 具有明确时间约束的计算任务 Eg 某时刻前必须开始处理某时刻前必须处理完毕实时调度 合理安排就绪实时任务的执行次序 满足每个实时任务时间约束条件的调度 实时任务分类 硬实时vs 软实时硬实时 hardreal time 必须满足任务截止期要求 软实时 softreal time 期望满足截止期要求 周期性vs 随机性周期性 每隔固定时间发生一次随机性 由随机事件触发 其发生时刻不确定 术语解释 Readytime 就绪时间Startingdeadline 开始截止期Processingtime 处理时间Completiondeadline 完成截止期Occurringfrequency 发生频率 周期性实时事务 周期性实时事务 令Ci为任务Pi处理时间 Ti为任务Pi的发生周期 则任务P1 Pm可调度的必要条件为 周期性实时事务 例 T1 100 T2 200 T3 500 ms C1 50 C2 30 C3 100 ms C1 T1 C2 T2 C3 T3 0 5 0 15 0 2 0 85 1满足可调度的必要条件 周期性实时事务 10 20 25 50 1 可调度 不考虑开销 例子 ProcessArrivaltimeExecutiontimecompletiondeadline A 1 A 2 A 3 A 4 A 5 B 1 B 2 020406080 050 1010101010 2525 20406080100 50100 3 4 1最早截止期调度 EDF EarliestDeadlineFirst 优先选择截止期最早的实时任务可抢先可以证明 对EDF来说 可调度充分条件是 在不可调度的条件下 可使错过截止期任务最小化 例子 EarliestDeadlineFirst 0102030405060708090100Time A2 B1 A3 B2 A5 B2 A4 3 4 2速率单调调度 RMS RateMonotonicScheduling 提出于1973年面向周期性实时事务 非剥夺式优先调度发生周期最短 频度最高 的实时任务可调度条件 RMS的上限值 RMSvs EDFRMS可调度条件强于EDFRMS调度较EDF实现简单 RMS例子 可调度 具体调度结果 02060160180220240300320360460 例题精选 假定要在一台处理机上执行右表作业 且假定这些作业同时到达的次序是1 2 3 4 5 数字越小优先级越高 1 给出Gantt图说明分别使用FCFS RR 时间片 1 SPN以及