实时操作系统 务管理与调度.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 调度策略，是指进行调度的规则、方法或方式。 调度算法是调度策略的具体实现和体现，是在一个特定时刻用来确定将要运行的任务的一组规则。 * * 设计调度程序时，通常需要综合考虑如下因素： CPU的使用率（CPU utilization） 输入/输出设备的吞吐率 响应时间（responsive time） 公平性 截止时间 调度算法 对于大量的实时调度方法而言，存在着以下几类主要的划分方法： 离线（off-line）和在线（on-line）调度 抢占（preemptive）和非抢占（non-preemptive）调度 静态（static）和动态（dynamic）调度 最佳（optimal）和试探性（heuristic）调度 调度算法 时间片轮转调度(round-robin scheduling)是指： ? 当有两个或多个就绪任务具有相同的优先级， ? 且它们是就绪任务中优先级最高的任务时， ? 调度器按照任务就绪的先后次序调度每个任务， ? 每个任务运行一段时间后调度下一个任务， ? 直到最后一个任务也得以运行一段时间后，接下来又让 第一个任务运行。 时间片轮转调度 时间片轮转调度 ? 基于优先级的调度的基本思路： ? 给每一个任务都设置一个优先级 ? 然后在任务调度的时候，在所有处于就绪 状态的任务中选择优先级最高的那个任务 去运行。 基于优先级的调度 优先级算法可以分为两种： 当一个任务正在运行的时 候，如果这时来了一个新的任 务，其优先级更高，那么在这种 情况下，是立即抢占CPU去运行 新任务，还是等当前任务运行完 后再决定。 ? 可抢占方式 ? 不可抢占方式 区别在于： 基于优先级的调度 ISR Low Priority Task High Priority Task ISR ISR make High Priority Task Ready ISR Completes (Return to Task) Low Priority Task Completes (Switch to HP Task) Interrupt Occurs Vector to ISR Non-Preemptive 不可抢占式调度 ISR Low Priority Task (LPT) High Priority Task (HPT) ISR ISR make High Priority Task Ready Interrupt occurs Vector to ISR ISR Completes (Switch to HP Task) HP Task Completes (Switch back to LP Task) Preemptive 可抢占式调度 低优先级任务 内核服务 ISR 高优先级任务 时间 (1) (2) (3) (4) (5) 不可抢占内核（允许中断） 不可抢占内核 低优先级任务 内核服务 ISR 高优先级任务 时间 (1) (2) (3) (4) (5) 可抢占内核 可抢占式内核 任务2就绪 任务3就绪 任务1 任务2 任务3 优先级 高 低 时间 任务2 任务1 抢占 抢占 任务3运行结束 任务2运行结束 在可抢占调度方式下的任务运行情况 基于优先级的可抢占调度 ? 在优先级算法中，如果两个任务的优先级相 同，又该如何处理呢? ?把任务按照不同的优先级进行分组， ?然后在不同组的任务之间使用优先级算法， ?而在同一组的各个任务之间使用时间片轮转法。 通常的做法： ＋时间片轮转调度 基于优先级的调度 任务1 任务2 任务3 优先级 高 低 时间 任务3就绪 任务3运行结束 任务1 任务2 任务1 任务2 时间片轮转调度 优先级可抢占与时间片轮转调度相结合方式下的任务运行情况 第五节优先级反转 优先级继承协议 优先级天花板协议 优先级反转(Priority Inversion)：指一个任务等待比它优先级低的任务释放资源而被阻塞，如果这时有中等优先级的就绪任务，阻塞会进一步恶化。 优先级反转 解决优先级反转现象的常用协议为： 优先级继承协议（priority inheritance protocol）； 优先级天花板协议（priority ceiling protocol）。 解决优先级反转 优先级继承协议的思想 当一个任务阻塞 一个或多个高优先级任务时，该任务将不使用其原来的优先