銀行家算法實(shí)習(xí)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上青 島 農(nóng) 業(yè) 大 學(xué)學(xué) 生 實(shí) 習(xí) 報(bào) 告實(shí) 習(xí) 名 稱： 軟件系統(tǒng)課程設(shè)計(jì) 實(shí) 習(xí) 時(shí) 間： 2010 - 2011 學(xué)年 第 2學(xué)期 專 業(yè) 班 級 ： 姓名（學(xué)號）： 同 組 成 員 ： 指 導(dǎo) 老 師： 于仁師 2011 年 3 月 22 日（一）編譯原理部分一、實(shí)習(xí)題目將詞法分析器設(shè)計(jì)成單獨(dú)的程序或供語法分析器調(diào)用的子程序,功能包括：要求能夠識別數(shù)字、標(biāo)識符、關(guān)鍵字、運(yùn)算符等。二、設(shè)計(jì)思路及算法描述詞法分析程序的功能：輸入源程序，輸出單詞符號，如圖所示：詞法分析器源程序單詞符號處理過程：在掃描源程序字符串時(shí)，一旦識別出關(guān)鍵字、分隔符、標(biāo)識符、無符號常數(shù)中之

2、一，即以單詞形式（各類單詞均采用相同的結(jié)構(gòu)，即二元式編碼形式）輸出。每次調(diào)用詞法分析程序，它均能自動(dòng)繼續(xù)掃描下去，形成下一個(gè)單詞，直至整個(gè)源程序全部掃描完畢，并形成相應(yīng)的單詞串形式的源程序。本程序規(guī)定：(1)關(guān)鍵字begin,end,if,then,else,while,write,read,do, call,const,char,until,procedure,repeat(2)運(yùn)算符：+,-,*,/,=(3)界符：,;,.,(,),:(4)其他標(biāo)記 如字符串，表示以字母開頭的標(biāo)識符。(5)空格、回車、換行符跳過。對于一段可能的輸入代碼，其結(jié)果在屏幕上顯示如下：( 1 , 無符號整數(shù))( b

3、egin , 關(guān)鍵字 )( if , 關(guān)鍵字 )( +, 運(yùn)算符 )( ； , 界符 )( a , 普通標(biāo)識符 )關(guān)鍵字或標(biāo)識符的判斷：讀入一串字符，將ASCII碼在字母范圍的字符存入數(shù)組中，將該數(shù)組與設(shè)置好的關(guān)鍵字比較，如果相等則輸出是關(guān)鍵字，否則繼續(xù)讀入直至下一字符既非數(shù)字也非字母，輸出為標(biāo)識符；數(shù)字的判斷：若跟在字母后面則一起輸出為標(biāo)識符，否則輸出為數(shù)字；界符、運(yùn)算符的判斷：直接判斷其ASCII碼運(yùn)行過程為：1預(yù)處理：把源文件一個(gè)字符一個(gè)字符的讀入詞法分析程序設(shè)置的輸入字符結(jié)構(gòu)體數(shù)組中（輸入緩沖區(qū)），讀入過程要?jiǎng)h除多余的空格；2源程序字符數(shù)組中獲得單詞, 編碼為二元式.：二元式采用結(jié)構(gòu)體

4、數(shù)組存儲, 把單詞類型和詞元記錄下來。 為了方便和適用起見，首先建立一個(gè)文本，進(jìn)而在文本中進(jìn)行pascal語言輸入。輸入完畢之后，就可以進(jìn)行從文本中取字符，進(jìn)而把它放在一個(gè)數(shù)組中。之后再數(shù)組中進(jìn)行取字符，之前要定義一個(gè)數(shù)組，定義一個(gè)指針指向數(shù)組，為first。之后就用一個(gè)循環(huán)依次從數(shù)組中取字符，假如是字符就放在buf中，first+；一次進(jìn)行下去，期間要時(shí)刻與關(guān)鍵字指針數(shù)組進(jìn)行比較如果相等就立馬輸出，并顯示是關(guān)鍵字此時(shí)將buf置為初值，first重新指向首地址。流程圖讀取字符輸出”關(guān)鍵字”是關(guān)鍵字是不可顯示符輸出”標(biāo)識符”YNYNY是字母或數(shù)字是字母讀取字符Y NY是數(shù)字輸出”常數(shù)”是數(shù)字N讀

5、取字符NN是界符Y輸出”界符”ERROR是=是：讀取字符NNY輸出”運(yùn)算符”是 運(yùn)算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)/關(guān)鍵字判斷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)/判斷是否為數(shù)字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$關(guān)鍵字endl;elsecoutarrt$普通標(biāo)識符endl;else if(IsDigit(ch)while(IsDigit(ch)|ch=.&IsDigit(fgetc(fpin)arr=arr+ch;ch=fgetc(fpin);fseek(fpin,-1L,SEEK_CUR);coutarrt$無符號實(shí)數(shù)endl;else switch(ch)case+:case- :case* :case= :case/ :coutcht$運(yùn)算符endl;break;case( :c

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

9、符) coutt$運(yùn)算符endl;elsecoutt$運(yùn)算符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文件路徑錯(cuò)誤！請輸入源文件名（包括路徑和后綴名）:;coutn*分析如下*endl;fenxi(fpin);fclose(fpin);四、運(yùn)行結(jié)果現(xiàn)將要處理的代碼段保存于文件中，在本程序中，我保存的位置是G:1.txt，文件內(nèi)容

10、如下圖所示：點(diǎn)擊運(yùn)行程序，其分析結(jié)果如下：（二）操作系統(tǒng)部分一、實(shí)習(xí)題目用銀行家算法實(shí)現(xiàn)資源分配二、設(shè)計(jì)思路及算法描述已知進(jìn)程P0,P1,P2,P3,P4，有三類系統(tǒng)資源A、B、C的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如下圖所示：（1）若進(jìn)程P1請求資源，發(fā)出請求向量Request1（1，0，2），編寫程序用銀行家算法判斷系統(tǒng)能否將資源分配給它；（2）若進(jìn)程P3提出請求Request(1，1，2)，用銀行家算法程序驗(yàn)證系統(tǒng)能否將資源分配給它。數(shù)據(jù)結(jié)構(gòu):1.可利用資源向量Available2.最大需求矩陣Max3.分配矩陣Allocation4.需求矩陣Need功能介紹:模擬實(shí)現(xiàn)Di

11、jkstra的銀行家算法以避免死鎖的出現(xiàn).分兩部分組成:第一部分:銀行家算法(掃描)1如果Request=Need,則轉(zhuǎn)向2;否則,出錯(cuò)2如果Request=Available,則轉(zhuǎn)向3,否則等待3系統(tǒng)試探分配請求的資源給進(jìn)程4系統(tǒng)執(zhí)行安全性算法第二部分:安全性算法1.設(shè)置兩個(gè)向量(1).工作向量:Work=Available(表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目)(2).Finish:表示系統(tǒng)是否有足夠資源分配給進(jìn)程(True:有;False:沒有).初始化為False2.若Finishi=False&Need=Work,則執(zhí)行3;否則執(zhí)行4(I為資源類別)3.進(jìn)程P獲得第i類資

12、源,則順利執(zhí)行直至完成!并釋放資源:Work=Work+Allocation;Finishi=true;轉(zhuǎn)24. 若所有進(jìn)程的Finishi=true,則表示系統(tǒng)安全;否則,不安全!三、程序代碼：#include #include #define M 5 /*M個(gè)進(jìn)程,N個(gè)資源*/#define N 3int AVAILABLEN; /*可用資源數(shù)組*/int MAXMN; /*最大需求矩陣*/int ALLOCATIONMN; /*分配矩陣*/int NEEDMN; /*需求矩陣*/int REQUESTMN; /*進(jìn)程需要資源數(shù)*/bool FINISHM; /*系統(tǒng)是否有足夠的資源分配*

13、/int pM; /*記錄序列*/void Init();bool Safe();void Banker();void Output();void main() Init(); Safe(); Banker();void Init() /*初始化算法*/ int i,j; cout請輸入每個(gè)進(jìn)程最多所需的各資源數(shù),按照MxN矩陣輸入:endl; for(i=0;iM;i+)for(j=0;jMAXij;cout請輸入每個(gè)進(jìn)程已分配的各資源數(shù),按照MxN矩陣輸入:endl;for(i=0;iM;i+)for(j=0;jALLOCATIONij;NEEDij=MAXij-ALLOCATIONij;

14、if(NEEDij0)cout您輸入的第i+1個(gè)進(jìn)程所擁有的第j+1個(gè)資源數(shù)錯(cuò)誤,請重新輸入:endl;j-;continue;cout請輸入各個(gè)資源現(xiàn)有的數(shù)目:endl;for(i=0;iAVAILABLEi;void Banker() /*銀行家算法*/ int i,pneed; char flag; while(1) cout請輸入要申請資源的進(jìn)程號(注:第1個(gè)進(jìn)程號為0,依次類推)pneed; cout請輸入進(jìn)程所請求的各資源的數(shù)量endl; for(i=0;iREQUESTpneedi; for(i=0;iNEEDpneedi) cout您輸入的對i進(jìn)程的請求數(shù)超過進(jìn)程的需求量!請重

15、新輸入!AVAILABLEi) cout您輸入的對i進(jìn)程的請求數(shù)超過系統(tǒng)有的資源數(shù)!請重新輸入!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進(jìn)程名 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; /*工作數(shù)組*/ for(i=0;iN;i+)Worki=AVAILABLEi; for(i=0;iM;i+) FINISHi=false; cout安全性：endl進(jìn)程名 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