操作系统 第三章处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

3.1.1 处理及调度的层次

  1. 高级调度(High Level Scheduling)

    又称作业调度长程调度,作业调度用于决定把外存上处于作业后备队列上的哪些作业调入内存,并为它们创建进程、分配必要的资源,然后再将新创建的进程排在就绪队列上,准备执行。

  2. 低级调度(Low Level Scheduling)

    又称进程调度短程调度,进程调度决定就绪队列中哪个进程将获得处理机,然后由分派程序执行把处理机分配给该进程的操作。

  3. 中级调度(Intermediate Scheduling) 又称内存调度,中级调度就是存储管理中的对换,采用虚拟存储技术的分时系统往往设立中级调度。

进程调度运行频率最高。作业调度周期较长,大约几分钟一次。中程调度位于两者之间。

3.1.2 处理及调度算法的目标

  1. 处理机调度算法的共同目标

    • 资源利用

      提高系统的资源利用率,应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态。

      \(CPU 的利用率=\frac{CPU 有效工作时间}{CPU 有效工作时间+CPU 空闲等待时间}\)

    • 公平性

      公平性是指应使诸进程都获得合理的 CPU 时间,不会发生进程饥饿现象。公平性是相对的,对相同类型的进程应获得相同的服务;但对于不同类型的进程,由于其紧急程度或重要性的不同,则应提供不同的服务。

    • 平衡性

      在系统中可能具有多种类型的进程,有的属于计算型作业,有的属于I/O型。为使系统中的 CPU 和各种外部设备都能经常处于忙碌状态,调度算法应尽可能保持系统资源使用的平衡性。

    • 策略强制执行

      对所制订的策略其中包括安全策略,只要需要,就必须予以准确地执行,即使会造成某些工作的延迟也要执行。

  2. 批处理系统的目标

    • 平均周转时间短

      希望能使平均周转时间最短,而不是单个作业。平均周转时间\(T=\frac1n[\sum_{i=1}^nT_i]​\)

      作业的周转时间 T 与系统为它提供服务的时间 Ts 之比,平均带权周转时间\(T=\frac1n[\sum_{i=1}^n\frac{T_i}{T_s}]\)

    • 系统吞吐量高

      吞吐量是指在单位时间内系统所完成的作业数,因而它与批处理作业的平均长度有关。单纯是为了获得高的系统吞吐量,就应尽量多地选择短作业运行。

    • 处理机利用率高

      单纯是为使处理机利用率高,应尽量多地选择计算量大的作业运行。

    由上所述可以看出,这些要求之间是存在着一定矛盾的。

  3. 分时系统的目标

    • 响应时间快
    • 均衡性
  4. 实时系统的目标

    • 截止时间的保证

      任务开始执行的最迟时间或必须完成的最迟时间。

    • 可预测性

3.2 作业与作业调度

3.2.1 批处理系统中的作业

  1. 作业和作业步

    • 作业(Job)

      包含通常的程序和数据,还应配有一份作业说明书。批处理系统中从外存调入内存的基本单位。

    • 作业步(Job Step)

      作业的若干个加工步骤。

  2. 作业控制块(Job Control Block,JCB)

    它是作业在系统中存在的标志,其中保存了系统对作业进行管理和调度所需的全部信息。

  3. 作业运行的三个阶段和三种状态

    作业从进入系统到运行结束,通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。

3.2.2 作业调度的主要任务

作业调度的主要任务是,根据 JCB 中的信息,检查系统中的资源能否满足作业对资源的需求,以及按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此,也称为接纳调度(Admission Scheduling)。在每次执行作业调度时,都需做出以下两个决定。

  • 接纳多少个作业
  • 接纳哪些作业

3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法

  1. 先来先服务(first-some first served, FCFS)调度算法

    最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。系统将按照作业到达的先后次序来进行调度,优先考虑在系统中等待时间最长的作业,而不管该作业所需执行时间的长短,

  2. 短作业优先(short job first, SJF)调度算法

    作业越短,其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF 算法可以分别用于作业调度和进程调度。

    缺点:

    • 必须预知作业的运行时间;
    • 对长作业非常不利;
    • 在采用 FCFS 算法时,人—机无法实现交互;
    • 完全未考虑作业的紧迫程度。

3.2.4 优先级调度算法和高响应比优先调度算法

  1. 优先级调度算法(priority-scheduling algorithm, PSA)

    FCFS 和 SJF 都不能反映作业的紧迫程度。PSA 从外部赋予作业相应的优先级,从而进行调度。

  2. 高响应比优先调度算法(Highest Response Ratio Next, HRRN)

    FCFS 只考虑作业的等待时间,忽视作业运行时间,SJF 正好相反。HRRN 则兼顾之。此优先级是动态的,随时间延长而增加。

    \(R_p(响应比) = 优先权=\frac{等待时间+要求服务时间}{要求服务时间} = \frac{响应时间}{要求服务时间}\),等待时间 = 当前时间 - 进程到达时间

3.3 进程调度

3.3.1 进程调度的任务、机制和方式

  1. 进程调度的任务

    • 保存处理机的现场信息。
    • 按某种算法选取进程。
    • 把处理器分配给进程。
  2. 进程调度机制

    • 排队器。所有进程按一定策略排成一个或多个队列。
    • 分派器。
    • 上下文切换器。两对上下文的切换操作:①OS 保存当前进程的上下文,在装入分派程序的上下文;②移出分派程序的上下文,而把新选进程的 CPU 现场信息装入到处理机的各个相应寄存器中。

  3. 进程调度方式

    • 非抢占方式(Nonpreemptive Mode)

      一旦把处理机分配给某进程后,就一直运行下去,决不会因为任何原因去抢占当前正在运行进程的处理机,直至该进程完成,或发生某事件而被阻塞时,才把处理机分配给其它进程。

    • 抢占方式(Preemptive Mode)

      允许调度程序根据某种原则暂停某个正在执行的进程,将已分配给该进程的处理机重新分配给另一进程。在现代 OS 中广泛采用抢占方式。

      主要原则有:优先权原则、短进程优先原则、时间片原则。

3.3.2 轮转调度算法

分时系统中,最简单也最常用的是基于时间片的轮转(round robin, RR) 调度算法。让就绪队列上的每个进程每次仅运行一个时间片。

  1. 轮转法的基本原理

    系统将所有的就绪进程按 FCFS 策略排成一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断,去激活进程调度程序进行调度,把 CPU 分配给队首进程,并令其执行一个时间片。当它运行完毕后,又把处理机分配给就绪队列中新的队首进程,也让它执行一个时间片。

  2. 进程切换时机

    在 RR 调度算法中,何时进行进程的切换,可分为两种情况:① 若一个时间片尚未用完,正在运行的进程便已经完成,就立即激活调度程序,将它从就绪队列中删除,再调度就绪队列中队首的进程运行,并启动一个新的时间片。② 在一个时间片用完时,计时器中断处理程序被激活。如果进程尚未运行完毕,调度程序将把它送往就绪队列的末尾。

  3. 时间片大小的确定

    时间片小,有利于短作业。但意味着频繁进程调度和进程上下文切换,增加系统开销。反之,时间片太长,每个进程都在一个时间片内完成,RR 退化为 FCFS。一个较为可取得时间片大小是略大于一次典型的交互所需要的时间

3.3.3 优先级调度算法

RR 中,隐含的假设:系统中所有进程的紧迫性是相同的。实际上,并非如此。

  1. 优先级调度算法的类型

    • 非抢占式优先级调度算法。一旦把处理机分配给就绪队列中优先级最高的进程后,该进程便一直执行直到完成。
    • 抢占式优先级调度算法。执行中,一旦出现另一个优先级更高的进程,便将处理机分配到新的进程。
  2. 优先级的类型

    • 静态优先级

      静态优先级是在创建进程时确定的,在进程的整个运行期间保持不变。确定进程优先级大小的依据有如下三个:①进程类型②进程对资源的要求③用户要求。

    • 动态优先级

      动态优先级是指在创建进程之初,先赋予其一个优先级,然后其值随进程的推进或等待时间的增加而改变。

3.3.4 多队列调度算法

如前所述的各种调度算法,由于系统中仅设置一个进程的就绪队列,即低级调度算法是固定的、单一的,无法满足系统中不同用户对进程调度策略的不同要求。

3.3.5 多级反馈队列(multileved feedback queue)调度算法

  1. 调度机制

    • 设置多个就绪队列。第一个队列的优先级最高,其余逐次降低。优先级愈高,时间片愈小。第 i+1 个度列的时间片比第 i 个的时间片长一倍。
    • 每个队列都采用 FCFS 算法。
    • 按队列优先级调度。
  2. 调度算法的性能

    对顶第一个队列的时间片略大于多数人机交互所需的处理时间,比较好。

    • 终端型用户
    • 短批处理作业用户
    • 长批处理作业用户

3.3.6 基于公平原则的调度算法

  1. 保证调度算法
  2. 公平分享调度算法

3.4 实时调度(不做要求)

3.5 死锁概述

3.5.1 资源问题

  1. 可重用性资源和消耗性资源

    • 可重用性资源。

      • 每一个可重用性资源中的单元只能分配给一个进程使用,不允许多个进程共享。
      • 进程在使用可重用性资源时,须按照这样的顺序:① 请求资源。如果请求资源失败,请求进程将会被阻塞或循环等待。② 使用资源。进程对资源进行操作,如用打印机进行打印;③ 释放资源。当进程使用完后自己释放资源。
      • 系统中每一类可重用性资源中的单元数目是相对固定的,进程在运行期间既不能创建也不能删除它。
    • 可消耗性资源

      又称为临时性资源(软件居多),它是在进程运行期间,由进程动态地创建和消耗的,它具有如下性质:① 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的,有时它可以有许多,有时可能为0;② 进程在运行过程中,可以不断地创造可消耗性资源的单元,将它们放入该资源类的缓冲区中,以增加该资源类的单元数目。③ 进程在运行过程中,可以请求若干个可消耗性资源单元,用于进程自己的消耗,不再返回给资源类。

  2. 可抢占性资源和不可抢占性资源

    • 可抢占性资源。是指某进程在获得这类资源后,该资源可以再被其它进程或系统抢占。
    • 不可抢占性资源。一旦系统把某资源分配给该进程后,就不能将它强行收回,只能在进程用完后自行释放。

3.5.2 计算机系统中的死锁

  1. 竞争不可抢占性资源引起死锁

  2. 竞争可消耗资源引起死锁

  3. 进程推进顺序不当引起死锁

3.5.3 死锁的定义、必要条件和处理方法

  1. 死锁的定义

    在一组进程发生死锁的情况下,这组死锁进程中的每一个进程,都在等待另一个死锁进程所占有的资源。

    原因:竞争资源、进程推进顺序非法。

  2. 产生死锁的必要条件

    • 互斥条件。
    • 请求和保持条件。
    • 不可抢占条件。
    • 循环等待条件。
  3. 处理死锁的方法

  • 预防死锁。
  • 避免死锁。
  • 检测死锁。
  • 解除死锁。

3.6 预防死锁

预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个,以避免发生死锁。主要是后 3 个。

3.6.1 破坏“请求和保持”条件

为了能破坏“请求和保持”条件,系统必须保证做到:当一个进程在请求资源时,它不能持有不可抢占资源。该保证可通过如下两个不同的协议实现:

  1. 第一种协议

    该协议规定,所有进程在开始运行之前,必须一次性地申请其在整个运行过程中所需的全部资源。

  2. 第二种协议

    该协议是对第一种协议的改进,它允许一个进程只获得运行初期所需的资源后,便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源,然后再请求新的所需资源。

3.6.2 破坏“不可抢占”条件

协议中规定,当一个已经保持了某些不可被抢占资源的进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放,或者说是被抢占了,从而破坏了“不可抢占”条件。

3.6.3 破坏“循环等待”条件

采用按序分配资源法:具体做法是把系统中所有资源排一个顺序,对每一个资源确定编号,规定任何一个进程必须按照序号递增的顺序请求资源。

这种预防死锁的策略可以提高资源利用率,但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。

3.7 避免死锁

在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。这种方法所施加的限制条件较弱,可能获得较好的系统性能,目前常用此方法来避免发生死锁。

3.7.1 系统安全状态

当系统处于安全状态时,可避免发生死锁。反之,当系统处于不安全状态时,则可能进入到死锁状态。

  1. 安全状态

    在此状态下系统能按某种顺序(例如P1、P2……Pn)来为各个进程分配其所需资源,直至最大需求,使每个进程都可顺序地一个个地完成。这个序列(P1、P2…….Pn)称为安全序列。

  2. 安全状态之例

  3. 由安全状态向不安全状态的转换

3.7.2 利用银行家算法避免死锁

  1. 银行家算法中的数据结构

    • 可利用资源向量 Available。
    • 最大需求矩阵 Max。
    • 分配矩阵 Allocation。
    • 需求矩阵 Need。
  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] - Request_i[j];\\Allocation[i, j] = Allocation[i, j] + Request_i[j];\\Need[i, j] = Need[i, j] - Request_i[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[j]+Allocation[i, j];\\Finish[i] =true;\\go \ to \ step \ 2;​\]

    4. 如果所有进程的 Finish[i]=true 都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

3.8 死锁的检测与解除

3.8.1 死锁的检测

为了能对系统中是否已发生了死锁进行检测,在系统中必须:① 保存有关资源的请求和分配信息;② 提供一种算法,它利用这些信息来检测系统是否已进入死锁状态。

  1. 死锁分配图(Resource Allocation Graph)

    G = (N, E),点集 N,边集 E。N = P ∪ R,P 是进程节点,R 是资源节点。

    凡属于 E 中的一个边 e∈E,都连接着 P 中的一个结点和 R 中的一个结点,e={Pi, Rj} 是资源请求边,由进程 Pi 指向资源 Rj,它表示进程 Pi 请求一个单位的 Rj 资源。E={Rj, Pi} 是资源分配边,由资源 Rj 指向进程 Pi,它表示把一个单位的资源 Rj 分配给进程 Pi

  2. 死锁定理

    S 为死锁状态的充要条件是:当且仅当 S 状态的资源分配图是不可化简的。该充分条件被称为死锁定理。简化方法如下:

    • 在资源分配图中,找出一个既不阻塞又非独立的进程结点 Pi,顺利的情况下,Pi 可获得所需资源而继续运行,直至运行完毕,再释放其所占有的全部资源,消去 Pi 的请求边和分配边,使之成为孤立的结点。
    • 再找下一个这样的进程结点,若能消去图中所有的边,使所有的进程结点都成为孤立结点,则该图是可完全简化的;狗则是不可完全简化的。

    不同的简化顺序,都将得到相同的不可简化图。

  3. 死锁检测中的数据结构

    • 可利用资源向量 Available,
    • 把不占用资源的进程(Allocation=0)记入 L 表中,即 Li∪L。
    • 从进程集合中找到一个 Requesti≤Work 的进程,做如下处理:① 将其资源分配图简化,释放出资源,增加工作向量 Work =Work + Allocation i。② 将它记入 L 表中。
    • 若不能把所有进程都记入 L 表中,便表明系统状态 S 的资源分配图是不可完全简化的。因此,该系统状态将发生死锁。

3.8.2 死锁的解除

  1. 终止进程的方法

    • 终止所有死锁进程
    • 逐个终止进程
  2. 付出代价最小的死锁解除算法

    找出每一层的最小代价,但不实际。

死锁处理方法总结

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×