处理机调度与死锁（操作系统）

2024-04-04 13:40:53

处理机调度与死锁

Content

调度

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

处理机调度的三个层次

  1. 高级调度（作业调度），从外存调入内存，并为作业创建进程分配资源，时间较长

  2. 低级调度（进程调度），重点关注（频率最高），决定哪个进程获得处理机，分非抢占和抢占两种

    非抢占式（CPU 不能抢） 抢占式（CPU 可以抢）
    无交互，多用于批处理，不能用于分时、实时 优先级原则，短作业优先原则，时间片原则

  3. 中级调度（内存调度），决定挂起（调入外存）和激活（唤醒）哪一个进程

调度算法的目标

  1. 共同目标

    提高资源利用率，CPU利用率这种自然是越高越好

  2. 批处理的目标：周转时间短

  3. 分时的目标：响应时间快

  4. 实时的目标：截止时间的保证

3.2 作业调度

调度算法

1.   先 来 先 服 务 F C F S ( F i r s t − C o m e   F i r s t − S e r v e d ) {1.\ 先来先服务FCFS (First-Come\ First-Served)} 1. 先来先服务FCFS(First−Come First−Served)

基础的调度算法，有利于 CPU 繁忙型（很少请求 I/O，一直计算）的作业，已少主用

（I/O 繁忙型：CPU 处理时较频繁请求 I/O）
2.   短 作 业 优 先 S J F ( S h o r t   J o b   F i r s t ) 2.\ 短作业优先SJF(Short\ Job\ First) 2. 短作业优先SJF(Short Job First)
缺点：长作业可能饿死
1.   优 先 级 调 度 算 法 P S A ( P r i o r i t y − S c h e d u l i n g   A l g o r i t h m ) 1.\ 优先级调度算法PSA(Priority-Scheduling\ Algorithm) 1. 优先级调度算法PSA(Priority−Scheduling Algorithm)
缺点：一出生优先级就低的可能饿死
2. 高响应比优先调度算法HRRN(Highest Response Ratio Next) ( 响 应 比 = 等 待   t i m e + 服 务   t i m e 服 务   t i m e ) \colorbox{yellow} {2. 高响应比优先调度算法HRRN(Highest Response Ratio Next)}\bigg(响应比 = {等待\ time + 服务\ time\above{1pt}服务\ time}\bigg) 2. 高响应比优先调度算法HRRN(Highest Response Ratio Next)​(响应比=服务 time等待 time+服务 time​)
其实就是动态优先级，等待 t 越长优先级越高，服务 t 越短优先级越高（类似于 SJF，有利于短作业）

缺点：会增加系统开销（每隔单位时间都要算一下优先级）

3.3 进程调度

进程调度方式

  1. 非抢占方式（Non-preemptive Mode）
  2. 抢占方式（Preemptive Mode）

调度算法

1.   时 间 片 轮 转 法 R R ( R o u n d   R o b i n ) 1.\ 时间片轮转法RR(Round\ Robin) 1. 时间片轮转法RR(Round Robin)

缺点：等优先级（无优先），时间片大小的确定对系统性能影响很大
2.   优 先 级 调 度 算 法 2.\ 优先级调度算法 2. 优先级调度算法

  1. 静态优先级，固定优先级
  2. 动态优先级，优先级的值随进程推进或等待时间的增加而改变

3.   多 级 反 馈 队 列 调 度 算 法 ( M u l t i l e v e d   F e e d b a c k   Q u e u e ) 3.\ 多级反馈队列调度算法(Multileved\ Feedback\ Queue) 3. 多级反馈队列调度算法(Multileved Feedback Queue)

现在用的就是这个，在时间片轮转的前提下加优先级，分多队

  • 每队优先级不同，同队优先级相同，用完时间片降一级
  • 每队时间片不同
  • 每次时间片逐队扫描

3.4 实时调度

调度算法

1.   最 早 截 止 时 间 优 先 E D F ( E a r l i e s t   D e a d l i n e   F i r s t ) 算 法 1.\ 最早截止时间优先EDF(Earliest\ Deadline\ First)算法 1. 最早截止时间优先EDF(Earliest Deadline First)算法

  1. 非抢占式，比较简单
  2. 抢占式，看书吧，没怎么学会，主要用于有周期的实时任务（书上大致是 A3 推迟了些，给 B1 腾时间结束）

2.   最 低 松 弛 度 优 先 L L F ( L e a s t   L a x i t y   F i r s t ) 算 法 2.\ 最低松弛度优先LLF(Least\ Laxity\ First)算法 2. 最低松弛度优先LLF(Least Laxity First)算法

最低松弛度即紧迫程度（松弛程度就是可以浪的时间）感觉差别不大
补 充 : 优 先 级 倒 置 ( P r i o r i t y   I n v e r s i o n   P r o b l e m ) 补充:优先级倒置(Priority\ Inversion\ Problem) 补充:优先级倒置(Priority Inversion Problem)
例：P3 拿走了打印机，a 时刻 P2 进入抢走处理机，b 时刻 P1 进入抢走处理机，因需要打印机而堵塞，换 P2 继续执行至结束，然后等 P3 释放打印机唤醒 P1（P2 延长的时间是不确定的）

解决方法：暂时将 P3 优先级提高到与 P1 相等

死锁

3.5 死锁概述

死锁的定义

死锁产生的原因：资源的争夺

死锁的定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的（Deadlock）

死锁产生的四个必要条件

  1. 互斥条件（必须保证的）
  2. 请求和保持条件
  3. 不可抢占条件（不可剥夺）
  4. 循环等待条件（环路等待）

处理死锁的方法

处理死锁的方法 说明
1. 预防死锁 可能造成 资源利用率下降 系统吞吐量下降
2. 避免死锁 常用
3. 检测死锁 与 4 配套使用，是相对最难实现的（没办法时用）
4. 解除死锁

3.6 预防死锁

破坏四个必要条件之一

产生条件 破坏
互斥 不能破坏，必须保证的
请求和保持 1. 预分配 2. 空手申请（频繁申请释放）
不可抢占 不好，比如打印机打印一半
循环等待 哲学家先拿偶数号筷子（先编号，有序资源分配策略）

3.7 避免死锁

系统安全状态：只要有一个组合（安全序列），是安全的，就是安全状态，否则不安全

不安全状态迟早死锁！

怎么找安全序列？

D i j k s t r a   的 银 行 家 算 法 Dijkstra\ 的银行家算法 Dijkstra 的银行家算法

四个数据结构，如图 是简单的例子（解题方法练手用）

进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2
P3 9 2
Need 尚需的 Max 共需 Allocation 已分配 Available 可用
这是银行家算法的四个数据结构 无需看 Max - Need 与 Need 比较即可

算法的四个步骤

  1. 检测 请求量 R 是否小于 Need
  2. 检测 R 是否小于 Available
  3. 试探性分配
  4. 安全性算法（看看分配完后是否处于安全状态，就是找安全序列）
肯定按安全序列的顺序才会安全啊

死锁的检测和解除，这两个配套使用

解 题 : ( 尽 量 让 自 己 以 后 能 一 眼 忆 起 ) 根 据   M a x   和   A l l o c a t i o n   计 算 出   N e e d ， 然 后 拿   A v a i l a b l e   与   N e e d   匹 配 ， 匹 配 到 的 就 把   A l l o c a t i o n   加 到   A v a i l a b l e ， 重 复 操 作 即 可   ( 匹 配 : N e e d   的 各 类 资 源 小 于   A v a i l a b l e ) 解题:(尽量让自己以后能一眼忆起) 根据\ Max\ 和\ Allocation\ 计算出\ Need，然后拿\ Available\ 与\ Need\ 匹配，\\匹配到的就把\ Allocation\ 加到\ Available，重复操作即可\ (匹配:Need\ 的各类资源小于\ Available) 解题:(尽量让自己以后能一眼忆起)根据 Max 和 Allocation 计算出 Need，然后拿 Available 与 Need 匹配，匹配到的就把 Allocation 加到 Available，重复操作即可 (匹配:Need 的各类资源小于 Available)

E n d . End. End.

上一篇：力扣76题（滑动窗口算法）


下一篇：【操作系统】银行家算法的例题详解