[数据结构与算法]C语言实现动态优先权算法调度模拟

一﹑实验目的

通过动态优先权算法的模拟加深对进程概念和进程调度过程的理解。

二﹑实验内容与基本要求

编制模拟动态优先权算法的程序，并给出的例子验证所编写的程序的正确性。
1.用C语言实现对N个进程采用动态优先权算法的调度。
2.每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段：
? 进程标识数ID。
? 进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高。
? 进程已占用CPU时间CPUTIME。
? 进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0。
? 进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，进程将进入阻塞状态。
? 进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME个时间片后，将转换成就绪状态。
? 进程状态STATE。
? 队列指针NEXT，用来将PCB排成队列。
3.优先数改变的原则：
? 进程在就绪队列中呆一个时间片，优先数增加1。
? 进程每运行一个时间片，优先数减3。
4.为了清楚地观察每个进程的调度过程，程序应将每个时间片内的进程的情况显示出来，包括正在运行的进程，处于就绪队列中的进程和处于阻塞队列中的进程。

#include<stdio.h>
#include<stdlib.h>
typedef struct PCB{
    int ID;      //进程标识数
    int priority;//优先数
    int cpuTime;//已用时间
    int allTime;//总共还需时间
    int startBlock;//运行多少时间片后阻塞
    int blockTime;//在阻塞队列多长时间后进入就绪状态
    int state;//进程状态1表示运行，2表示就绪，3表示阻塞，0表示运行完
    struct PCB *next;
}PCB,*pcb;
pcb p1,p2,lastp;
pcb ReadyQueue,BlockQueue,RunPCB;
pcb accQueue,acclast;//完成队列
void GetPCB();
void Run();
void PushReady(pcb p1);
void ShowQueue(int cputime);

int main(){
    ReadyQueue=BlockQueue=RunPCB=NULL;//初始化
    accQueue=acclast=(pcb)malloc(sizeof(PCB));
    accQueue->next = NULL;
    GetPCB();
    Run();
    system("pause");
}

void GetPCB(){
    FILE *fp;
    if((fp=fopen("F://pcb.txt","r"))==NULL){
        printf("打开文件失败\n");
        exit(1);
    }
    p1 = (pcb)malloc(sizeof(PCB));
    while(fscanf(fp,"%d %d %d %d %d %d %d",&p1->ID,&p1->priority,
&p1->cpuTime,&p1->allTime,&p1->startBlock,&p1->blockTime,&p1->state)==7){
        p1->next = NULL;
        if(p1->state==2) PushReady(p1);
        p1 = (pcb)malloc(sizeof(PCB));
    }
}


void Run(){
    int CupTime=0;
    RunPCB=ReadyQueue;
    ReadyQueue=ReadyQueue->next;
    ShowQueue(0);
    for(;1;CupTime++){
        //更新值
        if(RunPCB){
            RunPCB->cpuTime++;
            RunPCB->allTime--;
            RunPCB->priority -= 3;//优先数减3
            if(RunPCB->startBlock>0)
                RunPCB->startBlock--;
        }

        p1 = ReadyQueue;
        while(p1){//优先数加1
            p1->priority++;
            p1 = p1->next;
        }
        
        if(RunPCB){//判断RunPCB的状态
            if(RunPCB->allTime==0) {
                acclast->next = RunPCB;
                acclast = RunPCB;
                acclast->state = 0;
                RunPCB = NULL;
            }
        }//判断RunPCB
        
        if(RunPCB==NULL){//更新RunPCB
            RunPCB = ReadyQueue;
            if(ReadyQueue)  ReadyQueue = ReadyQueue->next;
        }else if(ReadyQueue && RunPCB->priority < ReadyQueue->priority){//优先值小了
            PushReady(RunPCB);
            RunPCB = ReadyQueue;
            ReadyQueue = ReadyQueue->next;
        }
        
        if(RunPCB) RunPCB->state= 1;
        ShowQueue(CupTime+1);
        if(ReadyQueue==BlockQueue && BlockQueue==RunPCB && RunPCB==NULL) break;
    }
}

void PushReady(pcb p1){//以priority降序
    p1->state = 2;
    lastp = p2 = ReadyQueue;
    while(p2 && p2->priority>=p1->priority)
    {//查找第一个比p1小的pcb
        lastp = p2;
        p2 = lastp->next;
    }
    if(lastp==p2){//插到队头
        p1->next = ReadyQueue;
        ReadyQueue = p1;
    }else{//插到队中
        p1->next = p2;
        lastp->next = p1;
    }
    //前插队列
}

void ShowQueue(int cputime){//显示两个队列，和运行的程序
    printf("\n----------------------------------------------");
    printf("----------------------------------------------\n");
    printf("\t当前时间片：%d\n", cputime);
    printf("\t%10s  %10s  %10s  %10s  %10s  %10s  %10s\n",
        "ID", "priority", "cpuTime", "allTime", "startBlock", "blockTime"," state");
    printf("正在运行程序：\n");
    p1 = RunPCB;
    if(RunPCB)
        printf("\t%10d  %10d  %10d  %10d  %10d  %10d  %10d\n", 
            p1->ID, p1->priority, p1->cpuTime, p1->allTime, p1->startBlock, p1->blockTime, p1->state);
    printf("\n就绪队列：\n");
    p1 = ReadyQueue;
    while(p1){//优先数加1
        printf("\t%10d  %10d  %10d  %10d  %10d  %10d  %10d\n", 
            p1->ID, p1->priority, p1->cpuTime, p1->allTime, p1->startBlock, p1->blockTime, p1->state);
        p1 = p1->next;
    }
    printf("\n阻塞队列：\n");
    p1=BlockQueue;
    while(p1){//阻塞时间-1
        printf("\t%10d  %10d  %10d  %10d  %10d  %10d  %10d\n", 
            p1->ID, p1->priority, p1->cpuTime, p1->allTime, p1->startBlock, p1->blockTime, p1->state);
        p1 = p1->next;
    }
    printf("\n完成队列：\n");
    p1 = accQueue;
    while (1){
        p1 = p1->next;
        if(p1) printf("\t%10d  %10d  %10d  %10d  %10d  %10d  %10d\n", 
            p1->ID, p1->priority, p1->cpuTime, p1->allTime, p1->startBlock, p1->blockTime, p1->state);
        if(p1==NULL||p1==acclast) break;
    }
}

运行截图