銀行家算法實習報告

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

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

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

4、數(shù)組存儲, 把單詞類型和詞元記錄下來。 為了方便和適用起見，首先建立一個文本，進而在文本中進行pascal語言輸入。輸入完畢之后，就可以進行從文本中取字符，進而把它放在一個數(shù)組中。之后再數(shù)組中進行取字符，之前要定義一個數(shù)組，定義一個指針指向數(shù)組，為first。之后就用一個循環(huán)依次從數(shù)組中取字符，假如是字符就放在buf中，first+；一次進行下去，期間要時刻與關(guān)鍵字指針數(shù)組進行比較如果相等就立馬輸出，并顯示是關(guān)鍵字此時將buf置為初值，first重新指向首地址。流程圖讀取字符輸出”關(guān)鍵字”是關(guān)鍵字是不可顯示符輸出”標識符”YNYNY是字母或數(shù)字是字母讀取字符Y NY是數(shù)字輸出”常數(shù)”是數(shù)字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)/關(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$普通標識符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ù)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);四、運行結(jié)果現(xiàn)將要處理的代碼段保存于文件中，在本程序中，我保存的位置是G:1.txt，文件內(nèi)容

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

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

12、源,則順利執(zhí)行直至完成!并釋放資源:Work=Work+Allocation;Finishi=true;轉(zhuǎn)24. 若所有進程的Finishi=true,則表示系統(tǒng)安全;否則,不安全!三、程序代碼：#include #include #define M 5 /*M個進程,N個資源*/#define N 3int AVAILABLEN; /*可用資源數(shù)組*/int MAXMN; /*最大需求矩陣*/int ALLOCATIONMN; /*分配矩陣*/int NEEDMN; /*需求矩陣*/int REQUESTMN; /*進程需要資源數(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請輸入每個進程最多所需的各資源數(shù),按照MxN矩陣輸入:endl; for(i=0;iM;i+)for(j=0;jMAXij;cout請輸入每個進程已分配的各資源數(shù),按照MxN矩陣輸入:endl;for(i=0;iM;i+)for(j=0;jALLOCATIONij;NEEDij=MAXij-ALLOCATIONij;

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

15、新輸入!AVAILABLEi) cout您輸入的對i進程的請求數(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進程名 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進程名 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