操作系统进程调度算法实现

本是古典何须时尚 2022-02-15 06:15 306阅读 0赞

bug好多，待完善

#include<unistd.h>
    #include<stdio.h>
    #include<stdlib.h>
    //enum STATE{Ready,Running,Blocked};
    
    #define MAX_SIZE 100
    typedef struct process_pcb
    {
    
        //进程ID
        int ID;//process ID
    
        int priority;
        int arrive_time;
        int service_time;
        int start_time;
        int end_time;
        int all_time;
        int cpu_time;
        int state;
        //周转时间=结束时间-到达时间
        int circulation_time;
        //带权周转时间=周转时间/服务时间
        int circulateWeight_time;
        int executeSequence;
        int remaining_time;
    
    
    
    
    
    } PCB;
    typedef struct
    {
    
        PCB data[MAX_SIZE];
        int font,rear;
    
    } sqQueue;
    sqQueue*  initQueue()
    {
        sqQueue *q=(sqQueue*)malloc(sizeof(sqQueue));
        if(q!=NULL)
        {
            q->font=0;
            q->rear=0;
            //  printf("%d %d",q->font,q->rear);
            //  printf("queue initalized successfully.\n");
    
    
        }
        return q;
    
    
    }
    int isEmpty(sqQueue *q)
    {
        if(q->rear==q->font)
        {
            return 1;
        }
        return 0;
    
    }
    int enQueue(sqQueue *q,PCB  data)
    {
        if((q->rear+1)%MAX_SIZE==q->font)
        {
    
            return 0;
        }
        else
        {
            q->rear=(q->rear+1)%MAX_SIZE;
            q->data[q->rear]=data;
            return 1;
    
        }
    
    
    }
    
    int deQueue(sqQueue *q,PCB *data)
    {
        if(q->rear==q->font)
        {
            return 0;
    
        }
        else
        {
            q->font=(q->font+1)%MAX_SIZE;
            *data=q->data[q->font];
            return 1;
        }
    
    
    }
    //按照服务时间最小排序
    sqQueue* selectSort(PCB pcb[],int n)
    {
        sqQueue *readyQueue=initQueue();
        int i,j;
        int t;
        PCB t2;
        for(i=0; i<n; i++)
        {
            for(j=i+1; j<n; j++)
            {
                if(pcb[i].arrive_time>pcb[j].arrive_time)
                {
                    t=pcb[i].executeSequence;
                    pcb[i].executeSequence=pcb[j].executeSequence;
                    pcb[j].executeSequence=t;
                    t2=pcb[i];
                    pcb[i]=pcb[j];
                    pcb[j]=t2;
    
                }
            }
            enQueue(readyQueue,pcb[i]);
            // printf("%d ",pcb[i].arrive_time);
        }
        return readyQueue;
    }
    
    //按照优先级最小排序
    sqQueue* selectSort2(PCB pcb[],int n)
    {
        sqQueue *readyQueue=initQueue();
        int i,j;
        int t;
        PCB t2;
        for(i=0; i<n; i++)
        {
            for(j=i+1; j<n; j++)
            {
                if(pcb[i].priority>pcb[j].priority)
                {
                    t=pcb[i].executeSequence;
                    pcb[i].executeSequence=pcb[j].executeSequence;
                    pcb[j].executeSequence=t;
                    t2=pcb[i];
                    pcb[i]=pcb[j];
                    pcb[j]=t2;
    
                }
            }
            enQueue(readyQueue,pcb[i]);
            // printf("%d ",pcb[i].arrive_time);
        }
        return readyQueue;
    }
    void printProcess(PCB pcb1);
    //先来先服务
    void FCFS(PCB pcb[],int n,sqQueue*readyQueue)
    {
        int time=0;
        int i=0;
        printf("\n");
        /* for(i=0; i<n; i++)
         {
             pcb[i].start_time=time;
             printf("process %d  start,start_time:%d,",pcb[i].ID,pcb[i].start_time);
             time+=pcb[i].service_time;
             pcb[i].end_time=time;
             pcb[i].executeSequence=i;
             printf("process %d end,end_time:%d\n",pcb[i].ID,pcb[i].end_time);
         }*/
    
        while(readyQueue->rear!=readyQueue->font)
        {
            PCB pcb1;
    
            deQueue(readyQueue,&pcb1);
            pcb1.start_time=time;
            time+=pcb1.service_time;
    
    
            pcb1.end_time=time;
            pcb1.circulation_time=pcb1.end_time-pcb1.arrive_time;
            pcb1.circulateWeight_time=pcb1.circulation_time/pcb1.service_time;
            pcb1.remaining_time=pcb1.remaining_time-pcb1.service_time;
            //enQueue(readyQueue,pcb[i]);
    
    
            i++;
            printProcess(pcb1);
    
    
        }
        // printProcess(pcb,n);
    }
    void printProcess(PCB pcb1)
    {
    
        printf("ID arrive_time service_time start_time end_time circulation_time circulateweight_time remaining_time  priority\n");
    
        printf("%d %6d %10d %10d %10d %10d %14d %20d %16d\n",pcb1.ID,pcb1.arrive_time,pcb1.service_time,pcb1.start_time,pcb1.end_time,pcb1.circulation_time,pcb1.circulateWeight_time,pcb1.remaining_time,pcb1.priority);
    
    }
    //短作业优先,非抢占
    void SJF(PCB pcb[],int num,sqQueue *readyQueue)
    {
        //readyQueue=selectSort(pcb,num);
        int time=0;
        int i=0;
        printf("\n");
        //到达队列存储当前已经到达的进程信息
        sqQueue*arriveQueue;
        int j=0;
        while(readyQueue->rear!=readyQueue->font)
        {
            //看当前是否有进程已经到达
            for(i=j; i<num; i++)
            {
    
                if(pcb[i].arrive_time>time)
                {
                    enQueue(arriveQueue,pcb[i]);
                }
                else
                {
                    j=i;
                    break;
                }
            }
            //对当前已经到达的进程进行按照服务时间由低到高排序
    
    
            //执行最短作业的进程,把该进程从到达队列里出列
    
        }
        // printProcess(pcb,num);
    
    }
    //最短剩余时间优先，抢占
    void SRT(PCB pcb[],int num,sqQueue *readyQueue)
    {
    
        while(readyQueue->rear!=readyQueue->font)
        {
            //查看当前是否有进程到达
    
            //如果有进程到达，查询当前时间是否
    
        }
    
    }
    //时间片轮转算法
    void RR(sqQueue* readyQueue,PCB pcb[],int num,int timeLength)
    {
        int time=0;
        int i=0;
        //初始化就绪队列
        //sqQueue *readyQueue=initQueue();
    
        //第一个进程0时刻到达，加入就绪队列
        /* i=0;
         enQueue(readyQueue,pcb[i]);
         i++;*/
    
        //初始化完成队列
        sqQueue *finishQueue=initQueue();
        int k=0;
        while(1)
        {
            //查看当前时间片是否有进程到达
            /* int j;
             for(j=i; j<num; j++)
             {
    
                 if(pcb[j].arrive_time<=time)
                 {
                     enQueue(readyQueue,pcb[j]);
                     printf("process %d has put into readyQueue int time %d\n",pcb[j].ID,pcb[i].arrive_time);
                 }
                 else
                 {sqQueue* readyQueue,PCB pcb[],int num
                     i=j;
    
                     break;
                 }
             }*/
            //到达队列执行一个时间片,如果一个进程为到一个时间片，则该进程加到队列末尾
            PCB pcb1;
            time+=timeLength;
            deQueue(readyQueue,&pcb1);
            pcb1.start_time=time-timeLength;
            pcb1.end_time=time;
            pcb1.circulation_time=pcb1.end_time-pcb1.arrive_time;
            pcb1.circulateWeight_time=pcb1.circulation_time/timeLength;
            printf("pcb1.remaining_time:%d timeLength:%d\n",pcb1.remaining_time,timeLength);
    
            if(pcb1.remaining_time>timeLength)
            {
    
                pcb1.remaining_time=pcb1.remaining_time-timeLength;
                printProcess(pcb1);
                enQueue(readyQueue,pcb1);
            }
            else
            {
                pcb1.remaining_time=0;
                printProcess(pcb1);
                printf("processs %d has finished\n",pcb1.ID);
                enQueue(finishQueue,pcb1);
                k++;
    
    
            }
            if(k==num)
            {
                printf("all processes has finished\n");
    
                break;
            }
    
        }
    }
    //动态优先级算法
    void dynamicPriority(sqQueue* readyQueue,PCB pcb[],int num)
    {
        //规定程序占用cpu时间大于1,优先级减小0.5
        //程序等待时间大于1，优先级增加1
        //程序等待时间=当前cpu时间-程序到达时间
        int nums=num;
    
    
        readyQueue=selectSort2(pcb,num);
    
        int time=0;
        int i=0;
        int k;
        int finished=0;
        printf("\n");
        while(readyQueue->rear!=readyQueue->font)
        {
    
            PCB pcb1;
    
            deQueue(readyQueue,&pcb1);
            if(pcb1.remaining_time>1)
            {
                pcb1.priority-=0.5;
                pcb1.remaining_time=pcb1.remaining_time-1;
                pcb1.start_time=time;
                time+=1;
                pcb1.end_time=time;
                pcb1.circulation_time=pcb1.end_time-pcb1.arrive_time;
                pcb1.circulateWeight_time=pcb1.circulation_time/1;
                pcb1.remaining_time=pcb1.remaining_time-1;
                pcb1.arrive_time=time;
    
                printProcess(pcb1);
                //直接更新就绪队列
                printf("1 ");
    
                for(k=0; k<num; k++)
                {
    
                    if(pcb[k].ID==pcb1.ID)
                    {
                        pcb[k]=pcb1;
    
    
                    }
    
                }
                printf("2 ");
    
                readyQueue=selectSort2(pcb,num);
                printf("3 ");
    
    
    
    
            }
            else
            {
                pcb1.start_time=time;
                time+=pcb1.service_time;
                pcb1.end_time=time;
                pcb1.circulation_time=pcb1.end_time-pcb1.arrive_time;
                pcb1.circulateWeight_time=pcb1.circulation_time/pcb1.service_time;
                pcb1.remaining_time=pcb1.remaining_time-pcb1.service_time;
                if(pcb1.remaining_time==0)
                {
    
                    pcb1.remaining_time=0;
                }
                printProcess(pcb1);
                printf("process %d has finished\n",pcb1.ID);
                finished++;
    
                if(finished==nums)
                {
                    break;
    
                }
    
    
                //删除数组中的元素
    
                PCB pcb2[num-1];
                int j=0;
    
                for(k=0; k<num; k++)
                {
    
                    if(pcb[k].ID!=pcb1.ID)
                    {
                        pcb2[j]=pcb[k];
                        j++;
    
                    }
    
                }
                num-=1;
                pcb=pcb2;
    
    
    
                //更新就绪队列
                 readyQueue=selectSort2(pcb,num);
                 for(k=0; k<num; k++)
                {
                    printProcess(pcb2[k]);
    
    
                }
    
    
            }
    
            //等待时间过程的进程优先级增加
            for(k=0; k<num; k++)
            {
    
    
                int wait_time=time-pcb[k].arrive_time;
                pcb[k].priority+=wait_time;
    
    
            }
            printf("remaining process num:%d\n",num);
    
    
    
    
    
        }
    
    
    }
    //静态优先级算法
    void staticPriority(sqQueue* readyQueue,PCB pcb[],int num)
    {
        readyQueue=selectSort2(pcb,num);
    
        int time=0;
        int i=0;
        printf("\n");
        /* for(i=0; i<n; i++)
         {
             pcb[i].start_time=time;
             printf("process %d  start,start_time:%d,",pcb[i].ID,pcb[i].start_time);
             time+=pcb[i].service_time;
             pcb[i].end_time=time;
             pcb[i].executeSequence=i;
             printf("process %d end,end_time:%d\n",pcb[i].ID,pcb[i].end_time);
         }*/
    
        while(readyQueue->rear!=readyQueue->font)
        {
    
            PCB pcb1;
    
            deQueue(readyQueue,&pcb1);
            pcb1.start_time=time;
            time+=pcb1.service_time;
    
    
            pcb1.end_time=time;
            pcb1.circulation_time=pcb1.end_time-pcb1.arrive_time;
            pcb1.circulateWeight_time=pcb1.circulation_time/pcb1.service_time;
            pcb1.remaining_time=pcb1.remaining_time-pcb1.service_time;
            //enQueue(readyQueue,pcb[i]);
    
    
            i++;
            printProcess(pcb1);
    
    
        }
    
    
    }
    
    int main()
    {
        sqQueue *readyQueue=initQueue();
        int num;
        printf("\nPlease input the num of process.\n");
        scanf("%d",&num);
        int i=0;
        PCB pcb[num];
        printf("Please input information for ready.\n");
        for(i=0; i<num; i++)
        {
            printf("Please input the %d process priority,arrive_time,service_time\n",i);
            scanf("%d %d %d",&pcb[i].priority,&pcb[i].arrive_time,
                  &pcb[i].service_time);
            pcb[i].ID=i;
            pcb[i].state=0;
            pcb[i].remaining_time=pcb[i].service_time;
            pcb[i].cpu_time=0;
            pcb[i].start_time=0;
            pcb[i].end_time=0;
            pcb[i].circulation_time=0;
            pcb[i].circulateWeight_time=0;
    
    
            printf("%d\n",enQueue(readyQueue,pcb[i]));
    
        }
    
        //FCFS(pcb,num,readyQueue);
    
        //时间片轮转算法
        /*int timeLength;
        printf("Please input the length of time:\n");
        scanf("%d",&timeLength);
        RR(readyQueue,pcb,num,timeLength);*/
    
        dynamicPriority(readyQueue,pcb,num);
        // staticPriority(readyQueue,pcb,num);
    
    
        /* for(i=0;i<num;i++)
         {
    
             printf("%d %d %d\n",pcb[i].priority,pcb[i].arrive_time,pcb[i].service_time);
    
         }*/
        /*readyQueue= selectSort(pcb,num);
        PCB data;
        int result=0;
        while(( result=deQueue(readyQueue,&data))>0)
        {
            printf("process %d deQueue\n",data.ID);
    
        }
    
        printf("process has put into queue");*/
    
    
    
        /* FCFS(pcb,num);
    
        SJF(pcb,num);*/
    
        return 0;
    }