操作系统课程设计报告

操作系统课程设计报告

指导教师：潘煜学号：070603115姓名：张鑫班级：070603学期：2009至2010学年1学期1、概述一、设计目的1.对死锁避免中的银行家算法作进一步理解。2.加深理解死锁的概念。3.加深理解安全序列和安全状态的概念。4.通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。二、开发环境

操作系统Windowsxp编译环境VC++6.0生成文件银行家算法.cpp2、需求分析一、死锁概念：是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去.此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程.

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

可抢占资源2）

不可抢占资源临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）“申请--分配--使用--释放”模式产生死锁的四个必要条件：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死锁预防:摒弃“请求和保持”摒弃“不剥夺”条件摒弃“环路等待”5.3安全状态与不安全状态：安全状态:如果操作系统能保证所有的进程在有限的时间内得到需要的全部资源，则称系统处于“安全状态”。3、数据结构设计一、可利用资源向量矩阵AVAILABLE。这是一个含有M个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果AVAILABLE[j]=K，则表示系统中现有R类资源K个二、最大需求矩阵MAX。这是一个N*M的矩阵，用以表示每一个进程对M类资源的最大需求。如果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]=MAX[i,j]﹣ALLOCATION[i,j]

4、算法的实现初始化由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求REQUEST[i]，则银行家算法按如下规则进行判断。(1)如果REQUEST[cusneed][i]<=NEED[cusneed][i]，则转(2)；否则，出错。(2)如果REQUEST[cusneed][i]<=AVAILABLE[cusneed][i]，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：

AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。三、安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO2(4)如所有的进程Finish=true，则表示安全；否则系统不安全。四、各算法流程图初始化算法流程图：银行家算法流程图：源程序清单#include"iostream.h"intmain(intargc,char*argv[]){ intI,J,i,i1,j,n,sign; intavail[10],max[10][10],alloc[10][10],need[10][10],requ[10][10],work[10],finish[10]; cout<<"请输入进程数和资源数，以空格分开:"; cin>>I>>J; for(i=0;i<I;i++) { for(j=0;j<J;j++) { cout<<"请输入进程"<<i<<"对资源"<<j<<"的最大需求量："; cin>>max[i][j];/*初始化max*/ } } for(i=0;i<I;i++) { for(j=0;j<J;j++) { cout<<"请输入进程"<<i<<"已分配到资源"<<j<<"的数量："; cin>>alloc[i][j];/*初始化alloc*/ } } for(i=0;i<I;i++) { for(j=0;j<J;j++) { cout<<"请输入进程"<<i<<"还需要资源"<<j<<"的数量："; cin>>need[i][j];/*初始化need*/ } } for(j=0;j<J;j++) { cout<<"资源"<<j<<"可利用数量："; cin>>avail[j];/*初始化avail*/ }/*************用安全性算法判断系统初始化后的当前状态是否安全START************/ for(j=0;j<J;j++) { work[j]=avail[j]; } for(i=0;i<I;i++) { finish[i]=0;/*设置两个工作向量*/ }A1: for(i=0;i<I;i++) { sign=1;/*sign==1表示need<=work*/ for(j=0;j<J;j++) { if(need[i][j]>work[j]) { sign=0; } } if(finish[i]==0&&sign==1) { for(j=0;j<J;j++) { work[j]=work[j]+alloc[i][j]; } finish[i]=1;/*设置finish向量*/ cout<<"P"<<i<<endl;/*输出安全序列*/ gotoA1; } } sign=1;/*判断系统状态是否安全*/ for(i=0;i<I;i++) { if(finish[i]==0) sign=0; } if(sign==0) { cout<<"当前系统处于不安全状态."<<endl; } else { cout<<"当前系统处于安全状态，可以接受资源请求."<<endl; }/*************用安全性算法判断系统初始化后的当前状态是否安全END************//***********************设置请求向量START***********************/S: cout<<"请输入请求资源的进程的进程号："; cin>>i;i1=i; for(j=0;j<J;j++) { cout<<"请输入进程"<<i<<"请求的资源"<<j<<"的数量："; cin>>requ[i][j]; /*进程请求资源*/ } for(j=0;j<J;j++) { if(requ[i][j]>need[i][j]) { cout<<"错误！请求数超过需要数！"<<endl; gotoS; } } for(j=0;j<J;j++) { if(requ[i][j]>avail[j]) { cout<<"可利用资源不足，无法分配。"<<endl; gotoS; } }/***********************设置请求向量END***********************/ for(j=0;j<J;j++) { avail[j]=avail[j]-requ[i][j];/*系统尝试分配资源*/ alloc[i][j]=alloc[i][j]+requ[i][j]; need[i][j]=need[i][j]-requ[i][j]; }/*************************安全性算法START****************************/ for(j=0;j<J;j++) { work[j]=avail[j]; } for(i=0;i<I;i++) { finish[i]=0;/*设置两个工作向量*/ }A2: for(i=0;i<I;i++) { sign=1;/*sign==1表示need<=work*/ for(j=0;j<J;j++) { if(need[i][j]>work[j]) { sign=0; } } if(finish[i]==0&&sign==1) { for(j=0;j<J;j++) { work[j]=work[j]+alloc[i][j]; } finish[i]=1;/*设置finish向量*/ cout<<"P"<<i<<endl;/*输出安全序列*/ gotoA2; } } sign=1; for(i=0;i<I;i++) { if(finish[i]==0) sign=0;/*判断系统状态是否安全*/ } if(sign==0) { cout<<"不安全，系统已收回尝试分配的资源！"<<endl;/*若不安全，不予分配，并将数据修改回原来的值*/ for(j=0;j<J;j++) { avail[j]=avail[j]+requ[i1][j]; alloc[i1][j]=alloc[i1][j]-requ[i1][j]; need[i1][j]=need[i1][j]+requ[i1][j]; } gotoS; } else { cout<<"安全，可以分配."<<endl;/*若安全，则可以分配*/ gotoS; }/*************************安全性算法END****************************/ return0;}5、结束语心得与体会：银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。银行家算法是为了使系统保持安全状态。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占有；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，单它仍继续宝石已得到的所有其他资源；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题，如银行贷款等。银行家算法能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。经过这次设计，让我基明白了银行家算法的基本原理，加深了对课堂上知识的理解，也懂得了如何让银行家算法实现。实例：（1）下列状态是否安全？(三个进程共享12个同类资源)进程

已分配资源数

最大需求数1

1

4

(状态a)2

4

43

5

8

1

1

4

(状态b)2

4

63