银行家算法实习报告

1、精选优质文档-倾情为你奉上青 岛 农 业 大 学学 生 实 习 报 告实 习 名 称： 软件系统课程设计 实 习 时 间： 2010 - 2011 学年 第 2学期 专 业 班 级 ： 姓名（学号）： 同 组 成 员 ： 指 导 老 师： 于仁师 2011 年 3 月 22 日（一）编译原理部分一、实习题目将词法分析器设计成单独的程序或供语法分析器调用的子程序,功能包括：要求能够识别数字、标识符、关键字、运算符等。二、设计思路及算法描述词法分析程序的功能：输入源程序，输出单词符号，如图所示：词法分析器源程序单词符号处理过程：在扫描源程序字符串时，一旦识别出关键字、分隔符、标识符、无符号常数中之

2、一，即以单词形式（各类单词均采用相同的结构，即二元式编码形式）输出。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。本程序规定：(1)关键字begin,end,if,then,else,while,write,read,do, call,const,char,until,procedure,repeat(2)运算符：+,-,*,/,=(3)界符：,;,.,(,),:(4)其他标记 如字符串，表示以字母开头的标识符。(5)空格、回车、换行符跳过。对于一段可能的输入代码，其结果在屏幕上显示如下：( 1 , 无符号整数)( b

3、egin , 关键字 )( if , 关键字 )( +, 运算符 )( ； , 界符 )( a , 普通标识符 )关键字或标识符的判断：读入一串字符，将ASCII码在字母范围的字符存入数组中，将该数组与设置好的关键字比较，如果相等则输出是关键字，否则继续读入直至下一字符既非数字也非字母，输出为标识符；数字的判断：若跟在字母后面则一起输出为标识符，否则输出为数字；界符、运算符的判断：直接判断其ASCII码运行过程为：1预处理：把源文件一个字符一个字符的读入词法分析程序设置的输入字符结构体数组中（输入缓冲区），读入过程要删除多余的空格；2源程序字符数组中获得单词, 编码为二元式.：二元式采用结构体

4、数组存储, 把单词类型和词元记录下来。 为了方便和适用起见，首先建立一个文本，进而在文本中进行pascal语言输入。输入完毕之后，就可以进行从文本中取字符，进而把它放在一个数组中。之后再数组中进行取字符，之前要定义一个数组，定义一个指针指向数组，为first。之后就用一个循环依次从数组中取字符，假如是字符就放在buf中，first+；一次进行下去，期间要时刻与关键字指针数组进行比较如果相等就立马输出，并显示是关键字此时将buf置为初值，first重新指向首地址。流程图读取字符输出”关键字”是关键字是不可显示符输出”标识符”YNYNY是字母或数字是字母读取字符Y NY是数字输出”常数”是数字N读

5、取字符NN是界符Y输出”界符”ERROR是=是：读取字符NNY输出”运算符”是 运算YNERROR三、程序代码：#include /其中#includeusing namespace std;#defineMAX 22char ch = ;string key15=begin,end,if,then,else,while,write,read,do, call,const,char,until,procedure,repeat;int Iskey(string c)/关键字判断int i;for(i=0;iMAX;i+) if(pare(c)=0) return 1;retur

6、n 0;int IsLetter(char c) /判断是否为字母if(c=a)|(c=A) return 1;else return 0;int IsDigit(char c)/判断是否为数字if(c=0&c=9) return 1;else return 0;void fenxi(FILE *fpin)string arr=;while(ch=fgetc(fpin)!=EOF) arr=;if(ch= |ch=t|ch=n)else if(IsLetter(ch)while(IsLetter(ch)|IsDigit(ch) if(ch=A) ch=ch+32;arr=arr+ch;ch=f

7、getc(fpin);fseek(fpin,-1L,SEEK_CUR);if (Iskey(arr)coutarrt$关键字endl;elsecoutarrt$普通标识符endl;else if(IsDigit(ch)while(IsDigit(ch)|ch=.&IsDigit(fgetc(fpin)arr=arr+ch;ch=fgetc(fpin);fseek(fpin,-1L,SEEK_CUR);coutarrt$无符号实数endl;else switch(ch)case+:case- :case* :case= :case/ :coutcht$运算符endl;break;case( :c

8、ase) :case :case :case; :case. :case, :case :case :coutcht$界符endl;break;case: :ch=fgetc(fpin);if(ch=) cout:=t$运算符endl;else cout=t$运算符 :ch=fgetc(fpin);if(ch=) cout=t$运算符)coutt$输入控制符endl;else coutt$运算符endl;fseek(fpin,-1L,SEEK_CUR);break;case :ch=fgetc(fpin);if(ch=)cout=t$运算符endl;else if(ch=)coutt$输出控制

9、符) coutt$运算符endl;elsecoutt$运算符endl;fseek(fpin,-1L,SEEK_CUR);break;default : coutcht$无法识别字符endl;void main()char in_fn30;FILE * fpin;coutin_fn;if(fpin=fopen(in_fn,r)!=NULL) break;else cout文件路径错误！请输入源文件名（包括路径和后缀名）:;coutn*分析如下*endl;fenxi(fpin);fclose(fpin);四、运行结果现将要处理的代码段保存于文件中，在本程序中，我保存的位置是G:1.txt，文件内容

10、如下图所示：点击运行程序，其分析结果如下：（二）操作系统部分一、实习题目用银行家算法实现资源分配二、设计思路及算法描述已知进程P0,P1,P2,P3,P4，有三类系统资源A、B、C的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示：（1）若进程P1请求资源，发出请求向量Request1（1，0，2），编写程序用银行家算法判断系统能否将资源分配给它；（2）若进程P3提出请求Request(1，1，2)，用银行家算法程序验证系统能否将资源分配给它。数据结构:1.可利用资源向量Available2.最大需求矩阵Max3.分配矩阵Allocation4.需求矩阵Need功能介绍:模拟实现Di

11、jkstra的银行家算法以避免死锁的出现.分两部分组成:第一部分:银行家算法(扫描)1如果Request=Need,则转向2;否则,出错2如果Request=Available,则转向3,否则等待3系统试探分配请求的资源给进程4系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finishi=False&Need=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资

12、源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finishi=true;转24. 若所有进程的Finishi=true,则表示系统安全;否则,不安全!三、程序代码：#include #include #define M 5 /*M个进程,N个资源*/#define N 3int AVAILABLEN; /*可用资源数组*/int MAXMN; /*最大需求矩阵*/int ALLOCATIONMN; /*分配矩阵*/int NEEDMN; /*需求矩阵*/int REQUESTMN; /*进程需要资源数*/bool FINISHM; /*系统是否有足够的资源分配*

13、/int pM; /*记录序列*/void Init();bool Safe();void Banker();void Output();void main() Init(); Safe(); Banker();void Init() /*初始化算法*/ int i,j; cout请输入每个进程最多所需的各资源数,按照MxN矩阵输入:endl; for(i=0;iM;i+)for(j=0;jMAXij;cout请输入每个进程已分配的各资源数,按照MxN矩阵输入:endl;for(i=0;iM;i+)for(j=0;jALLOCATIONij;NEEDij=MAXij-ALLOCATIONij;

14、if(NEEDij0)cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl;j-;continue;cout请输入各个资源现有的数目:endl;for(i=0;iAVAILABLEi;void Banker() /*银行家算法*/ int i,pneed; char flag; while(1) cout请输入要申请资源的进程号(注:第1个进程号为0,依次类推)pneed; cout请输入进程所请求的各资源的数量endl; for(i=0;iREQUESTpneedi; for(i=0;iNEEDpneedi) cout您输入的对i进程的请求数超过进程的需求量!请重

15、新输入!AVAILABLEi) cout您输入的对i进程的请求数超过系统有的资源数!请重新输入!endl; continue; for(i=0;iN;i+) AVAILABLEi-=REQUESTpneedi; ALLOCATIONpneedi+=REQUESTpneedi; NEEDpneedi-=REQUESTpneedi; if(Safe() cout同意分配请求!endl; else cout您的请求被拒绝!endl; for(i=0;iN;i+) AVAILABLEi+=REQUESTpneedi; ALLOCATIONpneedi-=REQUESTpneedi; NEEDpneed

16、i+=REQUESTpneedi; for(i=0;iM;i+) FINISHi=false; cout您还想再次请求分配吗?是请按y/Y,否请按其它键flag; if(flag=y|flag=Y) continue; break;void Output() /*输出*/int i,j;cout资源分配表：endl进程名 Max Allocation Need Availableendl;for (i=0;iM;i+)coutPi: ;for (j=0;jN;j+)coutsetw(2)MAXij ;cout ;for (j=0;jN;j+)coutsetw(2)ALLOCATIONij ;c

17、out ;for (j=0;jN;j+)coutsetw(2)NEEDij ;cout ;if(i=0)for (j=0;jN;j+)coutsetw(2)AVAILABLEj ;coutendl;bool Safe() /*安全性算法*/ int i,j,k,l=0; int WorkN; /*工作数组*/ for(i=0;iN;i+)Worki=AVAILABLEi; for(i=0;iM;i+) FINISHi=false; cout安全性：endl进程名 Work Need Allocation W+A Finishendl; for(i=0;iM;i+) if(FINISHi=true) continue; else for(j=0;jWorkj) break; if(j=N) FINISHi=true;coutPi: ;for (int z=0;zN;z+)coutsetw(2)Workz ;cout ;for (z=0;zN;z+)coutsetw(2)NEEDiz ;cout ;for (z=0;zN;z+)coutsetw(2)ALLOCATIONiz ;cout ; for(k=0;kN;k+) Workk+=ALLOCATIONik; for (z=0;zN;z+)coutsetw(2)Workz ;cout trueendl; pl+=i; i=-1