操作系统--死锁

2023-12-27 11:01:09

死锁

死锁定义

死锁是由于两个或以上的线程互相持有对方需要的资源，导致这些线程处于等待状态，无法执行
- 想到了罪犯绑架人质，要求其家属给钱才放人，然而家属这边要求先放人再给钱，这样一方不给钱，一方不放人，双方都得不到满足
- 一个例子:如果此时有一个线程A，按照先锁a再获得锁b的的顺序获得锁，而在此同时又有另外一个线程B，按照先锁b再锁a的顺序获得锁，图源网络

死锁产生原因

竞争资源
- 竞争不可抢占性资源
  - 系统中的资源可以分为两类：可剥夺资源和不可剥夺资源
  - 可剥夺资源：是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，CPU和主存均属于可剥夺性资源
  - 不可剥夺资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等
- 竞争临时资源
  - 临时资源：指由一个进程产生，被另一个进程使用，短时间后便无用的资源，故也称为消耗性资源，如硬件中断、信号、消息、缓冲区内的消息等
  - 例如，系统中拥有三个进程P1、P2和P3，m1、m2、m3是3可消耗资源。进程P1一方面产生消息m1，将其发送给P2，另一方面要从P3接收消息m3。而进程P2一方面产生消息m2，将其发送给P3，另一方面要从P1接收消息m1。类似的，进程P3一方面产生消息m3，将其发送给P1，另一方面要从P2接收消息m2，如果三个进程都先发送自己产生的消息后接收别人发来的消息，则可以顺利的运行下去不会产生死锁，但要是三个进程都先接收别人的消息而不产生消息则会永远等待下去，产生死锁。
进程间推进顺序不当（pv操作顺序不当）
- 先来看推进顺序合法的情况：当进程P1和P2并发执行时，如果按照下述顺序推进：P1：Request（R1）； P1：Request（R2）； P1: Relese（R1）；P1: Relese（R2）； P2：Request（R2）； P2：Request（R1）； P2: Relese（R2）；P2: Relese（R1）；这两个进程便可顺利完成，这种不会引起进程死锁的推进顺序是合法的
- 当进程间推进顺序不当：若P1保持了资源R1,P2保持了资源R2，系统处于不安全状态，因为这两个进程再向前推进，便可能发生死锁。例如，当P1运行到P1：Request（R2）时，将因R2已被P2占用而阻塞；当P2运行到P2：Request（R1）时，也将因R1已被P1占用而阻塞，于是发生进程死锁

死锁产生的四个必要条件

互斥：任意时刻只能有一个进程使用资源，其他进程若申请一个资源，而该资源被另一进程占有时，则申请者等待直到资源被占有者释放
不可剥夺(不可抢占)：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放
请求和保持：一个线程对请求被占有资源发生阻塞时，对已经获得的资源不释放
循环等待：在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源（循环等待条件并非如此严格，只要存在一个处于等待状态的进程集合{Pl, P2, …, pn}，**其中Pi等待的资源被P(i+1)占有（i=0, 1, …, n-1)**即可）

死锁处理 --> 静态预防动态避免动态检测及解除

死锁和防御的区别：死锁预防是设法至少破坏产生死锁的四个必要条件之一,严格的防止死锁的出现,而死锁避免则不那么严格的限制产生死锁的必要条件的存在,因为即使死锁的必要条件存在,也不一定发生死锁。死锁避免是在系统运行过程中注意避免死锁的最终发生
破坏死锁产生的四个必要条件来预防死锁（没有一个操作系统可以实现）
- 破坏互斥，一般来说互斥条件无法破坏，所以在死锁预防里主要是破坏其他几个必要条件（互斥条件不能被破坏，否则会造成结果的不可再现性）
- 破坏不可剥夺–>允许对资源进行抢夺
  - 若占有一些资源的一个进程进一步申请资源被拒绝，则该进程必须释放它最初占有的资源，如果有必要，可再次请求这些资源和另外的资源
  - 如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。只有在任意两个进程的优先级都不相同的条件下，这种方法才能预防死锁
- 破坏请求和保持
  - 资源一次性分配：创建进程时，要求它申请所需的全部资源，系统或满足其所有要求，或什么也不给它
  - 要求每个进程提出新的资源申请前，释放它所占有的资源
- 破坏循环等待
  - 资源统一编号，将系统中所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出
避免死锁
- 在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生
- 死锁避免算法：银行家算法
检测死锁
- 为每个进程和每个资源指定唯一编号
- 建立资源分配表，记录各进程与占用资源的关系
- 建立进程等待表，记录各进程与申请资源之间的关系
解除死锁
- 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态
- 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行
- 进程回退法：让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点