使用動態(tài)優(yōu)先權(quán)的進程調(diào)度算法的模擬實驗

1、使用動態(tài)優(yōu)先權(quán)的進程調(diào)度算法的模擬實驗1.實驗?zāi)康耐ㄟ^動態(tài)優(yōu)先權(quán)算法的模擬加深對進程概念和進程調(diào)度過程的理解。2.實驗內(nèi)容（1）用C語言實現(xiàn)對N個進程采用動態(tài)優(yōu)先權(quán)優(yōu)先算法的進程調(diào)度；（2）每個用來標識進程的進程控制塊PCB用結(jié)構(gòu)來描述，包括以下字段：l 進程標識數(shù)；l 進程優(yōu)先數(shù)priority，并規(guī)定優(yōu)先數(shù)越大的進程，其優(yōu)先權(quán)越高；l 進程已占用的CPU時間cputime；l 進程還需占用的CPU時間alltime，當進程運行完畢時，alltime變?yōu)?；l 進程的阻塞時間startblock，表示當進程再運行startblock個時間片后，進程將進入阻塞狀態(tài)；l 進程被阻塞的時間blic

2、ktime，表示已阻塞的進程再等待blocktime個時間片后，將轉(zhuǎn)換為就緒態(tài)；l 進程狀態(tài)state；l 隊列指針next，用來將PCB排成隊列。（3）優(yōu)先數(shù)改變的原則：l 進程在就緒隊列中呆一個時間片，優(yōu)先數(shù)增加1.l 進程每運行一個時間片，優(yōu)先數(shù)減3。（4）假設(shè)在調(diào)度前，系統(tǒng)中有5個進程，它們得 初始狀態(tài)如下：ID 01234PRIORITY9 38 30290CPUTIME 00000ALLTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATEREADYREADYREADYREADYREADY（5）為了清楚地觀察諸進程的調(diào)度過程，程序應(yīng)將每個時間

3、片內(nèi)的進程的情況顯示出來，參照的具體格式如下： RUNNING PROG：i READY_QUEUE：->id1->id2 BLOCK_QUEUE：->id3->id4=ID 01234PRIORITY P0 P1 P2P3 P4CPUTIME C0C1C3C4C5ALLTIMEA0A1A2A3A4STARTBLOCKT0T1T2T3T4BLOCKTIMEB0B1B2B3B4STATES0S1S2S3S4開始創(chuàng)建就緒隊列Alltime>0就緒執(zhí)行顯示狀態(tài)改變優(yōu)先數(shù)P.alltime-1P.cuptime+1P.alltime=0P.startblock>0P

4、.startblock-1P.startblock=0執(zhí)行阻塞執(zhí)行就緒BLK=NULLP.blocktime-1P.blocktime =0阻塞就緒結(jié)束是否否是是否是否是否否是3.過程（流程圖）4.代碼#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct nodeint id; /進程標識數(shù)int priority; /進程優(yōu)先數(shù)，優(yōu)先數(shù)越大優(yōu)先級越高int cputime; /進程已占用的CPU時間int alltime; /進程還需占用的CPU時間int startb

5、lock; /進程的阻塞時間int blocktime; /進程被阻塞的時間char state10; /進程狀態(tài)struct node *next; /隊列指針PCB;PCB *CreatQueue(int num) /創(chuàng)建一個就緒隊列int i; /i為循環(huán)計數(shù)器PCB *head, *temp1, *temp2, *temp3; /head為就緒隊列的頭指針，temp1為創(chuàng)建進程結(jié)點的指針，temp2、temp3分別為比較結(jié)點的前驅(qū)結(jié)點和比較結(jié)點for(i=0; i<num; i+) /根據(jù)進程的個數(shù)創(chuàng)建結(jié)點并按從大到小的順序進行排序temp1=(PCB *)malloc(size

6、of(PCB);printf("輸入第%d個進程的(idstate)n",i);scanf("%d%d%d%d%d%d%s",&temp1->id,&temp1->priority,&temp1->cputime,&temp1->alltime,&temp1->startblock,&temp1->blocktime,temp1->state);if(i=0) /如果創(chuàng)建的是第一個結(jié)點head=temp1;head->next=NULL;continue;if

7、(head->priority < temp1->priority) /如果創(chuàng)建結(jié)點中所保存的數(shù)比頭結(jié)點所保存的數(shù)要大，則直接把該結(jié)點插入到頭結(jié)點之前temp1->next=head;head=temp1;continue;temp2=head; /temp2為比較結(jié)點的直接前驅(qū)結(jié)點temp3=temp2->next; /temp3為比較的結(jié)點while(temp3!=NULL && temp3->priority>=temp1->priority) /實現(xiàn)查找的功能temp2=temp3;temp3=temp2->next

8、;temp2->next=temp1;temp1->next=temp3;return head;PCB *InsertQueue(PCB *head,PCB *run) /在就緒隊列中插入一個結(jié)點PCB *temp1,*temp2; /temp1和temp2分別為比較結(jié)點的前驅(qū)和比較結(jié)點if(head=NULL) /如果就緒隊列為空head=run;head->next=NULL;else if(head->priority < run->priority) /如果插入結(jié)點中所保存的數(shù)比頭結(jié)點所保存的數(shù)要大，則直接把該結(jié)點插入到頭結(jié)點之前run->n

9、ext=head;head=run;elsetemp1=head; /temp1為比較結(jié)點的直接前驅(qū)結(jié)點 temp2=temp1->next; /temp2為比較的結(jié)點 while(temp2!=NULL && temp2->priority>=run->priority) /實現(xiàn)查找的功能 temp1=temp2; temp2=temp1->next; temp1->next=run; run->next=temp2;return head;main()int num; /num為進程的個數(shù)int alltime=0; /用來保存所有

10、進程需要占用的CPU時間PCB *head; /head為就緒隊列的頭指針PCB *run=NULL; /run為執(zhí)行進程結(jié)點的指針PCB *block=NULL; /block為阻塞進程的結(jié)點PCB *temp;printf("請輸入進程的個數(shù):");scanf("%d",&num);head=CreatQueue(num);getchar();temp=head;while(temp!=NULL)alltime+=temp->alltime;temp=temp->next;while(alltime > 0)if(head!

11、=NULL) run=head; /把就緒隊列中的第一個進程取出來執(zhí)行 head=head->next; /就緒隊列的頭指針指向下一個結(jié)點 strcpy(run->state,"run"); /狀態(tài)改為執(zhí)行 run->next=NULL; /*顯示狀態(tài)*/ printf("RUNNING PROG:%dn",run->id); /顯示執(zhí)行進程 printf("READY_QUEUE:"); /顯示就緒進程 temp=head; while(temp!=NULL) printf("->%d&quo

12、t;,temp->id); temp=temp->next; printf("n"); printf("BLOCK_QUEUE:"); /顯示阻塞進程 if(block!=NULL) printf("%d",block->id); printf("n");printf("=n");printf("IDPRIORITYCPUTIMEALLTIMESTARTBLOCKBLOCKTIMESTATEn");printf("%d%d%d%d%d%d%sn&q

13、uot;,run->id,run->priority,run->cputime,run->alltime,run->startblock,run->blocktime,run->state);temp=head;while(temp!=NULL)printf("%d%d%d%d%d%d%sn",temp->id,temp->priority,temp->cputime,temp->alltime,temp->startblock,temp->blocktime,temp->state);te

14、mp=temp->next;if(block!=NULL) printf("%d%d%d%d%d%d%s",block->id,block->priority,block->cputime,block->alltime,block->startblock,block->blocktime,block->state); printf("n");printf("=n"); /*顯示狀態(tài)*/ /*改變優(yōu)先數(shù)*/ run->priority-=3; /執(zhí)行進程的優(yōu)先數(shù)減3 temp=hea

15、d; while(temp!=NULL) /就緒進程的優(yōu)先數(shù)加1 temp->priority+=1; temp=temp->next; /*改變優(yōu)先數(shù)*/ /*改變執(zhí)行進程的有關(guān)參數(shù)*/ run->cputime+=1; /執(zhí)行進程的已占用CPU時間加1 run->alltime-=1; /還需要的CPU時間減1 if(run->alltime!=0) if(run->startblock > 0) /如果該進程會被阻塞 run->startblock-=1; /執(zhí)行完一個時間片后，開始阻塞的時間減1 if(run->startblock

16、=0) /如果阻塞的時間到了 block=run; /執(zhí)行轉(zhuǎn)阻塞 strcpy(block->state,"b"); /狀態(tài)轉(zhuǎn)阻塞alltime-;printf("n"); continue; strcpy(run->state,"r"); /狀態(tài)轉(zhuǎn)就緒 head=InsertQueue(head,run); /執(zhí)行轉(zhuǎn)就緒 run=NULL; /*改變執(zhí)行進程的有關(guān)參數(shù)*/alltime-;else/*顯示狀態(tài)*/ printf("RUNNING PROG:n"); /顯示執(zhí)行進程 printf(&qu

17、ot;READY_QUEUE:n"); /顯示就緒進程 printf("BLOCK_QUEUE:"); /顯示阻塞進程 if(block!=NULL) printf("%d",block->id); printf("n");printf("=n");printf("IDPRIORITYCPUTIMEALLTIMESTARTBLOCKBLOCKTIMESTATEn");if(block!=NULL) printf("%d%d%d%d%d%d%s",block-&

18、gt;id,block->priority,block->cputime,block->alltime,block->startblock,block->blocktime,block->state); printf("n");printf("=n"); /*顯示狀態(tài)*/*改變阻塞進程的有關(guān)參數(shù)*/if(block!=NULL) /如果有阻塞進程block->blocktime-=1; /被阻塞的時間減1if(block->blocktime=0) /如果被阻塞的時間到了strcpy(block->s

19、tate,"r"); /狀態(tài)轉(zhuǎn)就緒head=InsertQueue(head,block); /阻塞轉(zhuǎn)就緒block=NULL;/*改變阻塞進程的有關(guān)參數(shù)*/getchar();5.運行結(jié)果輸入5個進程，分別是04進程，運行結(jié)果可以看到第一次運行進程1，優(yōu)先數(shù)為38。第二次運行的進程是進程1，優(yōu)先數(shù)為35，cpu時間占用為1，進程所需時間為2，同時下一個進程（進程1）的優(yōu)先數(shù)+1。第三次運行進程2，優(yōu)先數(shù)32，cpu占用時間將+1，所需時間將-1。同時下一個進程（進程1）優(yōu)先數(shù)+1,。第四次運行進程1，優(yōu)先數(shù)33，cpu占用時間2+1，所需時間將-1。同時下一個進程（進程3

20、）優(yōu)先數(shù)+1,第四次運行進程1完畢，所需時間為0。進程1運行完畢。第五次運行進程3，優(yōu)先數(shù)33，cpu占用時間0將+1，所需時間3將-1。同時下一個進程（進程2）優(yōu)先數(shù)+1。第六次運行進程2，優(yōu)先數(shù)31將-3，cpu占用時間1將+1，所需時間5將-1。同時下一個進程（進程3）優(yōu)先數(shù)+1。第七次運行進程3，優(yōu)先數(shù)31將-3，cpu占用時間1將+1，所需時間2將-1。同時下一個進程（進程2）優(yōu)先數(shù)+1。第八次運行進程2，優(yōu)先數(shù)29將-3，cpu占用時間2將+1，所需時間4將-1。同時下一個進程（進程3）優(yōu)先數(shù)+1。第九次運行進程3，優(yōu)先數(shù)29將-3，cpu占用時間2將+1，所需時間1將-1。同時下

21、一個進程（進程2）優(yōu)先數(shù)+1。第九次運行完畢，進程3的所需時間為0，進程3運行完畢。第十次運行進程2，優(yōu)先數(shù)27將-3，cpu占用時間3將+1，所需時間3將-1。同時下一個進程（進程0）優(yōu)先數(shù)+1。第十一次運行進程2，優(yōu)先數(shù)24將-3，cpu占用時間4將+1，所需時間2將-1。同時下一個進程（進程0）優(yōu)先數(shù)+1。第十二次運行進程2，優(yōu)先數(shù)21將-3，cpu占用時間5將+1，所需時間1將-1。同時下一個進程（進程0）優(yōu)先數(shù)+1。第十二次運行完畢，進程2所需時間為0，進程2運行完畢。第十三次運行進程0，優(yōu)先數(shù)21將-3，cpu占用時間0將+1，所需時間3將-1。同時下一個進程（進程4）優(yōu)先數(shù)+1。

22、第十四次運行進程0，優(yōu)先數(shù)18將-3，cpu占用時間1將+1，所需時間2將-1。同時下一個進程（進程4）優(yōu)先數(shù)+1。第十五次運行進程4，優(yōu)先數(shù)14將-3，cpu占用時間0將+1，所需時間4將-1。同時下一個進程（進程0）優(yōu)先數(shù)+1。第十六次運行進程4，優(yōu)先數(shù)11將-3，cpu占用時間1將+1，所需時間3將-1。同時下一個進程（進程0）優(yōu)先數(shù)+1。第十七次運行進程4，優(yōu)先數(shù)8將-3，cpu占用時間2將+1，所需時間2將-1。同時下一個進程（進程0）優(yōu)先數(shù)+1。第十八次運行進程0，優(yōu)先數(shù)15將-3，cpu占用時間2將+1，所需時間1將-1。同時下一個進程（進程4）優(yōu)先數(shù)+1。第十八次運行完畢，進程0所需時間為0，進程0運行完畢。第十九次運行進