進(jìn)程調(diào)度模擬設(shè)計——時間片輪轉(zhuǎn)、強占式短進(jìn)程優(yōu)先算法

1、學(xué) 號： 課 程 設(shè) 計題 目進(jìn)程調(diào)度模擬設(shè)計時間片輪轉(zhuǎn)、強占式短進(jìn)程優(yōu)先算法學(xué) 院計算機科學(xué)與技術(shù)專 業(yè)計算機科學(xué)與技術(shù)班 級姓 名指導(dǎo)教師2021年1月20日課程設(shè)計任務(wù)書學(xué)生姓名： 專業(yè)班級：計算機科學(xué)與技術(shù)學(xué)院 指導(dǎo)教師： 工作單位： 計算機科學(xué)與技術(shù)學(xué)院 題 目: 進(jìn)程調(diào)度模擬設(shè)計時間片輪轉(zhuǎn)、強占式短進(jìn)程優(yōu)先算法 初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的處理機管理章節(jié)內(nèi)容，對進(jìn)程調(diào)度的功能以及進(jìn)程調(diào)度算法有深入的理解。2實踐準(zhǔn)備：掌握一種計算機高級語言的使用。要求完成的主要任務(wù): 包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求1模擬進(jìn)程調(diào)度，能夠處理以下的情形： 能夠選擇不同的

2、調(diào)度算法要求中給出的調(diào)度算法； 能夠輸入進(jìn)程的根本信息，如進(jìn)程名、到達(dá)時間和運行時間等； 根據(jù)選擇的調(diào)度算法顯示進(jìn)程調(diào)度隊列； 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2設(shè)計報告內(nèi)容應(yīng)說明： 課程設(shè)計目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)； 源程序的主要局部； 測試用例，運行結(jié)果與運行情況分析； 自我評價與總結(jié)： = 1 * roman i你認(rèn)為你完成的設(shè)計哪些地方做得比擬好或比擬出色； = 2 * roman ii什么地方做得不太好，以后如何改正； = 3 * roman iii從本設(shè)計得到的收獲在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓(xùn)； = 4 * roman

3、iv完成此題是否有其他方法如果有，簡要說明該方法； = 5 * roman v對實驗題的評價和改良意見，請你推薦設(shè)計題目。時間安排：設(shè)計安排一周：周1、周2：完成程序分析及設(shè)計。周2、周3：完成程序調(diào)試及測試。周4、周5：驗收、撰寫課程設(shè)計報告?？记绊氈簢?yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記指導(dǎo)教師簽名： 年 月 日系主任或責(zé)任教師簽名： 年 月 日進(jìn)程調(diào)度模擬設(shè)計時間片輪轉(zhuǎn)、強占式短進(jìn)程優(yōu)先算法1.需求分析通過設(shè)計一個模擬進(jìn)程調(diào)度的系統(tǒng)，來實現(xiàn)進(jìn)程調(diào)度，對進(jìn)程調(diào)度的功能以及進(jìn)程調(diào)度算法有一個更加深入的理解。進(jìn)程PCB包含進(jìn)程名、到達(dá)時間、預(yù)計運行時間等調(diào)度算法時間片輪轉(zhuǎn)、強占式短進(jìn)程優(yōu)

4、先能夠處理以下的情形：1能夠選擇不同的調(diào)度算法要求中給出的調(diào)度算法2能夠輸入進(jìn)程的根本信息，如進(jìn)程名、到達(dá)時間和運行時間等3根據(jù)選擇的調(diào)度算法顯示進(jìn)程調(diào)度隊列4根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間此次做的進(jìn)程調(diào)度模擬系統(tǒng)，用戶可以輸入各進(jìn)程信息包含進(jìn)程名、到達(dá)時間、估計運行時間；輸入完畢確認(rèn)后，可選擇兩種調(diào)度算法中的一種執(zhí)行，查看結(jié)果可得到相應(yīng)算法的調(diào)度序列，每個進(jìn)程的到達(dá)時間、預(yù)計運行時間、開始時間、結(jié)束時間和周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間，以及平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。1.1 對進(jìn)程信息的描述和實現(xiàn)此次課程設(shè)計中，進(jìn)程作為根本數(shù)據(jù)處理單元，需要對進(jìn)程的根本信息進(jìn)行相關(guān)的描述。

5、進(jìn)程的根本信息包括進(jìn)程進(jìn)程名、到達(dá)的時間、預(yù)計的進(jìn)程運行時間、進(jìn)程開始運行時間、進(jìn)程仍需運行的時間、進(jìn)程完成的時間、進(jìn)程運行的次數(shù)等。在此，可以定義一個結(jié)構(gòu)體鏈表來儲存進(jìn)程信息。并在此根底上進(jìn)行其他操作。數(shù)據(jù)結(jié)構(gòu)如下：struct PCBstring name;/進(jìn)程名int ta;/進(jìn)程到達(dá)時間int ts;/進(jìn)程估計運行的時間int tb;/進(jìn)程開始運行時間int tm;/進(jìn)程仍需運行的時間int to;/進(jìn)程完成的時間int rn;/進(jìn)程運行的次數(shù)int totalTime;/周轉(zhuǎn)時間double weightTotalTime;/帶權(quán)周轉(zhuǎn)時間(周轉(zhuǎn)時間/估計運行時間PCB *next;

6、/定義指向下一個進(jìn)程的指針;1.2 對調(diào)度算法的描述和實現(xiàn)進(jìn)程根本信息所構(gòu)成的模塊作為根本單元，并且相關(guān)調(diào)度算法的側(cè)重進(jìn)程根本信息點不同，所以要根據(jù)其調(diào)度算法的特點來結(jié)合根本信息進(jìn)行對應(yīng)的設(shè)計。此次課程設(shè)計要求的調(diào)度算法描述如下： 時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)法的中心思想在于將CPU的運行劃分為一個個時間片，然后將這些時間片平均分配給已經(jīng)準(zhǔn)備就緒的進(jìn)程，在一個時間片內(nèi)只允許一個進(jìn)程占用處理器。如果當(dāng)前進(jìn)程運行結(jié)束那么時間片終止。這樣可以較公平的分配處理器運行時間，使每個進(jìn)程都可以得到處理。 強占式短進(jìn)程優(yōu)先調(diào)度算法此調(diào)度算法和先來先效勞調(diào)度算法相區(qū)別，強占式短進(jìn)程優(yōu)先調(diào)度算法 對強占式短進(jìn)程優(yōu)

7、先調(diào)度算法而言，其本質(zhì)特征便是按進(jìn)程的預(yù)計運行時間長短進(jìn)行排序，先執(zhí)行短進(jìn)程。假設(shè)內(nèi)存中運行的進(jìn)程優(yōu)先級比就緒隊列中的某進(jìn)程優(yōu)先級低即運行的進(jìn)程預(yù)計運行時間比就緒隊列中的某進(jìn)程長，此運行的進(jìn)程讓出內(nèi)存并進(jìn)入就緒隊列，優(yōu)先級更高的短進(jìn)程強占內(nèi)存資源并運行直到結(jié)束或者遇到優(yōu)先級更高的進(jìn)程強占為止。 2功能設(shè)計及模塊說明幾個主要函數(shù)的功能如下:void main() 程序主函數(shù),提示用戶輸入相關(guān)信息并輸出時間片輪轉(zhuǎn), 強占式短進(jìn)程算法的運行結(jié)果PCB *create(PCB *head);/創(chuàng)立進(jìn)程隊列void SJFrun(PCB *head);/強占式短進(jìn)程優(yōu)先算法 void cyclerun(

8、PCB *head);/時間片輪轉(zhuǎn)算法程序的主程序流程如下：void main()char choice;cout*進(jìn)程調(diào)度模擬設(shè)計時間片輪轉(zhuǎn)、強占式短進(jìn)程優(yōu)先算法*endl;cout*1.時間片輪轉(zhuǎn)算法*endl;cout*2.強占式短進(jìn)程優(yōu)先算法*endl;cout*else 退出*endl;cout請輸入您的選擇：choice;while(choice=1|choice=2)PCB *head=NULL;switch(choice)case 1:head=create(head);cyclerun(head);break;case 2:head=create(head);SJFrun(h

9、ead);break;cout*進(jìn)程調(diào)度模擬設(shè)計時間片輪轉(zhuǎn)、強占式短進(jìn)程優(yōu)先算法*endl;cout*1.時間片輪轉(zhuǎn)算法*endl;cout*2.強占式短進(jìn)程優(yōu)先算法*endl;cout*else 退出*endl;cout請輸入您的選擇：choice;3源程序的主要局部本次實驗是使用VC+6.0進(jìn)行編程,測試結(jié)果正確,程序運行無誤.本次課設(shè)設(shè)計重要代碼如下：3.1時間片輪轉(zhuǎn)算法void cyclerun(PCB *head)/時間片輪轉(zhuǎn)算法sort(head);int time=0;/記錄當(dāng)前時間int newarrive;/新到達(dá)進(jìn)程數(shù)PCB *rhead;rhead=new PCB;rhe

10、ad-next=rhead;/創(chuàng)立新的循環(huán)鏈表，存放當(dāng)前就緒隊列中的進(jìn)程PCB *p,*q;p=rhead;q=p-next;/q記錄當(dāng)前應(yīng)當(dāng)運行的進(jìn)程cout*endl;cout時間片長度為QTendl;cout*endl;while(time0)move(head,rhead,newarrive);/將head后的newarrive個節(jié)點移動到rhead隊列中if(rhead-next=rhead)time+;else if(q=rhead)p=q;q=q-next;elsecout進(jìn)程名:nameendl;cout到達(dá)時間:tarn=1)cout第rn次運行開始時間：timetb=tim

11、e;if(q-tmtm;q-to=time;q-totalTime=time-q-ta;cout進(jìn)程name運行結(jié)束時間：timeendl;cout周轉(zhuǎn)時間：totalTimeweightTotalTime=q-totalTime/(double)q-ts;weight+=q-weightTotalTime;cout帶權(quán)周轉(zhuǎn)時間：weightTotalTimeendl;cout*next;p-next=q;free(tmp);elseif(q-rn!=1)cout第rn次運行開始時間：timeendl;time+=QT;cout第rn次運行結(jié)束時間：timeendl;cout*tm-=QT;q

12、-rn+;p=q;q=q-next;cout平均周轉(zhuǎn)時間：total/(double)pronumendl;cout平均帶權(quán)周轉(zhuǎn)時間：weight/(double)pronumendl;cout*next!=NULL)count=getCount(head,time);if(count=0)time+;elseif(count=1)p=head;q=p-next;if(q-name!=re)cout*endl;cout進(jìn)程名：namename;cout到達(dá)時間：tarn=1)cout進(jìn)程開始運行時間：timern;-q-tm;if(q-tm=0)cout進(jìn)程name運行結(jié)束時間：timetot

13、alTime=time-q-ta;cout周轉(zhuǎn)時間：totalTimeweightTotalTime=q-totalTime/(double)q-ts;weight+=q-weightTotalTime;cout帶權(quán)周轉(zhuǎn)時間：weightTotalTimeendl;cout*next;if(q-name!=re)cout*endl;cout進(jìn)程名：namename;cout到達(dá)時間：tarn=1)cout進(jìn)程開始運行時間：timern;-q-tm;if(q-tm=0)cout進(jìn)程name運行結(jié)束時間：timetotalTime=time-q-ta;cout周轉(zhuǎn)時間：totalTimeweigh

14、tTotalTime=q-totalTime/(double)q-ts;weight+=q-weightTotalTime;cout帶權(quán)周轉(zhuǎn)時間：weightTotalTimeendl;cout*endl;del(p);cout平均周轉(zhuǎn)時間：total/(double)pronumendl;cout平均帶權(quán)周轉(zhuǎn)時間：weight/(double)pronumendl;cout*choice的時候流并不能將一個g正確賦給choice，而是停留在緩沖區(qū)。為了解決這一問題，我只能將choice設(shè)為char。雖然只有一字之差，但是結(jié)果就不一樣。本次課程設(shè)計還算簡單，所花時間不多。希望下次能難一些。 6

15、程序代碼附錄(重要代碼在之前已經(jīng)貼出來了，在此省略)#include#includeusing namespace std;#define QT 2/定義時間片長度為2struct PCBstring name;/進(jìn)程名int ta;/進(jìn)程到達(dá)時間int ts;/進(jìn)程估計運行的時間int tb;/進(jìn)程開始運行時間int tm;/進(jìn)程仍需運行的時間int to;/進(jìn)程完成的時間int rn;/進(jìn)程運行的次數(shù)int totalTime;/周轉(zhuǎn)時間double weightTotalTime;/帶權(quán)周轉(zhuǎn)時間(周轉(zhuǎn)時間/估計運行時間PCB *next;/定義指向下一個進(jìn)程的指針;int pronum;

16、/定義進(jìn)程數(shù)為pronumint total;/記錄所有進(jìn)程的總時間double weight;/記錄所有進(jìn)程的總帶權(quán)周轉(zhuǎn)時間PCB *create(PCB *head);/創(chuàng)立進(jìn)程隊列void del(PCB *p);/刪除p的下一個節(jié)點void sort(PCB *head);/將進(jìn)程按到達(dá)的先后順序排列int getCount(PCB *head,int time);/觀察在time之前到達(dá)但未移動到運行隊列的進(jìn)程數(shù)量PCB *searchEnd(PCB *head);/查找并返回循壞隊列的尾節(jié)點void move(PCB *headF,PCB *headT,int n);/將headF

17、后的n個節(jié)點移動到循環(huán)隊列headT中void cyclerun(PCB *head);/時間片輪轉(zhuǎn)算法PCB *SJF(PCB *head,int count);/在頭節(jié)點后的count個節(jié)點中選擇需時間最小的返回void SJFrun(PCB *head);/強占式短進(jìn)程優(yōu)先算法PCB *create(PCB *head)PCB *p1,*p2;p1=p2=new PCB;head=p1;coutpronum;for(int i=0;inext=NULL;cout請依次輸入第i+1個進(jìn)程的信息(進(jìn)程名、到達(dá)時間、估計運行時間)：p1-namep1-tap1-ts;p1-tm=p1-ts;p

18、1-rn=1;total+=p1-ts;p2-next=p1;return head;void sort(PCB *head)/將進(jìn)程按到達(dá)的先后順序排列PCB *p,*q,*r,*s;if(head-next!=NULL)p=head-next-next;head-next-next=NULL;while(p)q=p;p=p-next;r=head;s=head-next;while(s&s-tata)r=s;s=s-next;r-next=q;q-next=s;void del(PCB * p)/刪除p的下一個節(jié)點PCB *tmp;tmp=p-next;p-next=tmp-next;free(tmp);int getCount(PCB *head,int time)/觀察在time之前到達(dá)但未移動到運行隊列的進(jìn)程數(shù)量int count=0;PCB *s,*t;s=head;t=s-next;while(t!=NULL&t-tanext; count+;/count記錄當(dāng)前時刻到達(dá)的進(jìn)程數(shù)return count;PCB* searchEnd(PCB *head)/查找并返回循壞隊列的尾節(jié)點PCB *p,*q;p=head;q=head-next;while(q-next!=head) p=q; q=q-next;retu