用银行家算法拒绝死锁的例题

‘壹’ 避免死锁-----银行家算法详解

避免死锁策略旨在预防系统进入不安全状态，以防止死锁的发生，相较于预防死锁，其对资源分配的限制更宽松，旨在提升系统性能。

银行家算法由迪杰斯特拉为T.H.E系统设计，旨在避免在发放现金贷款时系统无法满足所有客户需要的情况。

算法通过四大数据结构实现：可利用资源向量、最大需求矩阵、分配矩阵和需求矩阵。其中，可利用资源向量动态反映系统中每类资源的可用数量；最大需求矩阵定义每个进程对各类资源的最大需求；分配矩阵记录已分配资源数量；需求矩阵表示进程尚需资源数量。

当新进程请求资源时，系统检查资源分配后是否会导致不安全状态。若资源充足且分配后系统仍安全，则进行分配；否则，进程等待。

安全性算法是银行家算法的一部分，用于检测资源分配后的系统状态。该算法创建工作向量和结束标志向量，从进程集合中选择一个满足条件的进程，分配所需资源并更新相关数据。若所有进程都可顺利运行，则系统安全，否则，系统不安全。

通过一个例子，我们可以了解银行家算法的执行过程。在这个例子中，我们检查了T0时刻的安全性，并模拟了进程P0请求资源的场景，分析了系统在不同状态下的行为。

总结，银行家算法是一种经典的避免死锁策略，通过限制相对宽松的资源分配，旨在提升系统性能。同时，安全性算法确保了系统在资源分配后保持安全状态。选择何种死锁处理方法应根据OS设计目的而定，没有绝对的优劣之分。

‘贰’ 银行家算法的算法实现

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
(3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 （1)设置两个工作向量Work=AVAILABLE;FINISH
(2)从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行（3)；否则，执行（4)
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
银行家算法流程图
算法（C语言实现） #include<STRING.H>#include<stdio.h>#include<stdlib.h>#include<CONIO.H>/*用到了getch()*/#defineM5/*进程数*/#defineN3/*资源数*/#defineFALSE0#defineTRUE1/*M个进程对N类资源最大资源需求量*/intMAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*系统可用资源数*/intAVAILABLE[N]={10,5,7};/*M个进程已分配到的N类数量*/intALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};/*M个进程已经得到N类资源的资源量*/intNEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*M个进程还需要N类资源的资源量*/intRequest[N]={0,0,0};voidmain(){inti=0,j=0;charflag;voidshowdata();voidchangdata(int);voidrstordata(int);intchkerr();showdata();enter:{printf(请输入需申请资源的进程号（从0到);printf(%d,M-1);printf(）:);scanf(%d,&i);}if(i<0||i>=M){printf(输入的进程号不存在，重新输入! );gotoenter;}err:{printf(请输入进程);printf(%d,i);printf(申请的资源数 );printf(类别:ABC );printf();for(j=0;j<N;j++){scanf(%d,&Request[j]);if(Request[j]>NEED[i][j]){printf(%d,i);printf(号进程);printf(申请的资源数>进程);printf(%d,i);printf(还需要);printf(%d,j);printf(类资源的资源量!申请不合理，出错!请重新选择! );gotoerr;}else{if(Request[j]>AVAILABLE[j]){printf(进程);printf(%d,i);printf(申请的资源数大于系统可用);printf(%d,j);printf(类资源的资源量!申请不合理，出错!请重新选择! );gotoerr;}}}}changdata(i);if(chkerr()){rstordata(i);showdata();}elseshowdata();printf( );printf(按'y'或'Y'键继续,否则退出 );flag=getch();if(flag=='y'||flag=='Y'){gotoenter;}else{exit(0);}}/*显示数组*/voidshowdata(){inti,j;printf(系统可用资源向量: );printf(***Available*** );printf(资源类别:ABC );printf(资源数目:);for(j=0;j<N;j++){printf(%d,AVAILABLE[j]);}printf( );printf( );printf(各进程还需要的资源量: );printf(******Need****** );printf(资源类别:ABC );for(i=0;i<M;i++){printf();printf(%d,i);printf(号进程:);for(j=0;j<N;j++){printf(%d,NEED[i][j]);}printf( );}printf( );printf(各进程已经得到的资源量: );printf(***Allocation*** );printf(资源类别:ABC );for(i=0;i<M;i++){printf();printf(%d,i);printf(号进程:);/*printf(: );*/for(j=0;j<N;j++){printf(%d,ALLOCATION[i][j]);}printf( );}printf( );}/*系统对进程请求响应，资源向量改变*/voidchangdata(intk){intj;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]-Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];NEED[k][j]=NEED[k][j]-Request[j];}}/*资源向量改变*/voidrstordata(intk){intj;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]+Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];NEED[k][j]=NEED[k][j]+Request[j];}}/*安全性检查函数*/intchkerr()//在假定分配资源的情况下检查系统的安全性{intWORK[N],FINISH[M],temp[M];//temp[]用来记录进程安全执行的顺序inti,j,m,k=0,count;for(i=0;i<M;i++)FINISH[i]=FALSE;for(j=0;j<N;j++)WORK[j]=AVAILABLE[j];//把可利用资源数赋给WORK[]for(i=0;i<M;i++){count=0;for(j=0;j<N;j++)if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j])count++;if(count==N)//当进程各类资源都满足NEED<=WORK时{for(m=0;m<N;m++)WORK[m]=WORK[m]+ALLOCATION[i][m];FINISH[i]=TRUE;temp[k]=i;//记录下满足条件的进程k++;i=-1;}}for(i=0;i<M;i++)if(FINISH[i]==FALSE){printf(系统不安全!!!本次资源申请不成功!!! );return1;}printf( );printf(经安全性检查，系统安全，本次分配成功。 );printf( );printf(本次安全序列：);for(i=0;i<M;i++)//打印安全系统的进程调用顺序{printf(进程);printf(%d,temp[i]);if(i<M-1)printf(->);}printf( );return0;}

‘叁’ 银行家算法

银行家算法是一种预防死锁的算法。具体算法步骤可以参考网络： 银行家算法

例子 ：某系统有A、B、C、D , 4类资源共5个进程（P0、P1、P2、P3、P4）共享，各进程对资源的需求和分配情况如下表所示。

输入进程的数目:5
输入资源的种类:4
输入每个进程最多所需的各类资源数:
P0 : 0 0 1 2
P1 : 1 7 5 0
P2 : 2 3 5 6
P3 : 0 6 5 2
P4 : 0 6 5 6
输入每个进程已经分配的各类资源数:
P0 : 0 0 1 2
P1 : 1 0 0 0
P2 : 1 3 5 4
P3 : 0 6 3 2
P4 : 0 0 1 4
请输入各个资源现有的数目:
1 5 2 0
当前系统安全!
系统安全序列是:
P0->P2->P1->P3->P4
输入要申请资源的进程号(0-4)：1
输入进程所请求的各资源的数量:0 4 2 0
系统安全!
系统安全序列是:
P0->P2->P1->P3->P4
同意分配请求!

系统可用的资源数为 : 1 1 0 0
各进程还需要的资源量:
进程 P0 : 0 0 0 0
进程 P1 : 0 3 3 0
进程 P2 : 1 0 0 2
进程 P3 : 0 0 2 0
进程 P4 : 0 6 4 2

各进程已经得到的资源量:
进程 P0 : 0 0 1 2
进程 P1 : 1 4 2 0
进程 P2 : 1 3 5 4
进程 P3 : 0 6 3 2
进程 P4 : 0 0 1 4

是否再次请求分配？是请按Y/y，否请按N/n:
N

‘肆’ 操作系统(死锁避免)----银行家算法解题

死锁：是指两个以上的进程都因要求对方已经占有的资源，导致无法运行下去的现象，死锁是系统的一种出错状态，不仅浪费大量的系统资源，甚至会导纤贺余致整个系统的崩溃，所以死锁是尽量预防和避免的。

产生死锁的四个条件：

死锁的处理

银行家算法是死锁避免的重要算法。

银行家算毁滚法：资源==钱；收回资源==收回贷款；收不回资源==不会放贷；

例题：假设系统中有三类互斥资源R1，R2，R3。可用资源分别是9,8,5.在T0时刻系统有P1，P2，P3，P4，P5五个进程，这些进程最大的需求和已分配的资源如下所示，如果按_执行，那么系统的状态是安全的。

解：第一步：根据可用资源，可以求得剩余资源。

R1=9-(1+2+2+1+1)=2

R2=8-(2+1+1+2+1)=1

R3=5-(1+1+0+0+3)=0

第二拍纳步：根据剩余资源求得还需要的资源数。

公式：还需资源（Need）=最大需求（Max）-已分配资源（Allocation）。

第三部，根据剩余资源数，求出安全序列。

根据剩余资源可得，p2可以执行（条件：每个值都必须≦剩余资源）

由此可见安全序列为P2-->p4-->p5-->p1-->p3。

其实安全序列不是唯一的，这是为什么呢？

大家可以看出来，现有资源要大于需要资源的情况下是有多种选择的，因此安全序列不唯一。

‘伍’ 怎样用C语言描述操作系统里的死锁算法谢谢。

利用银行家算法避免死锁 . 银行家算法 设Requesti是进程Pi的请求向量，如果Requesti〔j〕=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：� (1) 如果Requesti〔j〕≤Need〔i,j〕，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果Requesti〔j〕≤Available〔j〕，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 (3) 系统试探虚清着把资源分配给进程Pi，并修改下面数据结构中的数值：� Available〔j〕∶=Available〔j〕-Requesti〔j〕;� Allocation〔i,j〕∶=Allocation〔i,j〕+Requesti〔j〕;� Need〔i,j〕∶=Need〔i,j〕-Requesti〔j〕;� (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：� Available〔j〕∶=Available〔j〕-Requesti〔j〕;� Allocation〔i,j〕∶=Allocation〔i,j〕+Requesti〔j〕;� Need〔i,j〕∶=Need〔i,j〕-Requesti〔j〕;� (4) 系统执行安全性算法，检册散查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：� Available〔j〕∶=Available〔j〕-Requesti〔j〕;� Allocation〔i,j〕∶=Allocation〔i,j〕+Requesti〔j〕;� Need〔i,j〕∶=Need〔差姿前i,j〕-Requesti〔j〕;� (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

‘陆’ 什么是死锁，怎样引入死锁

1.死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。
2.产生死锁的原因：
（1）竞争不可抢占性资源。
（2）竞争可消耗资源。
当系统中供多个进程共享的资源如打印机，公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。12

（3）进程推进顺序不当。
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。12

如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。
一个线程也可引起死锁。12

3.产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求和保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不可抢占条件:进程已获得的资源，在末使用完之前，不能强行剥夺，只能在进程使用完时由自己释放。
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。因此可以写下如下的预防死锁的方法。
4.避免死锁的方法：
（1）破坏“互斥”条件:就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他三个必要条件，而不去涉及破坏“互斥”条件。
（2）破坏“请求和保持”条件:在系统中不允许进程在已获得某种资源的情况下，申请其他资源。即要想出一个办法，阻止进程在持有资源的同时申请其他资源。
方法一：所有进程在运行之前，必须一次性地申请在整个运行过程中所需的全部资源。这样，该进程在整个运行期间，便不会再提出资源请求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件。
该方法优点：简单、易行且安全。
缺点：a.资源被严重浪费，严重恶化了资源的利用率。
b.使进程经常会发生饥饿现象。12

方法二：要求每个进程提出新的资源申请前，释放它所占有的资源。这样，一个进程在需要资源S时，须先把它先前占有的资源R释放掉，然后才能提出对S的申请，即使它可能很快又要用到资源R。
（3）破坏“不可抢占”条件：允许对资源实行抢夺。
方法一：如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占有的资源，如果有必要，可再次请求这些资源和另外的资源。
方法二：如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。只有在任意两个进程的优先级都不相同的条件下，该方法才能预防死锁。
（4）破坏“循环等待”条件：将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。这样做就能保证系统不出现死锁。
利用银行家算法避免死锁：
银行家算法:
设进程i提出请求Request[j]，则银行家算法按如下规则进行判断。
(1) 如果Request[j]≤Need[i,j]，则转向（2），否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Request[j]≤Available[j]，则转向（3）；否则表示尚无足够资源，Pi需等待。
(3) 假设进程i的申请已获批准，于是修改系统状态：
Available[j]=Available[j]-Request[i]
Allocation[i,j]=Allocation[i,j]+Request[j]
Need[i,j]=Need[i,j]-Request[j]
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
安全性算法：
(1) 设置两个工作向量Work=Available；Finish[i]=False
(2) 从进程集合中找到一个满足下述条件的进程，
Finish [i]=False;

Need[i,j]≤Work[j];

如找到，执行(3)；否则，执行(4)123456

(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work[j]=Work[j]+Allocation[i,j];

Finish[i]=True;

Go to step 2;123456

(4) 如所有的进程Finish[i]=true，则表示安全；否则系统不安全。
5.死锁的解除：
一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。死锁解除的主要两种方法：
1) 抢占资源。从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
2) 终止（或撤销）进程。终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。
总结：
一般情况下,如果同一个线程先后两次调用lock,在第二次调用时,由于锁已经被占用,该线程会挂起等待别的线程释放锁,然而锁正是被自己占用着的,该线程又被挂起而没有机会释放锁,因此就永远处于挂起等待状态了,这叫做死锁(Deadlock)。另⼀一种典型的死锁情形是这样:线程A获得了锁1,线程B获得了锁2,这时线程A调⽤用lock试图获得锁2,结果是需要挂起等待线程B释放锁2,而这时线程B也调⽤用lock试图获得锁1,结果是需要挂起等待线程A释放锁1,于是线程A和B都永远处于挂起状态了。12

注意：
写程序时应该尽量避免同时获得多个锁,如果一定有必要这么做,则有一个原则:如果所有线程在需要多个锁时都按相同的先后顺序(常见的是按Mutex变量的地址顺序)获得锁,则不会出现死锁。比如一个程序中用到锁1、锁2、锁3,它们所对应的Mutex变量的地址是锁1<锁2<锁3,那么所有线程在需要同时获得2个或3个锁时都应该按锁1、锁2、锁3的顺序获得。如果要为所有的锁确定一个先后顺序比较困难,则应pthread_mutex_trylock调用代替pthread_mutex_lock 调用,以免死锁。