操作系统课程设计模拟银行家算法避免死锁（优秀）_死锁避免算法课程设计
操作系统课程设计模拟银行家算法避免死锁（优秀）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“死锁避免算法课程设计”。
模拟通过银行家算法避免死锁
一、银行家算法产生的背景及目的1：在多道程序系统中，虽然借助于多个进程的并发执行来改善系统的利用率，提高系统的吞吐量，但可能发生一种危险—死锁。死锁就是多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，如无外力作用，他们将无法再向前进行，如再把信号量作为同步工具时，多个Wait和Signal操作顺序不当，会产生进程死锁。
然而产生死锁的必要条件有互斥条件，请求和保持条件，不剥夺条件和环路等待条件。在预防死锁的几种方法中，都施加了较强的限制条件，在避免死锁的方法中，所施加的条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁。2：实验目的：让学生独立的使用编程语言编写和调试一个系统分配资源的简单模拟程序，了解死锁产生的原因及条件。采用银行家算法及时避免死锁的产生，进一步理解课堂上老师讲的相关知识点。银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。
二：银行家算法中的数据结构
1：可利用资源向量Available。这是一个含有m个元素的数组，其中的每个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Available[j]=k，z 则表示系统中现有Rj类资源K 个。
2：最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=k，表示第i个进程需要第Rj类资源的最大数目k个.3: 分配矩阵Allocation,也是n*m的矩阵，若Allocation[i,j]=k,表示第i 个进程已分配Rj类资源的数目为k个。
4：需求矩阵Need。也是一个n*m的矩阵，Need[i,j]=k,表示第i个进程还需Rj类资源k个。
三、银行家算法及安全性算法
1：银行家算法
设Request[i]是进程Pi的请求向量，若Request[i][j]=k;表示进程需要j类资源k个。当Pi发出资源请求时，系统按下属步骤进行检查；(1)如果Request[i][j]
(2)如果Request[i][j]
（1）设置两个向量；
1：工作向量Work，表示系统可提供给进程运行所需的各类资源数目，它含有m个元素，初始时Work=Available 2：Finish ,表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=true（2）从进程中找到一个能满需下属条件的进程
1；Finish[i]=false；
2：Need[i][j]
（3）当进程Pi顺利获得资源后，直至完成，并释放分配给它的资源，执行： Work[j]=Work[j]+Allocation[i][j];Finish[i]=true;Go to step(2);(5)如果所有的进程Finish[i]都满足，则表示系统处于安全状态，否则，处于不安全状态。
四、模块设计与分析及整体功能概述
模块设计与分析：
整个银行家算法分为初始化函数Init（），安全性算法函数 safe（），银行家算法函数bank（）三部分。初始化函数生成开始时刻系统中的进程和资源情况，安全性算法判断当某进程申请资源时，系统能否处于安全状态。在本实验中，若系统处于安全状态，便生成一个安全进程序列（安全序列可能有多个）。银行家算法函数bank（）负责整体的检查与异常判断。整体功能概述：
死锁会引起系统陷入僵局，操作系统必须防止此现象的发生。本实验通过一个动态分配资源的模拟程序，更清楚的理解死锁产生的原因和条件。Dijkstra的银行家算法是最有代表性的避免死锁的方法。运行程序时用户设定系统中进程和可利用资源的种类数目。输入各进程的可利用资源Available，最大需求MAX，已分配资源Allocation，需求资源Need，之后各系统发出资源请求Request，利用实验中的安全性算法判断能否产生一个安全性队列，若能，则给该进程分配成功，否则，不予分配。
五、流程图设计
六、源代码及调试分析
#include #define MAXm 50
// 定义最大进程数 #define MAXn 100
//定义最大资源数
int MAX[MAXm][MAXn];
//最大需求矩阵 int Allocation[MAXm][MAXn];
//已分配矩阵 int Available[MAXn];
//可用资源数组 int Need[MAXm][MAXn];
//需求矩阵 int Request[MAXm][MAXn];
//请求矩阵
int Finish[MAXm];
//存储完成资源分配的进程 int Sequence[MAXm];
//模拟的资源分配序列
int Work[MAXn];
//系统是否有足够的资源分配给进程 int m,n;
//m个进程,n个资源
#define False 0 #define True 1 void input();//数据输入函数 int safealg();//安全性算法函数 void banker();//银行家算法函数 void main(){input();safealg();banker();}
//*************初始化算法*************** void input(){ int i,j;
//************自定义进程数目与资源种类******************* cout
cout
*n“;cout>m;cout>n;//*****输入每个进程对每种资源的最大需求、已经获得的数量、每种类型资源的数目
cout
cout
for(j=0;j
{
cin>>MAX[i][j];
if(j==n)
cout
} } cout
cout
for(j=0;j
{
cin>>Allocation[i][j];
if(j==n)
cout
Need[i][j]=MAX[i][j]-Allocation[i][j];//需求数等于最大需求减去已经分配数
} } cout
cin>>Available[j];//输入各种资源的可利用数
} cout
for(i=0;i
cout
for(j=0;j
cout
for(j=0;j
cout
cout
for(j=0;j
cout
for(j=0;j
cout
cout
} } //*****************银行家算法，为进程分配资源***********// void banker(){ int i,j;
int choice;
while(1)
{
cout
cout
2:离开):”;
//用户选择
cin>>choice;
if(choice==1)
//分配资源
{
cout
cin>>i;
if(i>=m)
{
cout
cin>>i;//重新输入进程号
}
cout
for(j=0;j
cin>>Request[i][j];
//**********银行家算法进行检查*************//
for(j=0;j
{
if(Request[i][j]>Need[i][j])
{
cout
continue;
}
if(Request[i][j]>Available[j])
{
//资源申请数目大于可利用数，无法分配，得等待
cout
continue;
}
}
for(j=0;j
{
Available[j]=Available[j]-Request[i][j];
//可用资源减少
Allocation[i][j]=Allocation[i][j]+Request[i][j];//所得资源增加
Need[i][j]=Need[i][j]-Request[i][j];
//仍需资源减少
}
if(safealg()
{
cout
for(j=0;j
//把资源恢复成分配之前的状态
{
Available[j]=Available[j]+Request[i][j];
Allocation[i][j]=Allocation[i][j]-Request[i][j];
Need[i][j]=Need[i][j]+Request[i][j];
}
for(i=0;i
{
Finish[i]=False;//没有足够的资源分配给该进程
}
}//if(safealg()
else
{
cout
for(j=0;j
Work[j]=Available[j];
cout
for(i=0;i
{
cout
for(j=0;j
cout
cout
for(j=0;j
cout
cout
for(j=0;j
cout
cout
“;
for(j=0;j
cout
cout
”;
cout
for(j=0;j
Work[j]=Allocation[Sequence[i]][j]+Work[j];//回收该进程所分配的资源
cout
}
}//if(safealg()>=0)
}//if(choice=1)
else if(choice==2)
//离开————
break;
else cout
int i,j,k,l=0;
//int Work[MAXn];
//工作组
//记录序列
for(i=0;i
Work[i]=Available[i];
//工作分配初始化为系统可用资源
for(i=0;i
//扫描所有进程，预设所有进程不能运行
{
Finish[i]=False;
}
for(i=0;i
{ //
if(Finish[i]==True)
{
continue;
}
else //对于未运行的进程，进行如下处理
{///
for(j=0;j
{
if(Need[i][j]>Work[j])//由于部分资源得不到满足，进程i无法运行
{的资源
用资源
}
break;
} }
if(j==n)//进程各类资源全部得到满足
{
Finish[i]=True;
for(k=0;k
{ Work[k]+=Allocation[i][k];//工作分配加上可
}
Sequence[l++]=i;
//模拟资源分配序列生成i=-1;
//重新扫描所有进程从i=0开始
}
else
{ //某一资源得不到满足
continue;//试探下一个进程
} }// if(l==m)//都试探完毕
{
cout
cout
for(i=0;i
//输出安全序列
cout “;
cout
return 0;} }// cout
分析：输入各进程的可利用资源Available，最大需求MAX，已分配资源Allocation，需求资源Need，之后各系统发出资源请求Request，利用实验中的安全性算法判断能否产生一个安全性队列，若能，则给该进程分配成功，否则，不予分配。在确定安全序列的过程中，要检测所有进程的Finish[i]的值，每次循环检测完后要重复从第一个进程开始。
七、运行结果 假设输入进程个数为5，资源种类数为3，并以此输入各进程初始时刻的各种资源数量，如下
若再继续申请资源，假设为P4，申请资源（1 2 2）
假设P1 申请资源（2 2 4）有
八、心得体会
经过这次操作系统课程设计，让我受益匪浅，收获颇多。主要体会如下： 1.利用Vc++编译程序编写银行家算法，进一步理解到通过银行家算法避免死锁的思想,同时也理解了系统死锁产生的原因及条件。
2.在实验过程中所有的设计步骤遵循老师教授的程序功能化的思想，分别定义了三个函数，init()初始化函数,safealg()安全性算法函数，bank（）银行家算法函数，体现了函数的模块化思想。这样的话，不仅提高了程序的可读性和可操作性，而且还提高了CPU的利用率和内存的利用率，因为程序的运行是局部性的，这种思想对于段页式存储管理系统尤为重要。
3.实验过程中遇到的种种疑难问题通过自己上网查找答案，锻炼了自己纠错能力和搜索有价值信息的能力及自学的能力，并且进一步巩固了自己以前学过的专业知识。
