軟件系統(tǒng)課程設計操作系統(tǒng)：用銀行家算法實現(xiàn)資源分配

1、青島農(nóng)業(yè)大學理學與信息科學學院軟件系統(tǒng)課程設計報告 設 計 題 目 操作系統(tǒng)：用銀行家算法實現(xiàn)資源分配 編譯原理：詞法分析器 學生專業(yè)班級 學生姓名（學號） 設計小組其他同學姓名（學號） 指 導 教 師 完 成 時 間 2012年6月4日 設 計 地 點 信息樓139機房 2012年 6 月 7 日（二）編譯原理部分一、實習題目將詞法分析器設計成單獨的程序或供語法分析器調(diào)用的子程序,功能包括：要求能夠識別數(shù)字、標識符、關鍵字、運算符等。二、設計思路及算法描述詞法分析程序的功能：輸入源程序，輸出單詞符號，如圖所示：詞法分析器源程序單詞符號處理過程：在掃描源程序字符串時，一旦識別出關鍵字、分隔符、

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

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

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

5、輸出”常數(shù)”是數(shù)字n讀取字符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

6、 1;return 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

7、+ch;ch=fgetc(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$無符號實數(shù)endl;else switch(ch)case+:case- :case* :case= :case/ :coutcht$運算符endl;break;

8、case( :case) :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=)co

9、utt$輸出控制符) 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);四、運行結果現(xiàn)將要處理的代碼段保存于文件中，在本程序中，我保存的位置是e:1.

10、txt，文件內(nèi)容如下圖所示：點擊運行程序，其分析結果如下：（一）操作系統(tǒng)部分一、實習題目用銀行家算法實現(xiàn)資源分配二、設計思路及算法描述已知進程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ù)結構:1.可利用資源向量available2.最大需求矩陣max3.分配矩陣allocation4.需求矩陣need功能介

11、紹:模擬實現(xiàn)dijkstra的銀行家算法以避免死鎖的出現(xiàn).分兩部分組成:第一部分:銀行家算法(掃描)1如果request=need,則轉(zhuǎn)向2;否則,出錯2如果request=available,則轉(zhuǎn)向3,否則等待3系統(tǒng)試探分配請求的資源給進程4系統(tǒng)執(zhí)行安全性算法第二部分:安全性算法1.設置兩個向量(1).工作向量:work=available(表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源數(shù)目)(2).finish:表示系統(tǒng)是否有足夠資源分配給進程(true:有;false:沒有).初始化為false2.若finishi=false&need=work,則執(zhí)行3;否則執(zhí)行4(i為資源類別)3.進

12、程p獲得第i類資源,則順利執(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-alloc

14、ationij;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; n

16、eedpneedi+=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)allocat

17、ionij ;cout ;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(fin

18、ishi=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; else continue; if(l=m) cout系統(tǒng)是安全的!endl; cout安全序列:endl; for(i=0;il;i+) coutpi; if(i!=l-1) cout; coutendl;output(); return t