操作系统课程设计报告

1、操作系统课程设计报告指导教师：潘煜学号：070603115姓名：张鑫班级：070603学期：2009至2010学年1学期1、概述一、设计目的对死锁避免中的银行家算法作进一步理解。加深理解死锁的概念。加深理解安全序列和安全状态的概念。通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁 产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。二、开发环境操作系统Win dows xp编译环境VC+6.0生成文件银行家算法.cpp2、需求分析一、死锁概念：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去 此时称系统处于死锁状态或

2、系统产生了死锁，这些永远在互相等待的进程称为死锁进程.由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了死锁。二、关于死锁的一些结论:参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。三、资源分类：永久性资源：可以被多个进程多次使用（可再用资源）1）可抢占资源2）不可抢占资源临时性资源：只可使用一次的资源；如信号量，中断信号，同步信 号等（可消耗性资源）“申请-分

3、配-使用-释放”模式四、产生死锁的四个必要条件：1、互斥使用（资源独占）一个资源每次只能给一个进程使用2、不可强占（不可剥夺）资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放3、请求和保持（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有资源的占有 （只有这 样才是动态申请，动态分配）4、循环等待存在一个进程等待队列P1 , P2 ,其中P1等待P2占有的资源，P2等待P3占有的资源，Pn等待P1占有的资源，形成一 个进程等待环路。五、死锁的解决方案5.1产生死锁的例子申请不同类型资源产生死锁P1：申请打印机申请扫描仪使用释放打印机释放扫描仪P2：申请扫描仪申请

4、打印机使用释放打印机释放扫描仪申请同类资源产生死锁（如内存）设有资源R, R有m个分配单位，由n个进程P1,P2,PQn m） 共享。假设每个进程对 R的申请和释放符合下列原则：* 一次只能申请一个单位*满足总申请后才能使用 *使用完后一次性释放m=2, n=3资源分配不当导致死锁产生5.2死锁预防：1摒弃“请求和保持”2摒弃“不剥夺”条件3.摒弃“环路等待”5.3安全状态与不安全状态 ：安全状态：如果操作系统能保证所有的进程在 有限的时间 内 得到需要的 全部资源，则称系统处于“安全状态”。3、数据结构设计一、可利用资源向量矩阵 AVAILABLE这是一个含有M个元素的数组，其中的每一个元素

5、代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目， 其数值随该类资源的分配和 回收而动态地改变。如果 AVAILABLE j= K，则表示系统中现有 R 类资源K个二、最大需求矩阵 MAX这是一个N*M的矩阵，用以表示每一个 进程对M类资源的最大需求。如果 MAX i,j=K，则表示进程I需要 R类资源的数目为K。三、分配矩阵ALLOCATION这也是一个N*M的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果ALLOCATIONi,j=K ，则表示进程i当前已分得R类资源的数目为K。四、需求矩阵NEED这也是一个n*m的矩阵，用以表示每一个进 程尚需的

6、各类资源数。如果 NEED i,j=K，则表示进程i还需要R 类资源K个，才能完成其任务。上述矩阵存在下述关系：NEED i,j= MAXi,j - ALLOCATIONi,j4、算法的实现一、初始化由用户输入数据，分别对可利用资源向量矩阵 AVAILABLE最大需求矩阵MAX分配矩阵ALLOCATION需求矩阵NEED武值。二、银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人 满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状 态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前，判断系统是否是安全的； 若是,才分配。它是最具

7、有代表性的避免死锁的算法。设进程cusneed提出请求REQUEST i，则银行家算法按如下规则进行判断。如果 REQUESCusneed i allocij; /*初始化alloc*/int main (i nt argc, char* argv) int l,J,i,i1,j, n,sig n;intavail10,max1010,alloc1010, need1010,requ1010,work10,fi ni sh10；cout请输入进程数和资源数，以空格分开：；cinIJ;for(i=0;il;i+)for(j=0;jJ;j+)cout请输入进程i对资源jmaxij;/*初始化 ma

8、x*/for(i=0;iI;i+)for(j=0;jJ;j+)cout请输入进程i已分配到资源j的数量：for(i=0;il;i+)for(j=0;jJ;j+)cout请输入进程i还需要资源jneedij; /*初始化 need*/for(j=0;jJ;j+)cout资源javailj;/*初始化 avail*/START/* 用安全性算法判断系统初始化后的当前状态是否安全*/for(j=0;jJ;j+)workj=availj;for(i=0;il;i+)finishi=O;/*设置两个工作向量*/A1: for(i=0;il;i+)sign=1;/*sign=1表示 need=work*/

9、for(j=0;jworkj)sig n=0;if(fin ishi=O&sig n=1)for(j=0;jJ;j+)workj=workj+allocij;finishi=1;/*设置 finish 向量 */coutPiendl; /*输出安全序列 */ goto A1;cout请输入进程i请求的资源j的数量:sig n=1;/*判断系统状态是否安全*/for(i=0;il;i+)if(fin ishi=O)sig n=0;if(sig n=0)cout当前系统处于不安全状态.endl;elsecout当前系统处于安全状态，可以接受资源请求.endl;/*用安全性算法判断系统初始化后的当前

10、状态是否安全END */*设置请求向量 START */S: cout i; i1=i;for(j=0;j requij;/*进程请求资源*/for(j=0;j needij)cout错误！请求数超过需要数！endl;goto S;for(j=0;javailj)cout可利用资源不足，无法分配。endl;goto S;/*设置请求向量END */for(j=0;jJ;j+)/*系统尝试分配资源*/availj=availj_requij;allocij=allocij+requij;全性算法 START*设置两个工作向量*/*for(j=0;jJ;j+)workj=availj;for(i=

11、0;iI;i+)fin ishi=O;/*A2: for(i=0;il;i+)sign=1;/*sign=1表示 need=work*/for(j=0;jworkj)sig n=0;if(fin ishi=O&sig n=1)needi1j=needi1j+requi1j;for(j=0;jJ;j+)workj=workj+allocij;finishi=1;/*设置 finish 向量 */coutPiendl; /* 输出安全序列 */ goto A2;sig n=1;for(i=0;il;i+)if(fin ishi=0)sig n=0;/*判断系统状态是否安全*/if(sig n=0)

12、cout不安全，系统已收回尝试分配的资源！endl;/*若不安全，不予分配，并将数据修改回原来的值*/for(j=0;jJ;j+)availj=availj+requi1j;alloci1j=alloci1j-requi1j;goto S；elsecout安全，可以分配.1- 3状态b不安全，只剩1个可用资源，收不回已分配资源。(2)考虑下列系统状态分配矩阵最大需求矩阵可用资源矩阵0 0 1 20 0 1 21 5 2 01 0 0 01 7 5 01 3 5 42 3 5 60 6 3 20 6 5 20 0 1 40 6 5 6问系统是否安全？若安全就给出所有的安全序列。若进程2请求(0420)，可否立即分配?答：安全。安全序