操作系統(tǒng)課程設(shè)計報告-處理機調(diào)度問題

第第二十頁目錄TOC\o"1-3"\u目錄 11．設(shè)計題目與要求 21.1設(shè)計目的 21.2設(shè)計要求 22．總體設(shè)計思想 22.1總體設(shè)計思想 23．功能設(shè)計 43.1數(shù)據(jù)結(jié)構(gòu)設(shè)計 43.2程序清單 43.3運行結(jié)果 74.設(shè)計心得 95.參考資料 9附錄 10程序源代碼： 10一．設(shè)計題目與要求課題：理機調(diào)度模擬程序：選擇一個調(diào)度算法，實現(xiàn)處理機調(diào)度。1.設(shè)計目的：在多道程序和多任務(wù)系統(tǒng)中，系統(tǒng)內(nèi)同時處于就緒狀態(tài)的進程可能有若干個。也就是說能運行的進程數(shù)大于處理機個數(shù)。為了使系統(tǒng)中的進程能有條不紊地工作，必須選用某種調(diào)度策略，選擇一進程占用處理機。要求學生設(shè)計一個模擬處理機調(diào)度算法，以鞏固和加深處理機調(diào)度的概念。2.設(shè)計要求：1）進程調(diào)度算法包括：時間片輪轉(zhuǎn)法，短作業(yè)優(yōu)先算法，最高響應(yīng)比優(yōu)先算法。2）可選擇進程數(shù)量3）本程序包括三種算法，可用C語言實現(xiàn)，執(zhí)行時在主界面選擇算法（可用函數(shù)實現(xiàn)），進入子頁面后輸入進程數(shù)及每個進程的運行時間，每個進程的優(yōu)先數(shù)由隨機函數(shù)產(chǎn)生且優(yōu)先數(shù)隨等待時間而變化，執(zhí)行，顯示結(jié)果。二．總體設(shè)計思想(1)進程的創(chuàng)建：由系統(tǒng)為某個進程設(shè)置一個進程控制塊PCB，用于對進程進行控制和管理。進程任務(wù)完成，由系統(tǒng)收回其PCB，該進程便消亡。(2)進程的三種狀態(tài)：運行、就緒、完成。進程的三種狀態(tài)可以通過設(shè)計三個鏈隊列來實現(xiàn)：finish為完成隊列的頭指針，ready為就緒隊列的頭指針，tail為循環(huán)輪轉(zhuǎn)法隊列的尾指針。因為每一時刻，CPU只能運行一個進程，所以運行隊列只有一個run指針指向當前運行進程。(3)進程調(diào)度的功能：按照一定的策略從就緒隊列的多個進程中選取一個進程，使其獲得CPU而運行。①動態(tài)優(yōu)先數(shù)調(diào)度算法：思想：為每一個進程設(shè)一個優(yōu)先數(shù)，它總是把處理機給就緒隊列中具有最高優(yōu)先級的進程。初始的進程優(yōu)先數(shù)是隨機產(chǎn)生的，隨著進程的運行對優(yōu)先數(shù)進行調(diào)整，每次運行時都是從就緒隊列中選取優(yōu)先數(shù)最大的進程運行，所以將就緒隊列按照優(yōu)先數(shù)的大小從高到低排序，這樣，每次取對首進程即可。將進程按優(yōu)先數(shù)的大小排列在就緒隊列中，每次選取就緒隊列中優(yōu)先權(quán)最高的進程首先占用處理機。優(yōu)先數(shù)由隨機函數(shù)產(chǎn)生進程最初的優(yōu)先數(shù)。優(yōu)先數(shù)的動態(tài)變化：進程每執(zhí)行一次優(yōu)先數(shù)-1。優(yōu)先數(shù)隨著進程的執(zhí)行進行調(diào)整，每次執(zhí)行時都從就緒隊列中選取優(yōu)先數(shù)最大的進程投入運行。②時間片輪轉(zhuǎn)調(diào)度算法：思想：將所有進程按照先來先服務(wù)的規(guī)則排成一個隊列，把CPU分配給就緒隊列的隊首進程，并規(guī)定它的執(zhí)行時間（稱此時間為時間片），當時間片用完但并未執(zhí)行結(jié)束時，剝奪該進程的執(zhí)行，將其鏈接到就緒隊列的隊尾，等待下一次的選擇。將就緒隊列的隊首指針投入運行。③短作業(yè)優(yōu)先調(diào)度算法（不可剝奪式的）思想：根據(jù)估計運行時間的長短，將各個進程排成一個就緒隊列（估計運行時間最短的進程排在隊首），每次運行將隊首進程投入運行，直到運行結(jié)束，將此進程連接到完成隊列的隊尾。然后，再將下一個隊首進程投入運行，直到所有的進程都運行完畢。三．功能設(shè)計1.數(shù)據(jù)結(jié)構(gòu)設(shè)計PCB結(jié)構(gòu)體：typedefstructnode{charname[10];/*進程時間輪轉(zhuǎn)時間片*/intpid;/*進程的標號*/intprio;/*優(yōu)先級*/intround;/*時間片*/intcputime;/*進程占用cpu的時間*/intruntime;/*進程運行所用的時間*/intwaittime;/*進程的等待時間*/intlength;/*進程的長度*/intcount;/*計數(shù)器*/charstate;/*進程的狀態(tài)*/structnode*next;/*鏈指針*/}PCB ;PCB結(jié)構(gòu)體用于標識進程的創(chuàng)建與撤消。鏈指針：PCB*finish,*ready,*tail,*run;.Finish：完成隊列的首指針，用于標識完成隊列；Ready：就緒隊列的首指針，用于標識就緒隊列；；Run：運行隊列的首指針，用于標識運行隊列；；Tail：循環(huán)輪轉(zhuǎn)隊列的尾指針；2.程序清單（1）Create1（），create2（），create3（）分別為創(chuàng)建進程的函數(shù)Create1（）：按照優(yōu)先級調(diào)度算法創(chuàng)建進程，用戶輸入進程名及進程所需的時間后，創(chuàng)建每個進程的PCB，將每個進程的PCB調(diào)用函數(shù)insert1（）按照優(yōu)先數(shù)從高到低排列到就緒隊列中。create2（）：按照時間片調(diào)度算法創(chuàng)建進程，用戶輸入進程名及進程所需的時間后，創(chuàng)建每個進程的PCB，將每個進程的PCB調(diào)用函數(shù)insert2（）將每個進程PCB按照輸入的先后順序插入到就緒隊列的末尾。create3（）：按照短作業(yè)優(yōu)先調(diào)度算法創(chuàng)建進程，用戶輸入進程名及進程所需的時間后，創(chuàng)建每個進程的PCB，將每個進程的PCB調(diào)用函數(shù)insert3（）：按照作業(yè)估計執(zhí)行時間的長短從高到低排列到就緒隊列中。就緒隊列創(chuàng)建好后，將隊列當中的第一個PCB變?yōu)檫\行態(tài)“R”，將run指針指向它，ready指針后移，作為就緒隊列的新頭指針，然后調(diào)用調(diào)度算法。注意每個時刻只能有一個進程處于運行態(tài)。（2）insert1（），insert2（），insert3（）分別為插入函數(shù)這三個函數(shù)完成的是就緒隊列的創(chuàng)建和管理。①insert1（）的功能是將未完成且優(yōu)先數(shù)小于其它進程的PCB按進程優(yōu)先數(shù)的順序插入到就緒隊列中去。②insert2（）的功能是將執(zhí)行了一個時間片且還未完成的進程的PCB插入到就緒隊列的隊尾。③insert3（）的功能是將未完成且作業(yè)的執(zhí)行時間小于其它進程的PCB按進程的作業(yè)的執(zhí)行時間的長短插入到就緒隊列中去。（3）priority（）優(yōu)先數(shù)調(diào)度算法①假定系統(tǒng)有三個進程，每一個進程用一個進程控制塊PCB來代表，進程控制塊的格式為：typedefstructnode{intpid;/*進程的標號*/intprio;/*優(yōu)先級*/intcputime;/*進程占用cpu的時間*/intruntime;/*進程運行所用的時間*/charstate;/*進程的狀態(tài)*/structnode*next;/*鏈指針*/}PCB;（4）roundrun（）時間片輪轉(zhuǎn)法調(diào)度算法①假定系統(tǒng)有三個進程，每一個進程用一個進程控制塊PCB來代表。進程控制塊的格式為：進程名，進程占用cpu的時間，進程到完成還需的時間，時間片，計數(shù)器，狀態(tài)進程名——作為進程的標識，假設(shè)三個進程的進程名分別是p1，p2，p3。時間片——時間片輪轉(zhuǎn)循環(huán)所需的時間總數(shù)。計數(shù)器——對進程執(zhí)行時間進行計數(shù)。進程占用cpu的時間——假設(shè)進程已經(jīng)運行的單位時間數(shù)，初始值為“0”。狀態(tài)——有三種狀態(tài)，“就緒”狀態(tài)，“運行”狀態(tài)和“完成”狀態(tài)。三個進程的初始狀態(tài)都為“就緒”，用“w”表示，當一個進程運行結(jié)束后，它的狀態(tài)為“完成”，用“F”表示，當一個進程正在占用cpu時，它的狀態(tài)為“運行”狀態(tài)。②每次運行所設(shè)計的時間片輪轉(zhuǎn)調(diào)度程序之前，為每個進程任意確定它的“要求運行時間”。③把三個進程按先來先服務(wù)的順序排成循環(huán)隊列，用指針指出隊列連接情況。時間片輪轉(zhuǎn)調(diào)度總是選擇ready指針指示的進程運行。而是執(zhí)行：進程到完成還需的時間－1進程占用cpu的時間+1計數(shù)器+1來模擬進程的一次運行，表示進程已經(jīng)運行過一個單位的時間。（5）shortjob（）短作業(yè)優(yōu)先法調(diào)度算法 ①假定系統(tǒng)有三個進程，每一個進程用一個進程控制塊PCB來代表，進程控制塊的格式為：進程名，進程占用cpu的時間，進程到完成還需的時間，狀態(tài)進程名——作為進程的標識，假設(shè)三個進程的進程名分別為P1，P2，P3。進程占用cpu的時間——假設(shè)進程已經(jīng)運行的單位時間數(shù)，初始值為“0”。狀態(tài)——有三種狀態(tài)，“就緒”狀態(tài)，“運行”狀態(tài)和“完成”狀態(tài)。三個進程的初始狀態(tài)都為“就緒”，用“w”表示，當一個進程運行結(jié)束后，它的狀態(tài)為“完成”，用“F”表示，當一個進程正在占用cpu時，它的狀態(tài)為“運行”狀態(tài)。②在每次運行所設(shè)計的短作業(yè)優(yōu)先調(diào)度程序之前，為每個進程任意確定它的“要求運行時間”。③為了調(diào)度方便，把三個進程按任意給定的作業(yè)長短進行排序。用一單元指出隊首進程，用指針指出隊列的連接情況。每次取對首進程即可。④短作業(yè)調(diào)度總是選隊首進程運行。進程每運行一次，要求運行時間-1進程占用cpu的時間+1來模擬進程的一次運行。⑤進程運行一次后，若要求運行時間〉0，則再將它插入就緒隊列（按作業(yè)長短插入，且置隊首標志）；若要求運行時間=0，則把它的狀態(tài)修改成“完成”（F），且退出隊列。⑥若“就緒”狀態(tài)的進程隊列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進程都成為“完成”狀態(tài)。⑦在設(shè)計的程序中有顯示或打印語句，能顯示或打印每次被選中進程的進程名以及運行一次后進程隊列的變化及狀態(tài)。⑧為三個進程隨機確定“要求運行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中進程的進程名以及進程控制塊的動態(tài)變化過程。（6）界面設(shè)計：主界面：選擇調(diào)度算法；子界面：輸入進程數(shù)，進程名及進程所需的時間；利用c語言中的畫圖函數(shù)及清屏函數(shù)設(shè)計界面。3．運行結(jié)果主界面設(shè)計：（1,2,3算法4退出）算法1：動態(tài)優(yōu)先級算法算法2：時間片輪轉(zhuǎn)法算法3：短作業(yè)優(yōu)先法四．心得體會及總結(jié)：處理機調(diào)度問題實際上是處理機分配問題。只有那些參與競爭處理機所必須的資源都已得到滿足的進程才能享受競爭處理機的資格，這時它們處于內(nèi)存就緒狀態(tài)。這些必須的資源包括內(nèi)存、外設(shè)及有關(guān)數(shù)據(jù)結(jié)構(gòu)等。作業(yè)調(diào)度程序必須先調(diào)用存儲管理、外設(shè)管理，分配資源，讓它們能有競爭資格。為了提高資源利用率，一部分在內(nèi)存中處于就緒、等待狀態(tài)而短期內(nèi)不能執(zhí)行進程、作業(yè)換出內(nèi)存，所以外存中除了處于后備狀態(tài)的作業(yè)，還有處于就緒狀態(tài)的作業(yè)。這就需要一定的方法和策略來為這部分作業(yè)分配空間。學習完《操作系統(tǒng)原理》課程后，進行的這次全面的綜合訓(xùn)練，通過課程設(shè)計，使我更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強學生的動手能力，并與編程相結(jié)合應(yīng)用于實際中。參考資料[1]宗大華，宗濤，陳吉人著操作系統(tǒng)北京：人民郵電出版社，2009[2]李愛華，程磊著面相對象程序設(shè)計（C++語言）北京:清華大學出版社，2010[3]宋曉宇，windows操作系統(tǒng)核心編程實驗教程中國鐵道出版社[4]張麗芬劉利雄王金玉編著操作系統(tǒng)實驗教程清華大學出版社附錄：程序源代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>typedefstructnode{charname[10];intprio;intround;intcputime;intneedtime;intcount;charstate;structnode*next;}PCB;PCB*finish,*ready,*tail,*run;intN;firstin(){run=ready;run->state='R';ready=ready->next;}inttimesj(void){inti,xt;time_tt;srand((unsigned)time(&t));xt=rand()%10+1;returnxt;}voidprt1(chara){if(toupper(a)=='1')printf("namecputimeneedtimeprioritystate\n");elseif(toupper(a)=='2')printf("namecputimeneedtimeprioritystate\n");elseprintf("namecputimeneedtimeprioritystate\n");}voidprt2(chara,PCB*q){if(toupper(a)=='1')printf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);elseif(toupper(a)=='2')printf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);elseprintf("%-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);}voidprt(charalgo){PCB*p;prt1(algo);if(run!=NULL)prt2(algo,run);p=ready;while(p!=NULL){prt2(algo,p);p=p->next;}p=finish;while(p!=NULL){prt2(algo,p);p=p->next;}getch();return;}insert1(PCB*q){PCB*p1,*s,*r;intb;s=q;p1=ready;r=p1;b=1;while((p1!=NULL)&&b)if(p1->prio>=s->prio){r=p1;p1=p1->next;}elseb=0;if(r!=p1){r->next=s;s->next=p1;}else{s->next=p1;ready=s;}}insert2(PCB*p2){tail->next=p2;tail=p2;p2->next=NULL;}insert3(PCB*q){PCB*p1,*s,*r;intb;s=q;p1=ready;r=p1;b=1;while((p1!=NULL)&&b)if(p1->needtime<=s->needtime){r=p1;p1=p1->next;}elseb=0;if(r!=p1){r->next=s;s->next=p1;}else{s->next=p1;ready=s;}}voidcreate1(charalg){PCB*p;inti,time,sjt,priost;charna[10];ready=NULL;finish=NULL;run=NULL;printf("Enternameandtimeofprocess\n");printf("\n");for(i=1;i<=N;i++){p=malloc(sizeof(PCB));printf("Entername%d",i);printf(":");scanf("%s",na);printf("Randomtime%d",i);printf(":");sjt=timesj();printf("%d\n",sjt);printf("Randompriority%d",i);printf(":");printf("%d\n",20-sjt);strcpy(p->name,na);p->cputime=0;p->needtime=sjt;p->state='w';p->prio=20-sjt;if(ready!=NULL)insert1(p);else{p->next=ready;ready=p;}}printf("DisplayProcessOfPriority:\n");printf("\n");prt(alg);run=ready;ready=ready->next;run->state='R';}voidcreate2(charalg){PCB*p;inti,time,sjt;charna[10];ready=NULL;finish=NULL;run=NULL;printf("Enternameandtimeofroundprocess\n");printf("\n");for(i=1;i<=N;i++){p=malloc(sizeof(PCB));printf("Entername%d",i);printf(":");scanf("%s",na);printf("Randomtime%d",i);printf(":");sjt=timesj();printf("%d\n",sjt);printf("Randompriority%d",i);printf(":");printf("%d\n",20-sjt);strcpy(p->name,na);p->cputime=0;p->needtime=sjt;p->round=1;p->state='w';p->count=0;p->prio=20-sjt;if(ready!=NULL)insert2(p);else{p->next=ready;ready=p;tail=p;}}printf("DisplayProcessOfRoundrobin\n");printf("\n");prt(alg);run=ready;ready=ready->next;run->state='R';}voidcreate3(charalg){PCB*p;inti,time,sjt;charna[10];ready=NULL;finish=NULL;run=NULL;printf("Enternameandtimeofprocess\n");printf("\n");for(i=1;i<=N;i++){p=malloc(sizeof(PCB));printf("Entername%d",i);printf(":");scanf("%s",na);printf("Randomtime%d",i);printf(":");sjt=timesj();printf("%d\n",sjt);printf("Randompriority%d",i);printf(":");printf("%d\n",20-sjt);strcpy(p->name,na);p->cputime=0;p->needtime=sjt;p->state='w';p->prio=20-sjt;if(ready!=NULL)insert1(p);else{p->next=ready;ready=p;}}printf("DisplayProcessOfPriority:\n");printf("\n");prt(alg);run=ready;ready=ready->next;run->state='R';}priority(charalg){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->prio=run->prio-1;if(run->needtime==0){run->next=finish;finish=run;run->state='C';run=NULL;if(ready!=NULL)firstin();}elseif((ready!=NULL)&&(run->prio<ready->prio)){run->state='W';insert1(run);firstin();}prt(alg);}}roundrun(charalg){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->count=run->count+1;run->prio=run->prio-1;if(run->needtime==0){run->next=finish;finish=run;run->state='C';run=NULL;if(ready!=NULL)firstin();}elseif(run->count==run->round){run->count=0;if(ready!=NULL){run->state='W';insert2(run);firstin();}}prt(alg);}}shorttask(charalg){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->prio=run->prio-1;if(run->needtime==0){run->next=finish;finish=run;run->state='C';run=NULL;if(ready!=NULL)firstin();}elseif((ready!=NULL)&&(run->needtime>ready->needtime)){run->state='W';insert1(run);firstin();}prt(alg);}return;}menu(){charalgo;printf("\n\nCOMPUTEROSWORK\n\n");printf("\n\nBywanghao(Class2)\n\n\n");printf("chooseoneoffollowing:\n");printf("\n1.PRIORITY.\n\n");printf("2.ROUNDROBIN.\n\n");printf("3.SHORTTASK.\n\n");printf("4.EXIT.\n\n\n");printf("\npleaseenteryourchoice:");scanf("%c",&algo);if(algo=='1'){printf("Enterprocessnumber\n");scanf("%d",&N);create1(algo);priority(algo);}elseif(algo=='2'){printf("Enterprocessnumber\n");scanf("%d",&N);create2(algo);roundrun(algo);}elseif(algo=='3'){printf("Enterprocessnumber\n");scanf("%d",&N);create3(algo);shorttask(algo);return;}elseif(algo=='4')exit(0);}main(){while(1){menu();}}畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進行的研究工作及取得的成果。盡我所知，除文中特別加以標注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得及其它教育機構(gòu)的學位或?qū)W歷而使用過的材料。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。作者簽名：日期：指導(dǎo)教師簽名：日期：使用授權(quán)說明本人完全了解大學關(guān)于收集、保存、使用畢業(yè)設(shè)計（論文）的規(guī)定，即：按照學校要求提交畢業(yè)設(shè)計（論文）的印刷本和電子版本；學校有權(quán)保存畢業(yè)設(shè)計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學校可以公布論文的部分或全部內(nèi)容。作者簽名：日期：

學位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨立進行研究所取得的研究成果。除了文中特別加以標注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明的法律后果由本人承擔。作者簽名： 日期：年月日學位論文版權(quán)使用授權(quán)書本學位論文作者完全了解學校有關(guān)保留、使用學位論文的規(guī)定，同意學校保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)大學可以將本學位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學位論文。涉密論文按學校規(guī)定處理。作者簽名： 日期：年月日導(dǎo)師簽名：日期：年月日

注意事項1.設(shè)計（論文）的內(nèi)容包括：1）封面（按教務(wù)處制定的標準封面格式制作）2）原創(chuàng)性聲明3）中文摘要（300字左右）、關(guān)鍵詞4）外文摘要、關(guān)鍵詞5）目次頁（附件不統(tǒng)一編入）6）論文主體部分：引言（或緒論）、正文、結(jié)論7）參考文獻8）致謝9）附錄（對論文支持必要時）2.論文字數(shù)要求：理工類設(shè)計（論文）正文字數(shù)不少于1萬字（不包括圖紙、程序清單等），文科類論文正文字數(shù)不少于1.2萬字。3.附件包括：任務(wù)書、開題報告、外文譯文、譯文原文（復(fù)印件）。4.文字、圖表要求：1）文字通順，語言流暢，書寫字跡工整，打印字體及大小符合要求，無錯別字，不準請他人代寫2）工程設(shè)計類題目的圖紙，要求部分用尺規(guī)繪制，部分用計算機繪制，所有圖紙應(yīng)符合國家技術(shù)標準規(guī)范。圖表整潔，布局合理，文字注釋必須使用工程字書寫