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

1、計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)報(bào)告學(xué) 號(hào)： 姓 名： 提交日期： 成 績(jī)：計(jì)算機(jī)與通信工程學(xué)院實(shí)驗(yàn) 1 使用動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法的模擬1 實(shí)驗(yàn)?zāi)康?通過(guò)動(dòng)態(tài)優(yōu)先權(quán)算法的模擬加深對(duì)進(jìn)程概念和進(jìn)程調(diào)度過(guò)程的理解。2 實(shí)驗(yàn)容 （ 1）實(shí)現(xiàn)對(duì) N 個(gè)進(jìn)程采用動(dòng)態(tài)優(yōu)先權(quán)優(yōu)先算法的進(jìn)程調(diào)度。（ 2）每個(gè)用來(lái)標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊 PCB 用結(jié)構(gòu)來(lái)描述，包括以下字段：進(jìn)程標(biāo)識(shí)數(shù) ID 。進(jìn)程優(yōu)先數(shù) PRIORITY ，并規(guī)定優(yōu)先數(shù)越大的進(jìn)程，其優(yōu)先權(quán)越高。進(jìn)程已占用的 CPU 時(shí)間 CPUTIME 。進(jìn)程還需占用的 CPU 時(shí)間 ALLTIME 。當(dāng)進(jìn)程運(yùn)行完畢時(shí)， ALLTIME 變?yōu)?0。進(jìn)程的阻塞時(shí)間 STAR

2、TBLOCK ，表示當(dāng)進(jìn)程再運(yùn)行 STARTBLOCK 個(gè)時(shí)間片后，將進(jìn)入阻塞狀態(tài)。 進(jìn)程被阻塞的時(shí)間 BLOCKTIME ，表示已阻塞的進(jìn)程再等待 BLOCKTIME 個(gè)時(shí)間片后，將轉(zhuǎn)換成就緒狀 態(tài)。進(jìn)程狀態(tài) STATE 。4）假設(shè)在調(diào)度前，系統(tǒng)中有5 個(gè)進(jìn)程，它們的初始狀態(tài)如下：ID01234PRIORITY93830290CPUTIME00000ALLTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATEreadyreadyreadyreadyready3）優(yōu)先數(shù)改變的原則： 進(jìn)程在就緒隊(duì)列中停留一個(gè)時(shí)間片，優(yōu)先數(shù)加1。進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先數(shù)

3、減 3。隊(duì)列指針 NEXT ，用來(lái)將 PCB 排成隊(duì)列。5）為了清楚的觀察各進(jìn)程的調(diào)度過(guò)程，程序應(yīng)將每個(gè)時(shí)間片的情況顯示出來(lái)，參照的具體格式如下： RUNNING PROG ： iREADY-QUEUE ：->id1->id2BLOCK-QUEUE ：->id3->id4ID01234PRIORITYP0P1P2P3P4CUPTIMEC0C1C2C3C4ALLTIMEA0A1A2A3A4STARTBLOCKT0T1T2T3T4BLOCKTIMEB0B1B2B3B4STATES0S1S2S3S43 實(shí)驗(yàn)結(jié)果（1）流程圖2）程序源代碼#include <stdio.h

4、>#include <stdlib.h>#include <string.h> typedef struct node int id;int priority;int cputime;int alltime;int startblock; int blocktime; char state10; struct node *next; PCB;/ 進(jìn)程標(biāo)識(shí)數(shù)/ 進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越大優(yōu)先級(jí)越高/ 進(jìn)程已占用的 CPU時(shí)間/ 進(jìn)程還需占用的 CPU時(shí)間/ 進(jìn)程的阻塞時(shí)間/ 進(jìn)程被阻塞的時(shí)間/ 進(jìn)程狀態(tài)/ 隊(duì)列指針PCB *CreatQueue(int num)int

5、i; /i 為循環(huán)計(jì)數(shù)器PCB *head, *temp1, *temp2, *temp3;/ 創(chuàng)建一個(gè)就緒隊(duì)列/head 為就緒隊(duì)列的頭指針， temp1 為創(chuàng)建進(jìn)程結(jié)點(diǎn)的指針， temp2 、 temp3 分別為比較結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和比較結(jié)點(diǎn) / 根據(jù)進(jìn)程的個(gè)數(shù)創(chuàng)建結(jié)點(diǎn)并按從大到小的順序進(jìn)行排序for(i=0; i<num; i+)temp1=(PCB *)malloc(sizeof(PCB);printf(" 輸入第 %d 個(gè)進(jìn)程的 (id state)n",i); scanf("%d%d%d%d%d%d%s",&temp1->i

6、d,&temp1->priority,&temp1->cputime,&temp1->alltime,&temp1->startb lock,&temp1->blocktime,temp1->state);if(i=0)/ 如果創(chuàng)建的是第一個(gè)結(jié)點(diǎn)head=temp1; head->next=NULL; continue;if(head->priority < temp1->priority)/ 如果創(chuàng)建結(jié)點(diǎn)中所保存的數(shù)比頭結(jié)點(diǎn)所保存的數(shù)要大， 接把該結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之前則直temp1->n

7、ext=head; head=temp1; continue; temp2=head;temp3=temp2->next;while(temp3!=NULL && temp3->priority>=temp1->priority) temp2=temp3; temp3=temp2->next;temp2->next=temp1; temp1->next=temp3;/temp2 為比較結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)/temp3 為比較的結(jié)點(diǎn)/ 實(shí)現(xiàn)查找的功能/ 在就緒隊(duì)列中插入一個(gè)結(jié)點(diǎn)/temp1 和 temp2 分別為比較結(jié)點(diǎn)的前驅(qū)和比較結(jié)點(diǎn)/

8、如果就緒隊(duì)列為空else if(head->priority < run->priority)/ 如果插入結(jié)點(diǎn)中所保存的數(shù)比頭結(jié)點(diǎn)所保存的數(shù)要大， 結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之前則直接把該run->next=head;head=run;elsetemp1=head;temp2=temp1->next;/temp1 為比較結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)/temp2 為比較的結(jié)點(diǎn)while(temp2!=NULL && temp2->priority>=run->priority) / 實(shí)現(xiàn)查找的功能temp1=temp2;temp2=temp1->

9、next;temp1->next=run;run->next=temp2;return head;main()int num;int alltime=0;PCB *head;PCB *run=NULL;PCB *block=NULL;PCB *temp;printf(" 請(qǐng)輸入進(jìn)程的個(gè)數(shù) scanf("%d",&num); head=CreatQueue(num); getchar();temp=head; while(temp!=NULL):");/num 為進(jìn)程的個(gè)數(shù)/ 用來(lái)保存所有進(jìn)程需要占用的 /head 為就緒隊(duì)列的頭指針

10、/run 為執(zhí)行進(jìn)程結(jié)點(diǎn)的指針 /block 為阻塞進(jìn)程的結(jié)點(diǎn)CPU時(shí)間 return head;PCB *InsertQueue(PCB *head,PCB *run)PCB *temp1,*temp2;if(head=NULL)head=run; head->next=NULL;alltime+=temp->alltime;temp=temp->next; while(alltime > 0)if(head!=NULL)/ 把就緒隊(duì)列中的第一個(gè)進(jìn)程取出來(lái)執(zhí)行/ 就緒隊(duì)列的頭指針指向下一個(gè)結(jié)點(diǎn)/ 狀態(tài)改為執(zhí)行 run=head; head=head->next;

11、strcpy(run->state,"run"); run->next=NULL;/* 顯示狀態(tài) */ 顯示執(zhí)行進(jìn)程/ 顯示就緒進(jìn)程/ 顯示阻塞進(jìn)程printf("RUNNING PROG:%dn",run->id);printf("READY_QUEUE:");temp=head;while(temp!=NULL)printf("->%d",temp->id); temp=temp->next;printf("n");printf("BLOCK_Q

12、UEUE:");if(block!=NULL)printf("%d",block->id);printf("n");printf("=n"); printf("ID PRIORITY CPUTIME ALLTIMES TARTBLOCK BLOCKTIME STATEn");printf("%d %d %d %d %d %d %sn",run->id,run->priority,run->cputime,run->alltime,run->start

13、block,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); temp=temp->next;if(block!=NULL)printf("%d %d %d %d %d %d%s",b

14、lock->id,block->priority,block->cputime,block->alltime,block->startblock,block->blocktime,block->state);printf("n"); printf("=n");/* 顯示狀態(tài) */ elseprintf("/* 改變優(yōu)先數(shù) */ run->priority-=3; temp=head; while(temp!=NULL)temp->priority+=1;temp=temp->next;

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

16、ate,"b"); alltime-;printf("n");continue;strcpy(run->state,"r"); head=InsertQueue(head,run); run=NULL;/* 改變執(zhí)行進(jìn)程的有關(guān)參數(shù) */ alltime-;/* 顯示狀態(tài) */ printf("RUNNING PROG:n"); printf("READY_QUEUE:n"); printf("BLOCK_QUEUE:"); if(block!=NULL)printf(&

17、quot;%d",block->id); printf("n");/ 執(zhí)行轉(zhuǎn)阻塞/ 狀態(tài)轉(zhuǎn)阻塞/ 狀態(tài)轉(zhuǎn)就緒/ 執(zhí)行轉(zhuǎn)就緒/ 顯示執(zhí)行進(jìn)程/ 顯示就緒進(jìn)程 / 顯示阻塞進(jìn)程n");printf("ID PRIORITY CPUTIME ALLTIMES TARTBLOCK BLOCKTIME STATEn"); if(block!=NULL)printf("%d %d %d %d %d %d%s",block->id,block->priority,block->cputime,block-

18、>alltime,block->startblock,block->blocktime,block->state); printf("n");n");printf("/* 顯示狀態(tài) */* 改變阻塞進(jìn)程的有關(guān)參數(shù) */if(block!=NULL)block->blocktime-=1;/ 如果有阻塞進(jìn)程/ 被阻塞的時(shí)間減 1if(block->blocktime=0) / 如果被阻塞的時(shí)間到了strcpy(block->state,"r");/ 狀態(tài)轉(zhuǎn)就緒head=InsertQueue(head,block);/ 阻塞轉(zhuǎn)就緒block=NULL;/* 改變阻塞進(jìn)程的有關(guān)參數(shù) */ getchar();4 思考（1）實(shí)際進(jìn)程調(diào)度中，除了按調(diào)度算法選擇