操作系统课程设计报告21

1、 操作系统课程设计 1、概述一、设计目的1、了解多道程序系统中，多个进程并发执行的资源分配。 2、掌握死锁的产生的原因、产生死锁的必要条件和处理死锁的基本方法。 3、掌握预防死锁的方法，系统安全状态的基本概念。 4、掌握银行家算法，了解资源在进程并发执行中的资源分配策略。 5、理解死锁避免在当前计算机系统不常使用的原因二、开发环境操作系统编译环境生成文件windows vista vc+6.0bank for windows.exe源文件：bank.c2、需求分析避免多道程序系统中程序的死锁。一、死锁概念：在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量

2、，但可能发生一种危险死锁。所谓死锁(deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(deadly_embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。二、关于死锁的一些结论： 参与死锁的进程最少是两个（两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 三、资源分类：

3、 永久性资源： 可以被多个进程多次使用（可再用资源） l 可抢占资源 l 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请-分配-使用-释放”模式 四、产生死锁的四个必要条件：1、互斥使用（资源独占） 一个资源每次只能给一个进程使用 2、不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放 3、请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配） 4、循环等待 存在一个进程等待队列 p1 , p2 , , pn, 其中p1等待p2占有的资源

4、，p2等待p3占有的资源，pn等待p1占有的资源，形成一个进程等待环路 5、 死锁的解决方案 5.1 产生死锁的例子 申请不同类型资源产生死锁 p1： 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 p2： 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 申请同类资源产生死锁（如内存） 设有资源r，r有m个分配单位，由n个进程p1,p2,pn（n m）共享。假设每个进程对r的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放 m=2，n=3 资源分配不当导致死锁产生 5.2死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死

5、锁。具体的做法是破坏产生死锁的四个必要条件之一 破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配 破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。6安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列p1，pn，则系统处于安全状态。一个进程序列p1，p

6、n是安全的，如果对于每一个进程pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程pj (j i )当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的) 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。3、数据结构设计 一、可利用资源向量矩阵available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果available j= k，则表示系统中现有r类资源k个二、最大需求矩阵max。这是一个n*m的矩阵，用以表示每一个进程对m类资

7、源的最大需求。如果max i,j=k，则表示进程i需要r类资源的数目为k。三、分配矩阵allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果allocation i,j=k，则表示进程i当前已分得r类资源的数目为k。四、需求矩阵need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果need i,j=k，则表示进程i还需要r类资源k个，才能完成其任务。 上述矩阵存在下述关系： need i,j= maxi,j allocationi,j4、算法的实现一、初始化由用户输入数据，分别对可利用资源向量矩阵available、最大需求

8、矩阵max、分配矩阵allocation、需求矩阵need赋值。二、银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求request i，则银行家算法按如下规则进行判断。(1)如果request cusneed i= needcusneedi，则转(2)；否则，出错。(2)如果request cusneed i= available

9、cusneedi，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据： availablei-=requestcusneedi; allocationcusneedi+=requestcusneedi; needcusneedi-=requestcusneedi;(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。三、安全性检查算法(1)设置两个工作向量work=available;finish(2)从进程集合中找到一个满足下述条件的进程，finish=false;need=work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可

10、顺利执行，直至完成，从而释放资源。work+=allocation;finish=true;goto 2(4)如所有的进程finish= true，则表示安全；否则系统不安全。四、各算法流程图 初始化算法流程图：银行家算法流程图：安全性算法流程图：四、源程序清单#define m 50int maxmm, allocationmm,needmm,availablem; /*定义全局变量*/int i, j, n, m, r;main() void check(); void print(); int p,q; int reqm, allocation1mm,need1mm,available1

11、m; printf(输入进程总数:); scanf(%d, &n); /*输入进程总数*/ printf(输入资源种类总数:); scanf(%d, &m); /*输入资源种类总数*/ printf(输入最大矩阵:); for(i=0;in; i+) for(j=0;jm; j+) scanf(%2d,&maxij); /*输入最大矩阵*/ printf(输入已分配资源数 :); for(i=0;in; i+) for(j=0;jm; j+) scanf(%d, &allocationij); /*输入已分配资源数*/ printf(输出还需要的资源数:); for (i=0;in; i+)

12、for(j=0;jm; j+) needij=maxij-allocationij; printf(%2d,needij); /*输出还需要的资源数*/ printf(n输入可用资源数 :); for (i=0;im; i+) scanf(%d, &availablei); /*输入可用资源数*/ check(); /*检测已知的状态是否安全*/ if (r=1) /*如果已知的状态安全则执行以下代码*/ do p=0,q=0; printf(n输入请求资源的进程号: ); scanf(%d, &i); /*输入请求资源的进程号*/ printf(输入该进程所需的资源数:); for(j=0;

13、jm; j+) scanf(%d,&reqj); /*输入该进程所需的资源数 */ for(j=0;jneedij) p=1; /*判断请求是否超过最大资源数*/ if(p) printf(n请求超过最大资源数!); else for(j=0;javailablej) q=1; /*判断请求是否超过可用资源数 */ if(q) printf(n请求超过可用资源数!); else for(j=0;jm; j+) /*请求满足条件 */ available1j=availablej; /* 保存原已分配的资源数，需要的资源数，和可用的资源数*/ allocation1ij=allocationij

14、; need1ij=needij; availablej=availablej-reqj; /* 系统尝试把资源分配给请求的进程 */ allocationij=allocationij+reqj; needij=needij-reqj; print(); /*输出可用资源数*/ check(); /*进行安全检测*/ if(r=0) /*分配后状态不安全*/ for (j=0;jm; j+) availablej=available1j; /* 还原分配前的已分配的资 源数，仍需要的资源数和可用的资源数 */ allocationij=allocation1ij; needij=need1i

15、j; printf( 不安全 返回:n); print(); printf(n是否继续进行资源分配? y or n ?n); /*判断是否继续进行资源分配*/ while (getch()=y); void check() /*检测函数 */ int k, f, v=0; int workm,am; char finishm; r=1; for(i=0;in; i+) finishi=f; /*初始化各进程均没得到足够资源并完成*/ for(j=0;jm; j+) workj=availablej; /*用workj表示可提供进程继续运行的各类资源数 */ k=n; do for (i=0;i

16、n; i+) if (finishi=f) f=1; for (j=0;jworkj) f=0; if (f=1) /*找到还没完成的且需求数小于可提供进程继续运行的*/ finishi=t; /*资源数的进程*/ av+=i; /*记录安全序列 */ for (j=0;j0); f=1; for (i=0;in; i+) /*判断是否所有的进程都完成*/ if (finishi=f) f=0; break; if (f=0) /*若有进程没完成，则为不安全状态*/ printf(不安全状态 . n); r=0; else /* 否则为安全状态*/ printf(安全状态.); printf(

17、 输出安全序列:); for (i=0;in;i+) printf (%d ,ai); /*输出安全序列*/ printf(n); for (i=0;in; i+) printf(%2d,i); printf( ); for(j=0;jm; j+) printf(%2d,allocationij); printf( ); for(j=0;jm; j+) printf(%2d,needij); printf(n); void print() /*输出函数*/ int processm; printf(可用资源数: n); for(j=0;jm; j+) printf(%2d ,availablej); printf(n); 5、结束语心得与体会：银行家算法能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。对于较少实际编程的我来说，编写银行家算法具有较大难度。但是在仔细研究并且与同学讨论后，得出正确程序。开始时在编写系统试分配时有些问题，在系统试分配后不安全的情况