時(shí)間片輪轉(zhuǎn)、最高響應(yīng)比優(yōu)先調(diào)度算法

學(xué)號(hào)：012081034課程設(shè)計(jì)題目時(shí)間片輪轉(zhuǎn)、最高響應(yīng)比優(yōu)先調(diào)度算法學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)姓名指導(dǎo)教師2011年1月20日課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名：李文軒專(zhuān)業(yè)班級(jí)：計(jì)算機(jī)0809指導(dǎo)教師：汪祥莉工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院題目：進(jìn)程調(diào)度模擬設(shè)計(jì)一-一時(shí)間片輪轉(zhuǎn)、最高響應(yīng)比優(yōu)先調(diào)度算法初始條件：預(yù)備內(nèi)容：閱讀操作系統(tǒng)的處理機(jī)管理章節(jié)內(nèi)容，對(duì)進(jìn)程調(diào)度的功能以及進(jìn)程調(diào)度算法有深入的理解。實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語(yǔ)言的使用。要求完成的主要任務(wù)：（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）1.模擬進(jìn)程調(diào)度，能夠處理以下的情形：⑴能夠選擇不同的調(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ō)明）；⑶開(kāi)發(fā)平臺(tái)及源程序的主要部分；⑷測(cè)試用例，運(yùn)行結(jié)果與運(yùn)行情況分析；⑸我評(píng)價(jià)自與總結(jié)：i）你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計(jì)得到的收獲（在編寫(xiě)，調(diào)試，執(zhí)行過(guò)程中的經(jīng)驗(yàn)和教訓(xùn)）；iv）完成本題是否有其他方法（如果有，簡(jiǎn)要說(shuō)明該方法）；v）對(duì)實(shí)驗(yàn)題的評(píng)價(jià)和改進(jìn)意見(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)告。（注意事項(xiàng)：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）指導(dǎo)教師簽名：年月日系主任（或責(zé)任教師）簽名：年月日需求分析1.1.模擬進(jìn)程調(diào)度，能夠處理以下的情形：⑴能夠選擇不同的調(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í)間。L2這個(gè)實(shí)驗(yàn)主要是進(jìn)程調(diào)度模擬設(shè)計(jì)，進(jìn)程調(diào)度有很多方法，這個(gè)課程設(shè)計(jì)要求我要使用時(shí)間片輪轉(zhuǎn)和最高響應(yīng)比兩中算法，來(lái)實(shí)現(xiàn)對(duì)進(jìn)程的模擬。首先他要求能夠用兩種方法實(shí)現(xiàn)進(jìn)程調(diào)度，我們需要首先輸出一個(gè)選擇程序，來(lái)選擇一個(gè)調(diào)度算法，入數(shù)據(jù)來(lái)進(jìn)行運(yùn)算，這是我們首先要解決的問(wèn)題。其次，我們要接近輸入數(shù)據(jù)的存放問(wèn)題，畢竟我還需要數(shù)據(jù)來(lái)進(jìn)行操作和調(diào)度。我們要用結(jié)構(gòu)體來(lái)存放一個(gè)進(jìn)程的相關(guān)信息，例如：進(jìn)程名字，進(jìn)程到達(dá)時(shí)間，進(jìn)程的運(yùn)行時(shí)間。但是我們?cè)诔鰜?lái)進(jìn)程的時(shí)候，還必須要按照一定的順序來(lái)處理，所以我們必須要對(duì)結(jié)構(gòu)體里存放的進(jìn)程相關(guān)信息來(lái)進(jìn)行排序。只有經(jīng)過(guò)處理過(guò)后，才能更容易的實(shí)現(xiàn)進(jìn)程的調(diào)度，同時(shí)當(dāng)不只一個(gè)進(jìn)程的時(shí)候，我們還必須設(shè)置用多個(gè)地址單元來(lái)實(shí)驗(yàn)對(duì)輸入的數(shù)據(jù)進(jìn)行存儲(chǔ)，多個(gè)輸入就相當(dāng)于的鏈表的插入處理，因此我們又必須要對(duì)鏈表之間的指針進(jìn)行處理，這涉及到指針的跳轉(zhuǎn)，我們必須要運(yùn)用我們所學(xué)的知識(shí)進(jìn)行。我們還必須要對(duì)程序的輸出進(jìn)行處理，因?yàn)榘凑諏?shí)驗(yàn)要求，我們必須顯示進(jìn)程調(diào)度隊(duì)列；根據(jù)選擇的調(diào)度算法計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。這要求我們要設(shè)計(jì)算法，將進(jìn)程的調(diào)度順序給輸出，從輸出就可以檢查自己的設(shè)計(jì)是否是正確的，而響應(yīng)比其實(shí)進(jìn)程的等待時(shí)間加上執(zhí)行時(shí)間，在除以執(zhí)行時(shí)間，得到的結(jié)果就是響應(yīng)比。而最高響應(yīng)比就是沒(méi)當(dāng)一個(gè)進(jìn)程執(zhí)行完成后，在這個(gè)時(shí)間比較各個(gè)時(shí)間各個(gè)進(jìn)程的響應(yīng)比，響應(yīng)比最大的就會(huì)執(zhí)行，而其他的進(jìn)程則繼續(xù)等待，一直循環(huán)做這個(gè)操作，這就是所謂的是最高響應(yīng)比調(diào)度算法。時(shí)間片輪轉(zhuǎn)法就是將CPU的執(zhí)行時(shí)間分成一個(gè)個(gè)大小相等的時(shí)間片，將這些時(shí)間片分別執(zhí)行就緒隊(duì)列中的進(jìn)程，時(shí)間片用完的進(jìn)程就會(huì)回答就緒隊(duì)列的隊(duì)尾，等待CPU的再次執(zhí)行。而周轉(zhuǎn)時(shí)間則是完成時(shí)間減去提交時(shí)間，平均周轉(zhuǎn)時(shí)間就是幾個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間的平均值。而帶權(quán)周轉(zhuǎn)時(shí)間就是周轉(zhuǎn)時(shí)間除以執(zhí)行時(shí)間。功能設(shè)計(jì)2.1最高響應(yīng)比的功能設(shè)計(jì)2.1.1最高響應(yīng)比的結(jié)構(gòu)體structzgxyb{charname[10];floatarrivetime;floatservicetime;floatstarttime;floatfinishtime;floatzztime;floatdqzztime;}；2.2.1時(shí)間片的結(jié)構(gòu)體typedefstructnode{datatypeNum,runtime;charName[10];//定義成字符串structnode*next;}linknode;開(kāi)發(fā)平臺(tái)及源程序的主要部分3.1實(shí)驗(yàn)的開(kāi)發(fā)平臺(tái)VisualC++6.03.2實(shí)驗(yàn)的主要代碼voidinput(zgxyb*p,intN){inti;printf("intputtheprocess'sname&arrivetime&servicetime:\nforexmple:a0100\n");for(i=0;i<=N-1;i++){printf("inputthe%dthprocess'sinformation:\n”,i+1);scanf("%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);}}voidPrint(zgxyb*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,intN){intk;printf("runorder:");printf("%s”,p[0].name);for(k=1;k<N;k++){printf("一>%s”,p[k].name);}printf("\ntheprocess'sinformation:\n");printf("\nname\tarrive\tservice\tstart\tfinish\tzz\tdqzz\n");for(k=0;k<=N-1;k++){printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);}}//按到達(dá)時(shí)間排序voidsort(zgxyb*p,intN){for(inti=0;i<=N-1;i++)for(intj=0;j<=i;j++)if(p[i].arrivetime<p[j].arrivetime){zgxybtemp;temp=p[i];p[i]=p[j];p[j]=temp;}}//yunxingjieduanvoiddeal(zgxyb*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,intN){intk;for(k=0;k<=N-1;k++){if(k==0){p[k].starttime=p[k].arrivetime;p[k].finishtime=p[k].arrivetime+p[k].servicetime;}else{p[k].starttime=p[k-1].finishtime;p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}}for(k=0;k<=N-1;k++){p[k].zztime=p[k].finishtime-p[k].arrivetime;p[k].dqzztime=p[k].zztime/p[k].servicetime;}}voidZGXYB(zgxyb*p,intN){floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;sort(p,N);for(intm=0;m<N-1;m++){if(m==0)p[m].finishtime=p[m].arrivetime+p[m].servicetime;elsep[m].finishtime=p[m-1].finishtime+p[m].servicetime;inti=0,n;for(n=m+1;n<=N-1;n++){if(p[n].arrivetime<=p[m].finishtime)i++;}floatmax=(p[m].finishtime-p[m+1].arrivetime)/p[m+1].servicetime;//第m+1個(gè)的響應(yīng)比intfollow=m+1;for(intk=m+1;k<m+i;k++){if(max<=(p[m].finishtime-p[k+1].arrivetime)/p[k+1].servicetime){max=(p[m].finishtime-p[k+1].arrivetime)/p[k+1].servicetime;follow=k+1;}}zgxybtemp;temp=p[m+1];p[m+1]=p[follow];p[follow]=temp;}deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);}linklistcreatlinklist(){linklisthead,r,s;intx,y;charch[10];//因?yàn)橐數(shù)氖亲址甴ead=r=(linklist)malloc(sizeof(linknode));printf("\n請(qǐng)輸入一組編號(hào)，作業(yè)名，運(yùn)行時(shí)間，以結(jié)尾\n");scanf("%d%s%d”,&x,&ch,&y);while(x){inta=10;s=(linklist)malloc(sizeof(linknode));s->Num=x;s->runtime=y;//strcpy(s->Name,ch);//直接字符串復(fù)制for(inti=0;i<a;i++){s->Name[i]=ch[i];}r->next=s;r=s;scanf("%d%s%d”,&x,&ch,&y);}r->next=NULL;returnhead;}/*輸出帶頭結(jié)點(diǎn)的單鏈表*/voidprint(linklisthead){linklistp;p=head->next;printf("Listis:\n");printf("NumNameruntime\n");while(p){printf("%d%5s%6d\n”,p->Num,p->Name,p->runtime);p=p->next;}printf("\n");}voidmain(){intG;scanf("%d”,&G);if(G==1){linklisthead,pre,p,r;intt,i;head=creatlinklist();print(head);printf("請(qǐng)輸入runtime:");scanf("%d”,&t);pre=head;p=head->next;while(p){if(p->runtime>t)/*如果運(yùn)行時(shí)間大于時(shí)間片*/{r=p->next;p->runtime=p->runtime-t;/*將第一個(gè)進(jìn)程的運(yùn)行時(shí)間減去一個(gè)時(shí)間片的時(shí)間*/while(r->next)/*將r指向鏈表的最后一個(gè)結(jié)點(diǎn)以便用尾插法將P結(jié)點(diǎn)插入到鏈表的最后*/{r=r->next;}pre->next=p->next;p->next=NULL;r->next=p;p=head->next;i=1;while(p)/*將進(jìn)程的序號(hào)重新從開(kāi)始設(shè)置一遍*/{p->Num=i++;p=p->next;}}else{pre->next=p->next;/*如果進(jìn)程運(yùn)行時(shí)間小于時(shí)間片，就將第一個(gè)進(jìn)程刪除*/free(p);p=head->next;i=1;while(p)/*因?yàn)閯h了一個(gè)進(jìn)程就需要重新從開(kāi)始設(shè)置一遍進(jìn)程的排列序號(hào)*/{p->Num=i++;p=p->next;}}print(head);/*打印進(jìn)程列表*/pre=head;p=head->next;}}else{intN;printf("高響應(yīng)比調(diào)度算法\n");printf("inputtheprocess'snumber:\n");scanf("%d”,&N);input(a,N);zgxyb*c=a;ZGXYB(c,N);}}運(yùn)行結(jié)果與運(yùn)行情況分析程序的第一步選擇最高響應(yīng)比調(diào)度算法，輸入進(jìn)程輸入3個(gè)，進(jìn)程名字提交時(shí)間運(yùn)行時(shí)間a23b32c33程序的驗(yàn)證:第一個(gè)進(jìn)程在2點(diǎn)提交，3個(gè)小時(shí)的執(zhí)行時(shí)間，在2點(diǎn)沒(méi)有別的進(jìn)程，所以a先執(zhí)行，5點(diǎn)執(zhí)行完后，而在5點(diǎn)執(zhí)行前，b，c都提交了，所以就要判斷響應(yīng)比，響應(yīng)比是等待時(shí)間加上執(zhí)行時(shí)間，除以執(zhí)行時(shí)間，所以b的響應(yīng)比是2,c的響應(yīng)比是5/3,所以b的響應(yīng)比高，b先執(zhí)行，最后是c執(zhí)行，周轉(zhuǎn)時(shí)間是完成時(shí)間減去提交時(shí)間，而帶權(quán)周轉(zhuǎn)時(shí)間是周轉(zhuǎn)時(shí)間除以執(zhí)行時(shí)間。經(jīng)檢驗(yàn)，平均周轉(zhuǎn)時(shí)間4.67，平均帶權(quán)周轉(zhuǎn)時(shí)間是1.67.，經(jīng)檢驗(yàn)，結(jié)果是正確的。

如果是時(shí)間片輪轉(zhuǎn)則運(yùn)行結(jié)果為：我評(píng)價(jià)自與總結(jié)5.1程序好的方面本次實(shí)驗(yàn)的輸入與輸出基本滿足實(shí)驗(yàn)所要求的，最高響應(yīng)比的調(diào)度算法的輸出結(jié)果采用表格的形式的輸出，比較清晰，容易看懂，通過(guò)輸出結(jié)果能夠清晰的看出結(jié)果的正確與否。輸入與輸出比較明確，不會(huì)出現(xiàn)多種意思。結(jié)構(gòu)比較清晰，不會(huì)到處跳轉(zhuǎn)，容易理解。指令之間的跳轉(zhuǎn)不會(huì)讓人難以理解。最高響應(yīng)比中進(jìn)程分為兩個(gè)狀態(tài)，等待狀態(tài)和完成狀態(tài)，當(dāng)程序完成時(shí)候狀態(tài)變成完成狀態(tài)，每次執(zhí)行只會(huì)執(zhí)行等待狀態(tài)的進(jìn)程，不會(huì)執(zhí)行完成狀態(tài)的進(jìn)程。結(jié)果中還有調(diào)度順序，5.2從本設(shè)計(jì)得到的收獲從本次實(shí)驗(yàn)中，我學(xué)到了較多東西，首先是結(jié)構(gòu)體的定義和調(diào)用，這次實(shí)驗(yàn)首先遇到的問(wèn)題結(jié)構(gòu)體的定義和調(diào)用，之后還涉及到指針的跳轉(zhuǎn)，鏈表的插入與刪除，因此指針的跳轉(zhuǎn)是必須要飛行清楚明白的，否則就會(huì)出現(xiàn)各種錯(cuò)誤，最終將需要修改，而且還必須學(xué)會(huì)子函數(shù)的使用，必須實(shí)驗(yàn)各種子函數(shù)來(lái)實(shí)現(xiàn)不同的功能，綜合起來(lái)才能實(shí)現(xiàn)實(shí)驗(yàn)所要求的功能。同時(shí)函數(shù)的頭文件也必須要包含多個(gè)東西，來(lái)適應(yīng)我們的要求，同時(shí)我們還必須根據(jù)要求使用多個(gè)全局變量，來(lái)實(shí)現(xiàn)我們的各種要求。5.4其他方法對(duì)與最高響應(yīng)比的想法：前提設(shè)定：參數(shù)進(jìn)程隊(duì)列按順序排好。設(shè)置一個(gè)系統(tǒng)時(shí)間變量，記錄當(dāng)前系統(tǒng)時(shí)間調(diào)度算法思路：系統(tǒng)時(shí)間取得第一個(gè)進(jìn)程的提交時(shí)間，并執(zhí)行第一個(gè)進(jìn)程；當(dāng)某進(jìn)程執(zhí)行完成時(shí)，系統(tǒng)時(shí)間加上該完成進(jìn)程的運(yùn)行時(shí)間，并刪除該節(jié)點(diǎn)，若第一個(gè)節(jié)點(diǎn)的提交時(shí)間就比當(dāng)前系統(tǒng)時(shí)間大或等于，此情況下，需要修改系統(tǒng)時(shí)間，且此時(shí)第一個(gè)進(jìn)程就是下一個(gè)該調(diào)度的進(jìn)程，否側(cè)，在從頭結(jié)點(diǎn)開(kāi)始掃描進(jìn)程隊(duì)列，直到某進(jìn)程提交時(shí)間大于等于當(dāng)前系統(tǒng)時(shí)間，先假設(shè)第一個(gè)的響應(yīng)比最高，標(biāo)志指針指向第一個(gè)節(jié)點(diǎn)，掃描過(guò)程中，記錄當(dāng)前掃描到的進(jìn)程的響應(yīng)比，若比記錄值大，則修改記錄值和標(biāo)志指針。掃描完成后，執(zhí)行標(biāo)志指針指向的