资源的分类
1.可重用性资源/消耗性资源
1）每个可重用性资源中的单元只能分配给一个进程使用；
请求资源-》使用资源-》释放资源；
资源中的单元数目相对固定，进程在运行期间既不能创建也不能删除它；
通过系统调用实现，设备：request/release 文件open/close 需互斥访问的资源wait/signal
2)可消耗性资源又称为临时性资源，在进程运行期间，由进程动态的创建与消耗；
单元数目在运行过程中不断变化；
生产者创建的可消耗性资源的单元放到缓冲区中；
消费者那走之后就不还了；
最典型的可消耗性资源就是用于进程间通信的消息。
2.可抢占性资源和不可抢占性资源
1）可抢占，比如CPU和贮存，这类资源不会引起死锁。
2）不可抢占，不能强行收回，只能在进程用完后自行释放。
死锁，饥饿，死循环三者的区别
死锁1-竞争不可抢占性资源引起死锁
箭头从进程指向资源表示请求，从资源指向进程表示已分配给
形成了一个环路，说明已进入死锁状态
死锁2-竞争可消耗资源引起死锁
比如消息（等待一条永远不会发出的消息）
死锁3-进程推进顺序不当引起死锁
死锁的定义：
一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件。
产生死锁的必要条件：
1）互斥条件
2）请求和保持条件
进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不妨。（重点在于虽然阻塞了，但不释放手里的资源！）
3）不可抢占条件
4）循环等待条件
注意发生死锁时一定有循环等待，但发生循环等待时未必死锁。
处理死锁的方法
1.预防死锁
2.避免死锁
3.检测死锁
4.解除死锁
1到4对死锁的防范程度逐渐减弱，但对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度下降（即并发程度提高）
预防死锁
1.破坏“请求和保持”条件
当一个进程在请求资源时，它不能持有不可抢占资源。
1）第一种协议
所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。破坏“请求”条件
缺点：资源被严重浪费（因为并不是整个运行过程都要用某个资源）；使进程经常发生饥饿现象。
2）第二种协议
允许一个进程只获得运行初期所需资源后就开始运行，运行过程中再逐步释放已分配给自己的，且已用毕的全部资源，然后再请求新的所需资源。
2.破坏“不可抢占”条件
当一个已经保持了某些不可抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源。
实现起来复杂，代价大，比如CD刻录机被抢占会造成进程前一段工作的失效，反复的申请与释放会增加系统开销，降低系统吞吐量，还可能会导致饥饿。
3.破坏“循环等待”条件
R=(R1,R2,R3,...,Rm)为资源类型的集合
用F(Ri)给每类资源分配一个编号
一个进程在开始时，可以请求某类资源Ri的单元，以后，当且仅当F(Rj)>F(Ri)时，进程才可以请求Rj的单元。即每个进程必须按编号递增的顺序请求资源。
如果需要多个同编号资源单元，则必须一起请求。
若要申请编号低的，必须先把编号高的释放。
任一时刻总有一个进程持有的资源编号最大，那这个进程后序的申请过程肯定是畅通无阻的。
这样就不可能出现环路。
通常根据大多数进程需要资源的先后顺序来确定序号。输入设备用较低的序号，输出设备用较高的序号。
缺点：不方便增加新设备，进程使用资源的顺序可能和编号递增顺序不一样会造成资源浪费，编程麻烦
避免死锁
在资源动态分配过程中，防止系统进入不安全状态。
在资源分配之前要计算安全性。
银行家算法Dijkstra
MAX二维矩阵，Allocation二维矩阵，Need二维矩阵，Available一维数组，Request一维数组
注意如果系统处于安全状态就一定不会发生死锁，但进入不安全状态就可能发生死锁（可能，因为没有进程发出申请的话倒也不会进入死锁状态），但发生死锁时一定是在不安全状态。
死锁的检测与解除
系统中存有有关资源的请求和分配信息，并提供一种算法，利用这些信息来检查系统是否已经进行死锁状态。
S状态的资源分配图G=(N, E)
N：进程结点P={P1，P2，...，Pn}∪资源结点R={R1，R2，...，Rn}
E中的边表示分配与请求，P->R请求，R->P分配（一条边代表请求或分配一个资源）分配边应始于方框中的一个点
通过简化分配图来检测S状态是否为死锁状态
找一个既不阻塞也不独立的Pi，执行Pi并释放资源，即删掉与它相关的所有边变成孤立点（感觉原理上有点像银行家算法）
-》依次消除与不阻塞进程相连的边
若能使所有进程结点都变成孤立的，则称该图是可简化的。
S为死锁状态的充分条件（死锁定理）：当且仅当S状态的资源分配图是不可完全简化的。
化简完后，还连着边的那些进程就是死锁进程。
死锁的解除
注意这些操作都是针对死锁进程的。
化简完后，还连着边的那些进程就是死锁进程。
1.抢占资源
2.终止（或撤销）进程
终止进程的方法
1.终止所有死锁进程
2.逐个终止进程
每终止一个进程都要用死锁检测算法确定系统死锁是否已被解除
选择终止进程的策略最主要依据是，为死锁解除所付出的代价最小。
付出代价最小的死锁解除算法（没看懂P118）
一种算法类似于动态规划地去选择终止哪个进程
一种是类似于贪心地选择
看书上的那个图感觉第一种是构造整个树枚举所有情况然后找到最小的，而第二种第一层找到最小的再从最小的那个结点开始往下找最小的。
网友评论