首页 计算机科学 操作系统

操作系统复习三

# 处理机调度与死锁

# 作业

  • 在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关业务处理的全部工作称为一个作业

  • 作业步：在一个作业的处理过程中，计算机所做的相对独立的工作。作业由不同顺序的作业步组成

  • 作业组织：

    • 作业：作业 = 程序 + 数据 (作业体)+ 作业说明 (作业控制语言)
    • 作业说明书：
      • 体现用户的控制意图
      • 包括作业基本情况、作业控制、作业资源
      • 它由作业控制语言编写

  • 作业控制语言

    • 用户用于描述批处理作业处理过程控制意图的一种特殊程序
    • 作业控制语言（JCL），例如：批量处理文件或 shell

  • 作业的建立

    • 一个作业的全部程序和数据输入到外存且系统中建立了相应的作业控制块 (JCB)
    • 必须有外部启动信号通知系统调用相应的作业输入管理程序 —— 决定作业的输入方式

# 处理机调度

  • 高级调度 (又称为作业调度或长程调度)

    • 功能：用于决定把外存上处于后备队列的那些作业调入内存

  • 中级调度 (又称中程调度)

    • 目的：为了提高内存利用率和系统吞吐量
    • 功能：
      • 暂时不能运行的进程挂起，释放宝贵的内存资源
      • 具备条件时，把外存上的就绪进程重新调入内存，挂在就绪队列上等待调度

  • 低级调度 (又称进程调度或短程调度)

    • 功能：

      • 保存处理机的现场信息，统称保存断点信息
      • 按照某种算法选取进程
      • 把处理机分配给进程，即把选中的 PCB 内容装入处理机相应的寄存器中，从上次断点处开始运行

    • 进程调度机制：(包括三个基本部分：排队器、分派器、上下文切换器)

    • 进程调度方式：

      • 非抢占方式：
        • 正在执行的进程执行完毕，选一新进程
        • 执行中的进程因提出 I/O 请求而暂停运行
        • 进程调用了 P、V 操作
        • 分时系统中时间片用完
      • 抢占方式：
        • 抢占原则有：优先权原则、短作业优先原则、时间片原则

选择调度算法和调度方式的若干准则：

  • 面向用户的准则：

    • 周转时间短，所谓周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔
    • 响应时间快，响应时间是从用户通过键盘提交一个请求开始直到系统首次产生响应为止的时间
    • 截止时间的保证，截止时间为某任务必须开始执行的最迟时间
    • 优先权原则

  • 面向系统的原则：

    • 系统吞吐量高
    • 处理机利用率好
    • 各类资源的平衡利用

调度算法：

  • 先来先服务 (FCFS) 调度算法

  • 短进程优先 (SPF/SJF) 调度算法

  • 高优先权优先 (FPF) 调度算法

    • 优先权类型：

      • 静态优先权：静态优先权是在创建进程时确定的，而且在进程整个运行期间保持不变
      • 动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变，以便获得更好的调度性能

    • 确定进程优先权依据：

      • 进程类型
      • 进程对资源的需求
      • 用户要求

  • 高响应比有限调度算法：

    优先权的变化规律可描述为：

    优先权 =(等待时间 + 要求服务时间)/ 要求服务时间；响应时间 = 等待时间 + 要求服务时间

    • 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业
    • 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务
    • 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机

  • 基于时间片的轮转调度算法 (RR 算法)：

    进程切换时机：

    • 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片
    • 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾

  • 多级反馈队列调度算法：

    调度算法原则：

    • 设置多个就绪队列
    • 各个队列优先级不同
    • 各个队列中进程执行时间片的大小也各不相同。优先权愈高，执行时间片就愈小

  • 基于公平原则的调度算法：

    • 保证调度算法
    • 公平共享调度算法

调度算法例题：

有三个进程 A、B、C，它们分别单独运行时的 cpu 和 I/O 占用时间如下图所示：

作业 A：

I/O2(10)−>CPU(20)−>I/O1(30)−>CPU(10)−>I/O1(40)−>CPU(20)−>I/O1(20)I/O_2(10)->CPU(20)->I/O_1(30)->CPU(10)->I/O_1(40)->CPU(20)->I/O_1(20)

作业 B:

I/O1(30)−>CPU(40)−>I/O2(30)−>CPU(30)−>I/O1(30)I/O_1(30)->CPU(40)->I/O_2(30)->CPU(30)->I/O_1(30)

作业 C:

CPU(40)−>I/O1(20)−>CPU(20)−>I/O2(70)CPU(40)->I/O_1(20)->CPU(20)->I/O_2(70)

现在请考虑三个作业同时开始运行，系统中的资源有一个 CPU 和两台输入 / 输出设备 (I/O1 和 I/O2) 同时运行，三个作业的优先级为 A 最高，B 次之，C 最低，一旦低优先级的进程开始占用 cpu，高优先级进程也要等待到其结束后方可占用 cpu，请回答以下问题：1）最早结束的作业时哪个？2）最后结束的进程是哪个？3）计算这段时间 cpu 的利用率（三个作业全部结束为止）

I/O1:B(0−30),C(40−60),A(60−90),A(110−150),B(160−190),A(190−210)I/O2:A(0−10),B(100−130),C(130−200)CPU:C(0−40),A(40−60),B(60−100),A(100−110),C(110−130),B(130−160),A(160−180)I/O_1:B(0-30),C(40-60),A(60-90),A(110-150),B(160-190),A(190-210)\\ I/O_2:A(0-10),B(100-130),C(130-200)\\ CPU:C(0-40),A(40-60),B(60-100),A(100-110),C(110-130),B(130-160),A(160-180)

1、最早结束的是 B 作业，结束时间为 190ms

2、最后结束的是 A 作业，结束时间为 210ms

3、cpu 利用率为 180/210=6/7

实时调度算法：

1、非抢占式调度算法

  • 非抢占式轮转调度算法
  • 非抢占式优先调度算法

2、抢占式调度算法

  • 基于时钟中断的抢占式优先权调度算法
  • 立即抢占 (Immediate Preemption) 的优先权调度算法

最早截止时间优先即 EDF (Earliest Deadline First) 算法

最低松弛度优先即 LLF (Least Laxity First) 算法：松弛度越小表示该任务越紧迫，优先级别越高

多处理机的调度：

  • 对称式多处理系统

    • 集中控制
      • 静态分配 (static assignment)：每个 CPU 设立一个就绪队列，进程从开始执行到完成，都在同一个 CPU 上
      • 动态分配 (dynamic assignment)：各个 CPU 采用一个公共就绪队列，队首进程每次分派到当前空闲的 CPU 上执行
    • 分散控制
      • 自调度 (self-scheduling)：各个 CPU 采用一个公共就绪队列，每个处理机都可以从队列中选择适当进程来执行。需要对就绪队列的数据结构进行互斥访问控制

  • 非对称式多处理系统 (ASMP) 的处理机调度

    • 主 - 从处理机系统，由主处理机管理一个公共就绪队列，并分派进程给从处理机执行
    • 各个处理机有固定分工，如执行 OS 的系统功能，I/O 处理，应用程序

  • 成组调度 (gang scheduling)

    • 将一个进程中的一组线程，每次分派时同时分到一组处理机上执行，在剥夺处理机时也同时对这一组线程进行。
    • 面向所有应用程序平均分配处理器时间
    • 面向所有线程平均分配处理器时间

  • 专用处理机调度 (dedicated processor assignment)

    • 为进程中的每个线程都固定分配一个 CPU，直到该线程执行完成

# 死锁

死锁的概念：指两个或两个以上的进程都无限止的等待永不出现的资源而发生的一种状态

死锁产生原因：

  • 竞争资源
    • 可剥夺资源
    • 非剥夺性资源
    • 临时性资源
  • 进程间推进顺序非法

死锁的四个必要条件：

  • 互斥使用
  • 不可抢占
  • 请求和保持
  • 循环等待

死锁的处理方法概述：

  • 死锁预防 (破坏死锁出现条件)

    • 在进程执行前，一次性申请所有需要的资源，不会占有资源再去申请其它资源
    • 对资源类型进行排序，资源申请必须按序进行，不会出现环路等待

  • 死锁避免 (检测每个资源请求，如果造成死锁就拒绝)

    • 银行家算法

      • S1: 某个客户提出贷款请求
      • S2: 假设批准该请求，将得到系统状态 T
      • S3: 判断状态 T 是否安全，如果安全，则批准该请求，转 S1；如果不安全，则不批准该请求，延期到以后处理，转 S1

    • 判断一个状态 T 是否安全：

      • S1: 银行家检查一下，看他手里的资源能否满足某个客户的请求（剩余的最大限额）
      • S2: 如果可以，则该客户的贷款请求已经满足，因此他偿还了所有贷款。转 S1
      • S3: 如果到最后，所有的贷款都能偿还，则状态 T 就是安全的，否则就是不安全的

    • 例题：

      • 某系统有 n 台互斥使用的同类设备，三个并发进程分别需要 3、4、5 台设备，可确保系统不会发生死锁的设备数 n 最小为 (B)

        A.9 B.10 C.11 D.12

      • 若系统中有 3 个不用的临界资源 R1，R2，R3, 被 4 个进程 P1、P2、P3、P4 共享。各进程对资源的需求为 P1 申请 R1 和 R2，P2 申请 R2 和 R3，P3 申请 R1 和 R3，P4 申请 R2. 若系统出现死锁，则处于死锁状态进程数至少是 (C)。

        A.1 B.2 C.3 D.4

  • 死锁检测 + 恢复 (检测到死锁出现，让一些进程回滚，让出资源)

    • 定时检测或者是发现资源利用率低时检测
    • 死锁解除：
      • 剥夺资源
      • 撤销进程

  • 死锁忽略 (就好像没有出现死锁)

例题：

下列关于银行家算法叙述中，正确的是（B）

A. 银行家算法可以预防死锁

B. 当系统处于安全状态时，系统中一定无死锁进程

C. 当系统处于不安全状态时，系统中一定会出现死锁进程

D. 银行家算法破坏了死锁必要条件中的 “请求和保持” 条件

A 选项，银行家算法是死锁避免部分，不能预防死锁。B 选项，如果系统处于安全状态，系统一定可以避免进入死锁状态。C 选项，并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态。D、破坏 "请求和保持" 条件是预防死锁的方法，而银行家算法是避免死锁的办法

若系统 S1 采用死锁避免方法，S2 采用死锁检测方法，下列叙述中正确的是（B）

（1）S1 会限制用户申请资源的顺序，而 S2 不会

（2）S1 需要进程运行所需的资源总量信息，而 S2 不需要

（3）S1 不会给可能导致死锁的进程分配资源，而 S2 会

A. 仅（1）和（2） B. 仅（2）和（3） C. 仅（1）和（3） D.（1）（2）（3）

死锁预防典型是顺序资源分配法，限制进程申请资源的顺序。死锁避免算法，典型是银行家算法，不会限制申请资源的顺序，但是会限制分配资源的顺序。死锁检测不会限制任何顺序