死锁:
死锁产生的现场:当A进程P S2信号量而B进程P S1信号量时就会产生死锁,因为S2信号量需要B进程释放,而S1信号量需要A进程释放,因此两个进程都在等相互的资源,造成死锁。
![](https://www.codeprj.com/image/aHR0cDovL21ldGMuZ2R1dC5lZHUuY24vb3Mvb3NjYWkvY2hhcHRlcjIvaW1hZ2VzL2NoMjgwMS5HSUY=.png)
死锁产生的条件:
互斥条件:进程要求对所分配的资源进行排它性控制,即在一段时间内某资源仅为一进程所占用。(信号量s1 s2为互斥的信号量,只能被一个进程占用)
请求和保持条件:当进程因请求资源而阻塞时,对已获得的资源保持不放。(A进程在获取s2阻塞时,一直占用s1)
不可剥夺条件:进程已获得的资源在未使用完之前,不能剥夺,只能在使用完时由自己释放。(s1只能由A进程释放,s2只能由B进程释放)
环路等待条件:在发生死锁时,必然存在一个进程--资源的环形链。(A B 进程都是环形链路)
避免死锁的算法:
银行家算法是避免死锁的一种重要方法,防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题,如银行贷款等。
程序实现思路银行家算法顾名思义是来源于银行的借贷业务,一定数量的本金要应多个客户的借贷周转,为了防止银行加资金无法周转而倒闭,对每一笔贷款,必须 考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题,系统中有限的资源要供多个进程使用,必须保证得到的资源的进程能在有限的时间内归还 资源,以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源,则进程都无法继续执行下去的死锁现象。 把一个进程需要和已占有资源的情况记录在进程控制中,假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时,表示系统不能满 足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然,,每个进程的资源需求总量不能超过系统拥有的资源总 数, 银行算法进行资源分配可以避免死锁. 一.程序流程图: 1.初始化算法流程图: ![银行家算法实现 - 如雪 - 丢了幸福的猪](https://www.codeprj.com/image/aHR0cDovL2ltZy5ibG9nLjE2My5jb20vcGhvdG8vQW1vbzZLTV90TXBrM1N0THduQlZ2QT09LzMzODQ3MzY1OTQ5NDY2ODQ0MzUuanBn.png) 2.银行家算法流程图: ![银行家算法实现 - 如雪 - 丢了幸福的猪](https://www.codeprj.com/image/aHR0cDovL2ltZy5ibG9nLjE2My5jb20vcGhvdG8vTFVmaE1UVUx6RXJZXzFtMjdFUU9PZz09LzMzODQ3MzY1OTQ5NDY2ODQ0MzcuanBn.png) 3.安全性算法流程图: ![银行家算法实现 - 如雪 - 丢了幸福的猪](https://www.codeprj.com/image/aHR0cDovL2ltZy5ibG9nLjE2My5jb20vcGhvdG8vMUhVempiR0dvYlVzQm9fXzdFVUlNZz09LzMzODQ3MzY1OTQ5NDY2ODQ0MzkuanBn.png) 二.银行家算法设计: 1.设进程i提出请求Request[n],则银行家算法按如下规则进行判断。 (1)如果Request[n]>Need[i,n],则报错返回。 (2)如果Request[n]>Available,则进程i进入等待资源状态,返回。 (3)假设进程i的申请已获批准,于是修改系统状态: Available=Available-Request Allocation=Allocation+Request Need=Need-Request (4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。 2.安全性检查 (1)设置两个工作向量Work=Available;Finish =False (2)从进程集合中找到一个满足下述条件的进程, Finish =False Need<=Work 如找到,执行(3);否则,执行(4) (3)设进程获得资源,可顺利执行,直至完成,从而释放资源。 Work=Work+Allocation Finish=True GO TO 2 (4)如所有的进程Finish =true,则表示安全;否则系统不安全。 3.数据结构 假设有M个进程N类资源,则有如下数据结构: #define W 10 #define R 20 int A ; //总进程数 int B ; //资源种类 int ALL_RESOURCE[W]; //各种资源的数目总和 int MAX[W] ; //M个进程对N类资源最大资源需求量 int AVAILABLE ; //系统可用资源数 int ALLOCATION[W] ; //M个进程已经得到N类资源的资源量 int NEED[W] ; //M个进程还需要N类资源的资源量 int Request ; //请求资源个数 5.4主要函数说明 void showdata(); //主要用来输出资源分配情况 void changdata(int); //主要用来输出资源分配后后的情况 void rstordata(int); //用来恢复资源分配情况,如:银行家算法时,由于分配不安全则要恢复资源分配情况 int chkerr(int); //银行家分配算法的安全检查 void bank() ; //银行家算法 银行家算法的课程设计(二)VC++6.02008-01-28 15:29源程序 数据结构分析: 假设有M个进程N类资源,则有如下数据结构: #define W 10 #define R 20 int A ; //总进程数 int B ; //资源种类 int ALL_RESOURCE[W]; //各种资源的数目总和 int MAX[W] ; //M个进程对N类资源最大资源需求量 int AVAILABLE ; //系统可用资源数 int ALLOCATION[W] ; //M个进程已经得到N类资源的资源量 int NEED[W] ; //M个进程还需要N类资源的资源量 int Request ; //请求资源个数 第3章 程序清单#include <iostream> using namespace std; #define MAXPROCESS 50 /*最大进程数*/ #define MAXRESOURCE 100 /*最大资源数*/ int AVAILABLE[MAXRESOURCE]; /*可用资源数组*/ int MAX[MAXPROCESS][MAXRESOURCE]; /*最大需求矩阵*/ int ALLOCATION[MAXPROCESS][MAXRESOURCE]; /*分配矩阵*/ int NEED[MAXPROCESS][MAXRESOURCE]; /*需求矩阵*/ int REQUEST[MAXPROCESS][MAXRESOURCE]; /*进程需要资源数*/ bool FINISH[MAXPROCESS]; /*系统是否有足够的资源分配*/ int p[MAXPROCESS]; /*记录序列*/ int m,n; /*m个进程,n个资源*/ void Init(); bool Safe(); void Bank(); int main() { Init(); Safe(); Bank(); } void Init() /*初始化算法*/ { int i,j; cout<<"\t---------------------------------------------------"<<endl; cout<<"\t|| ||"<<endl; cout<<"\t|| 银行家算法 ||"<<endl; cout<<"\t|| ||"<<endl; cout<<"\t|| 计科04151 李宏 ||"<<endl; cout<<"\t|| ||"<<endl; cout<<"\t|| 0415084211 ||"<<endl; cout<<"\t---------------------------------------------------"<<endl; cout<<"请输入进程的数目:"; cin>>m; cout<<"请输入资源的种类:"; cin>>n; cout<<"请输入每个进程最多所需的各资源数,按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>MAX[j]; cout<<"请输入每个进程已分配的各资源数,也按照"<<m<<"x"<<n<<"矩阵输入"<<endl; for(i=0;i<m;i++) { for(j=0;j<n;j++) { cin>>ALLOCATION[j]; NEED[j]=MAX[j]-ALLOCATION[j]; if(NEED[j]<0) { cout<<"您输入的第"<<i+1<<"个进程所拥有的第"<<j+1<<"个资源数错误,请重新输入:"<<endl; j--; continue; } } } cout<<"请输入各个资源现有的数目:"<<endl; for(i=0;i<n;i++) { cin>>AVAILABLE; } } void Bank() /*银行家算法*/ { int i,cusneed; char again; while(1) { cout<<"请输入要申请资源的进程号(注:第1个进程号为0,依次类推)"<<endl; cin>>cusneed; cout<<"请输入进程所请求的各资源的数量"<<endl; for(i=0;i<n;i++) { cin>>REQUEST[cusneed]; } for(i=0;i<n;i++) { if(REQUEST[cusneed]>NEED[cusneed]) { cout<<"您输入的请求数超过进程的需求量!请重新输入!"<<endl; continue; } if(REQUEST[cusneed]>AVAILABLE) { cout<<"您输入的请求数超过系统有的资源数!请重新输入!"<<endl; continue; } } for(i=0;i<n;i++) { AVAILABLE-=REQUEST[cusneed]; ALLOCATION[cusneed]+=REQUEST[cusneed]; NEED[cusneed]-=REQUEST[cusneed]; } if(Safe()) { cout<<"同意分配请求!"<<endl; } else { cout<<"您的请求被拒绝!"<<endl; for(i=0;i<n;i++) { AVAILABLE+=REQUEST[cusneed]; ALLOCATION[cusneed]-=REQUEST[cusneed]; NEED[cusneed]+=REQUEST[cusneed]; } } for(i=0;i<m;i++) { FINISH=false; } cout<<"您还想再次请求分配吗?是请按y/Y,否请按其它键"<<endl; cin>>again; if(again=='y'||again=='Y') { continue; } break; } } bool Safe() /*安全性算法*/ { int i,j,k,l=0; int Work[MAXRESOURCE]; /*工作数组*/ for(i=0;i<n;i++) Work=AVAILABLE; for(i=0;i<m;i++) { FINISH=false; } for(i=0;i<m;i++) { if(FINISH==true) { continue; } else { for(j=0;j<n;j++) { if(NEED[j]>Work[j]) { break; } } if(j==n) { FINISH=true; for(k=0;k<n;k++) { Work[k]+=ALLOCATION[k]; } p[l++]=i; i=-1; } else { continue; } } if(l==m) { cout<<"系统是安全的"<<endl; cout<<"安全序列:"<<endl; for(i=0;i<l;i++) { cout<<p; if(i!=l-1) { cout<<"-->"; } } cout<<""<<endl; return true; } } cout<<"系统是不安全的"<<endl; return false; } 输出数据 ![银行家算法实现 - 如雪 - 丢了幸福的猪](https://www.codeprj.com/image/aHR0cDovL2ltZy5ibG9nLjE2My5jb20vcGhvdG8vUnZvdmJkNHJWekYtdWh0T1pQTWJ1UT09LzMzODQ3MzY1OTQ5NDY2ODQ0NDAuanBn.png) 银行家算法的模拟实现”是本学期操作系统课程唯一的课程设计。在设计此程序的过程中,我遇到过许多问题,也学到了很多东西。本程序的设计实现主要是用 C++语言实现,通过对程序算法的设计优化、输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决,在C++学习上也有了很大的进 步。程序设计过程中开始遇到的最大的问题是算法的结构设计问题,课本上只给了设计要求及简单的算法,要真正实现还需要考虑很多方面。在算法的数据结构设计 上考虑了很长时间。在程序设计中先后参考了很多网络资料,也参考了一些别人写的的程序,综合这些算法思想和自己的思路对程序做了很好的设计方式,对一些算 法的优越性等也作了一些考虑。此外考虑最多的就是异常错误处理的设计。一个好的程序必须能在各种环境下都有其相应的处理方式,至少能应对一些常见的可能发 生的错误。比如一般的要求输入为数字时,如果输入了一个非数字字符,程序就会立即出错无法继续运行,本程序针对这个问题设计了一个shuzi();函数进 行处理,处理方式为:接受键盘输入的字符为字符串,然后对字符串的每个字符进行判断是否为数字,如果有非数字字符出现则提示出错并要求重新输入。又如在判 断是否继续时要求输入Y/N时,按一般的方式,如果输入为多个字符,则多余的字符会保存在缓冲区,到下次要求输入时输入而导致出错,对此问题设计处理方式 为接受输入字符保存为串然后只取其首字符进行判断。还有很多类似的错误处理。还有在设置程序的显示优化时,发现暂停函数在不同的情况下执行顺序不同,如此 等等。在课程设计过程中遇到了许多问题,也向同宿舍的同学做了一些请教一起讨论,也因此从他们身上学到了许多东西。 |