操作系统教程第十周

本文格式为Word版，下载可任意编辑——操作系统教程第十周3.6死锁

教学内容：

3.6.4死锁的避免(△□)3.6.5死锁的检测和解除

教学时数：

2学时

教学进程：

3.6.4死锁的避免

银行家算法

银行家拥有一笔周转资金,客户要求分期贷款，假使客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款,银行家应提防的贷款，防止出现坏帐。

用银行家算法避免死锁

操作系统（银行家）

操作系统管理的资源(周转资金)进程（要求贷款的客户）

单种资源的银行家算法

进程PQR系统拥有某资源10个已有资源数422还需资源数427对每个请求进行检查，是否会导致担忧全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。假使所有投资最终都被收回，则该状态是安全的，最初的请求可以批准.

4个客户每个都有一个贷款额度

一个状态被称为是安全的

条件是存在一个状态序列能够使所有的客户均得到其所有的贷款。

上图所示状态是安全的，以使Marvin运行终止，释放所有的4个单位资金。这样下去便可满足Suzanne或Barbara的请求。

担忧全的状态

考虑给Barbara另一个她申请的资源，则得到的状态是担忧全的。

假使突然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。

多种资源的银行家算法

总的资源E、已分派资源P、剩余资源A

查找右边矩阵是否有一行，其未被满足的设备数均小于或等于向量A。假使找不到，系统将死锁，任何进程都无法运行终止

若找到这样一行，可以假设它获得所需的资源并运行终止，将该进程标记为终止，并将资源加到向量A上重复以上两步，直到所有进程都标记为终止，则状态是安全的，否则将发生死锁

资源轨迹图

两阶段上锁算法

第一阶段，进程试图将其所需全部记录加锁，一次锁一个记录若成功，则数据进行更新并解锁

若有些记录已被上锁，则它将已上锁的记录解锁并重新开始执行

银行家算法的数据结构

考虑一个系统有n个进程和m种不同类型的资源,现定义包含以下向量和矩阵的数据结构：?系统每类资源总数--该m个元素的向量为系统中每类资源的数量Resource=(R1,R2,?,Rm)

?每类资源未分派数量--该m个元素的向量为系统中每类资源尚可供分派的数量Avilable=(V1,V2,?,Vm)

最大需求矩阵--每个进程对每类资源的最大需求量,Cij表示进程Pi需Rj类资源最大数

?C11?C?21Claim????????Cn1C12C22??Cn2????A12A22??An2????????C1m?C2m???????Cnm??????A1n?A2n???????Anm??分派矩阵—表示进程当前已分得的资源数,Aij表示进程Pi已分到Rj类资源的个数

?A11?A?21Allocation????????An1

银行家算法中

以下关系式确保成立

?Ri=Vi+∑Aki对i=1,..,m,k=1,..,n;表示所有资源要么已被分派、要么尚可分派?Cki≤Rj对i=1,..,m,k=1,..,n;表示进程申请资源数不能超过系统拥有的资源总数

?Aki≤Cki对i=1,..,m,k=1,..,n;表示进程申请任何类资源数不能超过声明的最大资源需求数

一种死锁避免策略

系统中若要启动一个新进程工作,其对资源Ri的需求仅当满足以下不等式：Ri≥C(n+1)I+∑Cki对i=1,..,m,k=1,..,n;

即应满足当前系统中所有进程对资源Ri的最大资源需求数加上启动的新进程的最大资源需求数不超过系统拥有的最大数。

系统安全性定义

在时刻T0系统是安全的,仅当存在一个进程序列P1,..,Pn,对进程Pk(k=1,..,n)满足公式Cki-Aki≤Availablei+∑Aji,j=1,..,k;k=1,..,n;i=1,..,m

该序列称安全序列,公式左边表示进程Pk尚缺少的各类资源;Availablei是T0时刻系统尚可

用于分派且为Pk所想要的那类资源数;∑Aji表示排在进程Pk之前的所有进程占用的Pk所需要的资源的总数。

实例说明系统所处的安全或担忧全状态

假使系统中共有五个进程和A、B、C三类资源;A类资源共有10个,B类资源共有5个,C类资源共有7个。

在时刻T0,系统目前资源分派状况如下：

processAllocationClaimAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433

每个进程目前还需资源为Cki-AkiprocessCki-Aki

ABCP0743P1122P2600P3011P4431

进程P1申请资源request1=(1,0,2),检查request1≤Available、比较(1,0,2)≤(3,3,2),结果满足条件,试分派,得到新状态：

processAllocationClaimAvailableABCABCABCP0010743230P1302020P2302600P3211011P400243

判定新状态是否安全?可执行安全性测试算法，找到一个进程序列{P1,P3,P4,P0,P2}能满足安全性条件,可正式把资源分派给进程P1;

系统若处在下面状态中,进程P4请求资源(3,3,0),由于可用资源不足,申请被系统拒绝;此时,系统能满足进程P0的资源请求(0,2,0);但可看出系统已处于担忧全状态了。

银行家算法的基本思想

系统中的所有进程进入进程集合,在安全状态下系统收到进程的资源请求后,先把资源试探性分派给它。

系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。

把这个进程从集合中去掉,系统的剩余资源更多了,反复执行上述步骤。

最终,检查进程集合,若为空说明本次申请可行,系统处于安全状态,可实施本次分派;否则,有进程执行不完，系统处于担忧全状态,本次资源分派暂不实施,让申请进程等待。

银行家算法的程序及简短说明

typestate=record/*全局数据结构*/resource,available:array[0?m-1]ofinteger;claim,allocated:array[0?n-1,0?m-1]ofinteger;end/*资源分派算法*/

ifalloc[i,*]+request[*]>claim[i,*]then/*申请量超过最大需求量*/else

ifrequest[*]>available[*]thenelse/*模拟分派*/end;

ifsafe(newstate)thenelse

endend

functionsafe(state:s):boolean;/*banker’salgorithm*/varcurrentavail:array{0?m-1}ofinteger;rest:setofprocess;begin

currentavail:=available;rest:={allprocess};possible:=true;whilepossibledo

findaPkinrestsuchthat

claim[k,*]-alloc[k,*]≤currentavail;

iffoundthencurrentavail:=currentavail+allocation[k,*];rest:=rest-[Pk];else

possible:=false;endend;

safe:=(rest=null)e