使用动态优先权的进程调度算法的模拟实验

1、使用动态优先权的进程调度算法的模拟实验1.实验目的通过动态优先权算法的模拟加深对进程概念和进程调度过程的理解。2.实验内容（1）用C语言实现对N个进程采用动态优先权优先算法的进程调度；（2）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：l 进程标识数；l 进程优先数priority，并规定优先数越大的进程，其优先权越高；l 进程已占用的CPU时间cputime；l 进程还需占用的CPU时间alltime，当进程运行完毕时，alltime变为0；l 进程的阻塞时间startblock，表示当进程再运行startblock个时间片后，进程将进入阻塞状态；l 进程被阻塞的时间blic

2、ktime，表示已阻塞的进程再等待blocktime个时间片后，将转换为就绪态；l 进程状态state；l 队列指针next，用来将PCB排成队列。（3）优先数改变的原则：l 进程在就绪队列中呆一个时间片，优先数增加1.l 进程每运行一个时间片，优先数减3。（4）假设在调度前，系统中有5个进程，它们得 初始状态如下：ID 01234PRIORITY9 38 30290CPUTIME 00000ALLTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATEREADYREADYREADYREADYREADY（5）为了清楚地观察诸进程的调度过程，程序应将每个时间

3、片内的进程的情况显示出来，参照的具体格式如下： RUNNING PROG：i READY_QUEUE：->id1->id2 BLOCK_QUEUE：->id3->id4=ID 01234PRIORITY P0 P1 P2P3 P4CPUTIME C0C1C3C4C5ALLTIMEA0A1A2A3A4STARTBLOCKT0T1T2T3T4BLOCKTIMEB0B1B2B3B4STATES0S1S2S3S4开始创建就绪队列Alltime>0就绪执行显示状态改变优先数P.alltime-1P.cuptime+1P.alltime=0P.startblock>0P

4、.startblock-1P.startblock=0执行阻塞执行就绪BLK=NULLP.blocktime-1P.blocktime =0阻塞就绪结束是否否是是否是否是否否是3.过程（流程图）4.代码#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct nodeint id; /进程标识数int priority; /进程优先数，优先数越大优先级越高int cputime; /进程已占用的CPU时间int alltime; /进程还需占用的CPU时间int startb

5、lock; /进程的阻塞时间int blocktime; /进程被阻塞的时间char state10; /进程状态struct node *next; /队列指针PCB;PCB *CreatQueue(int num) /创建一个就绪队列int i; /i为循环计数器PCB *head, *temp1, *temp2, *temp3; /head为就绪队列的头指针，temp1为创建进程结点的指针，temp2、temp3分别为比较结点的前驱结点和比较结点for(i=0; i<num; i+) /根据进程的个数创建结点并按从大到小的顺序进行排序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) /如果创建的是第一个结点head=temp1;head->next=NULL;continue;if

7、(head->priority < temp1->priority) /如果创建结点中所保存的数比头结点所保存的数要大，则直接把该结点插入到头结点之前temp1->next=head;head=temp1;continue;temp2=head; /temp2为比较结点的直接前驱结点temp3=temp2->next; /temp3为比较的结点while(temp3!=NULL && temp3->priority>=temp1->priority) /实现查找的功能temp2=temp3;temp3=temp2->next

8、;temp2->next=temp1;temp1->next=temp3;return head;PCB *InsertQueue(PCB *head,PCB *run) /在就绪队列中插入一个结点PCB *temp1,*temp2; /temp1和temp2分别为比较结点的前驱和比较结点if(head=NULL) /如果就绪队列为空head=run;head->next=NULL;else if(head->priority < run->priority) /如果插入结点中所保存的数比头结点所保存的数要大，则直接把该结点插入到头结点之前run->n

9、ext=head;head=run;elsetemp1=head; /temp1为比较结点的直接前驱结点 temp2=temp1->next; /temp2为比较的结点 while(temp2!=NULL && temp2->priority>=run->priority) /实现查找的功能 temp1=temp2; temp2=temp1->next; temp1->next=run; run->next=temp2;return head;main()int num; /num为进程的个数int alltime=0; /用来保存所有

10、进程需要占用的CPU时间PCB *head; /head为就绪队列的头指针PCB *run=NULL; /run为执行进程结点的指针PCB *block=NULL; /block为阻塞进程的结点PCB *temp;printf("请输入进程的个数:");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; /把就绪队列中的第一个进程取出来执行 head=head->next; /就绪队列的头指针指向下一个结点 strcpy(run->state,"run"); /状态改为执行 run->next=NULL; /*显示状态*/ printf("RUNNING PROG:%dn",run->id); /显示执行进程 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"); /*显示状态*/ /*改变优先数*/ run->priority-=3; /执行进程的优先数减3 temp=hea

15、d; while(temp!=NULL) /就绪进程的优先数加1 temp->priority+=1; temp=temp->next; /*改变优先数*/ /*改变执行进程的有关参数*/ run->cputime+=1; /执行进程的已占用CPU时间加1 run->alltime-=1; /还需要的CPU时间减1 if(run->alltime!=0) if(run->startblock > 0) /如果该进程会被阻塞 run->startblock-=1; /执行完一个时间片后，开始阻塞的时间减1 if(run->startblock

16、=0) /如果阻塞的时间到了 block=run; /执行转阻塞 strcpy(block->state,"b"); /状态转阻塞alltime-;printf("n"); continue; strcpy(run->state,"r"); /状态转就绪 head=InsertQueue(head,run); /执行转就绪 run=NULL; /*改变执行进程的有关参数*/alltime-;else/*显示状态*/ printf("RUNNING PROG:n"); /显示执行进程 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"); /*显示状态*/*改变阻塞进程的有关参数*/if(block!=NULL) /如果有阻塞进程block->blocktime-=1; /被阻塞的时间减1if(block->blocktime=0) /如果被阻塞的时间到了strcpy(block->s

19、tate,"r"); /状态转就绪head=InsertQueue(head,block); /阻塞转就绪block=NULL;/*改变阻塞进程的有关参数*/getchar();5.运行结果输入5个进程，分别是04进程，运行结果可以看到第一次运行进程1，优先数为38。第二次运行的进程是进程1，优先数为35，cpu时间占用为1，进程所需时间为2，同时下一个进程（进程1）的优先数+1。第三次运行进程2，优先数32，cpu占用时间将+1，所需时间将-1。同时下一个进程（进程1）优先数+1,。第四次运行进程1，优先数33，cpu占用时间2+1，所需时间将-1。同时下一个进程（进程3

20、）优先数+1,第四次运行进程1完毕，所需时间为0。进程1运行完毕。第五次运行进程3，优先数33，cpu占用时间0将+1，所需时间3将-1。同时下一个进程（进程2）优先数+1。第六次运行进程2，优先数31将-3，cpu占用时间1将+1，所需时间5将-1。同时下一个进程（进程3）优先数+1。第七次运行进程3，优先数31将-3，cpu占用时间1将+1，所需时间2将-1。同时下一个进程（进程2）优先数+1。第八次运行进程2，优先数29将-3，cpu占用时间2将+1，所需时间4将-1。同时下一个进程（进程3）优先数+1。第九次运行进程3，优先数29将-3，cpu占用时间2将+1，所需时间1将-1。同时下

21、一个进程（进程2）优先数+1。第九次运行完毕，进程3的所需时间为0，进程3运行完毕。第十次运行进程2，优先数27将-3，cpu占用时间3将+1，所需时间3将-1。同时下一个进程（进程0）优先数+1。第十一次运行进程2，优先数24将-3，cpu占用时间4将+1，所需时间2将-1。同时下一个进程（进程0）优先数+1。第十二次运行进程2，优先数21将-3，cpu占用时间5将+1，所需时间1将-1。同时下一个进程（进程0）优先数+1。第十二次运行完毕，进程2所需时间为0，进程2运行完毕。第十三次运行进程0，优先数21将-3，cpu占用时间0将+1，所需时间3将-1。同时下一个进程（进程4）优先数+1。

22、第十四次运行进程0，优先数18将-3，cpu占用时间1将+1，所需时间2将-1。同时下一个进程（进程4）优先数+1。第十五次运行进程4，优先数14将-3，cpu占用时间0将+1，所需时间4将-1。同时下一个进程（进程0）优先数+1。第十六次运行进程4，优先数11将-3，cpu占用时间1将+1，所需时间3将-1。同时下一个进程（进程0）优先数+1。第十七次运行进程4，优先数8将-3，cpu占用时间2将+1，所需时间2将-1。同时下一个进程（进程0）优先数+1。第十八次运行进程0，优先数15将-3，cpu占用时间2将+1，所需时间1将-1。同时下一个进程（进程4）优先数+1。第十八次运行完毕，进程0所需时间为0，进程0运行完毕。第十九次运行进