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

教学目的让学生掌握常用的实时调度算法让学生掌握常用的多处理器调度算法教学重点单比率调度算法、限期调度算法、最少裕度调度算法多处理机调度算法的设计要点负载共享调度算法，群调度算法教学难点多处理机调度算法的设计要点2.8处理器调度算法（下）2.8处理器调度算法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)如何实际指派进程如何为进程分配处理机CPU1CPU2CPU3...CPUn就绪队列1就绪队列2就绪队列3...就绪队列n静态分配法CPU1CPU2CPU3...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)

•

如果有空闲处理器，满足要求。否则，对新到达进程，从当前分配了一个以上处理器的进程中收回一个，并把它分