（時(shí)間管理）時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法 C語(yǔ)言模擬實(shí)現(xiàn)收藏時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法 C 語(yǔ)言模擬實(shí)現(xiàn)收藏壹、目的和要求進(jìn)程調(diào)度是處理機(jī)管理的核心內(nèi)容。本實(shí)驗(yàn)要求用高級(jí)語(yǔ)言編寫模擬進(jìn)程調(diào)度程序，以便加深理解有關(guān)進(jìn)程控制快、進(jìn)程隊(duì)列等概念，且體會(huì)和了解優(yōu)先數(shù)算法和時(shí)間片輪轉(zhuǎn)算法的具體實(shí)施辦法。二、實(shí)驗(yàn)內(nèi)容1.設(shè)計(jì)進(jìn)程控制塊 PCB的結(jié)構(gòu)，通常應(yīng)包括如下信息：進(jìn)程名、進(jìn)程優(yōu)先數(shù)（或輪轉(zhuǎn)時(shí)間片數(shù)）、進(jìn)程已占用的 CPU時(shí)間、進(jìn)程到完成仍需要的時(shí)間、進(jìn)程的狀態(tài)、當(dāng)前隊(duì)列指針等。2.編寫倆種調(diào)度算法程序：優(yōu)先數(shù)調(diào)度算法程序循環(huán)輪轉(zhuǎn)調(diào)度算法程序3.按要求輸出結(jié)果。三、提示和說(shuō)明分別用倆種調(diào)度算法對(duì)伍個(gè)進(jìn)程進(jìn)行調(diào)度。每個(gè)進(jìn)程可有三種狀態(tài)；執(zhí)行狀態(tài)（RUN）、就緒狀態(tài)（READY,包括等待狀態(tài)）和完成狀態(tài)（），且假定初始狀態(tài)為就緒狀態(tài)。（壹）進(jìn)程控制塊結(jié)構(gòu)如下：NAME——進(jìn)程標(biāo)示符PRIO/ROUND——進(jìn)程優(yōu)先數(shù)/進(jìn)程每次輪轉(zhuǎn)的時(shí)間片數(shù)（設(shè)為常數(shù) 2）——進(jìn)程累計(jì)占用 CPU的時(shí)間片數(shù)——進(jìn)程到完成仍需要的時(shí)間片數(shù)STATE——進(jìn)程狀態(tài)NEXT——鏈指針注：1.為了便于處理，程序中進(jìn)程的的運(yùn)行時(shí)間以時(shí)間片為單位進(jìn)行計(jì)算；2.各進(jìn)程的優(yōu)先數(shù)或輪轉(zhuǎn)時(shí)間片數(shù)，以及進(jìn)程運(yùn)行時(shí)間片數(shù)的初值，均由用戶于程序運(yùn)行時(shí)給定。
（二）進(jìn)程的就緒態(tài)和等待態(tài)均為鏈表結(jié)構(gòu)，共有四個(gè)指針如下：RUN——當(dāng)前運(yùn)行進(jìn)程指針READY——就需隊(duì)列頭指針TAIL——就需隊(duì)列尾指針——完成隊(duì)列頭指針（三）程序說(shuō)明1.于優(yōu)先數(shù)算法中時(shí)間片輪轉(zhuǎn)算法流程圖，進(jìn)程優(yōu)先數(shù)的初值設(shè)為：50-每執(zhí)行壹次，優(yōu)先數(shù)減 1，CPU時(shí)間片數(shù)加 1，進(jìn)程仍需要的時(shí)間片數(shù)減 1。于輪轉(zhuǎn)法中，采用固定時(shí)間片單位（倆個(gè)時(shí)間片為壹個(gè)單位），進(jìn)程每輪轉(zhuǎn)壹次，CPU時(shí)間片數(shù)加 2，進(jìn)程仍需要的時(shí)間片數(shù)減 2，且退出 CPU，排到就緒隊(duì)列尾，等待下壹次調(diào)度。2.程序的模塊結(jié)構(gòu)提示如下：整個(gè)程序可由主程序和如下 7個(gè)過(guò)程組成：（1）——于優(yōu)先數(shù)算法中，將尚未完成的 PCB按優(yōu)先數(shù)順序插入到就緒隊(duì)列中；（2）——于輪轉(zhuǎn)法中，將執(zhí)行了壹個(gè)時(shí)間片單位（為 2），但尚未完成的進(jìn)程的 PCB，插到就緒隊(duì)列的隊(duì)尾；（3）——調(diào)度就緒隊(duì)列的第壹個(gè)進(jìn)程投入運(yùn)行；（4）PRINT——顯示每執(zhí)行壹次后所有進(jìn)程的狀態(tài)及有關(guān)信息。（5）——?jiǎng)?chuàng)建新進(jìn)程，且將它的 PCB插入就緒隊(duì)列；（6）——按優(yōu)先數(shù)算法調(diào)度進(jìn)程；（7）——按時(shí)間片輪轉(zhuǎn)法調(diào)度進(jìn)程。
主程序定義 PCB結(jié)構(gòu)和其他有關(guān)變量。（四）運(yùn)行和顯示程序開始運(yùn)行后，首先提示：請(qǐng)用戶選擇算法，輸入進(jìn)程名和相應(yīng)的 值。每次顯示結(jié)果均為如下 5個(gè)字段：注：1．于 state字段中，"R"代表執(zhí)行態(tài)，"W"代表就緒（等待）態(tài)，"F"代表完成態(tài)。2．應(yīng)先顯示"R"態(tài)的，再顯示"W"態(tài)的，再顯示"F"態(tài)的。3．于"W"態(tài)中，以優(yōu)先數(shù)高低或輪轉(zhuǎn)順序排隊(duì)；于"F"態(tài)中，以完成先后順序排隊(duì)。?1. /*2. 操作系統(tǒng)實(shí)驗(yàn)之時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法3. ++4. */###node{[20];/*進(jìn)程的名字*/;/*進(jìn)程的優(yōu)先級(jí)*/;/*分配 CPU的時(shí)間片*/;/*CPU執(zhí)行時(shí)間*/;/*進(jìn)程執(zhí)行所需要的時(shí)間*/;/*進(jìn)程的狀態(tài)，W——就緒態(tài)，R——執(zhí)行態(tài)，F(xiàn)——完成態(tài)*/;/*記錄執(zhí)行的次數(shù)*/*next;/*鏈表指針*/}PCB;PCB*ready=NULL,*run=NULL,*=NULL;/*定義三個(gè)隊(duì)列，就緒隊(duì)列，執(zhí)行隊(duì)列和完成隊(duì)列*/;();/*從就緒隊(duì)列取得第壹個(gè)節(jié)點(diǎn)*/();/*輸出隊(duì)列信息*/(PCB*in);/*創(chuàng)建優(yōu)先級(jí)隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級(jí)越高*/(PCB*in);/*時(shí)間片隊(duì)列*/(PCB*in);/*時(shí)間片隊(duì)列*/();/*優(yōu)先級(jí)輸入函數(shù)*/();/*時(shí)間片輸入函數(shù)*/();/*按照優(yōu)先級(jí)調(diào)度*/();/*時(shí)間片輪轉(zhuǎn)調(diào)度*/(void){;("請(qǐng)輸入要?jiǎng)?chuàng)建的進(jìn)程數(shù)目:\n");scanf("%d",&num);();("輸入進(jìn)程的調(diào)度方法：(P/R)\n");scanf("%c",&chose);(chose){case'P':case'p':();();break;case'R':case'r':();();break;:break;}();;}()/*取得第壹個(gè)就緒隊(duì)列節(jié)點(diǎn)*/{run=ready;if(ready!=NULL){run->state='R';ready=ready->next;run->next=NULL;}}()/*輸出隊(duì)列信息*/{PCB*p;p=ready;("進(jìn)程名\t優(yōu)先級(jí)\t輪數(shù)\tcpu時(shí)間\t需要時(shí)間\t進(jìn)程狀態(tài)\t計(jì)數(shù)器\n");while(p!=NULL){("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->,p->,p->state,p->count);p=p->next;}p=;while(p!=NULL){("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->,p->,p->state,p->count);p=p->next;}p=run;while(p!=NULL){("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->,p->,p->state,p->count);p=p->next;}}(PCB*in)/*創(chuàng)建優(yōu)先級(jí)隊(duì)列，規(guī)定優(yōu)先數(shù)越小時(shí)間片輪轉(zhuǎn)算法流程圖，優(yōu)先級(jí)越低*/{PCB*fst,*nxt;fst=nxt=ready;if(ready==NULL)/*如果隊(duì)列為空，則為第壹個(gè)元素*/{in->next=ready;ready=in;}else/*查到合適的位置進(jìn)行插入*/{if(in->prio>=fst->prio)/*比第壹個(gè)仍要大，則插入到隊(duì)頭*/{in->next=ready;ready=in;}else{while(fst->next!=NULL)/*移動(dòng)指針查找第壹個(gè)別它小的元素的位置進(jìn)行插入*/{nxt=fst;fst=fst->next;}if(fst->next==NULL)/*已經(jīng)搜索到隊(duì)尾，則其優(yōu)先級(jí)數(shù)最小，將其插入到隊(duì)尾即可*/{in->next=fst->next;fst->next=in;}else/*插入到隊(duì)列中*/{nxt=in;in->next=fst;}}}}(PCB*in)/*將進(jìn)程插入到就緒隊(duì)列尾部*/{PCB*fst;fst=ready;if(ready==NULL){in->next=ready;ready=in;}else{while(fst->next!=NULL){fst=fst->next;}in->next=fst->next;fst->next=in;}}(PCB*in)/*將進(jìn)程插入到完成隊(duì)列尾部*/{PCB*fst;fst=;if(==NULL){in->next=;=in;}else{while(fst->next!=NULL){fst=fst->next;}in->next=fst->next;fst->next=in;}}()/*優(yōu)先級(jí)調(diào)度輸入函數(shù)*/{PCB*tmp;inti;("輸入進(jìn)程名字和進(jìn)程所需時(shí)間：\n");for(i=0;iname);();/*吸收回車符號(hào)*/scanf("%d",&(tmp->));tmp->=0;tmp->state='W';tmp->prio=50-tmp->;/*設(shè)置其優(yōu)先級(jí)，需要的時(shí)間越多，優(yōu)先級(jí)越低*/tmp->round=0;tmp->count=0;(tmp);/*按照優(yōu)先級(jí)從高到低，插入到就緒隊(duì)列*/}}()/*時(shí)間片輸入函數(shù)*/{PCB*tmp;inti;("輸入進(jìn)程名字和進(jìn)程時(shí)間片所需時(shí)間：\n");for(i=0;iname);();scanf("%d",&(tmp->));tmp->=0;tmp->state='W';tmp->prio=0;tmp->round=2;/*假設(shè)每個(gè)進(jìn)程所分配的時(shí)間片是 2*/tmp->count=0;(tmp);}}()/*按照優(yōu)先級(jí)調(diào)度，每次執(zhí)行壹個(gè)時(shí)間片*/{=1;();while(run!=NULL)/*當(dāng)就緒隊(duì)列不為空時(shí)，則調(diào)度進(jìn)程如執(zhí)行隊(duì)列執(zhí)行*/{();/*輸出每次調(diào)度過(guò)程中各個(gè)節(jié)點(diǎn)的狀態(tài)*/while(flag){run->prio-=3;/*優(yōu)先級(jí)減去三*/run->++;/*CPU時(shí)間片加壹*/run->--;/*進(jìn)程執(zhí)行完成的剩余時(shí)間減壹*/if(run->==0)/*如果進(jìn)程執(zhí)行完畢，將進(jìn)程狀態(tài)置為 F，將其插入到完成隊(duì)列*/{run->state='F';run->count++;/*進(jìn)程執(zhí)行的次數(shù)加壹*/(run);flag=0;}else/*將進(jìn)程狀態(tài)置為 W，入就緒隊(duì)列*/{run->state='W';run->count++;/*進(jìn)程執(zhí)行的次數(shù)加壹*/(run);flag=0;}}flag=1;();/*繼續(xù)取就緒隊(duì)列隊(duì)頭進(jìn)程進(jìn)入執(zhí)行隊(duì)列*/}}()/*時(shí)間片輪轉(zhuǎn)調(diào)度算法*/{=1;();while(run!=NULL){();while(flag){run->count++;run->++;run->--;if(run->==0)/*進(jìn)程執(zhí)行完畢*/{run->state='F';(run);flag=0;}(run->count==run->round)/*時(shí)間片用完*/{run->state='W';run->count=0;/*計(jì)數(shù)器清零，為下次做準(zhǔn)備*/(run);flag=0;}}flag=1;();}}