操作系统银行家算法.docVIP

课程设计课程名称 操作系统 学生学院 计算机学院 专业班级2011级计算机科学与技术7班 学 号 3111006002 学生姓名 谢佳旭 2014 年 1月07日一、设计目的通过银行家算法设计与实现，可以加深学生对死锁的理解，掌握死锁的预防、避免、检测和解除的基本原理，重点掌握死锁的避免方法银行家算法。使学生初步具有研究、设计、编制和调试操作系统模块的能力。二、死锁概念在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。三、关于死锁的一些结论 1、参与死锁的进程最少是两个（两个以上进程才会出现死锁） 2、参与死锁的进程至少有两个已经占有资源 3、参与死锁的所有进程都在等待资源 4、参与死锁的进程是当前系统中所有进程的子集 四、产生死锁的四个必要条件：1、互斥使用（资源独占） 一个资源每次只能给一个进程使用 2、不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放 3、请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配） 4、循环等待 存在一个进程等待队列 P1 , P2 , , Pn, 其中P1等待P2占有的资源，P2等待P3占有的资源，Pn等待P1占有的资源，形成一个进程等待环路 五、 死锁的解决方案 5.1 产生死锁的例子 申请不同类型资源产生死锁 P1： 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 P2： 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 申请同类资源产生死锁（如内存） 设有资源R，R有m个分配单位，由n个进程P1,P2,Pn（n m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放 m=2，n=3 资源分配不当导致死锁产生5.2死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一 破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配 破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。六、设计思想我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。七、算法： n：系统中进程的总数 m：资源类总数 Available: ARRAY1.m of integer; Max: ARRAY1.n,1.m of integer; Allocation: ARRAY1.n,1.m of integer; Need: ARRAY1.n,1.m of integer; Request: ARRAY1.n,1.m of integer; 符号说明： Available 可用剩余资源 Max 最大需求 Allocation 已分配资源 Need 需求资源 Request 请求资源 当进程pi提出资源申请时，系统执行下列 步骤：(“=”为赋值符号，“=”为等号) （1）若Request=Need, goto step（2）；否则错误返回 （2）若Request=Available, goto step（3）；否则进程等待 （3）假设系统分配了资源，则有： Available=Available-Request; Allocation=Allocation+Request; Need=Need-Request 若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状态，进程等待 为进行安全性检查，定义数据结构： Work:ARRAY1.m of integer; Finish:ARRAY1.n of Boolean; 安全性检查的步骤： (1): Work=Available; Finish=false; (2) 寻找满足条件的i： a.Finish=false; b.Need=Work; 如果不存在，goto step(4) (3) Work=Work+Allocation; Finish=true; goto step(2) (4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态 /* 银行家算法，操作系统概念(OS concepts Six Edition) reedit by Johnny hagen，SCAU，run at vc6.0 */八、主要的数据结构 数据结构说明：#define MAX_RESOURCE_TYPE 10 /定义最大的系统资源类数struct task_struct /进程控制块 int pid; /进程编号 int maxMAX_RESOURCE_TYPE; /进程对资源的最大需求 int allocMAX_RESOURCE_TYPE; /进程已经分配的资源int requestMAX_RESOURCE_TYPE;/进程本次申请的资源数;等待队列采用链表结构进行设计。九、数据流程图1、初始算法流程图2、银行家算法流程图3、安全性算法流程图十、程序； #include malloc.h #include stdio.h #include stdlib.h #define alloclen sizeof(struct allocation) #define maxlen sizeof(struct max) #define avalen sizeof(struct available) #define needlen sizeof(struct need) #define finilen sizeof(struct finish) #define pathlen sizeof(struct path) struct allocation int value; struct allocation *next; ; struct max int value; struct max *next; ; struct available /*可用资源数*/ int value; struct available *next; ; struct need /*需求资源数*/ int value; struct need *next; ; struct path int value; struct path *next; ; struct finish int stat; struct finish *next; ; int main() int row,colum,status=0,i,j,t,temp,processtest; struct allocation *allochead,*alloc1,*alloc2,*alloctemp; struct max *maxhead,*maxium1,*maxium2,*maxtemp; struct available *avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1; struct need *needhead,*need1,*need2,*needtemp; struct finish *finihead,*finish1,*finish2,*finishtemp; struct path *pathhead,*path1,*path2; printf(n请输入系统资源的种类数:); scanf(%d,&colum); printf(请输入现时内存中的进程数:); scanf(%d,&row); printf(请输入已分配资源矩阵:n); for(i=0;irow;i+) for (j=0;jnext=alloc2-next=NULL; scanf(%d,&allochead-value); status+; else alloc2=(struct allocation *)malloc(alloclen); scanf(%d,%d,&alloc2-value); if(status=1) allochead-next=alloc2; status+; alloc1-next=alloc2; alloc1=alloc2; alloc2-next=NULL; status=0; printf(请输入最大需求矩阵:n); for(i=0;irow;i+) for (j=0;jnext=maxium2-next=NULL; scanf(%d,&maxium1-value); status+; else maxium2=(struct max *)malloc(maxlen); scanf(%d,%d,&maxium2-value); if(status=1) maxhead-next=maxium2; status+; maxium1-next=maxium2; maxium1=maxium2; maxium2-next=NULL; status=0; printf(请输入现时系统剩余的资源矩阵:n); for (j=0;jnext=available2-next=NULL; work1-next=work2-next=NULL; scanf(%d,&available1-value); work1-value=available1-value; status+; else available2=(struct available*)malloc(avalen); work2=(struct available*)malloc(avalen); scanf(%d,%d,&available2-value); work2-value=available2-value; if(status=1) avahead-next=available2; workhead-next=work2; status+; available1-next=available2; available1=available2; work1-next=work2; work1=work2; available2-next=NULL; work2-next=NULL; status=0; alloctemp=allochead; maxtemp=maxhead; for(i=0;irow;i+) for (j=0;jnext=need2-next=NULL; need1-value=maxtemp-value-alloctemp-value; status+; else need2=(struct need *)malloc(needlen); need2-value=(maxtemp-value)-(alloctemp-value); if(status=1) needhead-next=need2; status+; need1-next=need2; need1=need2; maxtemp=maxtemp-next; alloctemp=alloctemp-next; need2-next=NULL; status=0; for(i=0;inext=finish2-next=NULL; finish1-stat=0; status+; else finish2=(struct finish*)malloc(finilen); finish2-stat=0; if(status=1) finihead-next=finish2; status+; finish1-next=finish2; finish1=finish2; finish2-next=NULL; /*Initialization compleated*/ status=0; processtest=0; for(temp=0;temprow;temp+) alloctemp=allochead; needtemp=needhead; finishtemp=finihead; worktemp=workhead; for(i=0;istat=0) for(j=0;jnext,worktemp=worktemp-next) if(needtemp-valuevalue) processtest+; if(processtest=colum) for(j=0;jvalue+=alloctemp-value; worktemp1=worktemp1-next; alloctemp=alloctemp-next; if(status=0) pathhead=path1=path2=(struct path*)malloc(pathlen); path1-next=path2-next=NULL; path1-value=i; status+; else path2=(struct path*)malloc(pathlen); path2-value=i; if(status=1) pathhead-next=path2; status+; path1-next=path2; path1=path2; finishtemp-stat=1; else for(t=0;tnext; finishtemp-stat=0; else for(t=0;tnext; alloctemp=alloctemp-next; processtest=0; worktemp=workhead; finishtemp=finishtemp-next; pa