07 任务调度.pdf

1 嵌入式实时操作系统及实现嵌入式实时操作系统及实现 计算机学院 黄正全计算机学院 黄正全 2 嵌入式实时操作系统及实现 任务调度任务调度任务调度任务调度 3 88 内容提要 1 2 3 4 5 调度的时机调度的时机调度的时机调度的时机 调度的性能指标调度的性能指标调度的性能指标调度的性能指标 常见的调度算法常见的调度算法常见的调度算法常见的调度算法 调度的策略调度的策略调度的策略调度的策略 概述概述概述概述 4 88 上节回顾 C OS II概述概述 1 C OS II任务概述任务概述 2 C OS II任务管理任务管理 3 C OS II体系结构体系结构 用户应用程序 应用软件应用软件 与处理器无关的代码的核心代码核心代码 OS CORE C OS FLAG C OS MBOX C OS MEM C OS MUTEX C OS Q C OS SEM C OS TASK C OS TIME C C OS II C C OS II H 与应用程序相关的 配置代码配置代码 OS CFG C INCLUDES H 与处理器相关的设置代码 设置代码 C OS II移植时需要修改 CPU定时器 OS CPU H OS CPU A ASM OS CPU C 需要添加的 硬件抽象层 需要添加的 硬件抽象层 系统的其他硬件 7 88 8 88 睡眠态中断服务态 任务状态及转换 睡眠态中断服务态 任务状态及转换 任务的存储结构 任务任务 任务控制块 任务的代码 任务堆栈 任务控制块 任务的代码 任务堆栈 10 88 typedef struct os tcb OS STK OSTCBStkPtr 指向当前任务栈顶的指针 void OSTCBExtPtr 指向用户定义的任务控制块扩展 OS STK OSTCBStkBottom 指向任务栈底的指针 INT32U OSTCBStkSize 栈容量总数 INT16U OSTCBOpt 功能选择项 INT16U OSTCBId 用于存储任务的识别码 保留将来用 struct os tcb OSTCBNext 任务控制块OS TCBs的双重链接 struct os tcb OSTCBPrev OS EVENT OSTCBEventPtr 指向事件控制块的指针 void OSTCBMsg 指向传给任务的消息的指针 INT16U OSTCBDly 任务延时 INT8U OSTCBStat 任务的状态字 INT8U OSTCBPrio 任务优先级 INT8U OSTCBX 优先级计算相关参数 INT8U OSTCBY INT8U OSTCBBitX INT8U OSTCBBitY BOOLEAN OSTCBDelReq 表示该任务是否需要删除 OS TCB 任务 控制块 任务 代码 任务 堆栈 任务 控制块 任务 代码 任务 堆栈 多个任务形成一个链表多个任务形成一个链表 OSTCBTbl 0 OSTCBTbl OS MAX TASKS OS N SYS TASKS 2 OSTCBTbl OS MAX TASKS OS N SYS TASKS 1 OSTCBList OSTCBTbl 1 OSTCBNext OSTCBPre OSTCBPrio OSTCBNext OSTCBPre OSTCBPrio OSTCBTbl 2 OSTCBNext OSTCBPre OSTCBPrio OSTCBNext OSTCBPre OSTCBPrioOSTCBPrio OSTCBNext OSTCBPre OSTCBFreeList 0 OSTCBPioTble 0 1 2 OS MAX TASKS OS N SYS TASKS 2 OS MAX TASKS OS N SYS TASKS 1 3 OSTCBCur 正在运行的任务 控制块的指针 保存任务控制块 指针的数组 13 88 内容提要 1 2 3 4 5 调度的时机调度的时机调度的时机调度的时机 调度的性能指标调度的性能指标调度的性能指标调度的性能指标 常见的调度算法常见的调度算法常见的调度算法常见的调度算法 调度的策略调度的策略调度的策略调度的策略 概述概述概述概述 14 88 1 概述概述 计算机发展的初期 作业作业作业作业的方式 不存在调度 的概念 随后 批处理方式批处理方式批处理方式批处理方式 先来先服务 体现了一种 非常简单的调度概念 多道程序多道程序多道程序多道程序处理方式下 调度调度调度调度才变得复杂和重要 起来 15 88 1 概述概述 在多道程序操作系统中 经常会出现多个任务 同时去竞争CPU的情况 在系统的就绪队列中 有两个或多个任务同时处于就 绪状态 假设在系统中只有一个 在系统的就绪队列中 有两个或多个任务同时处于就 绪状态 假设在系统中只有一个CPU 而且这个 而且这个CPU已经 空闲下来了 已经 空闲下来了 对于就绪队列当中的那些任务 应该选择哪一 个去运行 对于就绪队列当中的那些任务 应该选择哪一 个去运行 执行多长时间执行多长时间 16 88 1 概述概述 上述问题是由操作系统操作系统操作系统操作系统来解决的 其过程就是任务调度任务调度任务调度任务调度 负责做出选择的那部分程序 称为调度程序调度程序调度程序调度程序 也叫调度器调度器调度器调度器 scheduler 调度器在决策过程中所采用的算法 就称为是 调度算法调度算法调度算法调度算法 17 88 1 概述概述 在多任务的实时操作系统中 在多任务的实时操作系统中 调度调度是一个非常 重要的功能 用来确定 是一个非常 重要的功能 用来确定多任务环境多任务环境下任务下任务执行 执行 的顺序的顺序和在和在获得获得获得获得CPUCPUCPUCPU资源资源资源资源后能够后能够执行的时间长 执行的时间长 度度 从资源管理的角度来看 也可以把调度器看成 是CPU这个资源的管理者 从资源管理的角度来看 也可以把调度器看成 是CPU这个资源的管理者 18 88 1 概述概述 操作系统通过一个操作系统通过一个调度器调度器 scheduler 来实现 调度功能 scheduler 来实现 调度功能 调度器以调度器以函数函数的形式存在 用来实现操作系统 的调度算法 的形式存在 用来实现操作系统 的调度算法 调度器本身并不是一个任务 而是一个调度器本身并不是一个任务 而是一个函数调 函数调 用用 可在内核的各个部分进行调用 可在内核的各个部分进行调用 19 88 1 概述概述 任务调度需要解决的三个问题 任务调度需要解决的三个问题 何时进行调度 何时进行调度 如何进行调度 如何进行调度 如何评价调度的效果 如何评价调度的效果 调度的时机调度的时机 调度的策略调度的策略 调度的性能指标调度的性能指标 20 88 内容提要 1 2 3 4 5 调度的时机调度的时机调度的时机调度的时机 调度的性能指标调度的性能指标调度的性能指标调度的性能指标 常见的调度算法常见的调度算法常见的调度算法常见的调度算法 调度的策略调度的策略调度的策略调度的策略 概述概述概述概述 21 88 2 调度的时机调度的时机 调用调度器的具体位置又被称为是一个调用调度器的具体位置又被称为是一个调度点 调度点 scheduling point scheduling point 任务调度的首要问题是何时进行调度 即调度 发生的时机 任务调度的首要问题是何时进行调度 即调度 发生的时机 22 88 2 调度的时机调度的时机 一般来说 在以下几种情形下 可能会发生任 务的调度 即调度点通常位于 当一个新的任务被创建时 当一个新的任务被创建时 当一个任务运行结束时 当一个任务运行结束时 当一个任务阻塞时 当一个任务阻塞时 当一个当一个I O中断发生时 中断发生时 当一个时钟中断发生时 当一个时钟中断发生时 23 88 2 调度的时机调度的时机 一般来说 在以下几种情形下 可能会发生任 务的调度 即调度点通常位于 当一个新的任务被创建时 当一个新的任务被创建时 当一个任务运行结束时 当一个任务运行结束时 当一个任务阻塞时 当一个任务阻塞时 当一个当一个I O中断发生时 中断发生时 当一个时钟中断发生时 当一个时钟中断发生时 当一个新的任务被创建时新的任务被创建时新的任务被创建时新的任务被创建时 需要做出一个 调度决策 是立即执行这个新任务还是继 续执行父任务 当一个任务运行结束时当一个任务运行结束时当一个任务运行结束时当一个任务运行结束时 它不再占用CPU 这时 调度器必须做出一个决策 从就绪队列中选择某 个任务去运行 如果此时没有任务处于就绪状态 系统一般会调 度一个特殊的空闲任务 当一个任务由于当一个任务由于I O操作 信号量或其 他原因被阻塞时 也必须另选一个任务运行 操作 信号量或其 他原因被阻塞时 也必须另选一个任务运行 当一个当一个I O中断发生时 表明某个中断发生时 表明某个I O操作已 经完成 而等待该 操作已 经完成 而等待该I O操作的任务将从阻塞状态操作的任务将从阻塞状态阻塞状态阻塞状态变 为就绪状态 变 为就绪状态就绪状态就绪状态 此时可能需要做出一个调度决策 是 立即执行这个新就绪的任务 还是继续执行刚才被 中断的那个任务 此时可能需要做出一个调度决策 是 立即执行这个新就绪的任务 还是继续执行刚才被 中断的那个任务 当一个时钟中断发生时 表明一个时钟节拍已经结束 当一个时钟中断发生时 表明一个时钟节拍已经结束 可能会唤醒一些可能会唤醒一些延时的任务延时的任务延时的任务延时的任务 使它们变为 使它们变为就绪状态就绪状态就绪状态就绪状态 也可能会发现也可能会发现当前任务的时间片已用完当前任务的时间片已用完当前任务的时间片已用完当前任务的时间片已用完 从而把它 变为 从而把它 变为就绪状态就绪状态就绪状态就绪状态 24 88 内容提要 1 2 3 4 5 调度的时机调度的时机调度的时机调度的时机 调度的性能指标调度的性能指标调度的性能指标调度的性能指标 常见的调度算法常见的调度算法常见的调度算法常见的调度算法 调度的策略调度的策略调度的策略调度的策略 概述概述概述概述 25 88 3 调度的性能指标调度的性能指标 实时系统中的实时系统中的调度算法调度算法调度算法调度算法是决定系统实时性的重 要指标 是决定系统实时性的重 要指标 RTOS调度算法的主要职责就是要确保RTOS调度算法的主要职责就是要确保所有的任 所有的任 务务都能够满足任务的都能够满足任务的时间约束特性时间约束特性要求 要求 26 88 3 调度的性能指标调度的性能指标 时间约束特性来源于任务的不同需求时间约束特性来源于任务的不同需求 如截止时 间 QoS等 且 如截止时 间 QoS等 且同一个任务同一个任务在在不同时候不同时候不同时候不同时候也可能 具有不同的时间约束特性 也可能 具有不同的时间约束特性 能够同时适应所有情况的调度算法是不存 能够同时适应所有情况的调度算法是不存 在的 在的 27 88 3 调度的性能指标调度的性能指标 从理论上来说 从理论上来说 最优调度最优调度最优调度最优调度只有在能够完全获知 所有任务在处理 同步和通信方面的需求 以 及硬件的处理和时间特性的基础上才能实现 只有在能够完全获知 所有任务在处理 同步和通信方面的需求 以 及硬件的处理和时间特性的基础上才能实现 在实际应用中 很难实现这一点 特别是当这 些需要获知的信息处于动态变化的情况下 在实际应用中 很难实现这一点 特别是当这 些需要获知的信息处于动态变化的情况下 28 88 3 调度的性能指标调度的性能指标 即使在这些需要的信息都是可以预见的情况 下 常用的调度问题仍然是一个 即使在这些需要的信息都是可以预见的情况 下 常用的调度问题仍然是一个NP NP 难题难题难题难题 调度的复杂性调度的复杂性调度的复杂性调度的复杂性将随调度需要考虑的任务和约束 特性的数量呈现出 将随调度需要考虑的任务和约束 特性的数量呈现出指数增长指数增长指数增长指数增长 NP Nondeterministic Polynomial time 非确定性多项式时间 非确定性多项式时间 29 88 3 调度的性能指标调度的性能指标 调度器本身需要一定的系统开销 需要花费时间来计 算下一个可被执行的任务 调度器本身需要一定的系统开销 需要花费时间来计 算下一个可被执行的任务 复杂的调度器通常具有不可预见性 需要花费更多的 时间和资源 其复杂性也增加了应用开发人员的使用 难度 因此 在 复杂的调度器通常具有不可预见性 需要花费更多的 时间和资源 其复杂性也增加了应用开发人员的使用 难度 因此 在RTOS中通常会依据系统需求 采用 简单实用的调度算法 以确保任务的实时结束性和可 预见性 中通常会依据系统需求 采用 简单实用的调度算法 以确保任务的实时结束性和可 预见性 30 88 3 调度的性能指标调度的性能指标 在设计调度器时 通常需要综合考虑综合考虑如下因素 冲突性冲突性 优先考虑最重要的需求优先考虑最重要的需求 折衷处理折衷处理 CPU的使用率的使用率 CPU utilization 输入输入 输出设备的吞吐率 输出设备的吞吐率 响应时间 响应时间 公平性 公平性 截止时间 截止时间 31 88 3 调度的性能指标调度的性能指标 相关概念 CPUCPU的使用率的使用率的使用率的使用率 utilization utilization 可调度性可调度性可调度性可调度性 schedulabilityschedulability 32 88 相关概念 相关概念 相关概念 相关概念 CPUCPU的使用率的使用率的使用率的使用率 CPUCPU的使用率的使用率的使用率的使用率 utilization utilization 表示对于给定的 一组任务 这些任务所使用的整个 表示对于给定的 一组任务 这些任务所使用的整个CPU资源的 比率 资源的 比率 对于一个给定的调度算法 其CPU使用率存在 着一个理论上的上限 如EDF算法的最大CPU 使用率为1 33 88 相关概念 可调度性相关概念 可调度性相关概念 可调度性相关概念 可调度性 可调度性的程度可以通过所有任务截止时间所有任务截止时间所有任务截止时间所有任务截止时间都 能得到满足的情况下的最大最大最大最大CPUCPU使用率使用率使用率使用率来进行 衡量 可调度性可调度性可调度性可调度性 schedulabilityschedulability 表示对于给定的 一组任务 如果所有任务都能满足截止时间的 要求 则这些任务就是可调度的 表示对于给定的 一组任务 如果所有任务都能满足截止时间的 要求 则这些任务就是可调度的 34 88 3 调度的性能指标调度的性能指标 在嵌入式操作系统当中 存在着许多的调度算 法 每一种算法都有各自的优点和缺点 在嵌入式操作系统当中 存在着许多的调度算 法 每一种算法都有各自的优点和缺点 如何来评价一个调度算法的好坏 即任务调度 算法的性能指标是什么 如何来评价一个调度算法的好坏 即任务调度 算法的性能指标是什么 35 88 3 调度的性能指标调度的性能指标 任务调度算法的性能指标主要包括下面几项 任务调度算法的性能指标主要包括下面几项 响应时间响应时间 response time 周转时间周转时间 turnaround time 调度开销调度开销 overhead 公平性公平性 fainness 均衡性均衡性 balance 吞吐量吞吐量 throughput 调度器为一个调度器为一个就绪就绪就绪 就绪 任务任务任务任务进行上下文进行上下文切切切 切 换换换时所需的时间 以及任务在就绪队 列中的 换时所需的时间 以及任务在就绪队 列中的等待时间等待时间等待时间 等待时间 一个任务从 提交到完成所经 历的时间 一个任务从 提交到完成所经 历的时间 调度器在做 出调度决策时所 需要的时间和空 间开销 调度器在做 出调度决策时所 需要的时间和空 间开销 大致相当的两个 任务所得到的 大致相当的两个 任务所得到的CPU 时间也应该是大致相 同的 另外 要防止饥 饿 时间也应该是大致相 同的 另外 要防止饥 饿 要尽可能使整 个系统的各个部分 要尽可能使整 个系统的各个部分 CPU I O 都忙 起来 提高系统资 源的使用效率 都忙 起来 提高系统资 源的使用效率 单位时间内 完成的任务数量 单位时间内 完成的任务数量 36 88 3 调度的性能指标调度的性能指标 在这些指标当中 有一些是可以共存共存共存共存的 也 有一些是相互牵制相互牵制相互牵制相互牵制的 因此 对于一个实际的调度算法来说 这些 指标不可能全部都实现 而是要根据系统的 需要 有一个综合的权衡权衡权衡权衡和折中折中折中折中的过程 37 88 内容提要 1 2 3 4 5 调度的时机调度的时机调度的时机调度的时机 调度的性能指标调度的性能指标调度的性能指标调度的性能指标 常见的调度算法常见的调度算法常见的调度算法常见的调度算法 调度的策略调度的策略调度的策略调度的策略 概述概述概述概述 38 88 4 调度的策略调度的策略 调度策略调度策略概述概述 时间片轮转调度时间片轮转调度 基于优先级的调度基于优先级的调度 39 88 4 1 调度策略概述调度策略概述 调度策略调度策略调度策略调度策略 是指进行调度的规则 方法或方 式 是指进行调度的规则 方法或方 式 调度算法调度算法调度算法调度算法是调度策略的具体实现和体现 是 在一个特定时刻用来确定将要运行的任务的 一组规则 是调度策略的具体实现和体现 是 在一个特定时刻用来确定将要运行的任务的 一组规则 40 88 4 1 调度策略概述调度策略概述 调度策略可以划分为以下三个主要的行为 脱机配置 运行时调度 先验性分析 脱机配置 运行时调度 先验性分析 脱机配置产生 运行时调度所需要 的静态信息 脱机配置产生 运行时调度所需要 的静态信息 运行时调度在 系统运行的时候根 据不同的事件在各 个计算之间进行切 换处理 运行时调度在 系统运行的时候根 据不同的事件在各 个计算之间进行切 换处理 先验性分析根据静 态配置信息和调度算法 在运行时的行为 分析 确定所有的时间需求是 否得到满足 先验性分析根据静 态配置信息和调度算法 在运行时的行为 分析 确定所有的时间需求是 否得到满足 先验性分析通过测 试来确定调度方法的可 行性 比如所有任务在 运行时的时间约束特性 是否都能得到满足 先验性分析通过测 试来确定调度方法的可 行性 比如所有任务在 运行时的时间约束特性 是否都能得到满足 41 88 4 1 调度策略概述调度策略概述 对于大量的实时调度方法而言 存在着以下几类主要的 划分方法 离线离线 off line 和在线和在线 0n line 调度 调度 抢占抢占 preemptive 和非抢占和非抢占 nonpreemptive 调度 调度 静态静态 static 和动态和动态 dynamic 调度 调度 最佳最佳 optimal 和试探性和试探性 heuristic 调度 调度 42 88 4 1 调度策略概述调度策略概述 根据获得调度信息的时机获得调度信息的时机 调度分为 离线调度离线调度 在线调度在线调度 对于离线调度算法 运 行过程中使用的调度信 息在系统 对于离线调度算法 运 行过程中使用的调度信 息在系统运行之前运行之前就确 定了 如时间驱动的调 度 就确 定了 如时间驱动的调 度 离线调度算法具有确定性 但缺乏灵活性 离线调度算法具有确定性 但缺乏灵活性 适用于那些特性能够预先确 定 且不容易发生变化的应 用 适用于那些特性能够预先确 定 且不容易发生变化的应 用 在线调度算法的调度信息是 在系统 在线调度算法的调度信息是 在系统运行过程中运行过程中动态获得 动态获得 如优先级驱动的调度如优先级驱动的调度 在线调度算法在形成最 佳调度决策上具有较大 的灵活性 在线调度算法在形成最 佳调度决策上具有较大 的灵活性 43 88 4 1 调度策略概述调度策略概述 根据任务在运行过程中能否被打断能否被打断的处理情况 调度分 为两类 抢占式调度抢占式调度 非抢占式调度非抢占式调度 在抢占式调度算法 中 正在运行的任 务可能被其他任务 所打断 在抢占式调度算法 中 正在运行的任 务可能被其他任务 所打断 在非抢占式调度算法在非抢占式调度算法中 一旦任务开始运行 该任 务只有在运行完成而主动 放弃 中 一旦任务开始运行 该任 务只有在运行完成而主动 放弃CPU资源 或是因为 等待其他资源被阻塞的情 况下才会停止运行 资源 或是因为 等待其他资源被阻塞的情 况下才会停止运行 实时内核大都采用了抢 抢 占式调度算法占式调度算法 使关键任 务能够打断非关键任务的 执行 确保关键任务的截 止时间能够得到满足 非抢占式调度算法非抢占式调度算法常用于 那些任务需要按照预先确 预先确 定的顺序定的顺序执行 且只有当 任务主动放弃CPU资源 后 其他任务才能得到执 行的情况 44 88 4 1 调度策略概述调度策略概述 根据任务优先级的确定时机任务优先级的确定时机 调度分为 静态调度静态调度 动态调度动态调度 在静态调度算法中 所有任务的优先级 在静态调度算法中 所有任务的优先级在 在 设计时设计时就确定下来 了 且在运行过程中 不会发生变化 就确定下来 了 且在运行过程中 不会发生变化 在动态调度算法中 任 务的优先级则 在动态调度算法中 任 务的优先级则在运行过 在运行过 程中程中确定 并可能不断 地发生变化 确定 并可能不断 地发生变化 静态调度静态调度算法适用于能够完 全把握系统中所有任务及其 时间约束特性的情况 算法适用于能够完 全把握系统中所有任务及其 时间约束特性的情况 静态调度比较简单 但缺乏 灵活性 不利于系统扩展 静态调度比较简单 但缺乏 灵活性 不利于系统扩展 动态调度动态调度有足够的灵活性有足够的灵活性灵活性灵活性来 处理变化的系统情况 但需 要消耗更多的系统资源 来 处理变化的系统情况 但需 要消耗更多的系统资源消耗更多的系统资源消耗更多的系统资源 45 88 4 1 调度策略概述调度策略概述 根据任务优先级的确定时机任务优先级的确定时机 调度分为 静态调度静态调度 动态调度动态调度 在静态调度算法中 所有任务的优先级 在静态调度算法中 所有任务的优先级在 在 设计时设计时就确定下来 了 且在运行过程中 不会发生变化 就确定下来 了 且在运行过程中 不会发生变化 在动态调度算法中 任 务的优先级则 在动态调度算法中 任 务的优先级则在运行过 在运行过 程中程中确定 并可能不断 地发生变化 确定 并可能不断 地发生变化 46 88 4 1 1 静态调度静态调度 在静态调度算法中 所有任务的优先级在静态调度算法中 所有任务的优先级在设计时在设计时在设计时在设计时就确定 下来了 且在运行过程中不会发生变化 就确定 下来了 且在运行过程中不会发生变化 静态调度算法适用于能够完全把握系统中所有任务及其 时间约束特性的情况 静态调度算法适用于能够完全把握系统中所有任务及其 时间约束特性的情况 优先级的确定可以依据任务的类型或重要性 例如 系 统任务的优先级要高于用户任务 实时任务的优先级要 高于非实时任务 优先级的确定可以依据任务的类型或重要性 例如 系 统任务的优先级要高于用户任务 实时任务的优先级要 高于非实时任务 47 88 4 1 1 静态调度静态调度 通常来说 在静态调度算法中通常来说 在静态调度算法中确立任务优先级的主要依 确立任务优先级的主要依 据据有四点 有四点 执行时间 周期 任务的 执行时间 周期 任务的CPU使用率 紧急程度 使用率 紧急程度 以执行时间为依据的调 度算法为 以执行时间为依据的调 度算法为 最短执行时间优先最短执行时间优先 最长执行时间优先最长执行时间优先 以周期为依据的调度 算法为 以周期为依据的调度 算法为 短周期任务优先 短周期任务优先 长周期任务优先 长周期任务优先 任务的任务的任务的任务的CPUCPU使用使用使用 使用 率率率率为任务计算时间 与任务周期的比值 为任务计算时间 与任务周期的比值 相应的调度算法为 相应的调度算法为 最小最小CPU使用 率优先 使用 率优先 最大最大CPU使用 率优先 使用 率优先 根据任务的紧急程度 以 人为的方式进行优先级的 静态安排 根据任务的紧急程度 以 人为的方式进行优先级的 静态安排 人为安排优先级人为安排优先级是嵌入式 实时软件开发中使用得非 常多的一种方法 是嵌入式 实时软件开发中使用得非 常多的一种方法 该方法以系统分析 对系统 需求的理解为基础 该方法以系统分析 对系统 需求的理解为基础 确定出系统中各个任务之间 的相对优先情况 确定出系统中各个任务之间 的相对优先情况 并据此确定出各个任务的优 先级 并据此确定出各个任务的优 先级 48 88 4 1 1 静态调度静态调度 静态调度的缺点 静态调度的缺点 高优先级的任务会一直占用着CPU运行 高优先级的任务会一直占用着CPU运行 而那些低优先级的任务可能会长时间地得 不到CPU 一直处于 而那些低优先级的任务可能会长时间地得 不到CPU 一直处于 饥饿饥饿 状态 状态 静态调度比较简单 但缺乏灵活性 不利于系统 扩展 静态调度比较简单 但缺乏灵活性 不利于系统 扩展 49 88 4 1 2 动态调度动态调度 在动态调度中 任务的优先级任务的优先级任务的优先级任务的优先级 可根据需要进行改变 可根据需要进行改变 也可能随着时间按照一定的策略自动发生变化 也可能随着时间按照一定的策略自动发生变化 在动态调度算法中 任务的优先级则在运行在运行在运行 在运行 过程中过程中过程中过程中确定 并可能不断地发生变化 50 88 4 1 2 动态调度动态调度 典型算法 截止时间优先调度算法 截止时间优先调度算法 最优的单处理器动态调度算法最优的单处理器动态调度算法 最短空闲时间优先调度算法最短空闲时间优先调度算法 51 88 4 1 2 动态调度动态调度 动态调度的出现是为了确保低优先级任务也能 确保低优先级任务也能 被调度被调度 这种公平性公平性对于所有任务都同等重要所有任务都同等重要的系 统比较合适 对于需要绝对可预测性绝对可预测性的系统一般不使用动 态调度 对于需要绝对可预测性绝对可预测性的系统 在出现临时过载临时过载的 情况下 要求调度算法能够选择最紧急的任务最紧急的任务执 行 而放弃那些不太紧急的任务 而动态调度的优先级只反映了任务的时间特性时间特性 没 有把任务的紧急程度紧急程度体现到优先级中去 52 88 4 1 2 动态调度动态调度 主要是由于主要是由于 动态调度在每一个调度点都需要对任务的优先级 进行重新计算 动态调度在每一个调度点都需要对任务的优先级 进行重新计算 而静态调度中任务的优先级则始终保持不变 不 需要进行计算 而静态调度中任务的优先级则始终保持不变 不 需要进行计算 动态调度动态调度有足够的有足够的灵活性灵活性灵活性灵活性来处理变化的系统情况 但需要 来处理变化的系统情况 但需要 消耗更多的系统资源消耗更多的系统资源消耗更多的系统资源消耗更多的系统资源 其其调度代价调度代价通常都比静态调度高 通常都比静态调度高 53 88 4 调度的策略调度的策略 调度策略调度策略概述概述 时间片轮转调度时间片轮转调度 基于优先级的调度基于优先级的调度 54 88 4 2 时间片轮转调度时间片轮转调度 时间片轮转调度 round robin scheduling 是指 时间片轮转调度 round robin scheduling 是指 当有两个或多个当有两个或多个就绪任务就绪任务具有具有相同的优先级相同的优先级 且它们是且它们是就绪任务就绪任务中中优先级最高优先级最高的任务时 的任务时 调度器按照调度器按照任务就绪的先后次序任务就绪的先后次序调度每个任务 调度每个任务 每个任务每个任务运行一段时间后运行一段时间后调度下一个任务 调度下一个任务 直到最后一个任务也得以运行一段时间后 接下来又让 第一个任务运行 直到最后一个任务也得以运行一段时间后 接下来又让 第一个任务运行 55 88 4 2 时间片轮转调度时间片轮转调度 56 88 4 2 时间片轮转调度时间片轮转调度 任务运行的这一段时间称 为 任务运行的这一段时间称 为时间片时间片 time slice time slice 57 88 4 2 时间片轮转调度时间片轮转调度 在时间片轮转调度方式中 当任务运行完一个 时间片后 该任务即使还没有停止运行 也必 须释放出处理器 让下一个与它有相同优先级 的任务运行 使实时系统中 在时间片轮转调度方式中 当任务运行完一个 时间片后 该任务即使还没有停止运行 也必 须释放出处理器 让下一个与它有相同优先级 的任务运行 使实时系统中优先级相同的任务 优先级相同的任务 具有平等的运行权利具有平等的运行权利 58 88 4 2 时间片轮转调度时间片轮转调度 释放处理器的任务被排到释放处理器的任务被排到同 同 优先级就绪任务链优先级就绪任务链的链尾 等待 再次运行 的链尾 等待 再次运行 59 88 4 2 时间片轮转调度时间片轮转调度 时间片轮转法的优点 时间片轮转法的优点 公平性公平性 活动性活动性 各个就绪任务平均地分 配 各个就绪任务平均地分 配CPU的使用时间 的使用时间 例如 假设有假设有n个就绪任务 那么每 个任务将得到 个就绪任务 那么每 个任务将得到1 n的的CPU时间 时间 每个就绪任务都能一直 保持着活动性 每个就绪任务都能一直 保持着活动性 假设时间片的大小为假设时间片的大小为q 那么 每个任务最多等待 那么 每个任务最多等待 n 1 q长的时 间 就能再次得到 长的时 间 就能再次得到CPU去运行 去运行 60 88 4 2 时间片轮转调度时间片轮转调度 采用时间片轮转调度算法时 任务的采用时间片轮转调度算法时 任务的时间片大小时间片大小要适当 选择 要适当 选择 时间片大小的选择会影响系统的性能和效率 时间片大小的选择会影响系统的性能和效率 时间片太大时间片太大时间片太大时间片太大 时间片轮转调度就没有意义 时间片轮转调度就没有意义 时间片太小时间片太小时间片太小时间片太小 任务切换过于频繁 处理器开销 大 真正用于运行应用程序的时间将会减小 任务切换过于频繁 处理器开销 大 真正用于运行应用程序的时间将会减小 61 88 4 2 时间片轮转调度时间片轮转调度 另外 不同的实时内核在实现时间片轮转调度算法上可 能有一些差异 另外 不同的实时内核在实现时间片轮转调度算法上可 能有一些差异 有的内核允许相同优先级的各个任务有有的内核允许相同优先级的各个任务有不一致不一致不一致 不一致 的时间片的时间片的时间片的时间片 有的内核要求相同优先级的任务具有有的内核要求相同优先级的任务具有一致的时一致的时一致的时 一致的时 间片间片间片间片 62 88 4 调度的策略调度的策略 调度策略调度策略概述概述 时间片轮转调度时间片轮转调度 基于优先级的调度基于优先级的调度 63 88 4 3 基于优先级的调度基于优先级的调度 时间片轮转调度有一个默认的前提 时间片轮转调度有一个默认的前提 位于就绪队列当中的各个任务是同等重要的位于就绪队列当中的各个任务是同等重要的位于就绪队列当中的各个任务是同等重要的位于就绪队列当中的各个任务是同等重要的 把它们按照先来后到把它们按照先来后到先来后到先来后到的顺序排成一个队列 大家轮流执行 的顺序排成一个队列 大家轮流执行轮流执行轮流执行相同长度的时间片 相同长度的时间片 64 88 4 3 基于优先级的调度基于优先级的调度 并不是每个任务都是同等重要的 并不是每个任务都是同等重要的 不同的任务对响应时间的要求不一样 不同的任务对响应时间的要求不一样 但是在实际的系统当中 尤其是在一些嵌入式 实时操作系统当中 但是在实际的系统当中 尤其是在一些嵌入式 实时操作系统当中 所以对它们的处理也应该有所区别 所以对它们的处理也应该有所区别 65 88 4 3 基于优先级的调度基于优先级的调度 基于优先级的调度的基本思路 基于优先级的调度的基本思路 给每一个任务都设置一个优先级 给每一个任务都设置一个优先级 然后在任务调度的时候 在所有处于就绪 状态的任务中选择优先级最高的那个任务 去运行 然后在任务调度的时候 在所有处于就绪 状态的任务中选择优先级最高的那个任务 去运行 66 88 4 3 基于优先级的调度基于优先级的调度 优先级算法可以分为两种 优先级算法可以分为两种 可抢占方式可抢占方式 不可抢占方式不可抢占方式 当一个任务正在运行的时 候 如果这时来了一个新的任 务 其优先级更高 那么在这种 情况下 是立即抢占 当一个任务正在运行的时 候 如果这时来了一个新的任 务 其优先级更高 那么在这种 情况下 是立即抢占CPU去运行 新任务 还是等当前任务运行完 后再决定 去运行 新任务 还是等当前任务运行完 后再决定 区别在于 区别在于 67 88 4 3 基于优先级的调度基于优先级的调度 任务1 任务2 任务3 任务1 任务2 抢占 抢占 任务3运行结束 任务2就绪 高 低 优先级 时间 任务2运行结束 任务3就绪 基于优先级的可抢占调度 68 88 4 3 基于优先级的调度基于优先级的调度 在任务优先级的确定方式任务优先级的确定方式任务优先级的确定方式任务优先级的确定方式上 可以分为 静态优先级方式静态优先级方式 在创建任务的时候就确定任务的 优先级 并且一直保持不变直到任务结束 动态优先级方式动态优先级方式 在创建任务的时候确定任务的优 先级 但是该优先级可以在任务的运行过程中动态 改变 以便获得更好的调度性能 静态调度静态调度 动态调度动态调度 69 88 4 3 基于优先级的调度基于优先级的调度 在优先级算法中 如果两个任务的优先级相 同 又该如何处理呢 把任务按照不同的优先级进行分组 把任务按照不同的优先级进行分组 然后在不同组的任务之间使用优先级算法 然后在不同组的任务之间使用优先级算法 而在同一组的各个任务之间使用时间片轮转法 而在同一组的各个任务之间使用时间片轮转法 通常的做法 通常的做法 时间片轮转调度 时间片轮转调度 70 88 4 3 2 基于优先级的可抢占调度基于优先级的可抢占调度 优先级可抢占与时间片轮转调度相结合方式下的任务运行情况优先级可抢占与时间片轮转调度相结合方式下的任务运行情况 任务1任务2 任务3 任务3运行结束 高 低 优先级 时间 任务2 任务3就绪 任务1任务2任务1任务2 71 88 4 3 基于优先级的调度基于优先级的调度 优先级队列优先级队列 72 88 内容提要 1 2 3 4 5 调度的时机调度的时机调度的时机调度的时机 调度的性能指标调度的性能指标调度的性能指标调度的性能指标 常见的调度算法常见的调度算法常见的调度算法常见的调度算法 调度的策略调度的策略调度的策略调度的策略 概述概述概述概述 73 88 下 节 讲 解 下 节 讲 解 5 常见的调度算法常见的调度算法 先来先服务算法先来先服务算法 短作业优先算法短作业优先算法 单调速率调度算法单调速率调度算法 最早截止期限优先调度算法最早截止期限优先调度算法 最早可达截止期限优先调度算法最早可达截止期限优先调度算法 最小裕度算法最小裕度算法 74 88 5 1 先来先服务算法 最简单的一种调度算法 First Come First Served FCFS First In First Out FIFO 先进先出算法 基本思想 按照任务到达的先后次序来进行调度 按照任务到达的先后次序来进行调度 75 88 5 1 先来先服务算法 FCFS算法示意图 它是一种它是一种不可抢占不可抢占不可抢占不可抢占的调度方式 如果当前任务占用 着 的调度方式 如果当前任务占用 着CPU运行 那么就要一直等到它执行完毕或者因 为某种原因被阻塞 才会让出 运行 那么就要一直等到它执行完毕或者因 为某种原因被阻塞 才会让出CPU给其他的任务 给其他的任务 另外 对于一个被阻塞的任务另外 对于一个被阻塞的任务被阻塞的任务被阻塞的任务 当它被唤醒 之后 就会把它放在就绪队列的末尾 当它被唤醒 之后 就会把它放在就绪队列的末尾就绪队列的末尾就绪队列的末尾 重新开始 排队 重新开始 排队 76 88 5 1 先来先服务算法 优点优点优点优点 简单 简单 易于理解 易于理解 也易于实现 也易于实现 77 88 5 1 先来先服务算法 FCFS算法不能保证任务的时限 一批任务的平均周 转时间取决于各个任务到达的顺序 如果