操作系统课程设计

1、模拟通过银行家算法避免死锁一、银行家算法产生的背景及目的1:在多道程序系统中，虽然借助于多个进程的并发执行来改善系统的利用率， 提高系统的吞吐量，但可能发生一种危险一死锁。死锁就是多个进程在运行过程 中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，如无外力作用， 他们将无法再向前进行，如再把信号量作为同步工具时，多个Wait和Signal操作顺序不当，会产生进程死锁。然而产生死锁的必要条件有互斥条件，请求和保持条件，不剥夺条件和环路等待条件。在预防死锁的几种方法中，都施加了较强的限制条件，在避免死锁的方法 中，所施加的条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安

2、全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁。 2:实验目的：让学生独立的使用编程语言编写和调试一个系统分配资源的简单 模拟程序，了解死锁产生的原因及条件。采用银行家算法及时避免死锁的产生， 进一步理解课堂上老师讲的相关知识点。银行家算法是从当前状态出发，逐个按安全序列检查各客户中谁能完成其工作，然后假定其完成工作且归还全部贷款， 再进而检查下一个能完成工作的客户。如果所有客户都能完成工作，则找到一个 安全序列，银行家才是安全的。二：银行家算法中的数据结构1 :可利用资源向量Available。这是一个含有m个元素的数组，其中的每个元素代表一类可利用的资源数目，其初始值是系统中

3、所配置的该类全部可用资源的 数目，其数值随该类资源的分配和回收而动态的改变。如果Availablej=k ，z则表示系统中现有Rj类资源K个。2 :最大需求矩阵Max>这是一个n*m的矩阵，它定义了系统中n个进程中的每 一个进程对m类资源的最大需求。如果 Maxi,j=k ，表示第i个进程需要第Rj 类资源的最大数目k个.3:分配矩阵Allocation, 也是n*m的矩阵，若 Allocationi,j=k,表示第i个进程已分配Rj类资源的数目为k个。4 :需求矩阵Need也是一个n*m的矩阵，Needi,j=k, 表示第i个进程还需 Rj类资源k个。三、银行家算法及安全性算法1：银行

4、家算法设Requesti是进程Pi的请求向量，若Requestij=k;表示进程需要j类资源k个。当Pi发出资源请求时，系统按下属步骤进行检查； 如果Requestij<=Needij;便转向步骤（2），否则认为出错，因为它所需要的资源数已超过他所宣布的最大值。如果 Requestij<=Availableij,便转向步骤（3），否则认为尚无足够资源，进程需等待。（3）系统试探着把资源分配给进程，并修改下面数据结构的数据Availableij=Availableij-Requestij;Allocati on ij=Allocatio nij+Requestij;Needij=Ne

5、edij-Requestij;（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，已完成此次分配。否则，将本次的试探分配作 废，回复原来的资源分配状态，将进程Pi等待。2：安全性算法1）设置两个向量；1 :工作向量Work,表示系统可提供给进程运行所需的各类资源数目，它含有m个元素，初始时Work=Available2 : Finish ,表示系统是否有足够的资源分配给进程，使之运行完成。开始 时先做 Finishi=true（2）从进程中找到一个能满需下属条件的进程1 ； Finishi=false ；2： Needij<=Workj

6、;若找到执行步骤（3），否则执行步骤（4）（3）当进程Pi顺利获得资源后，直至完成，并释放分配给它的资源，执行:Workj=Workj+Allocatio nij;Fini shi=true;Go to step （2）;（5）如果所有的进程Finishi都满足，则表示系统处于安全状态，否则，处于 不安全状态。四、模块设计与分析及整体功能概述模块设计与分析：整个银行家算法分为初始化函数Init （），安全性算法函数safe （），银行 家算法函数bank （）三部分。初始化函数生成开始时刻系统中的进程和资源情 况，安全性算法判断当某进程申请资源时，系统能否处于安全状态。在本实验中， 若系统处于

7、安全状态，便生成一个安全进程序列（安全序列可能有多个）。银行家算法函数bank （）负责整体的检查与异常判断。整体功能概述：死锁会引起系统陷入僵局，操作系统必须防止此现象的发生。本实验通过一个动态分配资源的模拟程序，更清楚的理解死锁产生的原因和条件。Dijkstra的银行家算法是最有代表性的避免死锁的方法。运行程序时用户设定系统中进程和 可利用资源的种类数目。输入各进程的可利用资源 Available，最大需求MAX已 分配资源Allocation，需求资源Need,之后各系统发出资源请求 Request，利用实验中的安全性算法判断能否产生一个安全性队列，若能，则给该进程分配成 功，否则，不予

8、分配。五、流程图设计讦始初始化後入Request大于Needfor j=0 to n-1耳请资源 大干Available是.申请资源Availablei, j >NeedAvai1ablej=Avai1ablej-Requesti, jAllocation, i, j=f<e quest. i, j +-A1 local ion _i, jNeedfij j=Needi? j-Request i. jWork j =Avai 1 abl ej, Finishi-false寻找NeMi, j <=Work j inishi=falseWork j=Workj_ +A1locat

9、ion1, j系统不安全六、源代码及调试分析#include<iostream.h> #define MAXm 50 #define MAXn 100 int MAXMAXmMAXn; int AllocationMAXmMAXn; int AvailableMAXn; int NeedMAXmMAXn; int RequestMAXmMAXn; int FinishMAXm; int SequenceMAXm; int WorkMAXn; int m,n;/定义最大进程数II定义最大资源数最大需求矩阵已分配矩阵可用资源数组II需求矩阵请求矩阵存储完成资源分配的进程II模拟的资源分

10、配序列系统是否有足够的资源分配给进程IIm个进程,n个资源#define False 0#define True 1II*初始化算法*void input(); 数据输入函数 int safealg(); 安全性算法函数 void banker(); 银行家算法函数 void main() input();safealg();banker();void input() II*int i,j;自定义进程数目与资源种类 *coutvv"*n" coutvv"*利用银行家算法避免死锁*n" coutvv"*n"cout<v"

11、*n" coutvv"请输入进程的数目:"cin>>m;coutvv"请输入资源的种类:"cin>>n;II*输入每个进程对每种资源的最大需求、已经获得的数 量、每种类型资源的数目coutvv"各进程资源最大需求(Max),按照"vvmvv"x"vvnvv" 矩阵输入:n"for(i=0;ivm;i+)coutvv"P"vvivv":"for(j=0;jvn;j+)cin»MAXij;if(j=n)coutvv&

12、quot;资源种类数匹配出现错误！ "/当资源配置的种 类数大于预先输入的数值时，出错coutvv"各进程当前获得资源(Allocation),按照"vvm<v"x"vvnvv"矩阵输入"vvendl;for(i=0;i<m;i+)coutvv"P"vvivv":"for(j=0;jvn;j+)cin»Allocationij;if(j=n)coutvv"资源种类数匹配出现错误！ "/当资源配置的种 类数大于预先输入的数值时，出错Needij=

13、MAXij-Allocationij; 需求数等于最大 需求减去已经分配数coutvv"系统可用资源(Available):"vvendl;for(j=0;jvn;j+)cin»Availablej;输入各种资源的可利用数coutvv"当前时刻的进程分配情况如图：n"coutvv"进程号-"vv"MAX-"vv"Allocation-"vv"Need-"vv"Available-n" 显示各进程的 资源情况for(i=0;ivm;i+)coutv

14、v"P"vvivv":"for(j=0;jvn;j+)coutvv" "vvMAXij;for(j=0;jvn;j+)coutvv" "vvAllocationij;coutvv""for(j=0;jvn;j+)coutvv" "vvNeedij;for(j=0;jvn;j+)coutvv" "vvAvailablej coutvvendl;/ 回车换行/*void banker() 银行家算法，为进程分配资源*/int i,j;int choice;wh

15、ile(1)coutvvendl;coutvv"输入要进行的操作(1:分配资源 2:离开):"用户选择cin»choice;if(choice=1) / 分配资源coutvv"从P0到P"vvm-lvv"之间选择要分配资源的进程号:n"cin»i;if(i>=m)coutvv"无此进程号！请重新输入:n"cin»i;重新输入进程号coutvv"请输入进程申请的资源(Request):"vvendl;for(j=0;jvn;j+)cin»Request

16、ij;/*银行家算法进行检杳*/for(j=0;jvn;j+)if(Requestij>Needij) coutvv"申请的资源大于它需要的资源数，请重 新输入!n"/资源申请不合理continue;if(Requestij>Availablej)资源申请数目大于可利用数，无法分配，得等待 coutvv"当前系统可用资源不够，请等待!"vvendl;continue;for(j=0；jvn;j+)资源申请得到允许时，变换各个资源数 Availablej=Availablej-Requestij;II 可用资源减少Allocationij=Al

17、locationij+Requestij; 所得资源增加Needij=Needij-Requestij;II 仍需资源减少if(safealg()v0)安全性算法的返回值coutvv"分配不成功，请等待！"；for (j=0;jvn;j+)把资源恢复成分配之前的状态Availablej=Availablej+Requestij;Allocationij=Allocationij-Requestij; Needij=Needij+Requestij;for(i=0;ivm;i+) Finishi=False;/I没有足够的资源分配给该进程/if(safealg()v0)els

18、ecoutvv"同意分配请求!"vvendl;for(j=0;jvn;j+)Workj=Availablej;coutvv"进程号-"vv"-Work-"vv"Need-"vv"Allocation-"vv"Work+Allocation-" vv"Finish-"vvendl;for(i=0;ivm;i+)II按模拟分配序列进行分配coutvv"进程 P"vvSequenceivv":"for(j=0;jvn;j+

19、) coutvvWorkjvv""coutvv""for(j=0;jvn;j+) coutvvNeedSequenceijvv""coutvv""for(j=0;jvn;j+) coutvvAllocationSequenceijvv""coutvv""for(j=0；j<n;j+) coutvvAllocationSequenceij+Workjvv"" coutvv""coutvvFinishSequenceivv"

20、 "/完成该进程for(j=0;jvn;j+) Workj=AllocationSequenceij+Workj; 回收 该进程所分配的资源coutvvendl;/离开 /if(safealg()>=0) /if(choice=1) else if(choice=2)break;else coutvv*请输入1或2!"/只认可1或2 /while(1)/*安全性算法*/int safealg()int i,j,k,l=0;/int WorkMAXn;/ 工作组/记录序列for(i=0;ivn;i+)Worki=Availablei;/工作分配初始化为系统可用资源for

21、(i=0;ivm;i+)/扫描所有进程，预设所有进程不能运行Finishi=False;for(i=0;ivm;i+) /if(Finishi=True)continue;else /对于未运行的进程，进行如下处理/for(j=0;jvn;j+)/ 找到一个满足 Finishi=false 且 Needijv=Workj的进程if(Needij>Workj)由于部分资源得不到满足，进程i无法运行break;if(j=n)进程各类资源全部得到满足Finishi=True;for(k=0;kvn;k+)进程i正常运行后，释放其占有的资源Workk+=Allocationik;II 工作分配加

22、上可用资源Sequencel+=i; 模拟资源分配序列生成 i=-1;II重新扫描所有进程从i=0开始else 某一资源得不到满足continue; /试探下一个进程/if(l=m)II都试探完毕coutvv"系统安全!"vvendl;coutvv"安全序列："for(i=0;ivl;i+)II输出安全序列coutvv"进程 P"vvSequenceivv"-> " coutvvendl;return 0;IIcoutvv"系统进入不安全状态！"vvendl;return -1;分析：输入

23、各进程的可利用资源Available ，最大需求 MAX已分配资源 Allocation，需求资源Need,之后各系统发出资源请求Request，利用实验中的安全性算法判断能否产生一个安全性队列，若能，则给该进程分配成功，否则，不予分配。在确定安全序列的过程中，要 检测所有进程的Fini shi的值，每次循环检测完后要重复从第一个进程开始。七、运行结果假设输入进程个数为5,资源种类数为3,并以此输入各进程初始时刻的各种资 源数量，如下*利用银行家算法避免死锁*雷输入进程的数目汚讼按照E X3矩阵输入:P0：4 5 7Pl：5 4 6P2：4 3 3P3：3 5 4P4；4 3 g各进程当前获得资源t Allocat ion,按照£ x3矩阵输入2 31 21 12 11 0P0：2Pl：2P2：8P3：l系统可用