动态高优先权优先调度

ゝ一世哀愁。 2022-01-31 12:57 159阅读 0赞

实验内容：

模拟实现动态高优先权优先（若数值越大优先权越高，每运行一个时间单位优先权-n，若数值越小优先权越高，每运行一个时间单位优先权+n），具体如下：

设置进程体：进程名，进程的到达时间，服务时间，初始优先权，进程状态（W——等待,R——运行,F——完成），进程间的链接指针

进程初始化：由用户输入进程名、服务时间、初始优先权进行初始化，同时，初始化进程的状态为W。

显示函数：在进程调度前、调度中和调度后进行显示。

排序函数：对就绪状态的进程按照优先权排序。优先权相同时进入等待队列时间早的进程在前。注意考虑到达时间

调度函数：每次从等待队列队首调度优先权最高的进程执行，状态变化。并在执行一个时间单位后优先权变化，服务时间变化，状态变化。当服务时间为0时，状态变为F。

删除函数：撤销状态为F的进程。

实验要求：

1.  测试数据可以随即输入或从文件中读入。
2.  必须要考虑到进程的到达时间
3.  最终能够计算每一个进程的周转时间。

#include<string.h>
    #include<stdlib.h>
    #include<stdio.h>
    using namespace std;
    struct PCB
    {
        char *name;
        int arrive;
        int need;
        int runtime;
        int priority;
        int endtime;
        int turn;
        char state;
        struct PCB *next;
    };
    int run_sum = 0;
    void chushihua(struct PCB *head,  char *name,  int arrive,  int need,  int priority)
    {
        struct PCB *temp = new PCB();
        temp->name = (char *) malloc(sizeof(char) * strlen(name));
        strcpy(temp->name,name);
        temp->arrive = arrive;
        temp->need = need;
        temp->runtime = need;
        temp->priority = priority;
        temp->state = 'W';
        temp->next = head->next;
        head ->next = temp;
        return;
    }
    
    void Print(struct PCB *temp)
    {
        printf("\n该进程已执行结束：");
        printf("进程名%s  \t周转时间%d\n",temp->name,temp->turn);
    }
    
    void Add(struct PCB *head_temp,struct PCB *head_queue)
    {
        struct PCB *temp = new PCB();
        temp->name = (char*)malloc(sizeof(char) * strlen(head_temp->name));
        strcpy(temp->name,head_temp->name);
        temp->arrive = head_temp->arrive;
        temp->need = head_temp->need;
        temp->runtime = head_temp->runtime;
        temp->priority = head_temp->priority;
        temp->state = 'W';
        struct PCB *p = NULL;
        for(p = head_queue; p ->next; p = p->next);
        p->next = temp;
        return;
    }
    
    void Sort(struct PCB *head_queue)
    {
        struct PCB *p = head_queue ->next;
        struct PCB *q = NULL;
        (head_queue) ->next = NULL;
        for(struct PCB *h = p; p; )
        {
            h = p;
            p = p ->next;
            h ->next = NULL;
            for(q = head_queue; q ->next; q = q ->next)
            {
                if(q ->next->priority < h ->priority)
                {
                    h->next = q->next;
                    q ->next = h;
                    break;
                }
                if(q ->next->priority == h ->priority)
                {
                    if(q->next->arrive > h->arrive)
                    {
                        h->next = q->next;
                        q ->next = h;
                        break;
                    }
                }
            }
            if(!q ->next)
                q ->next = h;
        }
        return;
    }
    
    void Free(struct PCB *head_queue)
    {
        if(!(head_queue ->next))
            return;
        head_queue ->next->state = 'F';
        Print(head_queue ->next);
        struct PCB *p = head_queue ->next;
        head_queue->next = p->next;
        delete p;
        return;
    }
    void display(struct PCB *head)
    {
        printf("======================");
        printf("\n就绪状态的进程有：\n");
        for(struct PCB *p = head ->next->next; p; p = p->next)
            if(p->state=='W')
                printf("%s ",p->name);
        printf("\n");
        printf("\n执行状态的进程有：\n");
        PCB *p = head ->next;
        printf("%s ",p->name);
        printf("\n======================\n");
    }
    void High(struct PCB *head,struct PCB *head_queue)
    {
        int run_i = 0,run_over = 0,time_runing = 0;
        struct PCB* h;
        /*run_i是表示一个时间片，run_over 时表示结束进程的数目，time_running 表示时间从0时刻开始++*/
        while(time_runing >= 0)
        {
            h=head_queue;
            for(struct PCB *p = head ->next; p; p = p->next)
                if(time_runing == p->arrive)
                    Add(p,head_queue);
            if(head_queue ->next)
            {
                if(run_i == 1 && head_queue->next->runtime)
                {
                    if(head_queue->next->priority)
                    {
                        head_queue->state='R';
                        head_queue->next->priority -= 1;
                        if(head_queue->next->priority < 0)
                            head_queue->next->priority = 0;
                    }
                    Sort(head_queue);
                    run_i = 0;
                }
                if(!head_queue->next->runtime)
                {
                    head_queue->state='F';
                    if(head_queue->next->priority)
                    {
                        head_queue->next->priority -= 1;
                        if(head_queue->next->priority < 0)
                            head_queue->next->priority = 0;
                    }
                    head_queue->next->turn=time_runing-head_queue->next->arrive;
                    Free(head_queue);
                    Sort(head_queue);
                    run_i = 0;
                    run_over++;
                }
                if(head_queue ->next)
                {
                    head_queue->next->runtime--;
                }
                if(run_over == run_sum)
                    return;
                if(run_over==run_sum-1)
                {
    
                    printf("\n时间%d各进程状态显示如下：\n",time_runing);
                    printf("======================");
                    printf("\n无就绪状态的进程\n");
    
                    printf("\n执行状态的进程有：\n");
                    PCB *p = head ->next;
                    printf("%s ",p->name);
                    printf("\n");
                }
                else
                {
                    printf("\n时间%d各进程状态显示如下：\n",time_runing);
                    display(h);
                }
                run_i++;
            }
            time_runing++;
            if(run_over == run_sum)
                return;
        }
        return;
    }
    
    int main()
    {
        struct PCB *head = new PCB();
        struct PCB *head_queue = new PCB();
        char name[20];
        int arrive,need,priority;
        int num;
        printf("请输入进程个数:\n");
        scanf("%d",&num);
        run_sum=num;
        printf("请输入进程信息，(进程名 到达时间 服务时间 优先权)\n");
        while( num--)
        {
            scanf("%s%d%d%d",name,&arrive,&need,&priority);
            chushihua(head,name,arrive,need,priority);
        }
        High(head,head_queue);
        return 0;
    }