第十八讲 处理器调度算法(下).ppt

教学目的 让学生掌握常用的实时调度算法 让学生掌握常用的多处理器调度算法 教学重点 单比率调度算法、限期调度算法、最少裕度调度算法 多处理机调度算法的设计要点 负载共享调度算法，群调度算法 教学难点 多处理机调度算法的设计要点 2.8.1 低级调度的功能和类型 2.8.2 作业调度和低级调度算法 2.8.3 实时调度算法 2.8.4 多处理机调度算法 2.8.3 实时调度算法 实时系统是那些时间因素非常关键的系统。 实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。 硬实时系统和软实时系统 实时系统通常分为硬实时系统和软实时系统。 前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制时可以容忍的。 周期性和非周期性事件 实时系统响应的事件可划分为周期性事件和非周期性事件。 例如，m个周期性事件，事件i的周期为Pi，每个事件需要Ci秒的CPU时间来处理，则只有满足以下条件： C1/P1 + C2/P2 + … + Cm/Pm ≤ 1 时，才可能处理所有的负载。满足该条件的实时系统称作任务可调度的。 ?实时调度算法(1) 1）单比率调度算法 基本思想：为每个进程分配一个与事件发生频率成正比的优先数。例如，周期为20ms的进程优先数为50，周期为100ms的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式分配策略。 实时调度算法(2) 2）限期调度算法 基本思想：当一个事件发生时，对应的进程就按照截止期限被加入就绪进程队列。对于一个周期性事件，其截止期限即为事件下一次发生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。 实时调度算法(3) 3）最少裕度法 基本思想：首先计算各个进程的富裕时间，即裕度（laxity），然后选择裕度最少的进程执行。 裕度=截止时间-(就绪时间+计算时间) 2.8.4 多处理器调度 1多处理机调度的设计要点 1)如何为进程分配处理机 2)在单个处理机上是否使用多道程序设计技术 3)如何实际指派进程 CPU1 CPU2 CPU3 . . . CPUn 就绪队列1 就绪队列2 就绪队列3 . . . 就绪队列n 静态分配法 CPU1 CPU2 CPU3 . . . CPUn 就绪队列 . . . 动态分配法 一个程序的多个线程同时在多个处理机上运行（性能佳） 在单个处理机上运行单个程序，让其线程多道运行 不再采用复杂的调度算法，而采用简单的优先数法或FCFS算法 多处理器调度算法(1) 1）负载共享调度算法 基本思想：进程并不指派到特定处理机上，系统维护全局性进程就绪队列，当处理机空闲时，就选择进程的一个线程去运行。 优点：负载均衡，不须集中调度 缺点：就绪队列必须被互斥访问，被剥夺线程很难在原处理机上运行，一个进程的所有线程未必能同时获得处理机 多处理器调度算法(2) 2）群调度算法 基本思想：一群相关线程基于一对一的原则，被同时调度到一组处理机上运行。它具有的优点： ?当紧密相关的进程同时执行时，同步造成的等待将减少，进程切换也相应减少，系统性能得到提高。 ?由于一次性同时调度一组处理器，调度的代价也将减少。 统一划分 进程1 进程2 空闲 空闲 空闲 浪费时间37.5% 浪费时间15% 空闲 空闲 空闲 50% 50% 80% 20% 例：4个处理机，2个进程，进程1有4个线程，进程2有1个线程。 加权划分 进程1 进程2 多处理器调度算法(3)3）处理器专派调度算法 基本思想：给同属一个进程的一组线程，同时分派到一组处理机上运行，每个线程获得一个处理机，且它专用于处理这个线程，直到进程运行结束，这是群调度的一种极端形式。 采用这一算法，处理器将不适用多道程序设计，即该应用的一个线程阻塞后，线程对应的处理器不会被调度给其他线程，而处于空闲状态。 多处理器调度算法(4)4）动态调度算法(1) 基本思想：由操作系统和应用进程共同完成调度。 操作系统负责在应用进程之间划分处理器。 应用进程在分配给它的处理器上执行可运行线程的子集，哪一些线程应该执行，哪一些线程应该挂起完全是应用进程自己的事。 多处理器调度算法(5)动态调度算法(2) ??如果有空闲处理器，满足要求。否则，对新到达进程，从当前分配了一个以上处理器的进程中收回一个，并把它分给新到达进程。 ? 如果要求不能被满足，则保留申请直到出现可用处理器或要求取消。 ? 释放了一个或多个处理器后，扫描申请处理器的进程队列，按照FCFS原则把处理器逐一分配给每个申请进程直到没有可