第3章处理机调度.ppt
《第3章处理机调度.ppt》由会员分享,可在线阅读,更多相关《第3章处理机调度.ppt(57页珍藏版)》请在三一文库上搜索。
1、第三章 处理机调度(CPU调度),无论在多道批处理系统还是分时系统中, 系统中的用户进程数都远远超过处理机数, 除用户进程要占用处理机外, 操作系统还要建立若干个系统进程完成系统功能。这么多的进程竞争处理机, 就要求系统提供进程调度功能, 以便采用一些策略, 将处理机动态地分配给系统中的各个就绪进程, 使之执行。分配处理机的任务是由处理机调度程序完成的; 处理机是计算机最重要的资源, 如何提高处理机的利用率及改善系统性能, 在很大程度上取决于处理机调度性能的好坏, 处理机调度成为操作系统设计中心工作。,要解决的问题 WHAT:按什么原则分配CPU 进程调度算法 WHEN:何时分配CPU 进程调
2、度的时机 HOW: 如何分配CPU CPU调度过程(进程的上下文切换),一批作业从进入系统到作业运行完毕可能经历三级调度高级、低级和中级调度。 一. 高级调度(High Scheduling) 又称为作业调度接纳调度或长程调度, 用于批处理系统, 确定将外存后备队列中哪些作业调入内存, 并为它们创建进程。实时系统和分时系统的前台作业不需要作业调度。每次作业调度时, 都必须做出两个决定: 1) 接纳多少个作业: 取决于多道程序度。 2) 接纳哪些作业(用什么调度算法): 先来先服务、短作业优先、优先权、响应比优先。,3.1 处理机调度的基本概念 3.1.1 高级、低级和中级调度,响应/运行,二.
3、 低级调度(进程调度,短程调度) 进程调度的任务是控制协调进程对CPU的竞争, 即按照一定的调度算法从就绪队列中选中一个进程,把CPU的使用权交给被选中的进程。它是最基本的一种调度, 批处理系统, 实时系统和分时系统都必须有进程调度。它通过进程调度程序来完成。 1. 进程调度程序的主要功能可描述如下: (1) 记录系统中各进程的状况 为了很好地实现进程调度, 进程调度程序首先必须管理系统中各进程的PCB,将进程的状态变化及资源需求情况及时地记录到PCB中。通过PCB变化来准确地掌握系统中所有进程的状态特征和执行情况。,(2) 选择进程真正占有CPU 这是进程调度的实质, 即按照系统规定的调度策
4、略从就绪队列中选择一个进程占有CPU执行。进程调度依据的算法与系统的设计目标相一致。对于不同的系统, 通常采用不同的调度策略。对于批处理系统常采用短进程的进程优先, 以减少各进程的周转时间。对于分时系统, 更多地采用时间片轮转。 (3) 进行进程上下文的切换 当进程调度选中一个进程占有CPU时, 进程调度程序要做的主要工作则是进行进程上下文切换: 将正在执行进程的运行现场保留在该进程的PCB中, 以便以后该进程恢复执行。将刚选中进程的运行现场恢复起来, 并将CPU的控制权交给被选中进程, 使其执行。,2. 进程调度方式 (1)非抢占方式(Non preemptive mode) 在非抢占方式下
5、, 调度程序一旦把 CPU分配给某一进程后便让它一直运行下去, 直到进程完成或发生某事件而不能运行时,才将CPU分给其它进程。 这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。 (2)抢占方式(Preemptive mode) 当一个进程正在执行时,系统可以基于某种策略剥夺CPU给其它进程。剥夺的原则有: 优先权原则、短进程优先原则、时间片原则。 显然这种调度方式多用在分时系统和实时系统中,以便及时响应各进程的请求。,3. 进程调度的时机 所谓进程调度的时机,是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下:,正在执行的进程正确完
6、成, 或由于某种错误而终止运行(陷阱或中断) ; 执行中的进程提出I/O请求, 等待I/O完成时; 在分时系统中, 按照时间片轮转, 分给进程的时间片用完时; 按照优先级调度时, 有更高优先级进程变为就绪时(抢占方式); 在进程通讯中, 执行中的进程执行了某种原语操作, 如wait操作、阻塞原语和唤醒原语时, 都可能引起进程调度。,三. 中级调度(中程调度) 中级调度使暂时停止的进程不再占用宝贵的内存资源, 将它们调到外存上去成为挂起状态。当处于挂起就绪的进程重新具备运行条件且内存稍有空闲时, 中级调度将它重新调入内存, 挂在活动就绪队列上等待进程调度。中级调度实质上就是存储管理中的对换功能。
7、 进程调度频率最高(10100ms/次)调度算法简单快速; 作业调度频率最低约几分钟一次,调度算法允许花费较多的时间; 中级调度介于两者之间。,3.1.2. 调度队列模型,1. 仅有进程调度的调度队列模型 在分时系统中, 通常仅有进程调度, 采用FIFO算法。,CPU,就 绪 队 列,阻 塞 队 列,时间片完,进程调度,等待事件,事件 出现,交互用户,完成,2. 具有高级和低级调度的调度队列模型 在批处理系统中,不仅需要进程调度而且需要作业调度。,3. 具有三级调度的调度队列模型 在具有三级调度系统中, 增加了在外存的挂起状态,对于不同的系统, 有不同的设计目标, 采用不同的调度算法。调度算法
8、实质上是个策略问题 面向用户的准则: 周转时间短 交互式系统的响应时间快 截止时间保证 优先权准则(公平合理) 面向系统的准则: 单位时间内运行尽可能多的进程, 吞吐量高 使处理机尽可能保持“忙碌”利用率高 使内外存、I/O设备得以均衡、充分利用,3.1.3. 调度算法的评价准则,进程(作业)平均周转时间(周转时间、吞吐量) 设某进程创建时间为Si, 结束的时间为Ei 它的周转时间(全过程所用时间)为 Ti =Ei Si 系统为它提供的实际服务时间为Tsi 则进程平均周转时间T,带权平均周转时间W为: T W= 其中,n为被测定进程流中的进程数,要设计一个理想的调度算法是一件十分困难的事,在实
9、际系统中, 调度算法往往折衷考虑。 大多数操作系统都采用比较简单的调度算法,3.2 调度算法,1.先进先出调度算法(FIFO) (先来先服务FCFS) 作业调度按照进入后备队列的先后次序调度, 进程调度按照进入进程就绪队列的先后次序来调度 优点:实现简单 缺点:不利于短作业(进程),紧迫性作业(进程)得不到及时处理 2.短作业(进程)优先调度算法(SJF,SPF) 选择就绪队列中估计运行时间最短的进程投入运行 优点: 平均周转时间,带权平均周转时间都改善 缺点: 对长作业(进程)非常不利 不能保证紧迫性作业(进程)得到及时处理 估计运行时间不准确,3. 优先权调度算法(HPFHighest P
10、riority First) 优先选择就绪队列中优先权最高的进程投入运行 非抢占式优先权算法:仅在事件发生放弃处理机时 抢占式优先权算法: 可将正在运行的运行权剥夺 优先权的类型 静态优先权: 在进程创建时指定优先权, 在进程运行时优先数不变 动态优先权: 在进程创建时创立一个优先权,但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变 确定优先权的依据 进程类型、对资源的需求、根据用户要求,4. 高响应比优先调度算法: 改进短作业(进程)优先调度算法,优先权用下式动态计算出来 优先权= = 上式可看出 等待时间相同要求服务的时间越短优先权越高, 有利于短作业 要求服务时间相同,等待时
11、间越长优先权越高,近似于先来先服务 长作业的优先权会随等待时间加长而升高,长作业也会得到执行,把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程,进程轮流占有CPU,当时间片用完时,即使进程未执行完毕,系统也剥夺该进程的CPU,将该进程排在就绪队列末尾。同时系统选择另一个进程运行 分时系统中常用时间片轮转法 时间片选择问题: 固定时间片、可变时间片 确定时间片大小的因素: 系统响应时间、就绪进程个数、CPU能力,5.时间片轮转调度算法,6.多队列反馈调度算法: 系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片,优先级高的第一级队列时间片最小, 随着队列优先级
12、的降低, 时间片加大 各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃CPU后, 进入等待队列, 一旦等待的事件发生, 则回到原来的就绪队列 当有一个优先级更高的进程就绪时, 可以抢占CPU,被抢占进程回到原来一级就绪队列末尾 当第一级队列空时, 就去调度第二级队列, 如此类推 时间片用完后进程放弃CPU, 进入下一级就绪队列,实时系统中, 对实时进程的调度有截止时间的要求 1.实现实时调度的基本条件 1) 提供必要的信息 就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级( 硬实时任务赋绝对优先级)。 2) 系统处理速度快 若系统中有m
13、个周期性硬实时任务, 处理时间为Ci周期时间为Pi , 则处理机处理速度应达到可调度条件: 1 (单处理机) n (多处理机) 3) 采用抢占式调度机制以满足对截止时间的要求 4) 具有快速切换机制: 快速中断响应、快速任务分派,3.3 实时调度,2. 实时调度算法的分类 1) 非抢占式调度算法 非抢占式轮转调度算法(响应时间数秒到数十秒) 轮转一圈后调度 非抢占式优先权调度算法(响应时间数百毫秒) 当前进程完成(或被阻塞)后调度 2) 抢占式调度算法 严格要求的实时系统, 响应时间在数十毫秒以内 基于时钟中断的抢占式调度算法 时钟中断到来时调度 立即抢占的优先权调度算法 立即剥夺当前进程 调
14、度时间见P 83 图3-6,3.几种常见的实时调度算法 1) 最早截止时间优先算法(Earliest Deadline First) 根据任务的开始截止时间确定优先级。 2) 最低松弛度优先算法(Least Laxity First) 根据任务的松弛度(紧急程度)确定优先级 根据任务完成截止时间和本身运行时间确定松弛度 松弛度= 必须完成时间-本身运行时间-当前时间 P 85 图 3-9,保存现场:顺序保存进程的上下文, 包括程序计数器和其它寄存器 用新状态和相关信息更新正在运行进程的PCB 把该进程移至合适的队列-就绪、阻塞 选择另一个要执行的进程,更新该进程的PCB 从被选中进程中重装入
15、CPU 上下文,恢复现场 若无就绪进程,系统会安排一个闲逛进程(idle), 一直运行, 在执行过程中可接收中断。,3.4 CPU调度的实现,操作系统的核心 向上提供无中断的虚拟机器, 在核心内不允许中断 特点: 核心常驻内存, 短小精焊, 为进程运行提供舞台 核心的组成 中断处理: 时钟、I/O、虚拟存储器 进程管理: 调度 控制 通讯 互斥 同步等 原语管理: 提供一系列原语, 同步, 通信, 创建, 撤消等 队列管理:中断之后调度之前(运行-就绪-等待队列) 现场管理: 保存现场、恢复现场 时钟管理: 绝对时钟、间隔时钟、虚时钟,保存现场、分析中断源 处理中断 原语管理、队列管理、时钟管
16、理、进程调度 恢复现场,中断,核心入口,核心处理流程 唯一入口: 中断,由硬件完成,作业: P101 2, 3, 5,3.5死锁,死锁的基本概念 死锁的解决方案 (预防,避免,检测及解除) 资源分配图,3.5.1 死锁的基本概念,死锁(Deadlock)的定义: 一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程 说明: 参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 注意:如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃。,死锁产生的原因 1.竞争资源引起 永
17、久性资源:可被多个进程多次使用(可再用资源) 剥夺性资源(CPU、内存) 非剥夺性资源(磁带机、打印机) 竞争非剥夺性资源会引起死锁 临时性资源:只可使用一次的资源; 如信号量,中断信号,同步信号等(可消耗性资源) 竞争临时性资源也会引起死锁 2. 进程推进顺序不当引起 对资源采用“申请-分配-使用-释放”模式, 由于推进顺序不当两进程都要申请对方已占有的资源,P1: 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 ,P2: 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 ,死锁的例子: 竞争非剥夺性资源进程推进顺序不当引起死锁,Req(R1) Req(R2) Rel(R1) Re
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 处理机 调度
链接地址:https://www.31doc.com/p-2577362.html