1、 北 華 航 天 工 業(yè) 學(xué) 院操作系統(tǒng)課程設(shè)計(jì)報(bào)告課設(shè)報(bào)告題目： 作者所在系部： 計(jì)算機(jī)科學(xué)與工程 作者所在專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 作者所在班級： 作 者 姓 名 ： 指導(dǎo)教師姓名： 完 成 時 間 ： 2011-12-13 北華航天工業(yè)學(xué)院教務(wù)處制摘 要通過一學(xué)期的對操作系統(tǒng)的學(xué)習(xí)，對操作系統(tǒng)有了一定的知識儲備，為了鞏固知識，加深印象，也為了更加深入的了解與鉆研操作系統(tǒng)，為以后的學(xué)習(xí)研究提供幫助，做操作系統(tǒng)課設(shè)，分別為進(jìn)程調(diào)度算法、銀行家算法。通過進(jìn)程調(diào)度算法課設(shè)，解決了進(jìn)程調(diào)度的幾個基本算法：先來先服務(wù)算法、短進(jìn)程優(yōu)先算法、高響應(yīng)比算法。通過銀行家算法課設(shè)，更加深刻的理解了銀行家算法，

2、安全算法避免死鎖的原理。兩個課設(shè)為兩個知識點(diǎn)，都為操作系統(tǒng)的難點(diǎn)與重點(diǎn)，在硬件不允許的情況下通過運(yùn)用vc+6.0和c+語言描述了它們的功能與具體實(shí)現(xiàn)，對以后的學(xué)習(xí)有很大的幫助。關(guān)鍵詞：操作系統(tǒng) 進(jìn)程 進(jìn)程調(diào)度算法 先來先服務(wù) 短進(jìn)程優(yōu)先 高響應(yīng)比銀行家算法 安全算法 死鎖 安全序列 安全狀態(tài)第一章 緒論11.1課程設(shè)計(jì)的背景和意義11.1.1 課程設(shè)計(jì)的理論研究基礎(chǔ)11.1.2 課程設(shè)計(jì)的意義11.2 課程設(shè)計(jì)環(huán)境1第二章 需求分析22.1 功能要求22.1.1進(jìn)程調(diào)度算法22.1.2銀行家算法22.2 問題的解決方案22.2.1進(jìn)程調(diào)度算法22.2.2銀行家算法3第三章 系統(tǒng)設(shè)計(jì)43.1 數(shù)

3、據(jù)設(shè)計(jì)43.1.1 結(jié)構(gòu)體設(shè)計(jì)43.1.2 結(jié)構(gòu)體之間的關(guān)系43.1.3 函數(shù)設(shè)計(jì)4第四章 系統(tǒng)實(shí)現(xiàn)24.1 結(jié)構(gòu)體實(shí)現(xiàn)24.2 函數(shù)實(shí)現(xiàn)24.2.1 進(jìn)程調(diào)度算法的函數(shù)實(shí)現(xiàn)24.2.2. 銀行家算法的函數(shù)實(shí)現(xiàn)64.3 主函數(shù)實(shí)現(xiàn)44.3.1. 進(jìn)程調(diào)度算法的主函數(shù)實(shí)現(xiàn)44.3.2. 銀行家算法的主函數(shù)實(shí)現(xiàn)14.4 系統(tǒng)界面14.4.1 進(jìn)程調(diào)度算法的運(yùn)行界面14.4.2 銀行家算法的運(yùn)行界面1第五章 系統(tǒng)測試25.1 模塊測試25.1.1 進(jìn)程調(diào)度算法25.1.2 銀行家算法45.2 課程設(shè)計(jì)過程中遇到的問題6總 結(jié)7致 謝8參考文獻(xiàn)9第一章 緒論隨著計(jì)算機(jī)的不斷的更新?lián)Q代，操作系統(tǒng)也越來越

4、多樣化，復(fù)雜化，這就要求我們大學(xué)生掌握一些操作系統(tǒng)的基本知識，了解操作系統(tǒng)的基本原理，能夠正確地使用操作系統(tǒng)，直到操作系統(tǒng)的作用，為此，我們列舉了兩個操作系統(tǒng)中常用的兩個知識點(diǎn)，進(jìn)程調(diào)度算法和銀行家算法，幫助學(xué)生能夠較快的了解并掌握這兩個常用的知識點(diǎn)。1.1 課程設(shè)計(jì)的背景和意義1.1.1 課程設(shè)計(jì)的理論研究基礎(chǔ)1.先來先服務(wù)算法：每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個或多個最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列，每次調(diào)度從就緒隊(duì)列中選擇一個最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。短進(jìn)程優(yōu)先調(diào)度算法：從就緒隊(duì)列中選出一個運(yùn)行時間最短的進(jìn)程，將

5、處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成。高響應(yīng)比調(diào)度算法：為每個作業(yè)引入動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時間的增加提高，則長作業(yè)等待一定的時間后，必然有機(jī)會分配到處理機(jī)。2.銀行家算法：要預(yù)防死鎖，有摒棄“請求和保持”條件，摒棄“不剝奪”條件，摒棄“環(huán)路等待”條件等方法。而最具代表性的避免死鎖的算法，便是dijkstra的銀行家算法。利用銀行家算法，我們可以來檢測cpu為進(jìn)程分配資源的情況，決定cpu是否響應(yīng)某進(jìn)程的的請求并為其分配資源，從而很好避免了死鎖的產(chǎn)生1.1.2 課程設(shè)計(jì)的意義課程設(shè)計(jì)是學(xué)生學(xué)習(xí)完操作系統(tǒng)課程后，進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，讓學(xué)生更好地掌握操作系

6、統(tǒng)的原理及實(shí)現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動手能力。1.2 課程設(shè)計(jì)環(huán)境軟件環(huán)境：vc+6.0。硬件環(huán)境：圖書館5樓實(shí)驗(yàn)室第二章 需求分析2.1 功能要求2.1.1進(jìn)程調(diào)度算法 編程實(shí)現(xiàn)進(jìn)程調(diào)度算法的基本過程，設(shè)計(jì)要求：（1）能夠選擇進(jìn)程調(diào)度算法（先來先服務(wù)、短進(jìn)程優(yōu)先算法和高響應(yīng)比優(yōu)先算法）。（2）可以輸入進(jìn)程數(shù)目（至少4個進(jìn)程），以及各進(jìn)程的提交時間和運(yùn)行時間。（3）能夠以下圖形式顯示調(diào)度過程及平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2.1.2銀行家算法編寫一程序，能夠模擬銀行家算法和安全算法來避免死鎖。假設(shè)系統(tǒng)資源有a、b、c三種，可以運(yùn)行5個進(jìn)程。該程序具備的基本功

7、能為：（1）程序可以輸入3種資源的數(shù)目，5個進(jìn)程對3種資源的最大需求量、已分配量和需求量。（2）能夠判斷某一時刻系統(tǒng)是否處于安全狀態(tài)，如果處于安全狀態(tài)能夠給出安全序列。（3）當(dāng)某進(jìn)程提出資源申請時，能夠判斷是否能把資源分配給申請進(jìn)程。2.2 問題的解決方案2.2.1進(jìn)程調(diào)度算法 運(yùn)用先來先服務(wù)，短進(jìn)程優(yōu)先算法，高響應(yīng)比算法來實(shí)現(xiàn)對操作系統(tǒng)進(jìn)程的調(diào)度算法。其中運(yùn)用數(shù)據(jù)結(jié)構(gòu)中的排序知識便可輕易解決。2.2.2銀行家算法銀行家算法，安全算法查看安全序列，運(yùn)用數(shù)組，循環(huán)判斷是否存在安全序列，從而即可判斷安全性，避免死鎖。第三章 系統(tǒng)設(shè)計(jì)3.1 數(shù)據(jù)設(shè)計(jì)3.1.1 結(jié)構(gòu)體設(shè)計(jì)1. 進(jìn)程調(diào)度算法的結(jié)構(gòu)體設(shè)

8、計(jì)（1）struct pcbint id;/進(jìn)程idfloat ptime;/到達(dá)時間float starttime;/開始時間float waittime;/等待時間float finishtime;/完成時間float runtime;/運(yùn)行時間float turntime;/周轉(zhuǎn)時間float qtime;/帶權(quán)周轉(zhuǎn)時間;/進(jìn)程控制塊（2）typedef pcb elemtype;typedef structelemtype elem100; int length; sqlist;/順序表，用于存儲進(jìn)程控制塊3.1.2 結(jié)構(gòu)體之間的關(guān)系 1. 進(jìn)程調(diào)度算法sqlist順序表結(jié)構(gòu)體，用于存

9、儲pcb進(jìn)程控制塊，以實(shí)現(xiàn)各種方法的進(jìn)程調(diào)度3.1.3 函數(shù)設(shè)計(jì)1. 進(jìn)程調(diào)度算法的函數(shù)設(shè)計(jì)（1）int listinsert_sq(sqlist &l,int i, elemtype e)/在順序表第i個位置插入數(shù)據(jù)e（2）void bubble_sort(elemtype e,int n)/冒泡法排序（3）int listinsert_sq2(sqlist &l,int i, elemtype e,int n)/按短進(jìn)程優(yōu)先法往順序表中插入數(shù)組en（4）int listinsert_sq3(sqlist &l,int i, elemtype e,int n)/按高響應(yīng)比法往順序表中插入數(shù)組

10、en（5）void fcfs(elemtype e,int n)/先來先服務(wù)計(jì)算各個時間（6）void sjf(sqlist &l)/短進(jìn)程優(yōu)先法計(jì)算各個時間（7）void fpf(sqlist &l)/高響應(yīng)比法計(jì)算各個時間（8）void display(sqlist &l)/輸出函數(shù)，把順序表中的數(shù)據(jù)輸出2. 銀行家算法的函數(shù)設(shè)計(jì)（1）void input(int available3,int max53,int allocation53,int need53,int finish5,string name5)/輸入可利用資源數(shù)目，最大需求數(shù)目，以分配數(shù)目，需求數(shù)目，完成標(biāo)記，進(jìn)程名字（2

11、）int fenpei(int available3,int allocation53,int need53,int finish5,int xb5)/分配函數(shù)，檢查分配是否安全（3）int request(int available3,int max53,int allocation53,int need53,string name5)/請求函數(shù)，輸入進(jìn)程名字和資源申請數(shù)目（4）int fanhui(int available3,int max53,int allocation53,int need53,string name5,string &name2)/申請資源不安全時 返還申請資源第

12、四章 系統(tǒng)實(shí)現(xiàn)4.1 結(jié)構(gòu)體實(shí)現(xiàn)1. 進(jìn)程調(diào)度算法的結(jié)構(gòu)體實(shí)現(xiàn)（1）struct pcbint id;/進(jìn)程idfloat ptime;/到達(dá)時間float starttime;/開始時間float waittime;/等待時間float finishtime;/完成時間float runtime;/運(yùn)行時間float turntime;/周轉(zhuǎn)時間float qtime;/帶權(quán)周轉(zhuǎn)時間;/進(jìn)程控制塊（2）typedef pcb elemtype;typedef structelemtype elem100; int length; sqlist;/順序表，用于存儲進(jìn)程控制塊4.2 函數(shù)實(shí)現(xiàn)4.

13、2.1 進(jìn)程調(diào)度算法的函數(shù)實(shí)現(xiàn)（1）int listinsert_sq(sqlist &l,int i, elemtype e) /在順序表第i個位置插入數(shù)據(jù)e if(il.length+1) return 0; if(l.length=100) return -1; int j; for(j=l.length;j=i-1;j-) l.elemj+1=l.elemj; l.elemi-1=e; l.length+; return 1;（2）void bubble_sort(elemtype e,int n) /冒泡法排序elemtype t;int i,j,swap;for(i=1;i=n;i

14、+)swap=0;for(j=0;jej+1.ptime)t=ej;ej=ej+1;ej+1=t;swap=1;if(swap=0)break;（3）int listinsert_sq2(sqlist &l,int i, elemtype e,int n) /按短進(jìn)程優(yōu)先法往順序表中插入數(shù)組enint j,q,swap,p;j=0;q=0;float t;listinsert_sq(l,i,ej);t=ej.ptime+ej.runtime;i+;j+;p=j;for(j;jt)listinsert_sq(l,i,ej);t=ej.ptime+ej.runtime;i+;p+;else if(

15、ej.ptimet|(j+1)=n)swap=1;if(swap=1)if(p=q)listinsert_sq(l,i,eq);t=eq.ptime+eq.runtime;i+;p+;if(qp)swap=0;elemtype x;for(q;qp;q-)if(eq.runtimeeq-1.runtime)x=eq;eq=eq-1;eq-1=x;if(swap=0)listinsert_sq(l,i,ep);t=t+ep.runtime;i+;p+;j=p-1;return 1;（4）int listinsert_sq3(sqlist &l,int i, elemtype e,int n) /

16、按高響應(yīng)比法往順序表中插入數(shù)組enint j,q,swap,p;j=0;q=0;float t;listinsert_sq(l,i,ej);t=ej.ptime+ej.runtime;i+;j+;p=j;for(j;jt)listinsert_sq(l,i,ej);t=ej.ptime+ej.runtime;i+;p+;else if(ej.ptimet|(j+1)=n)swap=1;if(swap=1)if(p=q)listinsert_sq(l,i,eq);t=eq.ptime+eq.runtime;i+;p+;if(qp)swap=0;elemtype x;for(q;qp;q-)if(

17、t-eq.ptime)/eq.runtime(t-eq-1.ptime)/eq-1.runtime)x=eq;eq=eq-1;eq-1=x;if(swap=0)listinsert_sq(l,i,ep);t=t+ep.runtime;i+;p+;j=p-1;return 1;（5）void fcfs(elemtype e,int n) /先來先服務(wù)計(jì)算各個時間int i=0;while(i=ei-1.finishtime)ei.starttime=ei.ptime; ei.finishtime=ei.starttime+ei.runtime;ei.turntime=ei.finishtime-

18、ei.ptime;ei.qtime=ei.turntime/ei.runtime;elseei.starttime=ei-1.finishtime;ei.waittime=ei.starttime-ei.ptime;ei.finishtime=ei.starttime+ei.runtime;ei.turntime=ei.finishtime-ei.ptime;ei.qtime=ei.turntime/ei.runtime;i+;（6）void sjf(sqlist &l) /短進(jìn)程優(yōu)先法計(jì)算各個時間int i=0;while(i=l.elemi-1.finishtime)l.elemi.sta

19、rttime=l.elemi.ptime; l.elemi.finishtime=l.elemi.starttime+l.elemi.runtime;l.elemi.turntime=l.elemi.finishtime-l.elemi.ptime;l.elemi.qtime=l.elemi.turntime/l.elemi.runtime;elsel.elemi.starttime=l.elemi-1.finishtime;l.elemi.waittime=l.elemi.starttime-l.elemi.ptime;l.elemi.finishtime=l.elemi.starttime

20、+l.elemi.runtime;l.elemi.turntime=l.elemi.finishtime-l.elemi.ptime;l.elemi.qtime=l.elemi.turntime/l.elemi.runtime;i+;（7）void fpf(sqlist &l)/高響應(yīng)比法計(jì)算各個時間int i=0;while(i=l.elemi-1.finishtime)l.elemi.starttime=l.elemi.ptime; l.elemi.finishtime=l.elemi.starttime+l.elemi.runtime;l.elemi.turntime=l.elemi.f

21、inishtime-l.elemi.ptime;l.elemi.qtime=l.elemi.turntime/l.elemi.runtime;elsel.elemi.starttime=l.elemi-1.finishtime;l.elemi.waittime=l.elemi.starttime-l.elemi.ptime;l.elemi.finishtime=l.elemi.starttime+l.elemi.runtime;l.elemi.turntime=l.elemi.finishtime-l.elemi.ptime;l.elemi.qtime=l.elemi.turntime/l.e

22、lemi.runtime;i+;（8）void display(sqlist &l)/輸出函數(shù)，把順序表中的數(shù)據(jù)輸出int i=0;float t1,t2;t1=0;t2=0;cout執(zhí)行次序setw(10)提交時間setw(10)開始時間setw(10)等待時間setw(10)完成時間setw(10)運(yùn)行時間setw(10)周轉(zhuǎn)時間setw(14)帶權(quán)周轉(zhuǎn)時間endl;while(il.length)coutl.elemi.idsetw(10)l.elemi.ptimesetw(10)l.elemi.starttimesetw(10)l.elemi.waittimesetw(10)l.ele

23、mi.finishtimesetw(10)l.elemi.runtimesetw(10)l.elemi.turntimesetw(10)l.elemi.qtimeendl;t1=t1+l.elemi.turntime;t2=t2+l.elemi.qtime;i+;cout平均周轉(zhuǎn)周期為：t1/l.lengthendl;cout平均帶權(quán)周轉(zhuǎn)周期為：t2/l.lengthendl;4.2.2. 銀行家算法的函數(shù)實(shí)現(xiàn)（1）void input(int available3,int max53,int allocation53,int need53,int finish5,string name5)

24、/輸入可利用資源數(shù)目，最大需求數(shù)目，以分配數(shù)目，需求數(shù)目，完成標(biāo)記，進(jìn)程名字cout請輸入3種資源的數(shù)目;for(int j=0;javailablej;for(int i=0;i5;i+)cout請輸入第i+1namei;cout請輸入第i+1個進(jìn)程對3種資源的最大需求量;for(int j=0;jmaxij;cout請輸入第i+1個進(jìn)程對3種資源的已分配量;for(j=0;jallocationij;for(j=0;j3;j+)needij=maxij-allocationij;finishi=0;（2）int fenpei(int available3,int allocation53,

25、int need53,int finish5,int xb5) /分配函數(shù)，檢查分配是否安全int m=0,k=0,n=0;for(int i=0;i5;i+)if(needi0=0&needi1=0&needi2=0)for(int j=0;j3;j+)availablej+=allocationij;finishi=1;m+;xbk+=i;while(m5)for(int i=0;i=needi0&available1=needi1&available2=needi2)for(int j=0;j5)return 0;return 1;（3）int request(int available

26、3,int max53,int allocation53,int need53,string name5,string &name2)/申請資源，輸入申請資源的進(jìn)程名字，申請數(shù)目int i;int flag;while(flag!=0)coutname2abc;for(int n=0;n5;n+)if(namen=name2)flag=0;i=n;if(flag!=0)cout進(jìn)程不存在 請重新輸入endl;if(a=needi0&b=needi1&c=needi2)if(a=available0&b=available1&c=available2)allocationi0+=a;alloca

27、tioni1+=b;allocationi2+=c;available0-=a;available1-=b;available2-=c;needi0=maxi0-allocationi0;needi1=maxi1-allocationi1;needi2=maxi2-allocationi2;cout各進(jìn)程目前所需資源數(shù)目:endl;cout進(jìn)程setw(10)資源asetw(10)資源bsetw(10)資源cendl;for(int w=0;w5;w+)coutnamewsetw(10)needw0setw(10)needw1setw(10)needw2endl;if(needi0=0&nee

28、di1=0&needi2=0)cout進(jìn)程namei得到運(yùn)行所需資源，可以運(yùn)行，釋放資源。endl;available0+=allocationi0;available1+=allocationi1;available2+=allocationi2;return 1;elsecout該進(jìn)程資源請求數(shù)目大于可利用資源，讓進(jìn)程name2等待endl;return 0;else cout該進(jìn)程資源請求數(shù)目大于該進(jìn)程所需資源數(shù)目，進(jìn)程name2不可以運(yùn)行endl;return 0;（4）int fanhui(int available3,int max53,int allocation53,int n

29、eed53,string name5,string &name2)/申請資源不安全時，返還資源int i;for(int n=0;n5;n+)if(namen=name2)i=n;allocationi0-=a;allocationi1-=b;allocationi2-=c;available0+=a;available1+=b;available2+=c;needi0=maxi0-allocationi0;needi1=maxi1-allocationi1;needi2=maxi2-allocationi2;cout各進(jìn)程目前所需資源數(shù)目:endl;cout進(jìn)程setw(10)資源asetw

30、(10)資源bsetw(10)資源cendl;for(int w=0;w5;w+)coutnamewsetw(10)needw0setw(10)needw1setw(10)needw2endl;return 1;4.3 主函數(shù)實(shí)現(xiàn)4.3.1. 進(jìn)程調(diào)度算法的主函數(shù)實(shí)現(xiàn)int main()int i;sqlist l1,l2,l3;l1.length=0;l2.length=0;l3.length=0;cout=歡迎使用進(jìn)程調(diào)度算法=endl;couti; /用于表示調(diào)度進(jìn)程數(shù)目pcb p100,p1100,p2100;int j=0;for(j;ji;j+)cout請輸入第j+1pj.idpj

31、.ptimepj.runtime;pj.starttime=0;pj.turntime=0;pj.finishtime=0;pj.qtime=0;pj.waittime=0;for(j=0;ji;j+)p2j=pj;p1j=pj;char q=1; while(q!=0)cout=endl;cout fifs先來先服務(wù) endl;cout 短進(jìn)程優(yōu)先 endl;cout 高響應(yīng)比優(yōu)先 endl;cout 退出 endl;cout=endl;coutq;while(q3)cout輸入錯誤!endl;coutq;switch(q)case 0:return 1;case 1:bubble_sort

32、(p,i); fcfs(p,i); for(j=0;ji;j+) listinsert_sq(l1,l1.length+1,pj); ; display(l1); l1.length=0; break;case 2:bubble_sort(p1,i); listinsert_sq2(l2,l2.length+1,p1,i); sjf(l2); display(l2); l2.length=0; break;case 3:bubble_sort(p2,i); listinsert_sq3(l3,l3.length+1,p2,i); fpf(l3); display(l3); l3.length=

33、0; return 1;4.3.2. 銀行家算法的主函數(shù)實(shí)現(xiàn)#include#include#includeusing namespace std;int a,b,c;void input(int available3,int max53,int allocation53,int need53,int finish5,string name5)cout請輸入3種資源的數(shù)目;for(int j=0;javailablej;for(int i=0;i5;i+)cout請輸入第i+1namei;cout請輸入第i+1個進(jìn)程對3種資源的最大需求量;for(int j=0;jmaxij;cout請輸入第

34、i+1個進(jìn)程對3種資源的已分配量;for(j=0;jallocationij;for(j=0;j3;j+)needij=maxij-allocationij;finishi=0;int fenpei(int available3,int allocation53,int need53,int finish5,int xb5)int m=0,k=0,n=0;for(int i=0;i5;i+)if(needi0=0&needi1=0&needi2=0)finishi=1;m+;xbk+=i;while(m5)for(int i=0;i=needi0&available1=needi1&available2=needi2)for(int j=0;j5)return 0;return 1;int request(int available3,int max53,int allocation53,int need53,string name5,string &name2)int i;int