处理机调度与死锁知识点

处理机调度与死锁知识点

【篇一：处理机调度与死锁知识点】

operatingsystem page 2017-4-18operating system page 2017-4-18第三章 第三章处理机调度与死锁 处理机调度与死锁 重点 掌握进程调度算法，各适用于何种情况 理解常用的几种实时调度算法 理解产生死锁的原因 掌握银行家算法避免死锁 难点 多道程序设计中的各种调度算法 响应比高者优先调度算法的计算过程 银行家算法

operating system page 2017-4-18第三章 第三章处理机调度与死锁 处理机调度与死锁 知识点 处理机调度及调度算法 多处理机环境下的进程（线程）调度方式 产生死锁的原因和必要条件 预防死锁的方法，死锁的检测与解除 银行家算法 operating system page 2017-4-18第三章 第三章处理机调度与死锁 处理机调度与死锁 处理机是计算机系统中的重要资源 在多道程序环境下，进程数目通常多于处 理机的数目 系统必须按一定方法动态地把处理机分配 给就绪队列中的一个进程 处理机利用率和系统性能（吞吐量、响应 时间）在很大程度上取决于处理机调度 分配处理机的任务是由进程调度程序完成 的。它是操作系统设计的中心问题之一。

分配处理机的任务是由进程调度程序完成 的。它是操作系统设计的中心问题之一。

周转时间 周转时间：从作业被提交给系统开始，到作业完成为 止的这段时间间隔。

吞吐量 吞吐量：是指在单位时间内系统所完成的作业数。

operating system page 12 2017-4-18 高级、中级和低级调度 高级、中级和低级调度 低级调度进程调度或短程调度（short-term

scheduling） 主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机 分配给它 常见的低级调度有非抢占式和抢占式两种 低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求 在实现时做到高效 operating system page 13 2017-4-18 高级、中级和低级调度 高级、中级和低级调度 中级调度(intermediate-levelscheduling) 中程调度(medium-term

scheduling) 引入目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占 用宝贵的内存资源，而将它们调至外存上 去等待 主要任务是按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的就 绪进程调入内存，或将处于内存就绪状态

或内存阻塞状态的进程交换到外存对换区 operating system page 14 2017-4-18 处理机调度的基本概念 处理机调度的基本概念 高级、中级和低级调度 确定算法的原则进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则 operating system page 15 2017-4-18 进程调度的任务 进程调度的任务 operatingsystem page 16 2017-4-18 处理机调度的基本概念 处理机调度的基本概念 高级、中级和低级调度 进程调度的任务 进程调度方式调度队列模型 选择调度方式和调度算法的若干准则 operating system page 17 2017-4-18 确定算法的原则 确定算法的原则 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量operating system page 18 2017-4-18 处理机调度的基本概念 处理机调度的基本概念 高级、中级和低级调度 进程调度的任务 确定算法的原则 调度队列模型选择调度方式和调度算法的若干准则 operating system page 19 2017-4-18 进程调度方式 进程调度方式 非抢占方式(non-preemptivemode) 抢占方式(preemptivemode) operating system page 20 2017-4-18 进程调度方式 进程调度方式 非抢占方式(non-preemptivemode) 当某一进程正在处理机上执行时，即使有某个更 为重要或紧迫的进程进入就绪队列，该进程仍继 续执行，直到其完成或发生某种事件而进入完成 或阻塞状态时，才把处理机分配给更为重要或紧 迫的进程 正在执行的进程执行完毕，或因发生某事 件而不能再继续执行 在进程通信或同步过程中执行了某种原语操作，如wait、block、wakeup原语 优点：算法简单， 系统开销小 缺点：紧急任务不 能及时响应；短进 程到达要等待长进 程运行结束

operating system page 21 2017-4-18 进程调度方式 进程调度方式 抢占方式(preemptivemode) 当某一进程正在处理机上执行时，若有某个 更为重要或紧迫的进程进入就绪队列，则立即 暂停正在执行的进程，将处理机分配给这个更 为重要或紧迫的进程 优先权原则允许高优先权的新到进程抢 占当前进程的处理机 短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机 时间片原则时间片用完后停止执行， 重新进行调度，适用于分时系统 优点：适于时间要 求严格的实时系统 缺点：调度算法复 杂，系统开销大

operating system page 22 2017-4-18 处理机调度的基本概念 处理机调度的基本概念 高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 选择调度方式和调度算法的若干准则

operating system page 23 2017-4-18 调度队列模型 调度队列模型

同时具有三级调度的调度队列模型operating system page 24

2017-4-18 调度队列模型 调度队列模型 任务在给定时间片内已完成，释放处理机后为完成状态 任务在时间片内未完成，进入就绪队列末尾 在执行期间因某事件而阻塞operating system page 25 2017-4-18 调度队列模型 调度队列模型 仅有进程调度的调度队列模型 进程调度cpu 进程完成 等待事件 交互用户 时间片完operating system page 26 2017-4-18 调度队列模型 调度队列模型 在批处理系统中，不仅需要进程调度，而且还要有作业调度 在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插 入相应位臵，调度程序总是把处理机分 配给就绪队首进程 根据事件的不同设臵多个队列提高效率operating system page 27 2017-4-18 调度队列模型 调度队列模型 进程调度 cpu 进程完成 时间片完 等待事件等待事件 等待事件 事件出现 事件 出现 事件出现 作业调度 与上一模型的主要区别：就绪队列的形式；与上一模型的主要区别：就绪队列的形式； 设臵多个阻塞队列 operatingsystem page 28 2017-4-18 调度队列模型 调度队列模型 同时具有三级调度的调度队列模型 就绪队列 进程调度 就绪，挂起队列 中级调度 阻塞，挂起队列 阻塞队列 等待事件 进程完成 时间片完 作业调度 交互型作业 后备队列 批量作业 挂起 事件出现 事件出现cpu operating system page 29 2017-4-18 处理机调度的基本概念 处理机调度的基本概念 如果你是用户，你希望系统如何为你服务，如何考虑？？如果你是调度者，从系统整体角度出发，应如何考虑？？ 如果你是用户，你希望系统如何为你服务，如何考虑？？ 如果你是调度者，从系统整体角度出发，应如何考虑？？ operating system page 30 2017-4-18 3.1.3 选择调度方式和调度算法的若干准则 面向系统的准则operating system page 31 2017-4-18 3.1.3 选择调度方式和调度算法的若干准则 优先权准则。operating system page 32 2017-4-18 选择调度方式和调度算法的若干准则 选择调度方式和调度算法的若干准则 带权周转时间：进程（或作业）的周转时间t与系统为它提供服务的时间t 。而平均带权周转时间则可表示为:operating system page 33 2017-4-18 选择调度方式和调度算法的若干准则 选择调度方式和调度算法的若干准则 面向用户的准则 响应时间快 响应时间是指从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间 交互式系统用周转时间衡量不是最佳截止时间保证 截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间 截止时间是实时系统中的重

要指标operating system page 34 2017-4-18 选择调度方式和调度算法的若干准则 选择调度方式和调度算法的若干准则 面向用户的准则 等待时间短 调度算法并不影响进程运行和执行i/o的时间量；只影响进程在就绪队列中等待所花费 的时间 优先权准则 在批处理、实时和分时系统中都可以选择优先权准则，以便让紧急任务先处理 有时还选择抢占式调度方式operating system page 35 2017-4-18 选择调度方式和调度算法的若干准则 选择调度方式和调度算法的若干准则 面向系统的准则 系统吞吐量高 作业调度的方式和算法对吞吐量的大小有较大影响 处理机利用率高 各类资源的平衡利用 使内存、外存和i/o设备的利用率高基于这样的准则，你设计操作系统的调度策略应如何？ 基于这样的准则，你设计操作系统的调度策略应如何？ operating system page 36 2017-4-18 第三章 第三章处理机调度与死锁 处理机调度与死锁 处理机调度的基本概念 实时调度多处理机系统中的调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除 operating system page 37 2017-4-18 调度算法 调度算法 在os中调度的实质是一种资源分配，因而 调度算法是指：根据系统的资源分配策略 所规定的资源分配算法 问题提出 如何制定分配策略：对不同的系统和系统 目标，通常采用不同的算法，如短作业优 先，时间片轮转等 有些算法适用于作业调度，有些适用于进 程调度，有些两者皆可 operating system page 38 2017-4-18 调度算法 调度算法 高优先权优先调度算法基于时间片的轮转调度算法 operating system page 39 2017-4-18 先来先服务和短作业优先算法 先来先服务和短作业优先算法 按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长 的作业/进程 是一种最简单的调度算法，即可用于作业调度，也可用于进程调度

operatingsystem page 40 2017-4-18 先来先服务和短作业优先算法 先来先服务和短作业优先算法 进程名 到达时间 服务时间 开始时间 完成时间 周转时间 转时间平均 1210 12 14 11 14 18 14 5.53.5 1015 18 operatingsystem page 41 2017-4-18 先来先服务和短作业优先算法 先来先服务和短作业优先算法 先来先服务（先进先出）优缺点 比较有利于长作业（进程），而不利于短作 业（进程） 有利于cpu繁忙型作业（进程），而不利于 i/o繁忙型作业（进程） 用于批处理系统，不适于分时系统 operating system page 42 2017-4-18 先来先服务和短作业优先算法 先来先服务和短作业优先算法 短作业(进程)优先调度算法sj(p)f 短作业(进程)优先调度算法sj(p)f，以要

求运 行时间长短进行调度，即启动要求运行时间最 短的作业 可以分别用于作业调度和进程调度 短作业优先(sjf)的调度算法，是从后备队列 中选择一个或若干个估计运行时间最短的作业， 将它们调入内存运行；而短进程优先(spf)调 度算法，则是从就绪队列中选出一估计运行时 间最短的进程，将处理机分配给它，使它立即 执行并一直执行到完成，或发生某事件而被阻 塞放弃处理机时，再重新调度 operatingsystem page 43 2017-4-18 先来先服务和短作业优先算法 先来先服务和短作业优先算法 进程名 到达时间 服务时间 开始时间 完成时间 周转时间 转时间平均 9/413 18 16 16/5 40/5 2.1 1015 18 operatingsystem page 44 2017-4-18 fcfs/sjf调度算法的性能 先来先服务和短作业优先算法 先来先服务和短作业优先算法 sjf能有效地降低作业的平均等待时间，提高系统吞吐量 作业 调度 情况 算法 fcfs sjf 进程名 到达时间 服务时间 完成时间 周转时间 带权周转时间 完成时间 周转时间 带权周转时间 1210 1816 3.1 1411 5.5 1814 3.5 13 2.25平均 2.1sjf平均周转 时间和平均带 权周转时间明 显改善 operating system page 45 2017-4-18 先来先服务和短作业优先算法 先来先服务和短作业优先算法 sj(p)f调度算法也存在不容忽视的缺点 对长作业不利。严重的是，若一长作业(进程)进 入系统的后备队列(就绪队列)，由于调度程序总 是优先调度那些(即使是后进来的)短作业(进程)， 将导致长作业(进程)长期不被调度——饥饿 完全未考虑作业(进程)的紧迫程度，因而不能保 证紧迫性作业(进程)会被及时处理 由于作业(进程)的长短只是根据用户所提供的估 计执行时间而定的，而用户又可能会有意或无意 地缩短其作业的估计运行时间，致使该算法不一 定能真正做到短作业优先调度。

operating system page 46 2017-4-18 调度算法 调度算法 先来先服务和短作业优先算法 基于时间片的轮转调度算法operating system page 47 2017-4-18 高优先权优先 高优先权优先（（hpf hpf，，highest priority first highest priority first））调度算法 调度算法 优先权调度算法的类型 非抢占式优先权调度算法 抢占式优先权调度算法 operatingsystem page 48 2017-4-18 高优先权优先 高优先权优先（（hpf hpf，，highest priority first highest priority first））调度算法 调度算法 优先权调度算法的类型 非抢占式优先权调度算法 特点：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一 直执行下去，直至完成，或因发生某事 件使该进程放弃处理机时，系统才将处 理机重新分配给另一优先权最高的进程 主要