操作系统考研大纲解读3.pdf

《操作系统考研大纲解读3.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
5.死锁检测和解除
系统资源分配图
死锁定理
解除的方法二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
5.死锁检测和解除
系统资源分配图：
系统死锁可以利用资源分配图描述。。资源分配图又。资源分配图又称进程—资源图，，是一个二元组，是一个二元组G=（V，E），其中中：中：
V是结点集，，被分成两个互斥的子集，被分成两个互斥的子集：：进程结点子集：进程结点子集P＝{p，p，…，p}，，资源结点子集，资源结点子集R＝｛r，r，…，12n12r｝。m
E是边集，，它连接着，它连接着P中的一个结点和R中的一个结点

2、，e＝是资源请求边，e＝是资源分配边。ijji
通常，，用圆圈代表一个进程，用圆圈代表一个进程，，用方框代表一类资，用方框代表一类资源源，源，，方框中的一个点代表一类资源中的一个资源，方框中的一个点代表一类资源中的一个资源。二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
5.死锁检测和解除
基于资源分配图的定义，，可以给出以下判断，可以给出以下判断：
如果资源分配图中未出现任何环，，则此时系统内，则此时系统内无死锁。
如果资源分配图中出现了环，，且此环中的每类资，且此环中的每类资源只有1个个，个，，则此时系统有环就有死锁，则此时系统有环就有死锁。。

3、此时环。此时环是系统死锁的充要条件。
如果资源分配图中出现了环，，且此环中的每类资，且此环中的每类资源个数不全为1，，则环的存在只是死锁的必要条，则环的存在只是死锁的必要条件件。件。二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
5.死锁检测和解除
将资源分配图简化可以检测系统状态S是否为死锁状态，方法如下：
在资源分配图中，找出一个既不阻塞又非孤立的进程结点p，进程p获得了它所需要的全部资源，能运行完成然后释ii放所有资源。这相当于消去p的所有请求边和分配边，使之i成为孤立结点。
进程pi释放资源后，可以唤醒因等待这些资源而阻塞的进程，从而可能使原来阻塞的进程变为非

4、阻塞进程。
在进行一系列化简后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能使该图完全化简，则称该图是不可完全简化的。二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
5.死锁检测和解除
可以证明：：所有的简化顺序将得到相同的不：所有的简化顺序将得到相同的不可简化图。
S为死锁状态的条件是当且仅当S状态的资源分配图是不可完全简化的。。该条件称为。该条件称为死锁定理。二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
5.死锁检测和解除
通过系统的检测机构及时地检测出死锁的发生，，然后采取某种措施解除死锁，然后采取某种措施解除死

5、锁。
特点：：死锁检测和解除可使系统获得较：死锁检测和解除可使系统获得较高的利用率，，但是实现难度最大，但是实现难度最大。二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
1)死锁检测算法中的数据结构
可利用资源向量Available：：表示：表示m类资源中每类资源的可用数目。
请求矩阵Request：：表示每个进程当前对各类资源：表示每个进程当前对各类资源的请求数目。
分配矩阵Allocation：：表示每个进程当前已分配的：表示每个进程当前已分配的资源数目。
工作向量Work：：表示系统当前可提供资源数：表示系统当前可提供资源数。
进程集合L：：记录当前已不占用资源

6、的进程：记录当前已不占用资源的进程。二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
2)死锁检测的算法Work=Available;L=

7、Allocation=0∩Request=0>iiiforallL∉∉∉Ldoi{if（Request≤Work）i{Work=Work+Allocation;iL=L∪L;i}}deadlock=¬¬¬(L==)12n二二、二、、进程管理、进程管理（（四（四四）四））死锁）死锁
3)死锁解除
一旦检测出系统中出现了死锁，，就应将陷入死锁的，就应将陷入死锁的进程从死锁状态中解脱出来。。死锁的解除实质上就。死锁的解

8、除实质上就是如何让释放资源的进程能够继续运行。。常用的死。常用的死锁解除方法有两种：
资源剥夺法：：当发现死锁后：当发现死锁后，，从其他进程那里剥夺足够，从其他进程那里剥夺足够数量的资源给死锁进程，，以解除死锁状态，以解除死锁状态。
撤消进程法：：最简单的方法是撤消全部死锁进程：最简单的方法是撤消全部死锁进程，，使系，使系统恢复到正常状态。。但这种做法付出的代价太大。但这种做法付出的代价太大。。另一。另一方法是按照某种顺序逐个撤消死锁进程，，直到有足够的，直到有足够的