在Windows系统下用C/C++编程实现两种处理机调度算法。

Question

1. CPU Scheduling (1)题目描述 编程实现两种处理机调度算法，可选择的以下组合方式其中之- -: 1) 高优先级优先调度算法和时间片轮转调度算法; 2) 短进程优先调度算法和时间片轮转调度算法; 3) 先入先出调度算法和时间片轮转让调度算法。 选择-一个调度算法，实现处理机调度。(2)功能实现 o输入提示选择哪种算法，例如:输入“0”--HPF，输入“1”--RR; ) 输入提示创建进程的个数，初始化进程; PCB内容:进程名/PID 运行时间 优先权 状态 PCB指针 ●运行过程中须提示所创建进程的状态信息，包括:已运行的时间,还需运行的时间，阻塞的时间，要阻塞多长时间; ●提示进程的状态:运行，就绪，阻塞三者之- -; ●建立进程的PCB， 用队列实现进程就绪队列和阻塞队列的管理。 可随机输入若干进程，并按所选算法的规则排序，从就绪队首选进程运行，进程在运行过程中定时(或发生调度时)更新各进程的状态信息， 进程名状态运行时间 剩余运行时间 优先级进程阻塞属性(有阻塞/无阻塞) 规定系统可接纳的进程的道数，设置后备队列和挂起状态。若内存中进程少于规定道数，可自动从后备队列调度- -作业进入。 被挂起进程入挂起队列，设置解挂功能用于将指定挂起进程解挂入就绪队列。

Answer 1

#include<stdio.h>
#include<stdlib.h>       //有用到malloc()
#include<conio.h>       //键盘输入
#include<windows.h>
 #define MAX 10


#define getpch(type)  (type*)malloc(sizeof(type))
#define NULL 0

struct task_struct
{
    char name[10];           /*进程名称*/
    int number;              /*进程编号*/
    float come_time;         /*到达时间*/
    float run_begin_time;     /*开始运行时间*/
    float run_time;          /*需要运行时间*/
    float runed_time;       /*运行时间*/
    float run_end_time;      /*运行结束时间*/
    int priority;           /*优先级*/
    int run_flag;          /*调度标志*/
    int start_flag;     //是否为第一次开始调度
} tasks[MAX];
int counter; /*实际进程个数*/
int time_counter=0;
int poutput(); /*调度结果输出*/
int time();
int charge();//判断是否所有的进程都被执行过

struct pcb                   //定义进程控制块
{
    char name[10];           //定义进程名
    char state;              //进程状态
    int  super;             //进程优先级
    int  rtime;              //已经运行时间
    int  ntime;                //运行所需时间
    struct pcb* link;           //定义一个队列指针，定义了一个指向pcb结构类型的指针link作为自己的成员函数
}*ready=NULL,*p;                 //定义两个指向pcb结构指针类型的指针ready和p，ready的初值为空,并建立了一个空的就绪队列


typedef struct pcb PCB;           //定义将struct pcb称为PCB




//***********************************************************************************************
void sort()                       //建立对进程进行优先级排列的函数
{
    PCB *f,*s;                   //定义两个用来排列的指针first和second
    int insert=0;                    //插入
    if((ready==NULL)||(p->super)>(ready->super))     //比较优先级，优先级最大者，直接插入队首
    {
        p->link=ready;                           //
        ready=p;                                // 将新建进程放入队首
    }
    else                                      //比较进程的优先级，并将其插入适当的地方
    {
        f=ready;                          //                                                
        s=f->link;                              //插入新的进程
        while(s!=NULL)                           //如果第二个进程不为空
        {
            if((p->super)>(s->super))            //将插入进程与当前进程比较
            {                                   //如果插入进程的优先级大于当前进程优先级，则插入当前优先级的前面
                p->link=s;
                f->link=p;
                s=NULL;
                insert=1;
            }
            else                                 //否则，将新插入的进程插入到当前进程的后面，向后移指针
            {
                f=f->link;
                s=s->link;
            }
        }
        if(insert==0)
            f->link=p;                           //将p指针指向队尾
    }
}




//**********************************************************************************
void input()                                          //建立进程控制块函数
{
    int i,num;                               
    printf("*********************最高优先级优先算法**********************");
    printf("\n 请输入进程的数量：");
    scanf("%d",&num);              //键盘上输入
    for(i=1;i<=num;i++)
    {
        printf("\n 进程号No.%d:",i);
        p=getpch(PCB);
        printf("\n 请输入进程名：");
        scanf("%s",p->name);
        printf("\n 请输入进程优先级：");
        scanf("%d",&p->super);
        printf("\n 请输入进程所需运行时间：");
        scanf("%d",&p->ntime);
        printf("\n");
        p->rtime=0;
        p->state='w';
        p->link=NULL;
        sort();                               //调用sort函数进行排序
    }
}






//********************************************************************************
int space()                 //计算进程控制块个数的函数
{
    int k=0;
    PCB*pr=ready;          //pr指向队首进程
    while(pr!=NULL)          //pr为空则说明计数完成，就绪队列没到头，就一直输出
    {
        k++;
        pr=pr->link;
    }
    printf(" 进程数量：%d\n",k);
    printf("*********************************************\n");
    return(k);
}






//************************************************************************************
void disp(PCB*pr)   //建立进程显示函数，显示当前的进程
{
    printf("\n name\t state\t super \t ntime\t rtime\n");
    printf(" %s  \t",pr->name);
    printf(" %c  \t",pr->state);
    printf(" %d  \t",pr->super);
    printf(" %d  \t",pr->ntime);
    printf(" %d  \t",pr->rtime);
    printf("\n");
}






//****************************************************************************
void check()            //建立进程查看函数，查看已经排列好的情况
{
    PCB* pr;
    printf("\n 当前正在运行的进程：%s",p->name);
    disp(p);                //调用disp()显示已经筛选出来的正在运行的进程
    pr=ready;                
    printf("\n 当前就绪队列状态为：\n");
    while(pr!=NULL)
    {
        disp(pr);             //调用disp()显示已经排列好的就绪队列  
        pr=pr->link;
    }
}


void destroy()      //建立函数，撤销进程
{
    printf("\n 进程[%s]已完成.\n",p->name);
    free(p);                            //释放空间
}






//********************************************************************************
void running()                 //建立进程就绪函数（进程运行时间到，置为就绪状态）
{
    (p->rtime)++;                    //运行时间加一
    if(p->rtime==p->ntime)
       destroy();                     //
     else
     {
         (p->super)--;             //运行时间减一
         p->state='w';
         sort();                   //调用一次之后，运行时间时间和运行状态改变后，重新去排序进程
     }
} 


//***************************************************************************
void HPF()                        //主函数
{
    int len,h=0;                                //h是用于计算执行次数的
    char ch;
    input();                                    //调用input函数输入相关的进程信息
    len=space();                              //input调用完之后，回到主函数调用space函数得到对列长度
    while((len!=0)&&(ready!=NULL))
    {
        ch=getchar();                  //从键盘输入一个字符型数据，把值赋给变量ch,这个是为了每一次被执行，自己手动回车呈现出来，如果没有，则会一次性出现全部被执行的情况
        h++;
        printf("\n The execute number:%d \n",h);
        p=ready;
        ready=p->link;
        p->link=NULL;
        p->state='R';
        check();                         //调用显示正在运行的函数和就绪的函数
        running();        // 调用进程就绪函数,上一个正在运行的进程运行完之后，运行时间加1，将就绪队列里面优先级最高的进程置为运行状态，如果是同优先级，则看哪个先进来，这个不可以运行在check()前，会导致多计算，并出现错误
        printf("\n 请回车继续......");
        ch=getchar();
    }
    printf("\n\n 进程已经完成.\n");
    ch=getchar();
}


void RR()
{

    pinput();
    printf("时间片轮转算法。\n\n");
    time();
    poutput();
}

int time()
{
    float time_temp=0;
    int i;
    int j=0;
    int k=0;
    char ch;
    struct task_struct  copy_task[MAX];//备份
    for(i=0; i<counter; i++)
    {
        copy_task[j++]=tasks[i];//对进程的初始化信息备份
    }

    time_temp=tasks[0].come_time;
    while(charge())
    {
        for(i=0; i<counter; i++)
        {
            if(tasks[i].come_time>time_temp)
            {
                time_temp=tasks[i].come_time;
                poutput();
                printf("\n 新进程进入输入...任意字符继续......");
                ch=getchar();
            }
            if(tasks[i].run_flag==0)//该进程还未结束
            {
                if(tasks[i].start_flag==0)  //该条件成立则说明，该进程是第一次执行，记录开始执行时间
                {
                    tasks[i].run_begin_time=time_temp;
                    tasks[i].start_flag=1;
                }
                if(tasks[i].run_time/time_counter>1)//至少有两倍的时间片未执行
                {
                    tasks[i].run_time=tasks[i].run_time-time_counter;
                    time_temp=time_temp+time_counter;
                    tasks[i].runed_time = tasks[i].runed_time + (float)time_counter;//加上的不知道又没用 
                    poutput();
                    printf("\n 执行一次时间片了..按任意字符继续........");
                    ch=getchar();
                }
                else if(tasks[i].run_time-time_counter==0)
                {
                    time_temp=time_temp+time_counter;
                    tasks[i].run_end_time=time_temp;
                    tasks[i].run_flag=1;
                    tasks[i].run_time=copy_task[i].run_time;
                    tasks[i].runed_time = tasks[i].runed_time + (float)time_counter;//加上的不知道又没用 
                    poutput();
                    printf("\n 任务完成..按任意字符继续........");
                    ch=getchar();
                }
                else//仅剩下不足一倍的时间片
                {
                    time_temp=time_temp+tasks[i].run_time;
                    tasks[i].runed_time = tasks[i].runed_time + tasks[i].run_time;//加上的不知道又没用 
                    tasks[i].run_end_time=time_temp;
                    tasks[i].run_flag=1;
                    tasks[i].run_time=copy_task[i].run_time;

                    poutput();
                    printf("\n 任务完成..按任意字符继续........");
                    ch=getchar();
                }
            }
        }
    }
}

int charge()//判断是否全部进程都执行完毕
{
    int k;
    int super_flag=0;//判断是否全部的进程都执行完毕
    for(k=0; k<counter; k++)
    {
        if(tasks[k].run_flag==0)
        {
            super_flag=1;
            return super_flag;
            break;
        }
        else
        {
            super_flag=0;
        }
    }
    return super_flag;
}

int pinput() /*进程参数输入*/
{
    printf("*********************最高优先级优先算法**********************\n");
    int i;
    printf("请输入进程数量:\n");
    scanf("%d",&counter);
    printf("请输入时间片长度:\n");
    scanf("%d",&time_counter);
    for(i=0; i<counter; i++)
    {
        printf("******************************************\n");
        printf("请输入第 %d 个进程的信息 :\n",i+1);
        printf("请输入进程的名字:\n");
        scanf("%s",tasks[i].name);
        printf("请输入进程编号:\n");
        scanf("%d",&tasks[i].number);
        printf("请输入进程进入时间:\n");
        scanf("%f",&tasks[i].come_time);
        printf("请输入进程运行时间:\n");
        scanf("%f",&tasks[i].run_time);
        printf("进程优先级:\n");
        scanf("%d",&tasks[i].priority);
        tasks[i].run_begin_time=0;
        tasks[i].run_end_time=0;
        tasks[i].runed_time=0; //运行时间初始化 
        tasks[i].run_flag=0;  //运行是否结束
        tasks[i].start_flag=0;//是否首次被执行
    }
    return 0;
}

int poutput() /*调度结果输出*/
{
    int i;
    float turn_round_time=0,f1,w=0;
    printf("进程名 进程号 到达时间 需要运行时间 开始时间 结束时间 优先级 周转时间 运行时间 运行状态\n");
    for(i=0; i<counter; i++)
    {
        f1=tasks[i].run_end_time-tasks[i].come_time;
        turn_round_time+=f1;
        printf("%s\t%d\t%5.3f\t%5.3f\t    %5.3f\t %5.3f\t    %d\t  %5.3f  %5.3f  %d\n",tasks[i].name,tasks[i].number,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,tasks[i].runed_time,f1,tasks[i].run_flag);
    }
    printf("average_turn_round_timer=%5.2f\n",turn_round_time/counter);
    return 0;
}
void main(){
    int flag = 0;
    printf("请输入算法规则（0是HPF->高优先级优先调度算法,1是RR->时间片轮转调度算法）：\n") ;
    scanf("%d",&flag);
    if (flag == 0){
        HPF();
    } else if(flag = 1){
        RR();
    } else{
        printf("没有其他了算法"); 
    }

}