chapter6[1]

null操作系统概念操作系统概念第六章：CPU调度本章主要内容本章主要内容基本概念 调度准则 调度算法 多处理器调度 实时调度 算法评估 进程调度模型6.1 基本概念6.1 基本概念利用多道程序最大化CPU使用率。 CPU – I/O周期 － 进程执行由CPU执行和I/O等待周期组成。 CPU区间分布情况CPU区间和I/O区间的交替序列CPU区间和I/O区间的交替序列CPU区间时间直方图CPU区间时间直方图CPU调度程序CPU调度程序调度程序从内存中就绪可执行的进程里选择一个，并为其中之一分配CPU。 CPU调度决策可以如下四种情况下发生 当一个进程从运行状态切换到等待状态 当一个进程从运行状态切换到就绪状态 当一个进程从等待状态切换到就绪状态 当一个进程终止时。 当调度只能发生在第一和第四两种情况时，称调度方法是非抢占的（nonpreemptive） 否则调度 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 就是可抢占（preemptive）的。分派程序（Dispatcher）分派程序（Dispatcher）分派程序是一个模块，用来将CPU的控制交给由短期调度程序所选择的进程。其功能包括 切换上下文 切换到用户模式 跳转到用户程序的合适位置以重新启动这个程序 分派延迟（dispatch latency） － 分派程序停止一个进程而启动另一个进程执行所要花费的时间。6.2 调度准则（Scheduling Criteria）6.2 调度准则（Scheduling Criteria）CPU使用率：使CPU尽可能忙 吞吐量（Throughput）：单位时间完成进程的数量 周转时间（Turnaround time）：从进程提交到进程完成的时间间隔称为周转时间 等待时间（Waiting time）：是在就绪队列中等待所花时间之和。 响应时间（Response time）：从提交请求到产生第一响应的时间。优化准则（Optimization Criteria）优化准则（Optimization Criteria）最大化CPU使用率 最大化吞吐量 最小化周转时间 最小化等待时间 最小化响应时间6.3 调度算法6.3 调度算法先到先服务调度（First Come, First Served, FCFS） 最短作业优先调度（Shortest-Job-First, SJR） 优先权调度（Priority Scheduling） 轮转法调度（Round Robin, RR） 多级队列调度（multilevel queue-scheduling） 多级反馈队列调度（multilevel feedback queue scheduling）先来先服务调度（FCFS）先来先服务调度（FCFS）假设进程按P1、P2、P3的顺序到达。则该调度的Gantt图如下：等待时间：P1 = 0; P2 = 24; P3 = 27 平均等待时间： (0 + 24 + 27) / 3 = 17 假设进程按P2, P3, P1的顺序到来，则其调度的Gannt图如下等待时间：P1 = 6; P2 = 0; P3 = 3 平均等待时间： (6 + 0 + 3) / 3 = 3 优于前一种情况 由于所有其他进程都等待一个大进程释放CPU，就会产生护航效果（convoy effect）。与可能允许较短进程先行相比，这种效果会导致CPU和设备的使用率真变得更低最短作业优先调度(Shortest-Job-First, SJR)最短作业优先调度(Shortest-Job-First, SJR)将每个进程与其下一个CPU区间段相关联。当CPU为可用时，它会赋给具有最短后续CPU区间的进程。如果两个进程具有同样长度的CPU区间，那么可以使用FCFS调度来处理。 两种方式 非抢占式：一旦进程获得CPU就一直占据CPU，直到其CPU区间完成为止 抢占式：如果一个新来的进程其CPU区间小于当前进程的CPU区间，则抢占之。这种调度方式称为最短剩余时间作业优先（Shortest Remaining Time First, SRTF） SJF是最佳的：对于给定的一组进程，SJF算法的平均等待时间最小。非抢占式SJF的实例非抢占式SJF的实例抢占式SJF的实例抢占式SJF的实例确定下一CPU区间的长度确定下一CPU区间的长度只能估计CPU区间的长度，无法精确计算 下一CPU区间的长度通常可预测为以前CPU区间的测量长度的指数平均 下一个CPU区间长度的预测下一个CPU区间长度的预测指数平均计算的实例指数平均计算的实例优先级调度（Priority Scheduling）优先级调度（Priority Scheduling）每个进程被赋予一个优先级数字（优先权） CPU分配给优先权高的进程（优先级数字越小，则优先权越大） 抢占式 非抢占式 SJF是一种特定的优先权调度方法，其优先权为下一个CPU区间的倒数 该算法存在的问题：饥饿（starvation） 低优先权的进程可能永远无法执行 解决办法：老化（aging） 随着时间的推进，进程的优先权逐渐提高 轮转法调度（Round Robin）轮转法调度（Round Robin）轮转法是专门为分时系统而 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的。每个进程获得一小片CPU时间量（time quantum），通常为10-100毫秒。时间片结束后，进程被抢占并放入到就绪队列的最后重新参加调度。 如果就绪队列中有n个进程，具时间片为q，则每个进程会得到1/n的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过(n-1)q个时间单元，直到它的下一个时间片为止。 性能低速于时间片的大小 如果时间片非常大（无限），那么RR策略与FCFS策略一样。 如果时间片很小，那么RR方法称处理器共享。n个进程对于用户来说都有它自己的处理器，速度各为真正处理器速度的1/n q必须大于上下文切换所需时间 时间片＝20时的RR实例时间片＝20时的RR实例时间片与上下文切换开销时间片与上下文切换开销周转时间随时间片大小而改变周转时间随时间片大小而改变多级队列调度多级队列调度就绪队列分成几个相对独立的队列 前台（或交互式） 后台（或批处理） 每个队列有自己的调度算法 前台：RR 后台：FCFS 队列之间必须有调度 通常采用固定优先权可抢占调度来实现。 另一种 可能是在队列之间划分时间片。每个队列都有一定的CPU时间，这可用于调度队列内的不同进程 20％给后台，80％给前台多级队列调度示意图多级队列调度示意图多级反馈队列调度多级反馈队列调度进程可以在不同队列间移动 通常，多级反馈队列调度程序可由下列参数来定义： 队列数量 每个队列的调度算法 用以确定进程何时升级到较高优先权队列的方法 用以确定进程何时降级到较低优先权队列的方法 用以确定进程在需要服务时应进入哪个队列的方法多级反馈队列调度的实例多级反馈队列调度的实例三个队列 Q0：时间片为8毫秒 Q1：时间片为16毫秒 Q2：FCFS 调度 进入就绪队列的进程被放在队列Q0内。队列0的每个进程都有8ms的时间片。如果一个进程不能在这一时间内完成，那么它就被移到队列1的尾部。 如果队列0为空，队列1头部进程会得到一个16ms的时间片。如果它不能完成，那么它将被抢占，并被放到队列2中。 只有当队0和队1为空时，队列2内的进程才可根据FCFS来运行。多级反馈队列示意图多级反馈队列示意图6.4 多处理器调度6.4 多处理器调度多处理器调度问题更复杂 主要讨论处理器功能相同的系统。 负载分配（Load Sharing） 非对称多道程序：只有一个处理器访问系统数据结构，减轻了数据共享的需要。6.5 实时调度6.5 实时调度硬实时系统： 需要在保证的时间内完成关键任务 在提交进程时，同时有一条语句告诉系统用来完成或执行I/O所需要的时间。接着，调度程序或者允许进程并保证进程能按时完成，或者因不可能而拒绝请求。（资源预约） 软实时系统： 要保证关键进程拥有比其他进程更高的优先权 要求仔细设计调度程序和操作系统有关方面。 第一、系统必须有优先权调度，且实时进程必须有最高的优先权。实时进程的优先权不能随时间而下降，尽管非实时进程的优先权可以。 实时进程不应该老化 第二、分派延迟必须小。 内核抢占分派延迟分派延迟6.6 算法评估6.6 算法评估确定性建模：采用特定预先确定的负荷，定义在给定负荷下每个算法的性能。 简单快速，给出了确切数字，以允许算法被比较 但通常过分特殊且要求过多精确知识，故用处有限 排队模型： 在许多系统上运行的进程每天都在变化，因此没有静态　的进程集合和时间用于确定性建模。 n为平均队列长度（不包括正在服务的进程） Ｗ为队列的平均等待时间 λ为新进程到达队列的平均到达率 n =λ×W (Little公式) 可用于比较调度算法，但计算结果的精确性值得怀疑通过模拟来评估CPU调度算法通过模拟来评估CPU调度算法实现实现即使模拟其精确度也是有限的。针对评估调度算法，惟一完全精确的方法是对它进行程序编码，将其放在操作系统内，并观测它如何工作。 主要困难是这种方法的代价 对算法编码、修改操作系统以支持该算法 用户对不断变化的操作系统的反应 另一困难是算法所使用的环境会变化 最为灵活的调度算法可以为系统管理员或用户所改变Linux调度Linux调度两种算法：分时与实时 分时 基于信用度的算法 信用度随着定时器中断的发生而降低 当所有进程的信用度都为0的时候，则重新计算信用度 这种算法似乎混合了两个因素：进程历史和它的优先级 实时 软实时 实现了两种POSIX.1b所要求的实时调度类型：FCFS 和 RR 高优先级的进程总是最先运行