11級操作系統(tǒng)-進(jìn)程模擬調(diào)度實驗報告

《操作系統(tǒng)》實驗報告單班級10計算機(jī)科學(xué)與技術(shù)(1)班學(xué)號姓名實驗時間星期五實驗地點H527實驗題目進(jìn)程調(diào)度模擬程序設(shè)計說明：僅作參考，請勿雷同一、實驗?zāi)康脑诓捎枚嗟莱绦蛟O(shè)計的系統(tǒng)中，往往有若干個進(jìn)程同時處于就緒狀態(tài)。當(dāng)就緒進(jìn)程個數(shù)大于處理器數(shù)時，就必須依照某種策略來決定哪些進(jìn)程優(yōu)先占用處理器。本實驗?zāi)M在單處理器情況下的處理器調(diào)度，加深了解處理器調(diào)度的工作二、實驗要求設(shè)計一個按優(yōu)先數(shù)調(diào)度算法或時間片輪轉(zhuǎn)法實現(xiàn)處理器調(diào)度。1．給出進(jìn)程調(diào)度的算法描述（基于動態(tài)優(yōu)先級和時間片輪轉(zhuǎn)調(diào)度算法的描述）。2．用C語言設(shè)計一個對n個并發(fā)進(jìn)程進(jìn)行調(diào)度的程序，每個進(jìn)程由一個進(jìn)程控制塊（PCB）結(jié)構(gòu)表示，該進(jìn)程控制塊應(yīng)包括下述信息：進(jìn)程標(biāo)識ID、進(jìn)程優(yōu)先數(shù)PRIORITY（并規(guī)定優(yōu)先數(shù)與優(yōu)先權(quán)成正比）、時間片數(shù)CHIP、進(jìn)程已經(jīng)占用CPU的時間CPUTIME，進(jìn)程還需要運行的時間ALLTIME（當(dāng)進(jìn)程運行完畢時，其值為0）、進(jìn)程的狀態(tài)STATE等（為簡化起見。設(shè)每個進(jìn)程處于運行R（run）、就緒W（ready）和完成F（finish）三種狀態(tài)之一，并假設(shè)起始狀態(tài)都是就緒狀態(tài)W。），以及進(jìn)程隊列指針NEXT（用來將PCB排成隊列）等，可按照調(diào)度算法的不同而增刪。3．調(diào)度程序應(yīng)當(dāng)包含2種不同的調(diào)度算法，運行時可以任選一種，以利于各種方法的分析和比較。4．程序應(yīng)能顯示或打印各種進(jìn)程狀態(tài)和參數(shù)變化情況，便于觀察。即要顯示每個時間片內(nèi)各進(jìn)程的情況，并且指出運行進(jìn)程及就緒和阻塞隊列中的內(nèi)容三、實驗內(nèi)容及主要步驟1.按優(yōu)先數(shù)調(diào)度算法(1)假定系統(tǒng)有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：進(jìn)程名指向下一個進(jìn)程的指針要求運行時間優(yōu)先數(shù)狀態(tài)獲得cpu時間已消耗cpu時間計數(shù)器其中，進(jìn)程名——作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為P1，P2，P3，P4，P5。指針——按優(yōu)先數(shù)的大小把五個進(jìn)程連成隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程中的指針為“0”。要求運行時間——假設(shè)進(jìn)程需要運行的單位時間數(shù)。優(yōu)先數(shù)——賦予進(jìn)程的優(yōu)先數(shù)，調(diào)度時總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。狀態(tài)——可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個進(jìn)程的初始狀態(tài)都為“就緒”，用“W”表示，當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“F”表示。獲得cpu時間 ——模擬cpu分配給進(jìn)程的時間片已消耗cpu時間——進(jìn)程運行已消耗的時間計數(shù)器——計算進(jìn)程已運行的時間(2)在每次運行你所設(shè)計的處理器調(diào)度程序之前，為每個進(jìn)程任意確定它的“優(yōu)先數(shù)”和“要求運行時間”。(3)為了調(diào)度方便，把五個進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊列。用一單元指出隊首進(jìn)程，用指針指出隊列的連接情況。(4)處理器調(diào)度總是選隊首進(jìn)程運行。采用動態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運行一次優(yōu)先數(shù)就減“3”優(yōu)先數(shù)-3要求運行時間-1來模擬進(jìn)程的一次運行。(5)進(jìn)程運行一次后，若要求運行時間0，則再將它加入隊列（按優(yōu)先數(shù)大小插入，且置隊首標(biāo)志）；若要求運行時間=0，則把它的狀態(tài)修改成“結(jié)束”（F），且退出隊列。(6)若“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。(7)在所設(shè)計的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運行一次后進(jìn)程隊列的變化。(8)為五個進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。2.時間片輪轉(zhuǎn)法(1)假定系統(tǒng)有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格式為：進(jìn)程名指向下一個進(jìn)程的指針要求運行時間優(yōu)先數(shù)狀態(tài)獲得cpu時間已消耗cpu時間計數(shù)器其中，進(jìn)程名——作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為S1，S2，S3。指針——按優(yōu)先數(shù)的大小把五個進(jìn)程連成隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程中的指針為“0”。要求運行時間——假設(shè)進(jìn)程需要運行的單位時間數(shù)。優(yōu)先數(shù)——賦予進(jìn)程的優(yōu)先數(shù)，調(diào)度時總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。狀態(tài)——可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個進(jìn)程的初始狀態(tài)都為“就緒”，用“W”表示，當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“F”表示。獲得cpu時間 ——模擬cpu分配給進(jìn)程的時間片已消耗cpu時間——進(jìn)程運行已消耗的時間計數(shù)器——計算進(jìn)程已運行的時間(2)每次運行所設(shè)計的處理器調(diào)度程序前，為每個進(jìn)程任意確定它的“要求運行時間”。(3)把五個進(jìn)程按順序排成循環(huán)隊列，用指針指出隊列連接情況。另用一標(biāo)志單元記錄輪到運行的進(jìn)程。(4)處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運行。由于本實驗是模擬處理器調(diào)度的功能，所以，對被選中的進(jìn)程并不實際的啟動運行，而是執(zhí)行：已運行時間+1來模擬進(jìn)程的一次運行，表示進(jìn)程已經(jīng)運行過一個單位的時間。(5)進(jìn)程運行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個輪到運行的進(jìn)程。同時，應(yīng)判斷該進(jìn)程的要求運行時間與已運行時間，若該進(jìn)程的要求運行時間已運行時間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時再運行。若該進(jìn)程的要求運行時間=已運行時間，則表示它已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修改成“結(jié)束”（F）且退出隊列。此時，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個進(jìn)程的指針位置。(6)若“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面的（4）和（5）的步驟，直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。(7)在所設(shè)計的程序中應(yīng)有顯示或打印語句，能顯示或打印每次選中進(jìn)程的進(jìn)程名以及運行一次后進(jìn)程隊列的變化。(8)為五個進(jìn)程任意確定一組“要求運行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中的進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。3．?dāng)?shù)據(jù)結(jié)構(gòu)程序中進(jìn)程可用PCB表示，其類型描述如下：typedefstructnode{charname[10];/*nameoftheprocess*/intprio;/*priorityoftheprocess*/intround;/*timegiven*/intcputime;/*timeused*/intneedtime;/*timedneeded*/intcount;/*counter*/charstate;/*stateoftheprocess'R':running,'W'：waiting,'F':finish*/structnode*next;/*pointertonextprocess*/}PCB;structPCB*ready=NULL,//ready隊列隊首指針*tail=NULL,//ready隊列隊尾指針*finish=NULL,//finish隊列隊首指針*run=NULL;//run隊列隊首指針?biāo)?、程序運行部分結(jié)果截圖Ubuntu6.10vi編譯器編譯采用優(yōu)先級優(yōu)先算法調(diào)度進(jìn)程結(jié)果采用時間片輪轉(zhuǎn)算法調(diào)度結(jié)果五、實驗程序清單#include<stdio.h>#include<stdlib.h>#include<string.h>/*processstruct*/typedefstructnode{charname[10];/*nameoftheprocess*/intprio;/*priorityoftheprocess*/intround;/*timegiven*/intcputime;/*timeused*/intneedtime;/*timedneeded*/intcount;/*counter*/charstate;/*stateoftheprocess'R':running,'W'：waiting,'F':finish*/structnode*next;/*pointertonextprocess*/}PCB;PCB*finish,*ready,*tail,*run;/*pointertothreeprocessSqueue，tailpointtotheendofreadySqueue*/intN;/*thenumberofprocess*//*function:putthefirstprocessinreadySqueueintorunningvoidfirstin(void)*/voidfirstin(void){if(ready!=NULL){run=ready;ready=ready->next;run->state='R';run->next=NULL;}else{run=NULL;}}/*function:outputthetypeoftheprocessCallingvoidprt1(chara)a=='p':priority，=='r':timeround*/voidprt1(chara){if((a=='P')||(a=='p')){printf("namecputimeneedtimeprioritystate\n");}else{printf("namecputimeneedtimecountroundstate\n");}}/*function:outputinformationofoneprocessvoidprt2(chara,PCB*p)chara:a=='p':priority=='r':timeroundPCB*p:ppointtotheprocessSqueuetobeoutputed*/voidprt2(chara,PCB*p){if(a=='P'||a=='p'){printf("%s,%d,%d,%d,%c\n",p->name,p->cputime,p->needtime,p->prio,p->state);}else{printf("%s,%d,%d,%d,%d,%c\n",p->name,p->cputime,p->needtime,p->count,p->round,p->state);}}/*function:outputinformationofalltheprocessSqueuevoidprt(charalgo)charalgo:algo=='p':priority，=='r':timeround*/voidprt(charalgo){PCB*p;prt1(algo);//outputthetypeif(run!=NULL)//iftherunningpointernotequalNULL,outputtheprocess'sinformation{prt2(algo,run);}p=ready;while(p!=NULL){prt2(algo,p);//outputtheinformationofthereadySqueuep=p->next;}p=finish;while(p!=NULL){prt2(algo,p);//outputtheinformationofthefinishSqueuep=p->next;}}/*function:Prioritymethodinsertaprocessintoasuqeuevoidinsert1(PCB*q)*/voidinsert1(PCB*q){PCB*p,*s,*r;intb;s=q;p=ready;r=p;b=1;if(s->prio>=ready->prio){s->next=ready;ready=s;}else{while((p!=NULL)&&b){if(p->prio>=s->prio){r=p;p=p->next;}else{b=0;}}s->next=p;r->next=s;}}/*function:timeroundinsertoprocessintoasqueuevoidinsert2(PCB*q)*/voidinsert2(PCB*q){tail->next=q;tail=q;q->next=NULL;}/*function:prioritymethodinitializationvoidpcreate_task(charalgo)*/voidpcreate_task(charalgo,intn){PCB*p;inti,time;charna[10];ready=NULL;finish=NULL;run=NULL;for(i=0;i<n;i++){p=(PCB*)malloc(sizeof(PCB));printf("Enterthenameofprocess%d:",i);scanf("%s",&na);getchar();printf("Enterthetimeofprocess%d:",i);scanf("%d",&time);getchar();strcpy(p->name,na);p->cputime=0;p->needtime=time;p->state='W';p->prio=time;if(ready==NULL){ready=p;ready->next=NULL;}else{insert1(p);}}printf("Outputthewaitingprocessesinformation\n");prt(algo);firstin();}/*function:timeroundinitializationvoidrcreate_task(charalgo)*/voidrcreate_task(charalgo,intn){PCB*p;inti,time;charna[10];ready=NULL;finish=NULL;run=NULL;for(i=0;i<n;i++){p=(PCB*)malloc(sizeof(PCB));printf("Enterthenameofprocessi:",i);scanf("%s",&na);getchar();printf("Enterthetimeofprocessi:",i);scanf("%d",&time);getchar();strcpy(p->name,na);p->cputime=0;p->needtime=time;p->count=0;p->state='W';p->round=2;if(ready!=NULL){insert2(p);}else{p->next=ready;ready=p;tail=p;}}printf("Outputthewaitingprocessesinformation\n");prt(algo);run=ready;ready=ready->next;run->state='R';}/*function:prioritymethodcallingvoidpriority(charalgo)charalgo:typesign:'P':priority'R':timeround*/voidpriority(charalgo){while(run!=NULL){run->cputime+=1;run->needtime-=1;run->prio-=3;if(run->needtime==0){run->next=finish;finish=run;run->state='F';run=NULL;firstin();}else{if((ready!=NULL)&&(run->prio<ready->prio)){run->state='W';insert1(run);run=NULL;firstin();}}//prt(algo);}prt(algo);}/*function:timeroundcallingvoidroundrun(charalgo)*/voidroundrun(charalgo){while(run!=NULL){run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->count=run->count+1;if(run->needtime==0){run-