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

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

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