第三章 进程调度与死锁

写在前面：

​ 这一章的内容比较简单，主要就是两方面：调度与死锁。

在调度有以下内容：

• 调度的基本概念

  • 调度种类
  • 调度模型
  • 调度准则

• 调度算法

  • FCFS与SJF
  • 优先权：响应时间比
  • 时间片思想

在死锁中有以下几方面：

• 死锁产生的原因与必要条件
• 预防死锁
  • 从三个必要条件入手
• 避免死锁
  • 银行家算法
• 检测死锁
  • 银行家算法
  • 资源分配图
• 解除死锁

一、进程调度基本概念

1.1 高级、中级、低级调度

1.1.1 高级调度：

​ 用于决定把哪些作业从外存中调入到内存中，并为其分配资源，并放入就绪队列上，也称为作业调度。需要指明的一点是，在分时与实时系统中，是不存在作业调度的。

需要考虑的问题：

• 调度多少个作业：太多——服务响应差；太少——利用率太低
• 调度哪些作业：先来先服务、短作业优先调度、作业优先权调度
  • 值得注意的一点是，从现在开始的一些调度思想，会一直沿用到后面
  • 短作业调度的思想：有人一分钟答疑/有人一小时答疑，所以选一分钟的

1.1.2 低级调度：

​ 用于决定在就绪队列中，哪个进程将获得处理机，也叫进程调度。

需要考虑的问题：

• 三种OS都需要采用这种低级调度
• 非抢占式调度：一直进行，直到完成或者阻塞
• 抢占式调度：根据某种算法，某个进程的CPU资源会被剥夺
  • 有时间片原则、优先权原则、短作业优先原则

1.1.3 中级调度：

​ 用于决定将那些暂时不用的进程挂起，放到外存上去。

注意： 以上三种调度，低级调度用的是最多的。

1.2 调度队列模型

1.2.1 仅有进程调度

每个进程都会出现以下三种情况：

• 该任务在该时间片内已完成，该进程释放处理机进入完成状态
• 任务在本次其对应的时间片内尚未完成，OS便将该任务放在就绪队列的后面
• 执行期间，进程因某事件而被阻塞后，OS将它放入阻塞队列

1.2.2 进程调度+作业调度

与之前不同的是，此时的阻塞是有多个队列，分别记录多个不同的原因。

1.2.3 三种调度都有

当引入中级调度后，就绪状态变成：内存就绪状态，外存就绪状态；阻塞状态变成：内存阻塞和外存阻塞。

• 内存就绪：正常的就绪态
• 外存就绪：在就绪队列上，暂时不用的进程放入外存
• 内存阻塞：正常运行的程序，因为某种情况而阻塞，但还在内存中
• 外存阻塞：把阻塞的程序放入外存中

**个人理解：**中级调度中，有两类：就绪到外存上、阻塞到外存上。

1.3 选择调度算法准则

1.3.1 面向用户

周转时间：

​ 把作业提交给系统，到作业完成的时间。其中包括以下几部分：

• 外存等待的时间
• 就绪队列上的时间
• 执行的时间
• 阻塞的时间

平均周转时间：

​ 多个进程取平均值

平均带权周转时间：

​ 多个进程的加权平均数

响应时间：

​ 主要是对外设的响应 = 等待时间 + 要求服务的时间

截止时间：

​ 任务开始的最迟时间/任务结束的最迟时间

优先权准则：

​ 在一定情况下使用抢占式方法

1.3.2 面向系统

系统吞吐量：

​ 单位时间内的作业数

CPU利用率：

​ 以前CPU贵的时候，现在CPU好像不是首选考虑的了。

各类资源的均衡利用：

​ 综合考虑内存、外存、I/O设备等资源充分利用。

二、调度算法

2.1 先来先服务FCFS与短作业优先SJF、SPF

2.1.1 FCFS

特点：

• 有利于长作业，不利于短作业：如果有一个短作业的话，其实最好先让短作业开始干
• 有利于CPU繁忙型作业(科学计算)，但是不利于I/O繁忙型作业
• 其实CPU繁忙型就相当于长作业，I/O繁忙相当于短作业

计算公式：

• 一般会给出到达时间、服务时间和第一个开始时间
• 由第一个开始时间与第一个服务时间推出完成时间与下一个开始时间
• 依次类推，最终求出所有的完成时间
• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间 / 服务时间

2.1.2 SJF、SPF

特点：

• 有利于短作业/进程
• 平均周转时间短，系统吞吐量高
• 也可能发生饥饿的现象
• 也不能保证紧迫性作业的处理
• 用户可能有意识地缩短其作业的估计执行时间

2.2 高优先权调度算法

根据类型，可分成抢占式与非抢占式。

根据优先权划分，可分为静态优先权与动态优先权。

更高级一点，可变成高响应比调度算法。其优先权 = 等待时间 / 要求服务时间 (标准是(等待时间 +要求服务时间)/ 要求服务时间)。其实就是将FCFS与SJF相结合。

2.3 基于时间片轮转调度

2.3.1 时间片轮询

特点：

• 抢占式方法
• 太大的话，退化为FCFS
• 太小的话，影响CPU使用率

2.3.2 多级反馈队列

特点：

• 随着队列向下，优先权越来越低，时间片越来越大
• 各个队列按先进先出调度
• 一个新进程就绪后，进入第一队列
• 第一队列为空时，调度第二队列，依次向下
• 时间片到了之后，回到下一个队列

优点：

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

三、死锁的产生原因与必要条件

3.1 死锁的原因

1.竞争资源引起死锁：

• 竞争可剥夺资源与不可剥夺资源(CPU与I/O)

• 资源分配图：

  • 进程用圆圈表示
  • 资源有方框表示
  • 方框中的小圈圈表示资源个数
  • 资源指向进程：资源已经分配给进程
  • 进程指向资源：进程去申请资源
  • 当分配图出现环路时，就会出现死锁

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

此情况个人觉得，还是因为对资源的访问造成的死锁

3.2 死锁的必要条件

1.互斥条件：

​ 一段时间内，某资源只能由一个进程占有，类似于临界资源

2.请求与保持条件：

​ 进程在申请资源得不到满足的时候，是不会放弃资源的，而是会阻塞

3.不剥夺条件：

​ 进程已经获得的资源，在未使用完之前，不能被剥夺。

4.环路条件：

​ 当发生死锁时，必然产生环路。

3.3 处理死锁

1.预防死锁：

​ 从必要性的角度出发，限制某些条件，从而去破坏死锁的必要条件。易实现、应用广泛、但资源利用率低。

2.避免死锁：

​ 经典的银行家算法，但实现起来有一定难度。

3.检测与解除死锁：

• 撤销进程
• 挂起进程

四、死锁的预防与避免

4.1 死锁的预防

1.破坏请求与保持条件：

​ 进程一次性申请全部资源(AND型信号量)，这样在运行期间无请求，在等待期间无保持

缺点：

• 资源利用率低
• 使进程延迟运行，甚至会出现饥饿的情况

2.摒弃不剥夺条件：

​ 已经申请一部分资源的进程，当申请新的资源的时候，如果不能分配给它，那就剥夺他所占有的全部资源，并将其加入等待队列。

缺点：

• 对打印机这种不友好
• 反复申请释放资源增加系统开销

3.摒弃环路等待：

​ 将所有资源按类型编号，只能按递增顺序申请资源，避免出现环路

道理：

​ 首先对于n个进程来说，每个进程当前所申请最大的资源编号为Ni，取现在申请了最大资源编号的那个进程，那么该进程在运行过程中，对于后续的资源申请是一定不会造成阻塞的，当运行完这个程序后，再去找第二大申请资源的编号的进程，就可以一直保证无死锁现象。

缺点：

• 系统各类资源分配顺序相对稳定，限制新设备的加入
• 资源类标号顺序要考虑实际情况
• 限制用户简单自主编程

4.2 死锁的避免

​ 将系统的状态定义为安全态与不安全态，保证每一刻系统都在安全态。

安全状态：

​ 存在着一个分配序列，使得每次在分配资源时，不会出现不满足的情况。

这里一定要注意计算点：！！！

​ 可用资源 = 可用 + 进程所需要的最大资源

银行家算法：

​ 先假定分配给资源，然后计算系统当前的安全状态，如果是安全态，那么就分配；如果是不安全状态，那么就不给他。

并非所有不安全状态都是死锁状态？

​ 进程是并发执行的！

这个算法是不难的，到时候直接做题就可以了。

五、死锁的检测与解除

5.1 死锁的检测

1.根据资源分配图：

​ 将资源分配图反复简化，如果线段都简化完了，那就可以跑完，否则就死锁了。

• 先画出资源分配图
• 再依次观察进程，如果这个进程可以跑，那么就先把这个边简化掉

2.根据银行家算法：

​ 略

5.2 死锁的接触

• 杀死进程
• 按某种顺序撤销进程，直到死锁接触
  • 可以按照运行时间撤销
  • 可以用资源的种类
  • 用老师的话讲：抓刺头！