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

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

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

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

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

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

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

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

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

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

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

12、-rn+;p=q;q=q-next;cout平均周轉(zhuǎn)時(shí)間：total/(double)pronumendl;cout平均帶權(quán)周轉(zhuǎn)時(shí)間：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á)時(shí)間：tarn=1)cout進(jìn)程開(kāi)始運(yùn)行時(shí)間：timern;-q-tm;if(q-tm=0)cout進(jìn)程name運(yùn)行結(jié)束時(shí)間：timetot

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

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

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

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

17、后的n個(gè)節(jié)點(diǎn)移動(dòng)到循環(huán)隊(duì)列headT中void cyclerun(PCB *head);/時(shí)間片輪轉(zhuǎn)算法PCB *SJF(PCB *head,int count);/在頭節(jié)點(diǎn)后的count個(gè)節(jié)點(diǎn)中選擇需時(shí)間最小的返回void SJFrun(PCB *head);/強(qiáng)占式短進(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請(qǐng)依次輸入第i+1個(gè)進(jìn)程的信息(進(jìn)程名、到達(dá)時(shí)間、估計(jì)運(yùn)行時(shí)間)：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的下一個(gè)節(jié)點(diǎn)PCB *tmp;tmp=p-next;p-next=tmp-next;free(tmp);int getCount(PCB *head,int time)/觀察在time之前到達(dá)但未移動(dòng)到運(yùn)行隊(duì)列的進(jìn)程數(shù)量int count=0;PCB *s,*t;s=head;t=s-next;while(t!=NULL&t-tanext; count+;/count記錄當(dāng)前時(shí)刻到達(dá)的進(jìn)程數(shù)return count;PCB* searchEnd(PCB *head)/查找并返回循壞隊(duì)列的尾節(jié)點(diǎn)PCB *p,*q;p=head;q=head-next;while(q-next!=head) p=q; q=q-next;retu