银行家算法实验报告.doc

银行家算法实验报告关键字：银行家算法、安全状态、不安全状态、向量矩阵、进程、死锁、资源、就绪状态、执行状态、阻塞状态；一 实验名称 进程同步互斥问题二 实验目的2.1 切实加深对进程死锁的认识；2.2 正确理解系统的安全状态与不安全状态；2.3 更进一步地理解和掌握银行家算法； 三 实验要求3.1将本实验分成两个阶段，第一阶段实现系统安全性检测算法；第二阶段实现银行家算法；3.2要求用户能自主地输入不同的向量矩阵；3.3你的程序能正确输出不同的运算结果；3.4你的程序应具备良好的容错能力；3.5力求用户界面的简洁美观； 四 实验原理4.1 进程及进程死锁；411 进程：是操作系统中最基本、最重要的概念，但直到目前还没有一个统一的定义，下面通过能反映进程实质的几点描述来认识进程： 进程是程序的一次执行； 进程是可以和别的计算并发执行的计算； 进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位； 进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。进程具有几个基本的特征：动态性、并发性、独立性、异步性；每个进程通常由程序段、数据段和进程控制块三部分组成，其中进程控制块能唯一标识一个进程。进程执行时间的间断性，决定了进程可能具有多种状态。事实上，运行中的进程至少具有以下三种基本状态：就绪状态：进程已获得除处理机以外的所有资源，一旦分到了处理机就可以立即执行，这时进程所处的状态为就绪状态；执行状态：又称运行状态。当一个进程获得必要的资源，并占有处理机，即在处理机上运行，此时进程所处的状态为执行状态；阻塞状态：又称等待状态，正在执行的进程，由于发生了某事件而暂时无法执行下去（如等待输入/输出完成），此时进程所处的状态称为阻塞状态。进程并非固定处于某一状态，它随着自身的推进和外界条件的变化而发生变化。412 进程死锁进程死锁是因多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都无法向前推进。例如，假设系统中有一台打印机和一台输入设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时答应机正被进程P2所占用。而P2在未释放打印机之前，又提出请求使用正被P1占用的输入设备的请求。这样，两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。42进程死锁产生的原因；进程产生死锁有以下两点： 系统资源不足。在上面举的例子里，如果输入设备不止被P1占用的一台，那么P2申请输入设备时，就可以得到满足，也就不会让P1、P2陷入死锁； 进程推进顺序不当。在上面举的例子里，如果P2在P1提出使用输入设备前，已经完成了对输入设备和打印机的使用，并且释放了它们；或者是在进程P2提出使用打印机的请求之前，进程P1已经完成了对输入设备和打印机的使用，并且释放了它们，则均不会发生死锁。4 3死锁产生的必要条件；死锁产生的必要条件有四条： 互斥条件 在某一段时间里，某资源被一个进程所占有，不能为别的进程使用； 不剥夺条件 进程所获得的资源在为使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放； 部分分配条件 进程每次申请它所需要的一部分资源。在等待新资源的同时，进程继续占用已分配到的资源； 环路条件 存在一种进程资源的循环等待链，链中的每一个进程已获得资源的同时被链中下一个进程所请求。44进程死锁的预防、避免和检测；441 死锁的预防 对资源加以某种限制，以使死锁不会发生。这种死锁的预防是静态的，基本的方法是相对应上面的产生死锁的四个必要条件，采取破坏的方式，以达到死锁不会产生的目的。442 死锁的避免 死锁的避免是对进程在申请某类资源时所使用的命令加以检测，通过这种方式来避免死锁的发生，相对于死锁的预防来说，这种方式是动态的。 另外，死锁的预防施加了比较强的限制条件，虽然实现起来比较简单，但是却严重损害了系统性能。在避免死锁的方法中，所施加的限制条件较弱，有可能获得较好的系统性能。443死锁的检测 死锁的检测是在死锁发生以后采取的一种方式，能够把死锁检测出来并解除之，它是动态的。前面两种方式，都是在系统为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施，则应该提供检测和解除死锁的手段。 死锁的解除常用两种方法： 资源剥夺法：当发现死锁时，从其他进程剥夺足够数量的资源给死锁进程，以解除死锁状态； 撤消进程法：此方法是采用强制手段从系统中撤消一个或一部分死锁进程，并剥夺这些进程的资源供其他进程使用。4 5死锁避免算法：银行家算法； 4.5.1 安全与不安全状态； 若在某一时刻，系统能按某种顺序如来为每个进程分配其所需的资源，直至最大需求，使每个进程都可顺利地完成，则称此时的系统状态为安全状态；称为安全序列。若某个时刻系统中不存在这样一个安全序列，则称此时的系统状态为不安全状态。 4.5.2 安全性算法； 系统所执行的安全性算法描述： 设置两个向量 Work 它表示系统可提供给进程继续运行的各类资源数目，它含有m个元素，开始执行安全性算法时，Work = Available; Finish 它表示系统是否有足够的资源分配给进程，使之运行完成，开始时，Finish(i)=false;当有足够资源分配给进程Pi时，令Finish(i)=true。 从进程集合中找到一个能满足下述条件的进程： Finish(i) = = false; Need(i) = Work; 如找到则执行步骤（4）；否则，执行步骤（4）。 （4） 当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行： Work = Work + Allocation(i); Finish(i) = true; 转步骤（2）； （4） 若所有进程的Finish(i)都为true,则表示系统处于安全状态；否则，系统处于不安全状态。 4.5.3 银行家算法； 在描述银行家算法之前，首先得定义几个关键向量：（1） 可利用资源向量Available,它是一个含有m个元素的数组，其中的每一个元素代表一类可利用资源的数目，其初值是系统中所配置的该类全部可利用资源数目。其数值随该类资源的分配和回收而动态地改变；（2） 最大需求矩阵Max，如Max(i,j) = k,表示进程I需要的j 类资源的最大数目是k；（3） 分配矩阵Allocation, Allocation(i,j) = k, 表示进程i当前已分到的j 类资源的数目为k;（4） 需求矩阵Need，Need(i,j) = k,表示进程i还需要j类资源k 个，才能正确执行完成。 上述的矩阵存在如下的关系： Need( i , j ) = Max( i , j ) Allocation ( i , j ) 银行家算法的描述如下： Request(i)是进程Pi的请求向量。Request(i,j) = k 表示进程Pi请求分配j类资源的数目是k 个。当Pi发出请求后，系统按下述步骤进行检查：（1） 如果Requet( i ) =Need，则转向步骤（2）；否则，认为出错，因为它所需要的资源数目已超过它所宣布的最大值；（2） 如果Request( i ) =Available，则转向步骤（4）；否则，表示系统中尚无足够的资源满足Pi的申请，Pi必须等待；（3） 系统试探把资源分配给进程Pi，并修改下面数据结构中的数值：Available = Available Request(i);Allocation(i) = Allocation(i) + Request(i);Need( i ) = Need( i ) Request (i);(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。五 实验过程5.1程序流程说明： 程序一开始会让用户输入各类资源总数，然后要求输入各类需求数，本地资源数,接着要求用户输入请求资源分配的的进程号，程序接受了以上的输入以后，会先进行试分配，如果可以完成，则出现：“进程安全！”的提示，否则出现：“进程不安全！”并将先前已经分配的资源还原！以下为程序的源代码和详细的说明：#includemain() int i,j,x=0; int r3,max53,allocation53,need53,avaiable3,sub3,request53,q3,p;printf(请输入各类资源总数：); for(j=0;j3;j+) scanf(%d,&rj);printf(请输入各类最大需求数：);/maxfor(i=0;i5;i+) for(j=0;j3;j+) scanf(%d,&maxij);printf(请输入本地拥有资源数：);/allocation for(i=0;i5;i+) for(j=0;j3;j+) scanf(%d,&allocationij);for(i=0;i5;i+) for(j=0;j3;j+) needij=maxij-allocationij;/计算每一个进程现在还需要多少的资源 for(j=0;j3;j+) subj=0; for(i=0;i5;i+) subj=subj+allocationij; avaiablej=rj-subj ; /计算每类资源还剩余多少printf(请输入进程号:); scanf(%d,&p);/以上为用户输入过程start: for(j=0;j3;j+) scanf(%d,&requestpj); for(j=0;j3;j+) qj=needpj-requestpj; for(j=0;j0|qj=0) +x; if(x!=3) printf(您输入错误，请重新输入：); goto start; if(!daxiao(p,avaiable,request) printf(请稍等); else for(j=0;j3;j+) avaiablej=avaiablej-requestpj; allocationpj=allocationpj+requestpj; needpj=needpj-requestpj; /以下为探测是否安全 if(safe(need,avaiable,allocation) printf(进程安全n); printf(本地拥有资源数:n) ; for(i=0;i5;i+) for(j=0;j3;j+) printf(%5d,allocationij);printf(n);printf(需要资源数：n); for(i=0;i5;i+) for(j=0;j3;j+) printf(%5d,needij);printf(n);printf(剩余资源：:n); for(j=0;j3;j+) printf(%5d,avaiablej); elseprintf(进程不安全 ); for(j=0;j3;j+) avaiablej=avaiablej+requestpj; allocationpj=allocationpj-requestpj; needpj=needpj+requestpj ; /将试分配的资源还原/daxiao(a,array1,array2) int a, array13,array253 ; int c,d=0,q3; for(c=0;c3;c+) qc=array1c-array2ac; for(c=0;c=0)+d; if(d=3) return 1; else return 0; /safe(array3,array4,array5) int array353,array43,array553; int i,j,e=0,z,x,work3,finish5,s5; for(j=0;j3;j+) workj=array4j ; for(i=0;i5;i+) finishi=0; z=0,x=0,i=0; for(i=0;i5;i=(+i)%5) if(finishi=0&daxiao(i,work,array3) for(j=0;j6) break; for(i=0;i5;i+) if(finishi=1) +