死锁
死锁
什么是死锁
死锁是指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。
也就是说，一组进程中，每个进程都无限等待被改组进程中另一进程锁占有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。
关于死锁的一些特征
-参与死锁的进程最少是两个
-参与死锁的进程至少有两个已经占有的资源
-参与死锁的所有进程都在等待资源（参与死锁的进程，而非系统所有进程）
-参与死锁的进程是当前系统中所有进程的子集（不仅仅是进程间，进程内也会死锁）
资源又分为什么呢
永久性资源（可再用资源）
可抢占资源：CPU
不可抢占资源:打印机
临时性资源（消耗性资源）
信号量，中断信号，同步信号等
死锁和死循环的区别和联系
1.死锁是偶然的（error），死循环是必然的（feature）
2.死锁处于阻塞状态，死循环一直在占用CPU运行
3.死锁是由于操作系统并发执行，进程之间对互斥资源共享等引起的，与操作系统的管理可控制有关；死循环是程序员自己写的，有可能是feature，也有可能就是单纯的bug
死锁与饥饿的区别和联系
-饥饿的进程是长时间得不到CPU，而其他所需资源均已获得，一旦得到CPU就可以立即运行；而死锁除了CPU之外还有其他资源也为得到（正在被占用），即使把CPU分配给它也不能够执行。
-死锁进程至少有两个，而饥饿仅仅是因为每页调度它执行，所有可能只有它一个
产生死锁的直接原因（充分条件）
1.系统资源的竞争（竞争不可剥夺资源）
2.进程推进顺序非法（例如信号量使用不当，导致两个进程死锁）
产生死锁的必要条件
1.互斥条件
-进程对锁分配到的资源进行排它性的使用
2.不剥夺条件
-进程已至少保持了一个资源，但又提出了新的资源请求，而该资源又被其他进程占有
3.请求和保持条件
-进程已获得的资源在未使用完之前不能被剥夺
4.循环等待条件
-在发生死锁时，必然存在一个进程——资源循环等待的环形链
为什么循环等待是必要条件而不是充要条件？
假如这个循环的S环节需要资源A，而系统有两个资源A，一个正在被S+1占用，另一个正在被一个不属于该循环的进程K占用，这个时候，如果K释放了它锁占用的资源A，死锁就可以解开了。所以不是充分条件。
死锁的处理策咯
分三类：预防死锁，避免死锁，检测及解除死锁
预防死锁（破坏这四个必要条件即可）
1.破坏互斥条件
不可行，因为有很多东西确实是没办法同时访问的，例如打印机
2.破坏不剥夺条件
当某个进程S所需要的资源A正在被进程K所占有时，强行让K让出资源A
缺点：会导致K之前的工作失效（想象一下，你正在打印一幅画，打印到一半有一个新进程来了，他想打印点文件，于是正在打印一半的画突然往下打印文字了..。）
3.破坏请求和保持条件
所有进程在开始运行之前必须一次性申请整个运行过程所需的全部资源
优点：简单、安全
缺点：资源浪费严重，可能导致饥饿
4.破坏循环等待条件
给资源和进程排好序，申请资源必须按照序号进行
确定：存在资源浪费，也不利于新的设备的增加
死锁避免
系统安全状态：系统能按某种（也就是存在）进程推动顺序，为每个进程分配所需资源，直到满足每个进程对资源的最大需求，使每个进程都可以顺序地完成。则处于安全状态。
不安全状态：无法找到一个安全序列，则处于非安全状态（并不等价于死锁状态）。不安全状态只是说按照当前的情况，可能会导致死锁，但是如果突然某个进程释放了大量资源，就会解除不安全状态。
银行家算法的数据结构描述
1.可利用资源Avaliable
含有m个元素的数组，每一个元素代表一类可用资源的数目。Available[j]=K，代表Available[j]资源有K个可用。（例如我Available[0]代表耳机，Available[1]代表鼠标，Available[2]代表键盘，Available[4]代表显示器，若Available[2]=3，代表我系统中有3个可用的键盘资源）
2.最大需求矩阵Max
一个nXm的矩阵，定义了系统中n个进程中的每一个ijnc对m类资源的最大需求。Max[i,j]=K，代表进程i需要j资源的最大数目为K。
3.分配矩阵Allocation
和Max矩阵类似，只不过数量代表以及给的资源数
4.需求矩阵Need
Need[i,j]=Max[i,j]-Allocation[i,j]
4.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
若安全，才正式将资源分配给Pi，否则，本次试探分配作废，回复原理的状态，让Pi等待
安全性算法
1.设置两个向量
工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available
Finish:表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=False；当有足够资源分配给进程时，在令Finish[i]=true
2.从进程集合中找到一个能满足下述条件的进程
1，Dinish[i]=false 2.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都满足，则表示系统处于安全抓个年头，否则，系统处于不安全状态。
死锁的检测与解除
死锁的检测：允许死锁发生，操作系统不断监听系统进展情况，判断死锁是否发生
一旦死锁发生，则采取专门的措施，解除死锁并以最小的代价回复操作系统允许
检测的时机：当进程等待时检测死锁或定时检测（但是无论如何系统开销都会因此增大）
资源分配图：用有向图描述进程的死锁，系统中各类资源的分配和各个进程对资源请求的状态
方框表示资源
方框中圆点表示资源实例
用圆圈加箭头名表示进程
资源实例指向进程的有向边表示分配边
进程指向资源类的有向边表示申请边
死锁定理：如果资源分配图中没有环路，则系统中没有死锁，如过存在环路，则可能存在死锁。
如果每个资源类中只包含一个资源实例，则环路是死锁存在的充要条件。
我们在分析资源分配图的时候要进行适当的化简，如果可以化简到只剩下资源和进程的样子，说明不存在死锁，反之，则说明存在死锁
死锁的解除
一般方法是：重新启动、撤销进程、剥夺资源、进程回退
