青岛科技大学.ppt

第三章处理机调度与死锁 教学目的与要求 熟悉处理机调度的层次掌握作业调度策略和算法掌握进程调度策略和算法了解实时调度系统理解死锁的基本概念掌握产生死锁的必要条件理解并掌握处理死锁的基本方法 重点和难点 作业调度策略和算法进程调度策略和算法用于死锁避免的银行家算法 主要外语词汇 JobSchedulingAlgorithmFCFS firstcomefirstserve SJF shortjobfirst Deadlock 第三章处理机调度与死锁 3 1处理机调度的层次 3 2调度算法 3 4预防死锁的方法 3 5死锁的检测与解除 3 3产生死锁的原因和必要条件 3 1处理机调度的层次 3 1 1高级调度 作业调度 3 1 2低级调度 进程调度 3 1 3中级调度 交换调度 3 1 1高级调度 高级调度 作业调度 按一定算法 把外存中处于后备队列中的作业调入内存 为其分配必要的资源 并创建进程 调度对象为作业 决定允许哪些作业竞争系统资源 在分时和实时系统中 一般不配置作业调度 3 1 2低级调度 低级调度 进程调度 将处理机分配给进程 主要任务 按照给定的某种策略和方法决定就绪队列中哪个进程应先获得处理机 并将处理机分配给选中的进程 是最基本的一种调度 低级调度的功能 1 保存当前进程的处理机现场信息 2 按某种算法选取投入执行的新进程 3 恢复新进程的处理机现场把处理器分配给进程 3 1 3中级调度 交换调度 中级调度 决定允许哪些进程竞争处理机 主要任务 按一定的算法 将外存中已具备运行条件的进程换入内存 而将内存中处于阻塞状态的某些进程交换到外存 引入中级调度的目的 为了提高内存的利用率和系统吞吐量 BasicConcepts基本概念 1 CPU I OBurstCycleCPU I O区间周期2 CPUSchedulerCPU调度程序3 PreemptiveScheduling抢占式调度4 Dispatcher分派程序 1 CPU I OBurstCycleCPU I O区间周期 2 CPUScheduler Selectsfromamongtheprocessesinmemorythatarereadytoexecute andallocatestheCPUtooneofthem Whenweconsiderthevariousschedulingalgorithms areadyqueuemaybeimplementedasaFIFOqueue apriorityqueue atree orsimplyanunorderedlinkedlist 3 PreemptiveScheduling CPUschedulingdecisionsmaytakeplacewhenaprocess Switchesfromrunningtowaitingstate Switchesfromrunningtoreadystate Switchesfromwaitingtoready Terminates Schedulingunder1and4isnonpreemptive非抢占方式调度 Allotherschedulingispreemptive 抢占方式调度 nonpreemptivescheduling非抢占方式调度oncetheCPUhasbeenallocatedtoaprocess theprocesskeepstheCPUuntilitreleasestheCPUeitherbyterminatingorbyswitchingtothewaitingstate 实现简单 系统开销小 适用于大多数的批处理系统环境 preemptivescheduling抢占方式调度incursacost 防止一个长进程长时间占用处理机 提供更公平的服务 抢占调度方式遵循的原则 1 优先权原则 对重要和紧急的作业或进程赋予较高的优先权 2 短作业 进程 优先原则 3 时间片原则 4 Dispatcher 分派程序 DispatchermodulegivescontroloftheCPUtotheprocessselectedbytheshort termscheduler thisinvolves 分派程序是一个模块 用来将CPU的控制交给短期调度程序所选择的进程 switchingcontext切换上下文switchingtousermode切换到用户模式jumpingtotheproperlocationintheuserprogramtorestartthatprogram跳转到用户程序的合适位置以重新启动这个程序 进程上下文 进程上下文 是一个与进程切换和处理机状态发生交换有关的概念 包括计算机系统中与执行该进程有关的各种寄存器的值 程序段在经过编译之后形成的机器指令代码集 数据集及各种堆栈值和PCB结构 上文 已执行过的进程指令和数据在相关寄存器和堆栈中的内容 正文 正在执行 下文 待执行 3 2调度算法 3 2 6多级反馈队列调度算法 3 2 5时间片轮转调度算法 3 2 4最高优先权优先调度算法 3 2 3最高响应比优先调度算法 3 2 2最短作业 进程 优先法 3 2 1先来先服务调度算法 调度准则SchedulingCriteria CPUutilizationCPU利用率 keeptheCPUasbusyaspossible Throughput吞吐量 numbersofprocessesthatcompletetheirexecutionpertimeunit Turnaroundtime周转时间 amountoftimetoexecuteaparticularprocess Itisthesumoftheperiodsspentwaitingtogetintomemory waitinginreadyqueue executingontheCPU anddoingI O Waitingtime等待周转时间 amountoftimeaprocesshasbeenwaitinginthereadyqueue TheCPU schedulingalgorithmdoesnotaffecttheamountoftimeduringwhichaprocessexecutesordoesI O itaffectsonlytheamountoftimethataprocessspendswaitinginthereadyqueue Responsetime响应时间 amountoftimeittakesfromwhenarequestwassubmitteduntilthefirstresponseisproduced OptimizationCriteria最优准则 MaxCPUutilizationMaxthroughputMinturnaroundtimeMinwaitingtimeMinresponsetime 1 周转时间 作业或进程i的周转时间Ti Ti Tei TsiTsi为作业或进程的提交时刻 Tei为作业或进程的完成时刻 作业或进程平均周转时间为T 有n个作业或进程 n 1 nT 1 n Tii 1 2 带权周转时间 带权周转时间Wi Wi Ti TriTi为作业或进程周转时间Tri为作业或进程执行时间平均带权周转时间为 nW 1 n Wii 1 3 2 1先来先服务 FCFS 调度算法 先来先服务 FCFS FirstComeFirstServe 是最简单的调度算法 按先后顺序进行调度 适用于作业和进程调度FCFS算法 选择最先进入就绪队列的作业或进程投入执行 属于非抢占调度方式 当前作业或进程占用CPU 直到执行完或阻塞 才出让CPU 特点 简单 易于实现 但不利于短作业 FCFS算法不利于短作业 进程 举例 下表列出了A B C D四个作业分别到达系统的时间 要求服务的时间 开始执行的时间及各自的完成时间 并计算出各自的周转时间和带权周转时间 调度算法思考题 假设在单道批处理环境下有四个作业 已知它们进入系统的时间 估计运行时间 应用先来先服务 最短作业优先和最高响应比优先作业调度算法 分别计算出作业的平均周转时间和带权的平均周转时间 3 2 2最短作业 进程 优先法 最短作业优先法 SJF ShortestJobFirst 又称为 短进程优先 SPF ShortestProcessFirst 是对FCFS算法的改进 其目标是减少平均周转时间 SJF SPF 算法 对预计执行时间短的作业 进程 优先分派处理机 通常后来的短作业不抢先正在执行的作业 FCFS和SJF的性能比较 图3 4FCFS和SJF调度算法的性能 SJF的特点 1 优点 缩短作业的等待时间 提高系统的吞吐量 2 缺点 对长作业非常不利 可能长时间得不到执行 未能依据作业 进程 的紧迫程度来划分执行的优先级 难以准确估计作业 进程 的执行时间 从而影响调度性能 SJF SPF 的变型 最短剩余时间优先SRT ShortestRemainingTime 允许比当前进程剩余时间更短的进程来抢占 最高响应比优先 3 2 3最高响应比优先调度算法 最高响应比优先法 HRRF HighestResponseRatioFirst 是对FCFS方式和SJF方式的一种综合平衡 响应比R 等待时间 要求执行时间 要求执行时间是一种动态优先权调度算法 以响应比作为作业或进程的动态优先权 选择响应比最高的作业或进程投入执行 HRRF算法的特点 即照顾了短作业 又考虑到达的先后次序 等待时间 不会使长作业 进程 长期得不到服务 由于每次调度前要计算响应比 系统开销也要相应增加 FCFS SJF和HRRF的性能比较 1 进程A运行完后 进程B C D和E到达 计算它们的响应比 RB 4 1 3 3 2 RC 4 2 5 5 1 4 RD 4 3 2 2 1 5 RE 1 2 选取进程B投入执行 运行完后 计算进程C D和E的响应比 RC 7 2 5 5 2 RD 7 3 2 2 3 RE 7 4 4 4 1 75 3 选取进程D投入执行 运行完后 计算进程C和E的响应比 RC 9 2 5 5 2 4 RE 9 4 4 4 2 25 4 选取进程C投入执行 进程C运行完后 进程E执行 3 2 4最高优先权优先调度算法 适用于作业调度和进程调度该算法的核心是 确定进程或作业的优先权 确定优先权的方法 静态法和动态法 1 静态优先权 创建进程时确定 直到进程终止前都不改变 通常是一个整数 依据 进程类型 系统进程优先级较高 对资源的需求 对CPU和内存需求较少的进程 优先权较高 用户要求 紧迫程度和付费多少 2 动态优先权 在创建进程时赋予的优先权 在进程运行过程中可自动改变 以获得更好的调度性能 依据 进程占用有CPU时间的长短进程每执行一个时间片 就降低其优先权 从而一个进程持续执行时 其优先权降低到让出CPU 就绪进程等待CPU的时间长短在就绪队列中 等待时间延长则优先权提高 从而使优先权较低的进程在等待足够的时间后 其优先权提高到可被调度执行 3 2 5时间片轮转调度算法 时间片轮转法 将CPU的处理时间分成固定大小的时间片 系统中所有就绪进程按照FCFS原则 排成一个队列 每次调度时将CPU分给队首进程 让其执行一个时间片 在一个时间片结束时 发生时钟中断 调度程序暂停当前进程的执行 将其送到就绪队列的末尾 执行当前的队首进程 该算法不适用于作业调度属于抢占调度方式 时间片长度的确定 时间片长度变化的影响过短 则用户的一次请求需要多个时间片才能处理完 上下文切换次数增加 响应时间长 过长 则退化为FCFS算法 进程在一个时间片内都执行完 响应时间长 时间片长度q的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定 q R Nmax就绪进程的数目越多 时间片越小 3 2 6多级反馈队列调度算法 多级反馈队列调度算法 RoundRobinwithMultipleFeedback 是时间片轮转算法和优先权算法的综合和发展 多级反馈队列调度算法示意图 FCFS算法 时间片轮转算法 多级反馈队列调度算法 设置多个不同优先级的就绪队列 并赋予各个队列大小不同的时间片 优先级越高的队列时间片越小 新进程进入内存后 先投入队列1 最高优先级 的末尾 按FCFS算法等待调度 若按队列1一个时间片未能执行完 则降低投入到队列2的末尾 同样按FCFS算法调度 如此下去 降低到最后的队列 则按 时间片轮转 算法调度直到完成 仅当较高优先级的队列为空 才调度较低优先级的队列中的进程执行 如果进程执行时有新进程进入较高优先级的队列 则抢先执行新进程 并把被抢先的进程投入原队列的末尾 多级反馈队列调度算法的优点 多级反馈队列调度算法具有较好的性能 能很好地满足各种类型用户的需要 终端型作业用户短批处理作业用户长批处理作业用户不必估计进程的执行时间 动态调节 3 3产生死锁的原因和必要条件 3 3 1死锁的定义3 3 2产生死锁的原因3 3 3产生死锁的必要条件3 3 4处理死锁的基本方法 哲学家就餐问题产生死锁 0 1 2 3 4 每个哲学家思考 饥饿 然后吃进餐 为了吃粉 每个哲学家必须获得两把筷子 且每人只能直接从自己左边或右边去取筷子 碗 哲学家 筷子 3 3 1死锁的定义 死锁 Deadlock 指多个并发进程在运行过程中因争夺资源而造成的一种僵局 若无外力作用 这些进程将无法再向前推进 关于死锁的一些结论 参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注 如果死锁发生 会浪费大量系统资源 甚至导致系统崩溃 3 3 2产生死锁的原因 1 竞争系统资源2 进程间推进顺序不当 1 竞争系统资源引起进程死锁 永久性资源 可以被多个进程多次使用 可再用资源 可抢占资源 CPU 内存等 不可抢占资源 打印机 扫描仪等 临时性资源 只可使用一次的资源 如信号量 中断信号 同步信号等 可消耗性资源 申请 分配 使用 释放 模式 系统资源分类 1 竞争系统资源引起的死锁情况 设系统有一台打印机 R1 一台扫描仪 R2 可供进程P1和P2共享 若形成环路 这样会产生死锁 2 进程之间通信时的死锁情况 P1 P2和P3为进程 S1 S2和S3为进程之间要发送的消息 假设 进程P1 P2和P3的运行顺序如下 P1 Request s3 Release s1 P2 Request s1 Release s2 P3 Request s2 Release s3 使用临时性资源时引起的死锁 P1 申请打印机申请扫描仪 P2 申请扫描仪申请打印机 阻塞 阻塞 等待 2 进程推进顺序不当引起死锁 假设系统有一台打印机和一台扫描仪 进程P1和P2共享这两台设备 两个进程对资源的执行顺序 3 3 3产生死锁的必要条件 互斥条件 资源独占 进程所竞争的资源必须被互斥使用请求和保持条件 部分分配 占有申请 请求资源得不到满足而等待时不释放已占有资源不剥夺条件 不可强占 进程已获得的资源 只能使用完时自行释放 不能被抢占 环路等待条件 循环等待条件 存在一个至少包含两个进程的循环等待资源链 其中 每个进程都正在等待前一个进程所占有的资源 3 3 4处理死锁的基本方法 预防死锁 破坏产生死锁的某个必要条件防止发生死锁 避免死锁 在资源的动态分配过程中 用某种方法防止系统进入不安全状态 从而避免发生死锁 检测死锁 允许发生死锁 及时地检测出死锁的发生 并精确地确定与死锁有关的进程和资源 恢复死锁 采取适当措施 从系统中将已发生的死锁清除掉 3 4预防死锁的方法 3 4 1预防死锁3 4 2系统安全状态3 4 3利用银行家算法避免死锁 3 4 1预防死锁 预防死锁的三种策略 1 摒弃 请求和保持 条件 2 摒弃 不剥夺 条件 3 摒弃 环路等待 条件 1 摒弃 请求和保持 条件 所有并发进程都必须一次性申请其在运行过程中所需的全部资源 优点 简单 易于实现且很安全 缺点 资源被严重浪费使进程延迟运行 2 摒弃 不剥夺 条件 规定一个已经保持了某些资源的进程 再提出新的资源请求而不能立即得到满足时 必须释放它已经保持了的所有资源 缺点 实现起来比较复杂 且要付出很大的代价 3 摒弃 环路等待 条件 系统将所有资源按类型进行线性排队 并赋予不同的序号 并规定所有进程必须严格按照资源序号递增的次序申请资源 把资源分类按顺序排列 使进程在申请 保持资源时不形成环路 缺点 限制了进程对资源的请求 不方便用户编程 而且对资源的分类编序也耗去一定的系统开销 3 4 2系统安全状态 避免死锁 把系统的状态分为安全状态和不安全状态 只有能使系统始终都处于安全状态 便可避免发生死锁 1 安全状态与不安全状态 安全状态 指系统能按某种进程顺序来为每个进程分配其所需资源 直至满足每个进程对资源的最大需求 使每个进程都可以顺序完成 若系统不存在这样一个序列 则称系统处于不安全状态 在T0时刻存在一个安全序列 P2 P1 P3 2 安全状态之例 假定系统中有三个进程P1 P2和P3 共有12台磁带机 进程P1总共要求10台磁带机 P2和P3分别要求4台和9台 假设在T0时刻 系统状态如下表所示 如果不按照安全序列分配资源 则系统可能会由安全状态进入不安全状态 3 由安全状态向不安全状态的转换 例如 在T0时刻以后 P3又请求1台磁带机 若此时系统把剩余3台中的1台分配给P3 则系统便进入不安全状态 大家可以思考一下 其中的原因 4 安全状态与不安全状态的结论 处于安全状态下的系统不会发生死锁 避免死锁的关键 让系统在动态分配资源的过程中 不要进入不安全状态 3 4 3利用银行家算法避免死锁 银行家算法每个客户第一次申请分期贷款时要声明所需的最大资金量 在满足所有贷款要求时 客户就一定能一次性归还 否则就一定不能归还贷款 银行家在客户申请的贷款数量不超过所拥有周转资金最大值时 都应满足客户的需要 银行家应谨慎的贷款 防止出现坏帐 用银行家算法避免死锁操作系统 银行家 操作系统管理的资源 周转资金 进程 要求贷款的客户 银行家算法的流程图 开始 1 所有进程的 运行完标志 置为假 2 对某进程的资源申请试探性分配 3 比较系统剩余资源数与 运行完标志 为假的进程尚需资源数 寻找能满足资源需求的进程 存在这样的进程吗 将该进程的 运行完标志 置真 并假定运行完归还所占资源 系统中还有 运行完标志 为假的进程吗 对 2 中进程的资源申请分配后 系统处于安全状态 完成分配 对 2 中进程的资源申请分配后 系统处于不安全状态 拒绝分配 结束 Y N Y N 1 银行家算法中的数据结构 1 可利用资源向量Available 数组 每一个元素代表一类可利用的资源数目 Available j K 表示系统中现有Rj类资源K个 2 最大需求矩阵Max n m的矩阵 定义系统中n个进程中的每一个进程对m类资源的最大需求 Max i j K 表示进程i需要Rj类资源的最大数目为K 1 银行家算法中的数据结构 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 需求矩阵Need可以用下述公式计算 1 银行家算法中的数据结构 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等待 1 设置两个向量 工作向量Work 表示系统可提供给进程继续运行所需的各类资源数目 含有m个元素 在执行安全算法开始时 Work Available 进程运行完标志Finish 表示系统是否有足够的资源分配给进程 使之运行完成 开始时先做Finish i false 当有足够资源分配给进程时 再令Finish i true 3 安全性算法 2 从进程集合中找一个能满足下述条件的进程 Finish i false Need i j Work j 若找到 执行步骤 3 否则 执行步骤 4 3 当进程Pi获得资源后 可顺利执行 直至完成 并释放出分配给它的资源 故应执行 Work j Work j Allocation i j Finish i true gotostep2 4 如果所有进程的Finish i true都满足 则表示系统处于安全状态 否则 系统处于不安全状态 银行家算法的流程图 开始 1 所有进程的 运行完标志 置为假 2 对某进程的资源申请试探性分配 3 比较系统剩余资源数与 运行完标志 为假的进程尚需资源数 寻找能满足资源需求的进程 存在这样的进程吗 将该进程的 运行完标志 置真 并假定运行完归还所占资源 系统中还有 运行完标志 为假的进程吗 对 2 中进程的资源申请分配后 系统处于安全状态 完成分配 对 2 中进程的资源申请分配后 系统处于不安全状态 拒绝分配 结束 Y N Y N T0时刻的资源分配表 最大需求矩阵 分配矩阵 需求矩阵 可用资源向量 4 银行家算法之例 假定系统中有五个进程 P0 P1 P2 P3 P4 和三类资源 A B C 各种资源的数量分别为10 5 7 在T0时刻的资源分配情况如下图所示 问题 1 利用安全性算法 检查T0时刻的安全性 2 在T0时刻 P1发出请求向量Request1 1 0 2 系统能否将资源分配给它 1 T0时刻的安全性 利用安全性算法对T0时刻的资源分配情况进行分析 在T0时刻存在一个安全序列 P1 P3 P4 P2 P0 因此 系统是安全的 在T0时刻还有其他的安全序列吗 T0时刻的安全序列 工作向量 2 P1请求资源 P1发出请求向量Request1 1 0 2 系统按银行家算法进行检查 Request1 1 0 2 Need1 1 2 2 Request1 1 0 2 Available1 3 3 2 系统先假定可为P1分配资源 并修改Available Allocation1和Need1向量 由此形成的资源变化情况如原图中的圆括号所示 再利用安全性算法检查此时系统是否安全 2 P1申请资源时的安全性检查 由所进行的安全性检查得知 可以找到一个安全序列 P1 P3 P4 P0 P2 因此 系统是安全的 可以把P1申请的资源分