操作系统|进程死锁以及处理 linux|rabbitmq

文章目录

前言
一、死锁的定义
- 1.死锁的引出
- 2.死锁产生原因
二、死锁策略
- 1.死锁预防
- 2.死锁避免
- 3.银行家算法
- 4.死锁检测与恢复
- 5.死锁忽略
总结

前言提示：以下是本篇文章正文内容
一、死锁的定义 1.死锁的引出死锁 (deallocks)：是指两个或两个以上的进程（线程）在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程（线程）称为死锁进程（线程）
生产者 --消费者问题

//用文件定义共享缓冲区 int fd = open("buffer.txt"); write(fd, 0, sizeof(int)); //写in write(fd, 0, sizeof(int)); //写out//信号量的定义和初始化 semaphore full = 0; //生产的产品的个数 semaphore empty = BUFFER_SIZE; //空闲缓冲区的个数 semaphore mutex = 1; //互斥信号量//生产者 Producer(item) {P(empty); //生产者先判断缓存区个数 empty是否满了，empty == 0，阻塞 P(mutex); //操作文件前，用mutex防止其他进程操作该文件读入in，将item写到in的位置上 V(mutex); //使用完文件，释放文件资源 V(full); //生产者生产产品，增加full，消费者就可以消费了 }//消费者 Consumer() {P(full); //当full == 0,缓冲区空了，阻塞 P(mutex); 读入out，从文件中的out位置读出到item，打印item; V(mutex); V(empty); //消费者消耗产品，增加缓冲区个数，增加empty，生产者就可以继续生产了 }

这时不管是生产者还是消费者都是先调用P(empty)/P(full),然后再调用互斥信号量mutex，进程能正确的执行
但是如果我们将这两个先后顺序调换一下：

文章图片

在这里假设 mutex初值是1，empty初值是0，缓冲区取满了
在生产者中，P(mutex) 会把 mutex 变成 0，// P(empty) 会把 empty 变成 -1，生产者阻塞，然后消费者启动，P(mutex)，mutex是0，执行P(mutex)将mutex变成 -1，消费者阻塞，此时消费者和生产者都阻塞了
生产者要执行，需要把empty释放了，即消费者要执行 V(empty)，当前消费者卡在 P(mutex)，释放不了
消费者要执行，需要生产者把 mutex释放了，生产者要执行 V(metux)，生产者卡在上边的 P(empty)，也释放不了
生产者在P(empty)往下执行，依赖于消费者，消费者要往下执行，又依赖生产者P(empty)下边的指令，形成环路等待，死锁。
2.死锁产生原因原因：
(1)系统资源的竞争
系统资源的竞争导致系统资源不足，以及资源分配不当，导致死锁。
(2)进程运行推进顺序不合适
进程在运行过程中，请求和释放资源的顺序不当，会导致死锁。

文章图片

死锁的四个必要条件
1.互斥条件：
一个资源每次只能被一个进程使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
2.请求和保持条件：
一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源。
3.不可抢占条件：
别人已经占有了某项资源，不能因为自己也需要该资源，就去把别人的资源抢过来。
4.循环等待条件：
若干进程间形成首尾相接循环等待资源的关系

文章图片

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。
二、死锁策略死锁处理方法概述

1.死锁预防破坏死锁出现的条件，不要占有资源又申请其他资源2.死锁避免检测每个资源请求，如果造成死锁就拒绝3.死锁检测 + 恢复检测到死锁出现时，让一些进程回滚，让出资源4.死锁忽略好像没有出现死锁一样

1.死锁预防方法1：
在进程执行前，一次性申请所有需要的资源，不会占有资源再去申请其他资源

优点：简单易实施且安全。
缺点：因为某项资源不满足，进程无法启动，而其他已经满足了的资源也不会得到利用，严重降低了资源的利用率，造成资源浪费。使进程经常发生饥饿现象

**方法2：**对资源类型进行排序，资源申请必须按序进行，不会出现环路等待

缺点：仍会造成资源浪费

2.死锁避免在使用前进行判断，只允许不会产生死锁的进程申请资源。死锁的避免是利用额外的检验信息，在分配资源时判断是否会出现死锁，只在不会出现死锁的情况下才分配资源。
两种避免办法：

1、如果一个进程的请求会导致死锁，则不启动该进程
2、如果一个进程的增加资源请求会导致死锁，则拒绝该申请。

问题：

文章图片

上图含有5个进程：P0-P4
Allocation:占有的资源,以P1 为例，占用资源A3个，资源B0个，资源C2个
Need：需要的资源
Available：系统中剩余的资源
分析：
当前系统剩余资源：ABC = 230，给 P1，P1可以执行完，P1 执行完 Available ABC = 532，P3 可以执行，P3 执行完，Available ABC = 743
其他进程都可以执行…A 是安全序列
3.银行家算法银行家算法通过对进程需求、占有和系统拥有资源的实时统计，确保系统在分配给进程资源不会造成死锁才会给与分配

int Available[1..m]; //每种资源剩余数量 int Allocation[1..n, 1..m]; //已分配资源数量 int Need[1..n, 1..m]; //进程还需的各种资源数量 int Max[1..n, 1..m]; //进程总共需要的资源数量 int Work[1..m]; //工作向量 bool Finifh[1..n]; //进程是否结束Work = Available; Finifh[1..n] = false; while(true) {for(i = 1; i <= n; i++) {// Need[i] <= Work 这个任务是可以完成的 if(Finish[i] == false && Need[i] <= Work) {Work = Work + Allocation[i]; // Work 累加系统曾分配给 i 的资源 Finish[i] = true; break; } else {goto end; } } }End: for(i = 1; i <=n; i++) if(Finish[i] == false) return "deadlock";

相关数据结构：
可利用资源向量Available：用于表示系统里边各种资源剩余的数目。由于系统里边拥有的资源通常都是有很多种（假设有m种），所以，我们用一个有m个元素的数组来表示各种资源。数组元素的初始值为系统里边所配置的该类全部可用资源的数目，其数值随着该类资源的分配与回收动态地改变。
分配矩阵Allocation：顾名思义，就是用于表示已经分配给各个进程的各种资源的数目。也是一个nxm的矩阵。
需求矩阵Need：用于表示进程仍然需要的资源数目，用一个nxm的矩阵表示。系统可能没法一下就满足了某个进程的最大需求（通常进程对资源的最大需求也是只它在整个运行周期中需要的资源数目，并不是每一个时刻都需要这么多），于是，为了进程的执行能够向前推进，通常，系统会先分配个进程一部分资源保证进程能够执行起来。那么，进程的最大需求减去已经分配给进程的数目，就得到了进程仍然需要的资源数目了。
所以,根据该算法可以解决上面的问题

文章图片

其时间复杂度是 T(n) = O(m* n^2)，m是资源数，n是进程数
死锁避免的优点：

不需要死锁预防中的抢占和重新运行进程，并且比死锁预防的限制要少

死锁避免的缺点：

必须事先声明每个进程请求的最大资源量
考虑的进程必须无关的，也就是说，它们执行的顺序必须没有任何同步要求的限制
分配的资源数目必须是固定的
在占有资源时，进程不能退出

4.死锁检测与恢复定时检测或者是发现资源利用率低时检测
检测算法：

Finish[1..n] = false; if(Allocation[i] == 0) Finish[i]=true; ...//和Banker算法完全一样 for(i=1; i<=n; i++) if(Finish[i]==false) deadlock = deadlock + { i};

检测处问题，进程解锁: