死锁常见的题目
定义
所谓死锁，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
产生死锁的必要条件
互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
常见死锁相关算法
银行家算法：避免死锁
资源有序分配法：预防死锁
资源分配图化简法：检测死锁
撤销进程法：解决死锁
银行家算法
算法思想
银行家算法：银行家算法是从当前状态出发，按照系统各类资源剩余量逐个检查各进程需要申请的资源量，找到一个各类资源申请量均小于等于系统剩余资源量的进程P1。然后分配给该P1进程所请求的资源，假定P1完成工作后归还其占有的所有资源，更新系统剩余资源状态并且移除进程列表中的P1，进而检查下一个能完成工作的客户，......。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。若找不到这样的安全序列，则当前状态不安全。
相关数据结构
可利用资源向量Available。这是一个含有m个元素的数组，其中的而每一个元素代表一类可利用资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K；则表示进程i需要Rj类资源的最大数目为K。
分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
-
需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成任务。
上述三个矩阵间存在下述关系：
Need[i,j]=Max[i,j]-Allocation[i,j]
例子
当前系统状态
从图中数据我们可以利用银行家算法的四个数据结构，来描述当前的系统状态：
因为系统总资源R=(17,5,20),所以可以计算出可利用资源向量
Available=R-Allocation(P1,P2,P3,P4,P5)=（2,3,3）分配资源
根据目前状态，用Available向量每一个进程的Need向量相比，发现
Available>=P5.Need,所以可以将目前的资源分配给P5向量(P4也可以，不唯一)。当P5获得所需的所有向量后执行完毕，之后释放其占有的所有资源。此时更新系统资源：
Available=R-Allocation(P1,P2,P3)=（7,4,11）按照上述同样的方法，P4 也可以安全运行，以及P3，P2，P1也能按顺序运行。因此，在T0时刻，存在安全序列：
P5，P4，P3，P2，P1（并不唯一）
死锁的算法实现
// 避免死锁银行家算法的C++ 编程实现
#include<iostream>
using namespace std;
// p 进程数，r 资源种类
#define p 4
#define r 3
/*-----------------------------------------------*/
/*输入函数*/
/*-----------------------------------------------*/
//a-max,b-allocation,c-need,d-available
void input(int a[p][r],int b[p][r],int c[p][r],int d[r])
{
int i,j;
cout<<"* input max data:\n";
for(i=0;i<p;i++)
for(j=0;j<r;j++)cin>>a[i][j];
cout<<"* input allocation data:\n";
for(i=0;i<p;i++)
for(j=0;j<r;j++)cin>>b[i][j];
cout<<"* input need data:\n";
for(i=0;i<p;i++)
for(j=0;j<r;j++)cin>>c[i][j];
cout<<"* input available data:\n";
for(j=0;j<r;j++)cin>>d[j];
}
/*-----------------------------------------------*/
/*比较函数*/
/*-----------------------------------------------*/
//比较结果为m中的元素全大于n中的元素返回1，否则返回0
int com(int m[r],int n[r])
{
int i,flag=0;
for(i=0;i<r;i++)
if(m[i]<n[i])
{
flag=1;
break;
}
if(flag==1) return(0);
else return(1);
}
/*-----------------------------------------------*/
/*安全性检验函数*/
/*-----------------------------------------------*/
//b、c、d意义同上
int stest(int b[p][r],int c[p][r],int d[r])
{
int i,j,k,l,flag=0,flag1=0;
int t[r],finish[p],dd[r];
for(i=0;i<p;i++)finish[i]=0;//finish为1即表示available满足某一进程并让其实现
for(i=0;i<r;i++)dd[i]=d[i];
cout<<"分配序列：\n";
for(k=0;k<p;k++) //全搜索，直至实现或不可能实现
{
for(i=0;i<p;i++)
{
if(finish[i]==1)continue;
else
{
for(j=0;j<r;j++)t[j]=c[i][j];
if(com(dd,t))
{
finish[i]=1;
cout<<i+1<<'\t';
flag=1;
for(l=0;l<r;l++)dd[l]=dd[l]+b[i][l];
break;
}
}
if(flag==1)break;
}
}
cout<<'\n';
for(l=0;l<p;l++)
{
//cout<<finish[l]<<endl;
if(finish[l]==0)flag1=1;
}
//cout<<flag1<<endl;
if(flag1==0)return(1); //flag1为记录finish是否有0存在的标记，当flag1=0时，安全
else return(0);
}
/*-----------------------------------------------*/
/*申请进程后的安全性检验函数*/
/*-----------------------------------------------*/
//req-request,n-第n个进程申请资源
void rtest(int b[p][r],int c[p][r],int d[r],int req[r],int n)
{
int i,j;
int t[r];
n=n-1;
for(i=0;i<r;i++)t[i]=c[n][i];
if(com(d,req)&&com(t,req))//对available，request进行比较
{
for(j=0;j<r;j++)
{
b[n][j]=b[n][j]+req[j];
c[n][j]=c[n][j]-req[j];
d[j]=d[j]-req[j];
}
if(stest(b,c,d))cout<<"允许"<<n+1<<"个进程申请资源！\n";
else
{
cout<<"不允许"<<n+1<<"个进程申请资源！\n";
cout<<"恢复以前状态！\n";
for(j=0;j<r;j++)
{
b[n][j]=b[n][j]-req[j];
c[n][j]=c[n][j]+req[j];
d[j]=d[j]+req[j];
}
}
}
else cout<<"申请资源量出错！\n";
}
/*-----------------------------------------------*/
/*主函数*/
/*-----------------------------------------------*/
void main()
{
int j,n; //n-第n个资源申请
int max[p][r],allocation[p][r],need[p][r];
int available[r],request[r];
input(max,allocation,need,available);
if(stest(allocation,need,available)==1)cout<<"初始状态安全！\n";
else cout<<"初始状态不安全！\n";
cout<<" input request data:\n";
for(j=0;j<r;j++)cin>>request[j];
cout<<"第n个进程申请资源——n的值\n";
cin>>n;
rtest(allocation,need,available,request,n);
}
