进程调度与死锁

笔记分享

2024-06-16

本文将讨论操作系统进程的概念，主要讨论死锁发生的条件、如何避免死锁。

进程

进程: 一个程序的一次动态执行过程，是操作系统在进行资源分配和调度时的一个独立单位。

程序：指令、数据及其组织形式的描述可以这么理解，在现代操作系统设计中，程序是静态的描述，而进程是其动态的执行过程

用户的所有程序近通过进程的形式运行操作系统为用户提供的服务已进程的方式执行 进程管理模型是操作系统的核心模块之一

特征

动态性上面提到，进程本质就是一个程序的执行过程，是一个动态的概念 进程有一定的生命周期，由创建产生、由调度执行、由撤销消亡
并发性多个进程可共存于内存中，并在一段时间内同时执行
独立性每个进程是一个能独立运行的基本单位在操作系统中，进程是独立获得资源和独立调度的基本单位
异步性各进程之间按各自独立的、不可预知的的速度向前推进
结构性进程由进程控制块(PCB)+进程体组成

状态

状态是动态的概念，程序无状态 一般而言，进程至少包含三个状态

就绪进程取得了除CPU外的所有必要资源，等待OS调度即可执行
执行就绪进程当获得CPU后，就将进入执行状态理论上单处理及系统同时只有一个进程进入执行状态
堵塞(等待) 当进程应某种事件(如IO请求，进程同步等)，此时即使进程取得CPU也无法执行，

状态转换

在执行过程中，进程的状态可能发生多次装换下图为最为常见的三状态转换关系图:

进程调度与死锁-三状态.png

还有更为复杂的5状态和7状态，下面只演示7状态

挂起操作

7状态图引入了挂起的概念

什么是挂起: 挂起(Suspend)就是将内存中暂时不能运行的进程转移到外存，以便与提升内存的利用率的一种操作

对于转移出内存的这个操作，被称为换出，转移到内存的操作叫换入，这里不深究挂起状态在一些书上被称为是静止状态，与仍保留在内存总的活动状态对立

挂起操作仅作用于暂时不能运行的进程，故只有就绪、堵塞状态下的进程可能会被挂起，7状态图如下：

进程调度与死锁-七状态.png

挂起的动机往往有两种:

回收内存主要还为了资源利用率，确保当系统重负荷时正常进行。
暂停进程方便开发人员调试、修改父进程需要对子进程进行操作 OS对进程进行监控等

被挂起进程的特点

被挂起的进程不能立即执行
只有进程自身、父进行、OS可挂起进程
进程由谁挂起，就由谁解除
若进程应等待某一事件处于阻塞挂起状态，阻塞事件不影响挂起状态

其他细节先跳过，本文主要研究死锁与进程调度。

调度

通常在一个时间段内，有许多进程处于就绪状态

而进程数往往要比处理机多得多，将导致进程之间相互竞争处理机此时就需要按照一定的策略从就绪队列种选取进程，交给处理机执行，这就是进程的调度

好的调度算法往往可以选择出更好的个体具体流程如下:

保存当前CPU现场信息(计算器、寄存器内容等)
按照某种方法选取进程
将CPU分配给进程

调度目标

一个好的调度算法要尽可能满足以下目标

响应时间尽可能快
进程的处理时间尽可能短
使系统吞吐量尽可能大
让资源利用率尽可能高
做到尽可能对所有进程公平
避免进程出现饥饿
避免进程间出现死锁

进程调度方式

对于进程的调度方式主要分为两类

抢占式

一旦将CPU分配给某一进程，除非进程结束或是发生某些事件导致进程不能运行，已获得的CPU不会转交给其他线程

非抢占式

当进程得到CPU时，操作系统可能根据某种策略回收CPU，并将当前进程移入就绪队列，然后将CPU交给其他进程

具体的调度算法非本文重点，先跳过

死锁

前面我们了解到，进程之间会相互竞争资源

死锁：当多个进程因资源竞争或执行顺序不当等问题，导致相互之间永久拥堵的现象

死锁一旦发生，若无外界干预，死锁状态将永远保持下去

死锁可以被避免和解除，当死锁发生，可能会影响系统的运行效率

产生死锁的必要条件

互斥

一段事件内某资源只能被某一进程占用

请求和保持

一个至少持有一个资源的进程，等待获取其他而外的由其他进程所持有的资源

不可抢占

一个资源只有在持有它的进程结束时，才能被释放

循环等待

存在“进程-支援”循环链，

例如进程P1持有R1,但在等待R2资源

进程P2持有R2，但在等待R1资源

如何预防死锁

只有上述提到的必要条件都满足时，死锁才会发生

反过来，只要破坏任意一个条件，死锁就会解除

预防死锁的思想是在死锁发生前，通过系统设计，利用限制措施破坏产生死锁的条件

不过这种方法往往不容易实现，例如对于非共享的设备(如打印机)，互斥就是这类资源与生俱来的特性

而且为了破坏条件，往往要做出很多限制，影响系统性能，通常这种方法只存在于理论

如何避免死锁

既然通过限制的方法不容易实现，那就在系统执行时动态检查资源分配情况，避免进入不安全的状态

安全状态

那什么叫不安全，什么情况下能保证安全

安全状态: 系统按某种进程推进顺序，为其分别分配资源，直到满足每个进程的需求，并且每个进程都能顺利完成的状态

安全序列: 能保持安全状态的进程序列

通常来说，安全序列并不唯一 ,若找不到安全序列，则称系统处于不安全状态

注意一点:
不安全状态不一定发生死锁，但安全状态一定不会发生死锁。

举个例子，有3个进程P1、P2、P3，需要为其分配磁带机，磁带机不可共享

当前3个进程的分配情况如下:

进程	要求	已分配
P1	10	5
P2	4	2
P3	9	7

此时还剩下3台空闲磁带机，求安全序列

很明显，3台磁带机只能分配给P2，在P2完成后由释放4台磁带机，此时我们就有5台空闲资源

同样在按顺序分配给P1、P3，我们就得到一个可以能确保所有进程可以顺利完成的执行顺序，这就是安全序列

系统只需要按照安全序列执行，就可以确保不会发生死锁，我们举个反例:

如果我们一开始将资源分配给P1、P3，此时没有任何进程取得的资源达到要求，3个进程依旧处于阻塞状态，都在等待更多的资源，可目前所有的资源都被进程占用，且不能被共享，此时死锁发生。

银行家算法

银行家算法由迪杰斯特拉提出，正如其名，算法最初是为银行系统设计的

我们把刚刚空闲磁带机想象为银行可以放出去的贷款，进程执行完成后释放的资源想象为银行能收回的钱

作为银行，肯定要确保自己发放的贷款不会发生资金周转上的问题

将操作系统想象成银行，为确保分配的资源能够满足进程的需求，OS要求进程在进入系统时事先声明需要的资源种类以及各种资源的需求最大值

当进程请求一组资源时，系统会判断是否由空闲的资源可用于分配，若有则将资源分配给进程，若无则让进程等待

其实我们刚刚在做的实验就是银行家算法的一个简化版

银行家算法的数据结构

这里我们简单说

可用资源向量(Available)

一个含有m个元素的数组，每个元素表示一类可用资源数量

Available[j] = k 表示系统种现由R_j类资源k个

最大需求矩阵(Max)

一个n × m的矩阵，定义n个进程对m类资源的最大需求量

Max[i,j] = k 标签进程P_i需要R_j类资源k个

已分配资源矩阵(Allocation)

一个n × m的矩阵，定义每个进程已获得的各类资源数量

Allocation[i,j] = k 表示进程P_i当前已经分配到k个资源R_j

需求矩阵(Need)

一个n × m的矩阵，定义每个进程还需的各类资源数目

Need[i,j] = k 表示进程P_i还需k个R_j类型的资源

它们的对应关系如下:

Need[i,j]=Max[i,j]-Allocation[i,j]

步骤

设矩阵Request_i是进程P_i的请求向量，如Request_i[i,k] = k,则代表进程P_i需要k个R_j类型的资源

如果Request_i[j]≤Need[i,j]，则下一步，否者认为出错
如果Request_i[j]≤Available[j]，则下一步，否则表示空闲资源不足，等待
系统尝试将资源分配给进程P_i,并修改以下值

Available[j] = Available[j] - Requesti[j]

Allocation[i,j] = Allocation[i,j] + Requesti[j]

Need[i,j] = Need[i,j] - Requesti[j]

检查分配后系统是否处于安全状态，若是则正式分配，否则撤销第3步，进程P_i等待
1. 定义一个工作向量Work[i,j]，表示系统可提供给进程继续执行的各类资源数目，初始值为来自Available
2. 依次尝试查找是否有进程的Need[i,j]≤Work[i,j],说人话就是现在剩下的还够不够分配给一个进程
3. 当进程执行完成后，回收资源，加回Work
4. 一直循环ii、iii，看看到最后够不够
5. 够就安全，期间有发生不够分配，就不安全

被绕晕了?举个例子: