yinhangjia.txt

一个操作系统的课程设计,C++的,银行家算法

计算机操作系统课程设计

班级  04计算机*班 姓名  张*  学号 04103074**  

课程设计起止日期     2007.01.20-2007.01.24     

实习地点     赛博北楼305（嵌入式系统实验室）   

课程设计题目      共享资源分配与银行家算法     

一、课程设计目的和意义

此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。

具体用银行家算法实现资源分配。要求如下：

(1) 设计一个3个并发进程共享3类不同资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。

(2) 设计用银行家算法和随机分配算法，实现资源分配的两个资源分配程序，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。

(3) 确定一组各进程依次申请资源数的序列，在相同的情况下分别运行上述两种资源分配程序，观察运行结果。

银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等.

通过对这个算法的设计,让学生能够对书本知识有更深的理解,在操作和其它方面有更高的提升.

二、方案设计及开发过程

随机分配算法:当进程申请资源时，如果系统中现存资源数能满足进程的当前资源申请量，就把资源能会产生死锁。随机分配算法很容易进入死锁.

银行家分配算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，个进程都无法继续执行下去的死锁现象。

把个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁.


2.算法描述


随机分配算法:

设进程I提出请求Request[N]，则银行家算法按如下规则进行判断

(1)  如果Request[N]<=AVAILABLE，则转(2)；否则，出错。

(2)  系统分配资源，修改相关数据：

AVAILABLE=AVAILABLE-REQUEST 
ALLOCATION=ALLOCATION+REQUEST 
NEED=NEED-REQUES

(3)  系统执行安全性检查

银行家算法: 
设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。 
(1)如果Request[N]<=NEED[I，N]，则转(2)；否则，出错。 
(2)如果Request[N]<=AVAILABLE，则转(3)；否则，出错。 
(3)系统试探分配资源，修改相关数据： 
AVAILABLE=AVAILABLE-REQUEST 
ALLOCATION=ALLOCATION+REQUEST 
NEED=NEED-REQUEST 
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 
3．安全性检查 
(1)设置两个工作向量WORK=AVAILABLE；FINISH[M]=FALSE 
(2)从进程集合中找到一个满足下述条件的进程， 
FINISH[i]=FALSE 
NEED<=WORK 
如找到，执行(3)；否则，执行(4) 
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 
WORK=WORK+ALLOCATION 
FINISH=TRUE 
GO TO 2 
(4)如所有的进程Finish[M]=true，则表示安全；否则系统不安全。 



3.数据结构

假设有M个进程N类资源，则有如下数据结构:

#define W 10

#define R 20

int M ;                     //总进程数

int N ;                    //资源种类 

int ALL_RESOURCE[W];       //各种资源的数目总和

int MAX[W][R];            //M个进程对N类资源最大资源需求量

int AVAILABLE[R];         //系统可用资源数

int ALLOCATION[W][R];     //M个进程已经得到N类资源的资源量

int NEED[W][R];           //M个进程还需要N类资源的资源量

int Request[R];           //请求资源个数


4.主要函数说明

void showdata();          //主要用来输出资源分配情况

void changdata(int);      //主要用来输出资源分配后后的情况

void rstordata(int);      //用来恢复资源分配情况,如:银行家算法时,由于分配不安全

则要恢复资源分配情况

int chkerr(int);          //银行家分配算法的安全检查

int chkerr2(int) ;        //随机分配算法安全检查

void bank()  ;            //银行家算法

void randomallocation();  //随机分配算法
 



#include "string.h" 

#include "iostream"

using namespace std;


#define FALSE 0 

#define TRUE 1 


#define W 10

#define R 20

int M ; //总进程数

int N ; //资源种类 

int ALL_RESOURCE[W];//各种资源的数目总和

int MAX[W][R]; //M个进程对N类资源最大资源需求量

int AVAILABLE[R]; //系统可用资源数

int ALLOCATION[W][R]; //M个进程已经得到N类资源的资源量

int NEED[W][R]; //M个进程还需要N类资源的资源量

int Request[R]; //请求资源个数


void showdata() //函数showdata,输出资源分配情况

{ 

int i,j; 

cout<<"各种资源的总数量(all):"<<endl; 

cout<<" "; 

for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<ALL_RESOURCE[j]; 

cout<<endl<<endl; 

cout<<"系统目前各种资源可用的数为(available):"<<endl; 

cout<<" "; 

for (j=0;j<N;j++)cout<<" 资源"<<j<<": "<<AVAILABLE[j]; 

cout<<endl<<endl; 


cout<<" 各进程还需要的资源量(need):"<<endl<<endl; 


cout<<"       资源"<<"     资源"<<"    资源"<<endl;

for (i=0;i<M;i++) 

for (i=0;i<M;i++) 

{ 

cout<<"进程p"<<i<<":   "; 

for (j=0;j<N;j++)cout<<NEED[i][j]<<"        ";; 

cout<<endl; 

} 

cout<<endl; 

cout<<" 各进程已经得到的资源量(allocation): "<<endl<<endl; 

cout<<"       资源"<<"     资源"<<"     资源"<<endl;

for (i=0;i<M;i++) 

{ 

cout<<"进程p"<<i<<":    "; 

for (j=0;j<N;j++)cout<<ALLOCATION[i][j]<<"       "; 

cout<<endl; 

} 

cout<<endl; 

}; 


void changdata(int k) //函数changdata,改变可用资源和已经拿到资源和还需要的资源的值

{ 

int j; 

for (j=0;j<N;j++) 

{ 

AVAILABLE[j]=AVAILABLE[j]-Request[j]; 

ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; 

NEED[k][j]=NEED[k][j]-Request[j]; 

} 

}; 


void rstordata(int k) //函数rstordata,恢复可用资源和已经拿到资源和还需要的资源的值

{ 

int j; 

for (j=0;j<N;j++) 

{ 

AVAILABLE[j]=AVAILABLE[j]+Request[j]; 

ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; 

NEED[k][j]=NEED[k][j]+Request[j]; 

} 

}; 


int chkerr(int s) //函数chkerr,检查是否安全

{ 

int WORK,FINISH[W],temp[R]; 

int i,j,k=0; 

for(i=0;i<M;i++)FINISH[i]=FALSE; 

for(j=0;j<N;j++) 

{ 

WORK=AVAILABLE[j]; 

i=s; 

while(i<M) 

{ 

if (FINISH[i]==FALSE&&NEED[i][j]<=WORK) 

{ 

WORK=WORK+ALLOCATION[i][j]; 

FINISH[i]=TRUE; 

temp[k]=i; 

k++; 

i=0; 

} 

else 

{ 

i++; 

} 

} 

for(i=0;i<M;i++) 

if(FINISH[i]==FALSE) 

{ 

cout<<endl; 

cout<<" 系统不安全!!! 本次资源申请不成功!!!"<<endl; 

cout<<endl; 

return 1; 

} 

} 

cout<<endl; 

cout<<" 经安全性检查，系统安全，本次分配成功。"<<endl; 

cout<<endl; 

cout<<" 本次安全序列："; 

for(i=0;i<M;i++)cout<<"p"<<temp[i]<<"->"; 

cout<<endl<<endl;

return 0; 

}





 
int chkerr2(int s) //函数chkerr2,检查是否安全

{ 

int WORK,FINISH[W],temp[R]; 

int i,j,k=0; 

for(i=0;i<M;i++)FINISH[i]=FALSE; 

for(j=0;j<N;j++) 

{ 

WORK=AVAILABLE[j]; 

i=s; 

while(i<M) 

{ 

if (FINISH[i]==FALSE&&NEED[i][j]<=WORK) 

{ 

WORK=WORK+ALLOCATION[i][j]; 

FINISH[i]=TRUE; 

temp[k]=i; 

k++; 

i=0; 

} 

else 

{ 

i++; 

} 

} 

for(i=0;i<M;i++) 

if(FINISH[i]==FALSE) 

{ 

cout<<endl; 

cout<<" 本次资源申请成功!!!但系统不安全!!! "<<endl; 

cout<<endl; 

return 1; 

} 

} 

cout<<endl; 

cout<<" 经安全性检查，系统安全，本次分配成功。"<<endl; 

cout<<endl; 

cout<<" 本次安全序列："; 

for(i=0;i<M;i++)cout<<"p"<<temp[i]<<"->"; 

cout<<endl<<endl;

return 0; 

}


void   bank()   //银行家算法

{

     int i=0,j=0; 

     char flag='Y'; 

     

     while(flag=='Y'||flag=='y') 

{ 

i=-1; 

while(i<0||i>=M) 

{ 

cout<<" 请输入需申请资源的进程号（从P0到P"<<M-1<<"，否则重输入!）:"; 

cout<<"p";cin>>i; 

if(i<0||i>=M)cout<<" 输入的进程号不存在，重新输入!"<<endl; 

} 

cout<<" 请输入进程P"<<i<<"申请的资源数:"<<endl; 

for (j=0;j<N;j++) 

{ 

cout<<" 资源"<<j<<": "; 

cin>>Request[j]; 

if(Request[j]>NEED[i][j]) 

{ 

cout<<" 进程P"<<i<<"申请的资源数大于进程P"<<i<<"还需要"<<j<<"类资源的资源量!"; 

cout<<"申请不合理，出错!请重新选择!"<<endl<<endl; 

flag='N'; 

break; 

} 

else 

{ 

if(Request[j]>AVAILABLE[j]) 

{ 

cout<<" 进程P"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!"; 

cout<<"申请不合理，出错!请重新选择!"<<endl<<endl; 

flag='N'; 

break; 

} 

} 

} 

if(flag=='Y'||flag=='y') 

{ 

changdata(i); 

if(chkerr(i)) 

{ 

rstordata(i); 

showdata(); 

} 

else 

showdata(); 

} 

else 

showdata(); 

cout<<endl; 

cout<<" 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: "; 

cin>>flag; 

} 


}


 
void randomallocation()   //随机分配算法

{

int i=0,j=0; 

     char flag='Y'; 

     

     while(flag=='Y'||flag=='y') 

{ 

  i=-1; 

  while(i<0||i>=M) 

   { 

        cout<<" 请输入需申请资源的进程号（从P0到P"<<M-1<<"，否则重输入!）:"; 

        cout<<"p";cin>>i; 

        if(i<0||i>=M)cout<<" 输入的进程号不存在，重新输入!"<<endl; 

    } 

   cout<<" 请输入进程P"<<i<<"申请的资源数:"<<endl; 

   for (j=0;j<N;j++) 

    { 

         cout<<" 资源"<<j<<": "; 

         cin>>Request[j]; 

         if(Request[j]>AVAILABLE[j]) 

        { 

             cout<<" 进程P"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!";