高(动态)优先权优先的进程调度算法模拟

河南工业大学实验报告课程一计算机操作系统实验名称高(动态)优先权优先的进程调度算法模拟系别 信息科学与工程学院计算机科学系 专业班级 实验日期2012-10-26姓名 学号 教师审批签字实验目的通过动态优先权算法的模拟加深对进程概念和进程调度过程的理解。实验环境装有操作系统WindowsXP和开发工具VC++6.0,内存在256M以上的微机；或者：装有Linux(Fedora7)操作系统和gcc编译器，内存在256M以上的微机。实验内容用C语言来实现对N个进程采用动态优先权优先算法的进程调度。每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：进程标识数ID；进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高；进程已占用的CPU时间CPUTIME；进程还需占用的CPU时间NEEDTIME。当进程运行完毕时，NEEDTIME变为0；进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，进程将进入阻塞状态；进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME个时间片后，进程将转换成就绪状态；进程状态STATE；(READY,RUNNING,BLOCK,FINISH)队列指针NEXT，用来将PCB排成队列。优先数改变的原则：进程在就绪队列中呆一个时间片，优先数增加1；进程每运行一个时间片，优先数减3。假设在调度前，系统中有5个进程，它们的初始状态如下：ID01234PRIORITY93830290CPUTIME00000NEEDTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATE READY READY READY READY READY为了清楚地观察进程的调度过程，程序应将每个时间片内的进程的情况显示出来参照的具体格式如下：RUNNINGPROCESS:$id0READYQUEUE:$id1->$id2BLOCKQUEUE:$id3->$id4FINISHQUEUE:$id0->$id1->$id2->$id3->$id4IDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME0XXXXXXXXXXXX1XXXXXXXXXXXX2XXXXXXXXXXXX3XXXXXXXXXXXX4XXXXXXXXXXXX实验要求将源程序(priority.c)和程序运行结果写入实验报告。将该算法执行过程与高响应比优先调度算法的执行过程进行比较实验过程及结果(1).代码：#include<stdio.h>#include<string.h>#include<stdlib.h>char*State[]={"READY","RUNNING","BLOCK","FINISH"};typedefstructPCB{intid;intpriority;intcputime;intneedtime;intstartblock;intblocktime;char*state;structPCB*next;structPCB*nt;}PCB;PCB*Ready,*Block,*Finish,*Runing,*ALL;PCB*findHighest();voidinsert(PCB*node,PCB*insert,inti);voidModifyPriority();voidModifyBlock();voidBlockToReady();voidPrint();voidFreeAllPCB();voidinit(){PCB*pro=(PCB*)malloc(sizeof(PCB));Ready->next=ALL=pro;pro->id=0;pro->priority=9;pro->cputime=0;pro->needtime=3;pro->startblock=2;pro->blocktime=3;pro=pro->next=pro->nt=(PCB*)malloc(sizeof(PCB));pro->id=1;pro->priority=38;pro->cputime=0;pro->needtime=3;pro->startblock=-1;pro->blocktime=0;pro=pro->next=pro->nt=(PCB*)malloc(sizeof(PCB));pro->id=2;pro->priority=30;pro->cputime=0;pro->needtime=6;pro->startblock=-1;pro->blocktime=0;pro=pro->next=pro->nt=(PCB*)malloc(sizeof(PCB));pro->id=3;pro->priority=29;pro->cputime=0;pro->needtime=3;pro->startblock=-1;pro->blocktime=0;pro=pro->next=pro->nt=(PCB*)malloc(sizeof(PCB));pro->id=4;pro->priority=0;pro->cputime=0;pro->needtime=4;pro->startblock=-1;pro->blocktime=0;pro->next=pro->nt=NULL;}PCB*findHighest(){PCB*pro,*highest;PCB*propre=Ready;PCB*highpre=Ready;highest=pro=Ready->next;while(pro!=NULL){if(pro->priority>highest->priority){highest=pro;highpre=propre;}propre=propre->next;pro=pro->next;}highpre->next=highest->next;highest->next=NULL;returnhighest;}voidinsert(PCB*node,PCB*insert,inti){node->state=State[i];node->next=insert->next;insert->next=node;}voidModifyPriority(){PCB*p;p=Ready->next;while(p!=NULL){p->priority++;p=p->next;voidModifyBlock(){PCB*p;p=Block->next;while(p!=NULL){p->blocktime--;p=p->next;}}voidBlockToReady(){PCB*p,*pre,*node;pre=Block;p=pre->next;while(p!=NULL){if(p->blocktime==0){p->startblock--;node=p;p=pre->next=node->next;node->next=NULL;insert(node,Ready,0);}else{pre=pre->next;p=p->next;}}}voidPrint(){PCB*pro,*All;if(Runing!=NULL)printf("RUNNINGPROCESS:$id%d\n",Runing->id);printf("READYQUEUE:");pro=Ready->next;while(pro!=NULL){printf("->$id%d",pro->id);pro=pro->next;}puts("");printf("BLOCKQUEUE:");pro=Block->next;while(pro!=NULL){printf("->$id%d",pro->id);pro=pro->next;}puts("");printf("FINISHQUEUE:");pro=Finish->next;while(pro!=NULL){printf("->$id%d",pro->id);pro=pro->next;}puts("");printf("===============================================================\n");printf("IDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME\n");All=ALL;while(All!=NULL){printf("%d%10d%10d%10d%8s%10d%11d\n",All->id,All->priority,All->cputime,All->needtime,All->state,All->startblock,All->blocktime);All=All->nt;}}voidFreeAllPCB(){free(Finish);}intmain(void){PCB*pro;Ready=(PCB*)malloc(sizeof(PCB));Block=(PCB*)malloc(sizeof(PCB));Finish=(PCB*)malloc(sizeof(PCB));Ready->next=NULL;Block->next=NULL;Finish->next=NULL;init();while(Ready->next!=NULL){pro=findHighest();Runing=pro;pro->state=State[1];pro->cputime++;pro->needtime--;if(pro->startblock>0){pro->startblock--;}pro->priority-=3;Print();ModifyBlock();ModifyPriority();BlockToReady();if(pro->needtime==0){insert(pro,Finish,3);Runing=NULL;}else{if(pro->startblock==0){insert(pro,Block,2);}else{insert(pro,Ready,0);}Runing=NULL;

Print();FreeAllPCB();return0;}程序运行结果RUNNINGPROCESS:$idl^EADVQUEUE：->$id0->$id2->$id3->$id4BLOCKQUEUE：FINISHQUEUE：IDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME0 903READV231 3512READV-10* 3006READV-10□ 2903READV-104 004READV-10誠C:\Windows\system32\cmd£»e4卜jRunningprocess:$idi^EADVQUEUE：->$id0->$id2->$id3->$id4BLOCKQUEUE：FINISHQUEUE：IDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME01003READV231 3221READV-10* 3106READV-10□ 3003READV-104 104READV-10誠C:\WindoW5\system32\cmd.exe

RUNNINGPROCESS:$id2READVQUEUE：BLOCKQUEUE：FINISHQUEUE：->$idB->$id3->$id4:->$idlIDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME01203READV231 2930READV-10* 3015READV-103 3203READV-104 3a4READV-10nrawC:\WindDws\system32\cmd,exeRUNNINGPROCESS:$id2READVQUEUE：BLOCKQUEUE：FINISHQUEUE->$id0->$id4:->$id3->$idlIDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME01803READV231 2930READV-10* 2442READV-10□2630READV-104 904READV-10■誠C:\Wind0ws\system32\cmd.exe

RUNNINGPROCESS:$id0HEADVQUEUE：->$id4BLOCKQUEUE：FINISHQUEUE：:->$id2->$id3->$idlIDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME01812READV131 2930READV-10*1860READV-103 2630READV-104 12a4READV-10rawC:\Windows\system32\cmd.exeRUNNINGPROCESS:$id4READVQUEUE：BLOCKQUEUE：FINISHQUEUE->$idB:->$id2->$id3->$idlIDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME01521READV0312930READV-1021860READV-1032630READV-1041113READV-10■ 誠C:\Wind0W5\system32\cmd.exeRUNNINGPROCESS:$id4READVQUEUE：BLOCKQUEUE：RUNNINGPROCESS:$id4READVQUEUE：BLOCKQUEUE：->$id0FINISHQUEUE：:->$id2->$id3->$idlIDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME0 1521READV011 2930READV-10*1860READV-103 2630READV-104 531READV-10rawC:\Windows\systeni32\cmd.exerawC:\Windows\system32\cmd.exe[RUNNINGPROCESS:$id0READVQUEUE：->$id4BLOCKQUEUE：rawC:\Windows\systrawC:\Windows\system32\cmd.exeIDPRIORITYCPUTIMENEEDTIMESTATESTARTBLOCKBLOCKTIME01230READV-1012930READV-1021860READV-1032630READV-104531READV-10rrrrawC:\Windows\system32\cmd.exeRUNNINGPROCESS:$id4READVQUEUE：BLOCKQUEUE：FINISHQUEUE：->$id0->$id2->$id3->$idlIDPRI