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

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

2、已阻塞的进程再等待blocktime个时间片后，将转换为就绪态；进程状态state ；队列指针next，用来将PCB排成队列。（3）优先数改变的原则：进程在就绪队列中呆一个时间片，优先数增加1.进程每运行一个时间片，优先数减3。（4）假设在调度前，系统中有5个进程,它们得初始状态如下ID01234PRIORITY93830290CPUTIME00000ALLTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATEREADY READYREADYREADYREADY（5）为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来, 参照的具体格

3、式如下：RUNNING PROG iREADY_QUEUE ->id1->id2BLOCK_QUEUE ->id3->id4ID01234PRIORITYP0P1P2P3P4CPUTIMEC0C1C3C4C5ALLTIMEA0A1A2A3A4STARTBLOCKT0T1T2T3T4BLOCKTIMEB0B1B2B3B4STATES0S1S2S3S4开始3过程（流程图）4代码#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <stri ng.h> typedef struct node i

4、nt id;int priority;int cputime;int alltime;int startblock; int blocktime; char state10; struct node *n ext; PCB;/进程标识数/进程优先数，优先数越大优先级越高/进程已占用的CPU时间/进程还需占用的 CPU时间/进程的阻塞时间/进程被阻塞的时间/进程状态/队列指针PCB *CreatQueue(int num)/ 创建一个就绪队列int i;/i为循环计数器PCB *head, *temp1, *temp2, *temp3;/head 为就绪队列的头指针，temp1 为创建进程结点的

5、指针，temp2、temp3分别为比较结点的前驱结点和比较结点for(i=0; i<num; i+)/根据进程的个数创建结点并按从大到小的顺序进行排序temp1=(PCB *)malloc(sizeof(PCB); printf("输入第 %d个进程的(id state)n",i);scan f("%d%d%d%d%d%d%s"，& temp1->id, &temp1->priority, &temp1->cputime, &temp1->all time, &temp1->st

6、artblock，& temp1->blocktime,temp1->state);if(i=0)/如果创建的是第一个结点 head=temp1;head-> next=NULL;con ti nue;if(head->priority < temp1->priority)/如果创建结点中所保存的数比头结点所保存的数要大，则直接把该结点插入到头结点之前temp1- >n ext=head; head=temp1;con ti nue;temp2=head;temp2为比较结点的直接前驱结点temp3为比较的结点temp3=temp2->n

7、 ext;while(temp3!=NULL && temp3->priority>=temp1->priority)/ 实现查找的功能temp2=temp3; temp3=temp2->n ext;temp2->n ext=temp1;temp1- >n ext=temp3;retur n head;PCB *ln sertQueue(PCB *head,PCB *run)/ 在就绪队列中插入一个结点PCB *temp1,*temp2;temp1和temp2分别为比较结点的前驱和比较结点if(head=NULL)/如果就绪队列为空head=

8、run;head-> next=NULL;else if(head->priority < run-'priority)/如果插入结点中所保存的数比头结点所保存的数要大，则直接把该结点插入到头结点之前run->n ext=head;head=run;elsetemp仁head;/tempi为比较结点的直接前驱结点temp2=temp1->next;temp2 为比较的结点while(temp2!=NULL && temp2->priority>=run-'priority)/ 实现查找的功能temp1=temp2;tem

9、p2=temp1- >n ext;tempi- >n ext=r un;run->n ext=temp2;retur n head;main ()int num;int alltime=0;n um为进程的个数/用来保存所有进程需要占用的CPU时间PCB *head;/head为就绪队列的头指针PCB *run=NULL;/run为执行进程结点的指针PCB *block=NULL;/block为阻塞进程的结点PCB *temp;printf(”请输入进程的个数：”)；scan f("%d",&n um);head=CreatQueue( nu m)

10、;getchar();temp=head;while(temp!=NULL)alltime+=temp->alltime;temp=temp->n ext;while(alltime > 0)if(head!=NULL)run=head;/把就绪队列中的第一个进程取出来执行head=head-> next; /就绪队列的头指针指向下一个结点strcpy(run->state,"run");/ 状态改为执行run-> next=NULL;/*显示状态*/printf("RUNNING PROG:%dn",run->

11、id);/ 显示执行进程printf("READY_QUEUE:");/ 显示就绪进程temp=head;while(temp!=NULL)prin tf("->%d",temp->id);temp=temp->n ext;prin tf("n");printf("BLOCK_QUEUE:");/ 显示阻塞进程if(block!=NULL)prin tf("%d",block->id);prin tf("n");prin tf(”= ：=n"

12、);prin tf("ID PRIORITY CPUTIME ALLTIMESTARTBLOCKBLOCKTIME STATE'n");printf("%d %d %d %d %d %d%sn",ru n->id,ru n->priority,ru n->cputime,ru n->alltime,ru n->startblock,ru n->blocktime,ru n->state);temp=head;while(temp!=NULL)printf("%d%d %d %d %d %d%sn

13、 ",temp->id,temp->priority,temp->cputime,temp->alltime,temp->startblock,temp->block time,temp->state);temp=temp->n ext;if(block!=NULL)printf("%d%d %d %d %d %d%s",block->id,block->priority,block->cputime,block->alltime,block->startblock,block->

14、blockti me,block->state);prin tf("n");prin tf(”= =n");/*显示状态*/ /*改变优先数*/执行进程的优先数减3/就绪进程的优先数加1*/执行进程的已占用 CPU时间加1II还需要的CPU时间减1run->priority-=3; temp=head; while(temp!=NULL) temp->priority+=1; temp=temp->n ext;/*改变优先数*/*改变执行进程的有关参数run->cputime+=1;run->alltime-=1;if(run-

15、>alltime!=O)if(run->startblock > 0)run->startblock-=1;如果该进程会被阻塞/执行完一个时间片后，开始阻塞的时间减if(run->startblock=0)/如果阻塞的时间到了/执行转阻塞/状态转阻塞block=r un; strcpy(block->state,"b"); alltime-;prin tf("n");con ti nue;strcpy(ru n->state,"r");/ 状态转就绪head=l nsertQueue(head

16、,ru n);/ 执行转就绪run=NULL;/*改变执行进程的有关参数 */ alltime-;else/*显示状态*/prin tf("RUNNING PROG:n");prin tf("READY_QUEUE:n");prin tf("BLOCK_QUEUE:"); if(block!=NULL)prin tf("%d",block->id);/显示执行进程/显示就绪进程/显示阻塞进程prin tf("n");prin tf(”= =n");prin tf("ID

17、 PRIORITY CPUTIME ALLTIMESTARTBLOCKBLOCKTIME STATE'n"); if(block!=NULL)printf("%d%d %d %d %d %d%s",block->id,block->priority,block->cputime,block->alltime,block->startblock,block->blockti me,block->state);prin tf("n");prin tf("=、n");/*显示状态*

18、/*改变阻塞进程的有关参数if(block!=NULL)block->blocktime-=1;*/如果有阻塞进程/被阻塞的时间减1if(block->blocktime=0) /如果被阻塞的时间到了strcpy(block->state,"r");/状态转就绪/阻塞转就绪head=In sertQueue(head,block); block=NULL;/*改变阻塞进程的有关参数*/getchar();5运行结果I D:CodeC_Co detestte5t_ 3.exe血/山山*IIDPRIORITY1 382 30B29bg4&CPUTIME

19、 ALLTIME ST A RIBLOCKBLOCKTIME 00STfiTE run ready readyreadyDUNNING PROG：1ReADYJJU BUE j >2->3->0->4BLOCK.QUEUE：IDPRIORITY35313a101CPUTIME ALLTIME STARTBLOCK12-10 6-1BLOCKTIME 00STATErun ready Pfradp ready ready输入5个进程，分别是04进程，运行结果可以看到第一次运行进程1,优先数为38。第二次运行的进程是进程1，优先数为35， cpu时间占用为1，进程所需时间为

20、 2，同时下一个进程（进程 1）的优先数+1。 D: CodeC_Codete?t_3.ej<eBUNN1NG PROG:2READV.QUEUE>1->3->0->4 BLOCK.QUEUE：IDPRIORITVCPUTinEALLIIMESTfiRTBLOCKBLOCKTIMESTATE23206-19run13221-1&3*33103-10readj?M11U323ready42m m m m 壬壬三=三m m 64-10re adj?RUNNING l_ N. M PROG:1READV_QUEUE：->3->2->0->

21、4BLOCK.QUEUE：IDPRIORITYCPUT1HEALLIIHESTARTBLOCKBLOCKTIHESTfiTE13321-1flrun33203-10readih22915-10r0120323reader4304-10re ad ifRUNNING PROG:3 REfiDV_QUEUE:->2->0->4 E：LOCK_QUEUE：IDPRIORITYCPUTINEftLLTIMESTARTBLOCKHL0CKT1HESTATE.i33Q3-1&run2301S-10r0136323readj4404-10re adv第三次运行进程2,优先数32,

22、cpu占用时间将+1,所需时间将-1。 同时下一个进程（进程 1）优先数+1,。第四次运行进程1,优先数33, cpu占用时间2+1，所需时间将-1。 同时下一个进程（进程 3）优先数+1,第四次运行进程1完毕，所需时间为 0。进程1运行完毕。第五次运行进程3,优先数33, cpu占用时间0将+ 1,所需时间3将-1。 同时下一个进程（进程 2）优先数+1。RUNNING PROG:2READV.QUEUE>3->0->4BILOCK .QUEUE：IDPRIORITYCPUTJHEALLIIMESTfiRTBLOCKBLOCKTIMESTATE23115-19runB301

23、2-1&3*0140323readj?45U4-10ready|n-RUNNING PA0G；3HEfiMf.QUEUE:->2->0->4biLOCK.QUEUE：IDPRIORITYCPUTinEALLTIMESTfiRTBLOCKBLOCKTIMESTATEB3112-1Qrun22924-1flr0150323readih4604-10readyHUNN1NC PflOG:2READV_4UEUE:->3-BLOCICQUEUE：IDPRIORITYCPUTJHEALLIIMESIfiRTBLOCKBLOCKTIMESTATE*2924-10run329

24、21-10r0 16Q323readjyr4704-10ready D:'-CodeC_C o dete5t'-. ex e=|回1将+1,所需时间1将+1,所需时间2将+1,所需时间5 将-1。2 将-1。4 将-1 。第六次运行进程2,优先数31将-3, cpu占用时间 同时下一个进程（进程 3）优先数+1。第七次运行进程3,优先数31将-3，cpu占用时间 同时下一个进程（进程 2）优先数+1。第八次运行进程2,优先数29将-3，cpu占用时间 同时下一个进程（进程 3）优先数+1。 D: CodeC 匚dew量exeRUNNING PROG:3READV.QUEUE:-

25、>2->0->4 IILOCK.QUEUE：IDPfllORITVCPUTIHEALLTIMEARTBLOCKHLOCKT1MESTATEQ2921-10run2 2633-10r0176323re adj?4804-10re ad ifRUNNING PROG：2 REfiDV_QUEUE：->0->4 HLOCK_QUEUE：IDPfllORlTVCFUT1NEALLTIMESTARTBLOCK HLOCKT1HESTATEQ2733-10runU180323readj4904-10readerRUNNING PROG：2READV_QUEUE：->0-

26、 >4BLOCK.QUEUE：IDPRIORITYCPUTinEALLIIMESTARTBLOCKHLOCKTIHESTATEE2442-10runB190323readjyr41004-10ready第九次运行进程3,优先数29将-3, cpu占用时间2将+1,所需时间1将-1。 同时下一个进程（进程 2）优先数+1。第九次运行完毕，进程3的所需时间为0，进程3运行完毕。第十次运行进程2,优先数27将-3，cpu占用时间3将+1,所需时间3将-1。 同时下一个进程（进程 0）优先数+1。第十一次运行进程 2，优先数24将-3，cpu占用时间4将+1,所需时间2将-1。 同时下一个进程（

27、进程 0）优先数+1。 D :C o deC_C o de 弓匕:亡或_3.exe1 回RUNNING PROG：2"1PEAD¥_QUEU1i：->0-MBLOCK_QUEUE：IDPRIORITYCPUTIMEALLTIMESTfiRTBLOCKBLOCKTIMESTATE2 2151-10run0 200m23ready411&4-1&l*eadvRUNNING PROG:0RERDVqUEUE：->4IDPRIORITYCPUTIMEALLTIMESTARTBLOCKBLOCKTIMESTATE0 210323run41204-10re

28、ad ifRUNNING PROG：0READV.QUEUE：->4EJLOCK.QUEUE：IDPRIORITYCPUTIMEALLTIMESTARTBLOCKULOCKT1HESTATE0 181213run41304-10readyNUNN1NC PAOG e 4REftDV.QUEUE：BLOCK_QUEUE：0IDPRIORITYCPUTIHEALLIIMESIARTBLOCKBLOCKT1MESTATE41404-10run0IS2103=bT第十二次运行进程 2，优先数21将-3, 同时下一个进程（进程 0）优先数+1。 第十二次运行完毕，进程 第十三次运行进程 0, 同时

29、下一个进程（进程 第十四次运行进程 0, 同时下一个进程（进程 第十五次运行进程 4, 同时下一个进程（进程cpu占用时间5将+1,所需时间1将-12所需时间为 优先数21将-3, 4）优先数+1。优先数18将-3, 4）优先数+1。优先数14将-3, 0）优先数+1。0，进程2运行完毕。0 将+1,cpucpucpu占用时间占用时间占用时间所需时间3将-11 将+1,0 将+1,所需时间所需时间2将-14将-1RUNNING PROG:4READV.QUEUE：B；LOCK_QUEUE：0IDPRIORITYCPUTinEALLIIMESTfiRTBLOCKBLOCKTIMESTfiTE13

30、-19runB152102bRUNNING PROG:4 HiEADY .QUEUE：BLOCK_QUEUE：0IDPRIORITYCPUTIHEALLTIMESTARTBLOCKBLOCKTIMESTATE4822-1&run0152101bRUNNING PflOGiE)REfiDV.QUEUE：->4HILOCK.QUEUE：IDPRIORITYCPUTJHEALLTIMESTfiRTBLOCKBLOCKTIMESTATEB152100runP 531LQrFANNING PROG:4 READVQUEUE： BLOCK-QUEUE:IDPRIORITYCPUTIMEALLTINEUARIBLOCKBLOCKT1MESTATE4631-1Qrun- D:' Co deC_C o de 'test、. ex e.=| 回第十六次运行进程 4，优先数11将-3, cpu占用时间1将+1,所需时间3将-1。 同时下一个进程（进程 0）优先数+1。第十七次运行进程 4，优先数8将-3，cpu占用时间2将+ 1,所需时间2将-1。 同时下一个进程（进程 0）优先数+1。第十八次运行进程