OS：处理机调度与死锁🔒
处理机调度与死锁 🔒
Q:如果系统只有一个 cpu,有两个进程要运行.进程 A 的运行时间将是 1 小时,进程 B 的运行时间是 1 分钟.那么认为操作系统让哪个进程先运行比较合理?
A：与操作系统的调度策略有关，即更重视优先级还是到来顺序、时长等因素。
调度
对处理机（CPU）资源进行分配。
调度层次
高级（作业）调度、中级（内存）调度、低级（进程）调度。
区分主要是运行频率，低级调度最频繁，也是重点。
后备队列（Spooling Queue 或 Backup Queue）是指操作系统或系统调度过程中用于存放尚未进入内存执行的进程或任务的队列。根据实际情况，后备队列可以位于外存或与外存相关的区域，而非内存。
作业（Job）：一组需要完成的任务或程序的组合。
- 高级调度：决定哪些后备队列中的（外存中的）作业调入内存并创建进程与分配资源。
- 中级调度：决定哪些进程可参与竞争 CPU。（内存->外存）
- 低级调度：决定哪个进程可以获得 CPU。
低级调度有两种方式：
- 非抢占式：一直执行完成或自动阻塞。
- 抢占式：允许其他进程依据一定规则抢占 CPU。
（1）时间片原则、（2）优先权原则 、（3）短作业（进程）优先原则
1. 周转时间 (Turnaround Time)
作业（进程）从提交（进入时刻）到完成的时间称为该作业的周转时间 (T_i)：
$$ T_i = \text{完成时刻} - \text{进入时刻} $$
2. 平均周转时间 (Average Turnaround Time)
平均周转时间为 (n) 个作业（进程）周转时间的平均值：
$$ T = \frac{1}{n} \left( \sum_{i=1}^{n} T_i \right) $$
3. 带权周转时间 (Weighted Turnaround Time)
作业（进程）周转时间 (Ti) 与实际运行时间 (T{si}) 之比称为该作业的带权周转时间 (W_i)：
$$ W_i = \frac{T_i}{T_{si}} $$
4. 平均带权周转时间 (Average Weighted Turnaround Time)
平均带权周转时间为 (n) 个作业（进程）带权周转时间的平均值：
$$ W = \frac{1}{n} \left( \sum_{i=1}^{n} \frac{T_i}{T_{si}} \right) $$
调度算法
根据系统的资源分配策略所规定的资源分配方法
-
先来先服务（FCFS）
作业调度：从后背队列选择一个或多个最先进入队列的作业
-
短作业（进程）优先（SF）
从就绪队列中选择 CPU 执行时间最短的作业
-
高响应比优先（HRN）
选择待调度的作业中响应比最高的
$$ R_p = \frac{W_i + S_i}{S_i} $$
Rp:响应比
Wi：已等待时间
Si：要求服务时间
-
最高优先权（HPF）
选择优先权最高的，其中又分为：
静态优先权
动态优先权
-
时间片轮转（RR）
每次为一个进程执行一个时间片 T
-
多级队列调度
将就绪队列分为多种不同队列，不同队列使用不同调度算法
-
多级反馈队列调度算法
设置多个就绪队列，从高到低赋予不同优先级，每个队列采用 RR 算法，时间片长度依次增加。
死锁
概述
死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前进。
产生原因
- 资源竞争
-
当两个或以上进程需要两个或以上资源(非剥夺性资源 or 临时性资源)：
- 可剥夺性资源
- 非剥夺性资源
- 临时性资源：由某进程产生，由另一进程使用的资源。（信号量）
-
进程推进非法
请求和释放资源的顺序不当。
产生死锁必要条件
-
互斥条件：请求的资源为临界资源
临界资源（Critical Resource）：指多个进程或线程在同一时间只能由一个进程使用的资源。对这种资源的访问必须受到严格的控制，以防止数据不一致或竞争问题的发生。典型的临界资源包括共享内存、文件、数据库等。
可见，访问临界资源必须要有同步或互斥机制（同步：信号量，互斥：锁）！！
-
请求和保持条件：申请新资源，保持旧资源
-
不剥夺条件：已获得的资源，在使用完之前，不被外力剥夺。
-
环路等待条件：互相等待资源
处理死锁的基本方法
- 预防死锁：设置限制条件，破坏死锁产生
- 避免死锁：资源分配的动态方法
- 检测死锁：采取措施，解除死锁
- 解除死锁：剥夺资源或撤销进程回收 ♻️ 资源
银行家算法 🏦
安全序列
安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程 Pi 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
• 可用资源：目前系统中剩余的可用资源数量。
• 最大需求：每个进程所需的最大资源量。
• 已分配资源：每个进程当前占用的资源量。
需求 = 最大需求 - 已分配资源
要找到一个安全序列，需要按照银行家算法，依次寻找一个可以满足当前可用资源条件的进程，完成该进程后，释放其资源，增加可用资源。重复这个过程，直到所有进程都完成。
算法实现
核心：根据系统是否处于安全状态，来决定分配资源与否。
对于银行家算法的具体实现主要由以下几个数据结构：
1、可利用资源向量 Available：
一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目
2、最大需求矩阵 Max：
一个 n×m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求
3、分配矩阵 Allocation：
一个 n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数
4、需求矩阵 Need：
一个 n×m 的矩阵，用以表示每一个进程还需的各类资源数
Need［i,j］=Max［i,j］-Allocation［i,j］
设 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］-Requesti［j］;
② Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
③ Need［i,j］∶=Need［i,j］-Requesti［j］;
(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。 对于系统整体安全状态的检查，引入安全性算法，核心实现如下：
(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［i］+Allocation［i,j］; Finish［i］∶=true; go to step 2; (4) 如果所有进程的 Finish［i］=true 都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。
银行家算法的缺点如下：
1.很少有进程能够在运行前就知道其所需资源的最大值
2.而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出）
3.原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）
4.银行家算法的开销较大，实时性不是很好
解除死锁
利用死锁定理
对于死锁的解除，即**（1）剥夺资源，(2) 撤消进程**。
实用而又简便的方法是： 逐个撤消那些代价最小的进程，或者，使撤消进程的数量最少，直至获得为解除死锁所需要的足够可用的资源。