（六）操作系统-处理器调度及死锁

Published: at 09:59:50

调度与作业

调度的层次

  1. 长期调度
    • 又称作业调度；
    • 主要功能是按照某种原则从磁盘某些盘区的作业队列和交互作业中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。
  2. 中期调度
    • 决定哪些进程被允许参与竞争处理器资源；
    • 主要起到短期调整系统负荷的作用，以平顺系统的操作。
  3. 短期调度
    • 又称处理器调度；
    • 主要功能是按照某种原则将处理器分配给就绪进程或线程。

2

作业状态

作业在每一阶段中所处的状况称为作业的状态；

系统中的作业通常分为四种状态：

  1. 提交状态

  2. 后备状态

  3. 运行状态

  4. 完成状态

    3

处理器调度

常见的调度算法

  1. 先进先出调度算法
  2. 优先级调度算法——非抢占的、可抢占的
  3. 时间片轮转算法
  4. 最短进程优先调度算法
  5. 最短剩余时间优先调度算法
  6. 最高响应比优先调度算法

调度性能的衡量

通常采用平均周转时间和平均带权周转时间来衡量作业调度算法性能的好坏；

作业的平均周转时间t为：

4

平均带权周转时间w为：

5

先进先出调度算法

按作业来到的先后次序进行调度，优先考虑在系统中等待时间最长的作业，而不管它要求执行时间的长短；

算法容易实现，但效率较低；

对短作业不利，因为短作业执行时间很短，若令它等待较长时间，则带权周转时间会很高。 先进先出调度算法（单位：小时，以十进制计）：

6 计算过程：

  1. 周转时间 = 完成时间 - 提交时间
  2. 带权周转时间 = 周转时间/执行时间
  3. 平均周转时间 = 所有任务周转时间之和/任务数
  4. 平均带权周转时间 = 带权周转时间之和/任务数

最短作业优先调度算法

最短作业优先调度算法（单位：小时，以十进制计）：

7

执行时间最短的任务优先执行，所以任务执行的顺序是：作业1→作业3→作业4→作业2；

计算过程和先进先出调度算法一样。

最高响应比优先调度算法

先进先出调度算法只考虑作业的等候时间而忽略了作业的执行时间；

最短作业优先调度算法只考虑用户估计的作业执行时间而忽略了作业的等待时间；

最高响应比优先调度算法是介于上述两算法之间的一种折衷算法，既照顾了短作业，又不使长作业的等待时间过长。

高响应比优先调度算法的基本思想是把CPU分配给就绪队列中响应比最高的进程。

响应比 =（等待时间+要求服务时间）/ 要求服务时间,即RR=（w+s）/s=1+w/s，因此响应比一定是大于等于1的。

最高响应比优先调度算法（单位：小时，以十进制计）：

8

死锁问题

死锁：在系统中的一组进程，由于竞争系统资源或由于彼此通信而永远阻塞，称这些进程处于死锁状态；

死锁的必要条件

  1. 互斥条件：一个资源一次只能被一个进程所使用；
  2. 不可抢占条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强行抢占；
  3. 请求又保持（部分分配）条件：一个进程已占有了分给它的资源，但仍然要求其他资源；
  4. 循环等待条件：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有若干种资源中的某一种，同时每一个进程还要求（链上）下一个进程所占有的资源。

防止死锁

防止死锁的发生，根本办法是使上述必要条件之一（或多个条件）永不存在，即破坏其必要条件使之永不成立，如果有一条或若干条不具备，那么死锁就不会产生；

  1. 破坏互斥条件，允许多个进程同时访问资源；（但不太实际）
  2. 破坏不可抢占条件，强迫进程暂时把资源释放出来给其他进程；（考虑到资源在进程间转移的开销和对资源的有效利用，必须小心地控制破坏该条件）
  3. 破坏部分分配条件；
  4. 破坏循环等待条件。

死锁预防

  1. 预先静态分配法
    • 是针对部分分配条件的策略；
    • 在进程开始运行前，一次分配给其所需的全部资源，若系统不能满足，则进程阻塞，直到系统满足其要求；
    • 将导致严重的资源浪费；
    • 改进策略：把程序分成几个相对独立的“程序步”来运行，并且资源分配以程序步为单位来进行，而不以整个进程为单位来静态地分配资源；
    • 可以得到较好的资源利用率，减少资源浪费，但增加了应用系统的设计和执行的开销；
    • 而且，为满足一个进程所需的全部资源，要逐渐积累，造成资源的浪费。
  2. 有序资源使用法
    • 针对循环等待条件的；
    • 系统设计者把系统中所有资源类都分给一个唯一的序号，并且要求每个进程均应严格按照递增的次序请求资源；
    • 这样，系统中不可能形成几个进程对资源的环行请求链，破坏了循环等待条件；
    • 把各进程经常用到的、比较普通的资源安排成低序号，而把比较贵重或稀少的资源安排成高序号，可能使最有价值的资源的利用率大为提高，但也有可能造成低序号资源的空闲等待浪费现象；
    • 存在的问题：
      • 各类设备的资源序号一经安排，不宜经常地随意加以改动，至少应该维持一个较长的时期，在此期间，若要添置一些新设备，就必须重新改写已经存在的程序和系统；
      • 资源序号的安排要反映大多数进程实际使用资源的正常顺序，对于与此序号相匹配的进程，资源能得到有效利用，否则，资源浪费现象虽然有所改善，但仍然存在。

死锁模型—有向图

9

  1. (a)占用一资源：资源R被进程A占用
  2. (b)请求一资源：进程B正等待着资源S
  3. (c)死锁：进程C等待着资源T，资源T被进程D占用着，进程D又等待着由进程C占用着的资源U。

从死锁恢复

  1. 剥夺法恢复
    • 将某一资源从一个进程强占过来给另一个进程使用，并在不影响原进程执行的情况下返回，这种作法取决于该资源的特性；
    • 用这种方法恢复通常比较困难或者说不太可能，因为选择中止某进程很大程度上取决于哪一类资源比较容易被收回；
  2. 回退法恢复
    • 系统设计人员以及主机操作员周期性地对进程进行检查，在检查点将进程的状态写入文件以备重启，文件中不仅包括内存图象，还包括了资源状态，既哪些资源对应哪些进程；
    • 一旦检测到死锁，恢复时，进程会回滚到较早的检查点，该检查点后做的所有工作都丢失了；
  3. 杀死进程来恢复杀掉环中的一个进程；
    • 将一个环外的进程作为牺牲品放入环中以释放被死锁的资源。