先來先服務和短進程優(yōu)先調(diào)度算法模擬課程設計(共20頁).doc

1、課程設計（論文）題 目: 先來先服務和短進程 優(yōu)先調(diào)度算法模擬 院 （系）： 華清學院 專業(yè)班級： 計算機2011 姓 名： 王江 學 號： 11 指導教師： 曾應員 2013年 12 月 18日西安建筑科技大學華清學院課程設計（論文）任務書專業(yè)班級： 計算機1101 學生姓名： 王江 指導教師（簽名）： 一、課程設計（論文）題目先來先服務和短進程優(yōu)先調(diào)度算法模擬（進程調(diào)度）：編寫一個進程調(diào)度程序，允許多個進程并行執(zhí)行，并能選擇是先來先服務算法還是短進程優(yōu)先算法。二、本次課程設計（論文）應達到的目的操作系統(tǒng)課程實踐性比較強。課程設計是加強學生實踐能力的一個強有力手段。課程設計要求學生在完成程序

2、設計的同時能夠?qū)懗霰容^規(guī)范的設計報告。嚴格實施課程設計這一環(huán)節(jié)，對于學生基本程序設計素養(yǎng)的培養(yǎng)和軟件工作者工作作風的訓練，將起到顯著的促進作用。本題目要達到目的：深入掌握進程調(diào)度的概念原理和實現(xiàn)方法。三、本次課程設計（論文）任務的主要內(nèi)容和要求（包括原始數(shù)據(jù)、技術參數(shù)、設計要求等） 先來先服務調(diào)度算法是以進程的到達時間為判斷標準，按各個進程所的到達時間先后順序進行調(diào)度。短進程優(yōu)先調(diào)度算法是按進程的預計運行時間長短進行排序，先執(zhí)行短進程。四、應收集的資料及主要參考文獻： 操作系統(tǒng)經(jīng)典算法的編程實現(xiàn)資料非常豐富，可以在圖書館找書籍或在因特網(wǎng)上找資料，都很容易找到，但是大部分代碼是不全的，不能直接運

3、行，希望大家只是把它當參考，編碼還是自己做。 參考文獻：【1】湯小丹、梁紅兵、哲鳳屏、湯子瀛 編著.計算機操作系統(tǒng)（第三版）.西安：西安電子科技大學出版社，2007.5【2】史美林編.計算機操作系統(tǒng)教程.北京：清華大學出版社，1999.11【3】徐甲同編著.操作系統(tǒng)教程.西安：西安電子科技大學出版社，1996.8【4】Clifford，A.Shaffer編著.數(shù)決結(jié)構(gòu)與算法分析(C+版).北京：電子工業(yè)出版社，2005.7【5】蔣立翔編著.C+程序設計技能百練.北京：中國鐵道出版社，2004.1五、審核批準意見教研室主任（簽字） 設計總說明能夠選擇不同的調(diào)度算法（先來先服務，非強占式短進程優(yōu)先

4、算法），通過給出進程名、進程的到達時間和進程的運行時間，根據(jù)調(diào)度算法計算出進程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，比較調(diào)度算法的優(yōu)劣。關鍵字：先來先服務 短進程優(yōu)先調(diào)度 進程 平均周轉(zhuǎn)時間 平均帶權(quán)周轉(zhuǎn)時間目錄1.設計目的12.問題描述23.需求分析24.概要設計35.詳細設計46.調(diào)試分析77.使用說明88.設計總結(jié)109.參考文獻1110.程序源代碼12操作系統(tǒng)課程設計先來先服務和短進程優(yōu)先調(diào)度算法模擬1.設計目的“操作系統(tǒng)”是計算機專業(yè)的核心專業(yè)課，“操作系統(tǒng)課程設計”是理解和鞏固操作系統(tǒng)基本理論、原理和方法的重要的實踐環(huán)節(jié)。 操作系統(tǒng)課程主要講述的內(nèi)容是多道操作系統(tǒng)的原理與技術，與其它計

5、算機原理、編譯原理、匯編語言、計算機網(wǎng)絡、程序設計等專業(yè)課程關系十分密切。本課程設計的目的綜合應用學生所學知識，建立系統(tǒng)和完整的計算機系統(tǒng)概念，理解和鞏固操作系統(tǒng)基本理論、原理和方法，掌握操作系統(tǒng)基本理論與管理方式。在算法基礎上，解決實際的管理功能的問題，提高學生實際應用、編程的能力。課程設計要求學生在完成程序設計的同時能夠撰寫比較規(guī)范的設計報告。嚴格實施課程設計這一環(huán)節(jié)，對于學生基本程序設計素養(yǎng)的培養(yǎng)和軟件工作者工作作風的訓練，將起到顯著的促進作用。2.問題描述此次做的進程調(diào)度模擬系統(tǒng)，用戶可以輸入各進程信息（包含進程名、到達時間、運行時間）。輸入進程數(shù)，然后輸入進程的提交時間和運行時間，顯

6、示先來先服務調(diào)度算法和非強占式短進程優(yōu)先調(diào)度算法的作業(yè)號、提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、執(zhí)行時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。3.需求分析3.1 數(shù)據(jù)需求 需要用戶自行鍵入進程數(shù),進程提交時間和運行時間.3.2 基本功能需求模擬進程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）； 能夠輸入進程的基本信息，如進程名、到達時間和運行時間等； 根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列； 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。 3.3 非功能性需求用戶界面需求：簡潔、易用、易懂、友好的用戶界面。硬件要求：裝有Visual C+

7、6.0的計算機。可靠性需求：保證用戶在正常使用本系統(tǒng)時，用戶的操作或誤操作不會產(chǎn)生數(shù)據(jù)的丟失。4.概要設計4.1 數(shù)據(jù)結(jié)構(gòu)此次程序從大的方面來說是利用鏈表來實現(xiàn)的，在程序中定義了一個結(jié)構(gòu)體struct PCB用來保存每一條記錄，每個結(jié)點包括進程名（作業(yè)名）、進程的提交時間、運行時間、開始時間、結(jié)束時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。定義一個double型的handtime（提交時間），一個double型的asktime（運行時間）、starttime（開始時間）、endtime（結(jié)束時間）、usetime（周轉(zhuǎn)時間）、right（帶權(quán)周轉(zhuǎn)時間）以及整型的runorde

8、r（執(zhí)行的順序）和num（進程數(shù)），還定義一個指針next。4.2 系統(tǒng)包含的函數(shù) 先來先服務調(diào)度算法：void FCFS(pro p,int n)非強占式短進程優(yōu)先調(diào)度算法：void SJF(pro p,int n)4.2.3主函數(shù):int main()4.3 函數(shù)間的關系函數(shù)SJF和函數(shù)FCFS都在主函數(shù)中進行調(diào)用4.4 系統(tǒng)功能模塊圖圖4-1系統(tǒng)功能模塊圖5.詳細設計5.1 結(jié)構(gòu)體的詳細定義Struct pro的定義如下： struct prodouble handtime;double asktime;double starttime;double endtime;double use

9、time;double right;int runorder;int num;pro *next;5.2 系統(tǒng)函數(shù)詳細介紹先來先服務調(diào)度算法有兩種情況：一是進程的提交時間不一樣，是根據(jù)到達的先后順序來執(zhí)行的，先到達先執(zhí)行；二是進程的提交時間一樣，即所有的進程的到達時間是一樣的，要看進程的執(zhí)行順序，在前的進程先執(zhí)行。非強占式短進程優(yōu)先調(diào)度算法，有兩種情況：一是進程的到達的時間不一樣，那么首先執(zhí)行第一個到達的進程，執(zhí)行完后，然后比較剩下進程的到達時間和運行時間，先到達的和運行時間短的進程先運行；二是進程的到達時間一樣，比較所有的進程的運行時間，運行時間短的進程先執(zhí)行。5.3 系統(tǒng)功能模塊介紹系統(tǒng)功

10、能模塊主要分為兩大部分:先來先服務調(diào)度算法和非強占式短進程優(yōu)先調(diào)度算法.5.4 具體模塊設計先來先服務調(diào)度算法(圖1) 圖5-1先來先服務調(diào)度非強占式短進程優(yōu)先調(diào)度算法圖5-2非強占式短進程優(yōu)先調(diào)度6.調(diào)試分析測試數(shù)據(jù):到達時間不一樣進程3（1.2 2.4 3.2）進程4（1.3 2.5 3.1 4.2）到達時間一樣進程3（1.2 1.1 1.3）進程4（1.4 1.1 1.2 ）7.使用說明7.1到達時間不一樣 進程數(shù)為：3圖7-1進程數(shù)為：4圖7-27.2到達時間一樣 進程數(shù)為：3圖7-3進程數(shù)為：4圖7-48.設計總結(jié)這次課程設計給我一個很好的鍛煉和實踐的機會，讓我對那些算法有了更深的了

11、解。這次做的比較好的是直接把進程信息設定為一個結(jié)構(gòu)體，如此以來對進程的操作比較方便，實現(xiàn)了基本信息的有效封裝，充分利用鏈表來實現(xiàn)算法；還有就是基本上完成課程設計的要求，計算出平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，比較了兩種算法的優(yōu)劣。不過，這次課設也有很多不足之處，比如說在提交時間一樣的情況下，先來先服務是按照進程號的順序執(zhí)行，非強占式短進程優(yōu)先調(diào)度算法先執(zhí)行第一個進程，然后比較剩下進程的運行時間，運行時間最短的進程先進行。當提交時間一樣時，對于短進程優(yōu)先調(diào)度算法，應該是直接比較各個進程的運行時間，運行時間最短的進程先執(zhí)行，這個不足之處需要改進。通過這次課程設計，提高了方面的水平。從這次課設，我不僅

12、加深對操作系統(tǒng)知識的了解，而且更加提高自己的編程能力和實踐水平。雖然這次課程設計結(jié)束了，然而對操作系統(tǒng)的學習不能間斷，我要繼續(xù)學習操作系統(tǒng)的知識，了解和掌握各種不同類型的操作系統(tǒng)；還要加強自己的編程能力，讓自己的實踐水平更上一層樓。但是，我覺得既然是操作系統(tǒng)課程設計應該涉及到多個操作系統(tǒng)，讓我們了解更多不同的操作系統(tǒng)，通過不同的操作系統(tǒng)實踐，掌握各個不同系統(tǒng)的特點和區(qū)別。9.參考文獻【1】湯小丹、梁紅兵、哲鳳屏、湯子瀛 編著.計算機操作系統(tǒng)（第三版）.西安：西安電子科技大學出版社，2007.5【2】史美林編.計算機操作系統(tǒng)教程.北京：清華大學出版社，1999.11【3】徐甲同編著.操作系統(tǒng)教程

13、.西安：西安電子科技大學出版社，1996.8【4】Clifford，A.Shaffer編著.數(shù)決結(jié)構(gòu)與算法分析(C+版).北京：電子工業(yè)出版社，2005.7【5】蔣立翔編著.C+程序設計技能百練.北京：中國鐵道出版社，2004.1 10程序源代碼#include<iostream>using namespace std;struct prodouble handtime;double asktime;double starttime;double endtime;double usetime;double right;int runorder;int num;pro *next;/

14、-void SJF(pro p,int n);void FCFS(pro p,int n);/-int pronum;int main()pro p20;cout<<"請輸入進程的個數(shù):"cin>>pronum;cout<<"按時間先后順序輸入進程的提交時間和運行時間"<<endl;for(int i=0;i<pronum;i+)pi.num=i+1; cout<<"第"<<i+1<<"個進程:" cin>>pi.

15、handtime>>pi.asktime;while(pi.handtime<pi-1.handtime)cout<<"請從新輸入第"<<i+1<<"個進程:" cin>>pi.handtime>>pi.asktime; FCFS(p,pronum); SJF(p,pronum); return 0; /cout<<p1->handtime <<p1->asktime<<endl;/-void SJF(pro p,int n)in

16、t i,order=1;pro *now=&p0;pro *temp,*nextrun;p0.starttime=p0.handtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=order;+order;for(i=0;i<n-1;i+)pi.next=&pi+1;/cout<<now->next->num<<endl;pn-1.next=NULL;/*while(now!=NULL)cout<<now-

17、>num<<"t"<<now->handtime<<endl;now=now->next;*/while(now->next!=NULL)nextrun=now->next;/cout<<nextrun->handtime<<"t"<<nextrun->asktime<<"asdfafdsa"<<endl;/while(nextrun!=NULL) /確定nextrun /if(nextrun-&g

18、t;handtime>=now->endtime)nextrun->starttime=nextrun->handtime; elseif(nextrun->next!=NULL)temp=nextrun->next; while(temp->handtime<=now->endtime) /用來確定nextrun是否改變 if(temp->asktime<nextrun->asktime)nextrun=temp; if(temp->next!=NULL)temp=temp->next;else break;

19、 nextrun->starttime=now->endtime; /確定nextrun完畢 if(nextrun!=now->next)temp=now; /修改鏈表while(temp->next!=nextrun)temp=temp->next;temp->next=nextrun->next;temp=now->next; now->next=nextrun;nextrun->next=temp; /鏈表修改完畢 nextrun->endtime=nextrun->starttime+nextrun->ask

20、time;nextrun->usetime=nextrun->endtime-nextrun->handtime;nextrun->right=nextrun->usetime/nextrun->asktime;nextrun->runorder=order;+order; /進程信息修改完畢 now=nextrun;double sumtime=0,sumright=0;cout<<"SJF"<<endl;cout<<"作業(yè)號t提交t運行t開始t結(jié)束t周轉(zhuǎn)t帶權(quán)t執(zhí)行"<

21、;<endl;for(i=0;i<n;i+)sumtime+=pi.usetime;sumright+=pi.right;cout<<pi.num<<"t"<<pi.handtime<<"t"<<pi.asktime<<"t"<<pi.starttime<<"t"<<pi.endtime<<"t"<<pi.usetime<<"t&q

22、uot;<<pi.right<<"t"<<pi.runorder<<endl;cout<<"平均ttttt"<<sumtime/n<<"t"<<sumright/n<<endl;/-void FCFS(pro p,int n)int i;p0.starttime=p0.handtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=1;for(i=1;i<n;i+)if(pi.handtime<pi-1.endtime) pi.starttime=pi-1.endtime;elsepi.