第四章 调度与.ppt

第四章调度与 在多道程环境下 进程数目往往多于处理机数目 致使它们争用处理机 这就要求系统能按某种算法 动态地把CPU分配给就绪队列中的一个进程 使之执行 分配CPU的任务是由进程调度程序完成的 它是操作系统设计的中心问题之一 4 1调度的层次与性能评价4 1 1调度的层次1 作业调度 为进程的活动做准备 又称宏观调度 高级调度 运行频率较低 通常为几分钟一次在系统中可以不设2 进程调度 使进程活动起来 又称微观调度 低级调度 运行频率较高 通常为几十毫秒一次 在系统中必不可少 3 中级调度 内存的管理 又称中程调度或交换调度 功能 根据内存的使用情况 完成进程的换入或换出运行频率介于作业调度与进程调度之间4 1 2调度性能的评价1 调度算法应达到的目标 实际采用的调度算法往往依赖于系统的设计目标 系统的设计目标可以是 1 系统的处理能力高 系统每天运行尽可能多的作业 2 系统资源利用充分 使CPU 各个设备保持忙碌状态 3 算法对所有的作业公平合理2 确定调度算法时应考虑的因素 1 设计目标 2 资源使用的均衡性 3 平衡系统和用户的要求 3 调度性能的评价准则面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则面向系统的准则 系统吞吐量高 CPU用率好 各类资源的平衡利用 1 CPU的利用率 2 系统吞吐量 表示单位时间内CPU完成作业的数量 3 周转时间 从作业提交到作业完成之间的时间间隔 4 响应时间 从用户提交请求到系统首次产生响应所用的时间不同系统可有一级 二级 三级调度 但进程调度必不可少 4 2作业调度4 2 1作业的状态及转换一个作业从进入系统到运行结束 一般需要经历提交 收容 运行 完成4个阶段 与这4个阶段相对应的作业处于提交 后备 运行和完成4种状态1 提交状态用户作业由输入设备向系统外存 硬盘 输入时作业所处的状态称为提交状态2 后备状态当一个作业通过输入设备送入计算机 并由OS将其存放在磁盘 硬盘 中以后 系统为这个作业建立一个作业控制块 并把它插入到后备作业队列中等待调度运行 3 运行状态当作业调度程序选中一个作业 为它分配了必要的资源并建立了相应的进程之后 这个作业就由后备状态转变为运行状态从宏观上看 作业一旦由作业调度程序选中进入内存就开始了运行从微观上讲 作业进入内存的三种状态a 就绪态b 运行态 CPU c 阻塞态4 完成状态当作业正常运行结束或因发生错误而终止运行时 作业就处于完成状态 4 2 2作业调度作业调度的主要功能是按照某种原则从后备作业队列中选取作业进入内存 并为作业做好运行前的准备工作和作业完成后的善后处理工作 完成这种功能的程序称为作业调度程序1 作业调度程序的功能 1 记录进入系统的各个作业情况 2 从后备作业中挑选一些作业投入执行 3 为选中的作业做好执行前的准备工作 4 在作业运行结束或运行过程中因某种原因需要撤离时 作业调度程序还要完成作业的善后处理工作2 作业控制块 JCB 进程控制块 PCB 主要内容 1 资源要求 2 资源使用情况 3 作业的控制方式 类型和优先级等 4 作业名 作业状态 4 3进程调度 进程 1 用户进程2 系统进程在多道程序系统中 用户进程数目往往多于CPU的个数 此外 系统进程也需要使用CPU 因此 OS需要按一定的策略动态的把CPU分配给就绪队列中的某个进程 以便让它执行 CPU分配的任务由进程调度程序完成4 3 1进程调度的功能1 记录系统中所有进程的有关情况及状态特征 PCB 2 选择获得CPU的进程3 CPU分配4 3 2进程调度的方式指当某一个进程正在处理机上执行时 若有某个更为重要或紧迫的进程需要进行处理 即有优先级更高的进程进入就绪队列 此时应如何分配CPU 1 抢占方式 2 非抢占方式 4 4调度算法 4 4 1先来先服务调度算法可用于 作业调度进程调度作业调度中 每次从后备作业队列中选择最先进入该队列的一个或几个作业 将它们调入内存 分配必要的资源 创建进程并放入就绪队列进程调度中 每次从就绪队列中选择最先进入该队列的进程 将处理机分配给它 使之投入运行 该进程一直运行下去 直到完成或因某种原因而阻塞时才释放CPU特点 1 算法简单 但没考虑进程的优先级 效率较低2 有利于长作业但对短作业不利3 有利于CPU繁忙型作业而不利于I O繁忙型作业 4 4 2短作业 短进程优先调度算法可用于 作业调度进程调度作业调度中 每次从后备作业队列中选择估计运行时间最短的一个或几个作业 将它们调入内存 分配必要的资源 创建进程并放入就绪队列进程调度中 每次从就绪队列中选择估计运行时间最短的进程 将处理机分配给它 使之投入运行 该进程一直运行下去 直到完成或因某种原因而阻塞时才释放CPU特点 具有较短的平均周转时间和平均带权周转时间 具有较好的调度性能 但该算法对长作业不利 4 4 3优先级调度算法 1 可用于 作业调度进程调度作业调度中 每次从后备作业队列中选择优先级最高的的一个或几个作业 将它们调入内存 分配必要的资源 创建进程并放入就绪队列进程调度中 每次从就绪队列中选择优先级最高的进程 将处理机分配给它 使之投入运行 2 优先级进程调度算法 a 非抢占式优先级进程调度算法b 抢占式优先级进程调度算法进程的优先级用于表示进程的重要性及运行的优先性 一般用优先数来衡量 3 优先级分类 静态优先级动态优先级 4 4 4时间片轮转调度算法主要用于分时系统中的进程调度把CPU划分成若干时间片 并且按到达的先后顺序分配给给就绪队列中的每一个进程 进程轮流使用CPU 当时间片用完时 即使进程未执行完毕 系统也剥夺该进程的CPU 将该进程排在就绪队列末尾 同时系统选择另一个进程运行时间片的选择 1 系统的响应时间 分时系统必须满足系统对响应时间的要求 T Nq其中 T 系统响应时间q 时间片大小N 就绪队列中的进程数2 就绪队列中的进程数3 系统的处理能力 通常要求用户输入的常用命令能够在一个时间片内处理完毕 因此 计算机的速度越快 时间片就越短 4 4 5高响应比优先调度算法主要用于作业调度 是对先来先服务调度算法和短作业优先调度算法的一种综合平衡 实现思想 每次进行作业调度时 先计算后备作业队列中每个作业的响应比 然后挑选响应比最高的作业投入运行 响应比 作业响应时间 估计运行时间 1 作业等待时间 估计运行时间相同等待时间 短作业优先相同运行时间 等待时间长的作业优先缺点 作业调度前需要计算后备队列中每个作业的响应比 从而增加了系统开销 4 4 6多级队列调度算法主要用于进程调度基本思想 根据进程的性质或类型 将就绪队列划分为若干个子队列 每个进程固定属于一个就绪队列 每个就绪对列采用一种调度算法 不同的队列可以采用不同的调度算法4 4 7多级反馈队列调度算法 是时间片轮转调度算法和优先级调度算法的综合和发展 通过动态调整进程优先级和时间片大小 多级反馈队列调度算法可以兼顾多方面的系统目标特点 1 如对终端型作业而言 由于这类作业需要的CPU时间较短 因而能够在前一两个队列中完成2 短作业能在前几个队列中完成3 长作业可以依次在各队列中得到服务 4 4 7多级反馈队列调度算法 4 5死锁多个进程的并发执行 改善了系统资源的利用率并提高了系统的处理能力 也带来了新问题 死锁4 5 1死锁的概念举例 1 两辆汽车过桥2 上机时 Ctrl Alt Delete概念 指多个进程因竞争系统资源或相互通信而处于永久阻塞状态 若无外力作用 这些进程都将无法向前推进一组进程中 每个进程都无限等待被该组进程中另一进程所占有的资源 因而永远无法得到的资源 这种现象称为进程死锁 这一组进程就称为死锁进程 4 5 2死锁产生的原因和必要条件1 资源分类 1 可剥夺资源 例CPU 2 不可剥夺资源 例打印机按资源使用期限来看 可再次使用的永久资源 硬件资源消耗性的临时资源 进程同步和通信中出现的消息 信号和数据 2 死锁产生的原因 1 竞争资源 2 进程推进顺序不当若系统中只有一台打印机R1和一台扫描仪R2 可供进程P1和P2共享 若形成环路 这样会产生死锁 参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集3 死锁产生的必要条件 1 互斥条件 资源独占 2 不剥夺条件 不可强占 3 请求和保持条件 部分分配 占有申请 4 循环等待条件 4 5 3处理死锁的基本办法 1 忽略死锁 2 预防死锁 3 避免死锁 4 检测及解除死锁4 5 4死锁的预防要想防止死锁的发生 只需要破坏死锁产生的4个必要条件之一即可 1 互斥条件 2 资源一次性分配 破坏请求和保持条件 3 可剥夺资源 即当某进程新的资源未满足时 释放已占有的资源 破坏不可剥夺条件 4 资源有序分配法 做法 系统给每类资源赋予一个编号 按使用价值或频度 每一个进程按编号递增的顺序请求资源 同类资源一次申请完 释放则相反 破坏循环等待条件 问题 a 限制资源的使用b 编号不易例 资源R1R2R3 Rn序号123 n进程P3申请了R3 则P3以后只能申请比R3序号大的资源进程对资源的需求是自身动态的执行决定的 4 5 5死锁的避免死锁避免定义 在系统运行过程中 对进程发出的每一个系统能够满足的资源申请进行动态检查 并根据检查结果决定是否分配资源 若分配后系统可能发生死锁 则不予分配 否则予以分配 预防死锁的几种策略 会严重地损害了系统性能 因此要施加较弱的限制 从而获得较满意得系统性能来避免死锁 由于在避免死锁的策略中 允许进程动态地申请资源 因而 系统在进行资源分配之前预先计算资源分配的安全性 若此次分配不会导致系统进入不安全状态 则将资源分配给进程 否则 进程等待 其中最具有代表性的避免死锁算法是银行家算法 1 安全状态与不安全状态安全状态 如果在某一时刻 系统能按某种顺序如来为每个进程分配其所需的资源 直至最大需求 使每个进程都可以顺利运行完成 则称此时的系统状态为安全状态安全序列 进程序列 若对于每一个进程Pi 1为一个安全序列说明 1 系统处于安全状态 则一定不会进入死锁状态 2 若产生死锁 则系统一定处于不安全状态 3 但是 系统处于不安全状态 也未必会产生死锁 1 安全状态之例 我们通过一个例子来说明安全性 假定系统中有三个进程P1 P2和P3 共有12台磁带机 进程P1总共要求10台磁带机 P2和P3分别要求4台和9台 假设在T0时刻 进程P1 P2和P3已分别获得5台 2台和2台磁带机 尚有3台空闲未分配 如下表所示 安全序列 P2P1P3 2 由安全状态向不安全状态的转换 如果不按照安全序分配资源 则系统可能会由安全状态进入不安全状态 例如 在T0时刻以后 P3又请求1台磁带机 若此时系统把剩余3台中的1台分配给P3 则系统便进入不安全状态 因为 此时也无法再找到一个安全序列 例如 把其余的2台分配给P2 这样 在P2完成后只能释放出4台 既不能满足P1尚需5台的要求 也不能满足P3尚需6台的要求 致使它们都无法推进到完成 彼此都在等待对方释放资源 即陷入僵局 结果导致死锁 2 银行家算法 为系统寻找一个安全序列 基本思想 为每个进程分配资源前 先判断如果给该进程分配了资源 系统是否安全 若是安全的 才分配 假定系统中有n个进程 P1 P2 Pn m类资源 R1 R2 Rm 银行家算法数据结构如下 可利用资源向量Available 这是一个含有m个元素的数组 其中的每一个元素代表一类可利用的资源数目 其初始值是系统中所配置的该类全部可用资源的数目 其数值随该类资源的分配和回收而动态地改变 如果Available j K 则表示系统中现有Rj类资源K个 2 最大需求矩阵Max 这是一个n m的矩阵 它定义了系统中n个进程中的每一个进程对m类资源的最大需求 如果Max i j K 则表示进程i需要Rj类资源的最大数目为K 3 分配矩阵Allocation 这也是一个n m的矩阵 它定义了系统中每一类资源当前已分配给每一进程的资源数 如果Allocation i j K 则表示进程i当前已分得Rj类资源的数目为K 4 需求矩阵Need 这也是一个n m的矩阵 用以表示每一个进程尚需的各类资源数 如果Need i j K 则表示进程i还需要Rj类资源K个 方能完成其任务 上述三个矩阵 Need i j Max i j Allocation i j 2 银行家算法实现思想设Requesti是进程Pi的请求向量 如果Requesti j K 表示进程Pi需要K个Rj类型的资源 当Pi发出资源请求后 系统按下述步骤进行检查 1 如果Requesti j Need i j 便转向步骤2 否则认为出错 因为它所需要的资源数已超过它所宣布的最大值 2 如果Requesti j Available j 便转向步骤 3 否则 表示尚无足够资源 Pi须等待 3 系统试探着把资源分配给进程Pi 并修改下面数据结构中的数值 Available j Available j Requesti j Allocation i j Allocation i j Requesti j Need i j Need i j Requesti j 4 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 若安全 才正式将资源分配给进程Pi 以完成本次分配 否则 将本次的试探分配作废 恢复原来的资源分配状态 让进程Pi等待 3 安全性算法 1 设置两个向量 工作向量Work 它表示系统可提供给进程继续运行所需的各类资源数目 它含有m个元素 在执行安全算法开始时 Work Available Finish 它表示系统是否有足够的资源分配给进程 使之运行完成 开始时先做Finish i false 当有足够资源分配给进程时 再令Finish i true 2 从进程集合中找到一个能满足下述条件的进程 Finish i false Need i j Work j 若找到 执行步骤 3 否则 执行步骤 4 3 当进程Pi获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故应执行 Work j Work i Allocation i j Finish i true gotostep2 4 如果所有进程的Finish i true都满足 则表示系统处于安全状态 否则 系统处于不安全状态 银行家算法示例假定系统中有4个进程P1 P2 P3 P4 三种类型的资源R1 R2 R3 数量分别为9 3 6 在T0时刻的资源分配情况如表所示 试问T0时刻是否安全T0时刻的安全性 安全序列 P2 P1 P3 P4 1 P2执行 P2 Need 1 0 2 Available 1 1 2 则P2可执行 2 P2执行后 释放资源 则Available 6 2 3 Allocation Available 5 1 1 1 1 2 3 P1执行 P1 Need 2 2 2 Available 6 2 3 则P1可执行 4 P1执行后 释放资源 则Available 7 2 3 5 P3执行 P3 Need 1 0 3 Available 7 2 3 则P3可执行 6 P3执行后 释放资源 则Available 9 3 4 7 P4执行 P4 Need 4 2 0 Available 9 3 4 则P4可执行 8 P4执行后 释放资源 则Available 9 3 6 4 5 6死锁的检测和解除若系统为进程分配资源时不采取任何措施 操作系统不断监视系统进展情况 判断死锁是否发生一旦死锁发生则采取专门的措施 解除死锁并以最小的代价恢复操作系统运行1 资源分