欢迎来到天天文库
浏览记录
ID:52516427
大小:643.88 KB
页数:77页
时间:2020-03-28
《操作系统考研大纲解读3.pdf》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、二二、二、、进程管理、进程管理((四(四四)四))死锁)死锁5.死锁检测和解除系统资源分配图死锁定理解除的方法二二、二、、进程管理、进程管理((四(四四)四))死锁)死锁5.死锁检测和解除系统资源分配图:系统死锁可以利用资源分配图描述。。资源分配图又。资源分配图又称进程—资源图,,是一个二元组,是一个二元组G=(V,E),其中中:中:V是结点集,,被分成两个互斥的子集,被分成两个互斥的子集::进程结点子集:进程结点子集P={p,p,…,p},,资源结点子集,资源结点子集R={r,r,…,12n12r}。mE是边集,,它连接着,它连接着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、除实质上就是如何让释放资源的进程能够继续运行。。常用的死。常用的死锁解除方法有两种:资源剥夺法::当发现死锁后:当发现死锁后,,从其他进程那里剥夺足够,从其他进程那里剥夺足够数量的资源给死锁进程,,以解除死锁状态,以解除死锁状态。撤消进程法::最简单的方法是撤消全部死锁进程:最简单的方法是撤消全部死锁进程,,使系,使系统恢复到正常状态。。但这种做法付出的代价太大。但这种做法付出的代价太大。。另一。另一方法是按照某种顺序逐个撤消死锁进程,,直到有足够的,直到有足够的
7、Allocation=0∩Request=0>iiiforallL∉∉∉Ldoi{if(Request≤Work)i{Work=Work+Allocation;iL=L∪L;i}}deadlock=¬¬¬(L==
)12n二二、二、、进程管理、进程管理((四(四四)四))死锁)死锁3)死锁解除一旦检测出系统中出现了死锁,,就应将陷入死锁的,就应将陷入死锁的进程从死锁状态中解脱出来。。死锁的解除实质上就。死锁的解
8、除实质上就是如何让释放资源的进程能够继续运行。。常用的死。常用的死锁解除方法有两种:资源剥夺法::当发现死锁后:当发现死锁后,,从其他进程那里剥夺足够,从其他进程那里剥夺足够数量的资源给死锁进程,,以解除死锁状态,以解除死锁状态。撤消进程法::最简单的方法是撤消全部死锁进程:最简单的方法是撤消全部死锁进程,,使系,使系统恢复到正常状态。。但这种做法付出的代价太大。但这种做法付出的代价太大。。另一。另一方法是按照某种顺序逐个撤消死锁进程,,直到有足够的,直到有足够的
此文档下载收益归作者所有