操作系统FCFS调度算法C语言实现

里克贝斯

发布于 2021-05-21 15:50:11

3.4K0

发布于 2021-05-21 15:50:11

FCFS调度算法原理

FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。

数据结构

设计一个链式队列，链式指针代表按照进程到达系统的时间将处于就绪状态的进程连接成一个就绪队列。指针指出下一个到达进程的进程控制块首地址。最后一个进程的链指针为NULL。

其中

周转时间=结束时间-到达时间、平均周转时间=周转时间/运行时间

代码

#include<stdio.h>
#include<windows.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
typedef double Time;

typedef struct Process{
    int PID;
    Time runTime;
    Time arriveTime;
    Time finishTime;
    Time workTime;
    Time cycleTime;
    Time avecycleTime;
    int status;
    struct Process *next;
}LinkQueue, PCB, *process;

LinkQueue *InitQueue(LinkQueue *Q){
    /*初始化队列*/
    Q=(LinkQueue *)malloc(sizeof(LinkQueue));
    Q->next=NULL;
    return Q;
}

LinkQueue *EnQueue(LinkQueue *Q,int PID0,Time arrive0,Time run0,int i){
    /* 在i位置插入元素e为Q的新进程 */
    int j=0;
    LinkQueue *q,*p;
    q = Q;
    if(!Q)
        printf("Empty list\n");
    else
        while(j<i)
        {
            j++;
            q=q->next;
        }
    p=(LinkQueue *)malloc(sizeof(LinkQueue));
    p->PID=PID0;
    p->arriveTime=arrive0;
    p->runTime=run0;
    p->status = 0;
    printf("进程信息:PID:%d     到达时间:%lf     运行时间:%lf     \n",p->PID,p->arriveTime,p->runTime);
    p->next=q->next;
    q->next = p;
    return Q;
}

void showInfo(LinkQueue *Q){
    process p;
    p=Q->next;
    printf("PID     到达时间     运行时间     结束时间     周转时间     平均周转时间\n");

    for(;p!=NULL;p=p->next)
    {
        printf("%d      %3lf      %3lf      %3lf      %3lf      %3lf\n",p->PID,p->arriveTime,p->runTime,p->finishTime,p->cycleTime,p->avecycleTime);
    }
}

void FCFS(LinkQueue *Q){
    process p;
    if(Q->next==NULL)
        printf("error\n");
    p=Q->next;
    Time current_time=0;    //系统当前时间
    for(;p!=NULL;)
    {
        if(p->arriveTime <= current_time)
        {
            p->workTime = p->runTime;
            while(p->workTime){
                printf("正在执行的进程: %d      剩余时间：%5lf\n",p->PID,p->workTime);

                Sleep(p->workTime*1000);
                p->workTime--;
            }
            process q;
            q=p->next;
            printf("就绪队列的进程ID为:");
            for(;q!=NULL;){
                printf("%d----",q->PID);
                q=q->next;
            }
            printf("NULL\n");
            printf("当前进程执行完毕\n");
            current_time += p->runTime;
            p->finishTime = current_time;
            p->cycleTime = p->finishTime - p->arriveTime;
            p->avecycleTime = p->cycleTime/p->runTime;
            p->status = 1;
            printf("当前进程信息%d        %5lf      %5lf        %5lf\n",p->PID,p->finishTime,p->cycleTime,p->avecycleTime);
            p = p->next;
        }
        else
        {
            current_time = p->arriveTime;
        }
    }
}

int main(){
    PCB *buffer;
    buffer=InitQueue(buffer);
    int num;
    printf("进程数量：");
    scanf("%d",&num);
    printf("输入%d个进程（PID、运行时间）\n",num);
    int i;
    srand((unsigned) time(NULL));
    int temp = 0;
    for(i=0;i<num;i++){
        int PID0;
        Time arrive0,run0;
        arrive0 = temp + rand()%5;
        temp = arrive0;
        scanf("%d  %lf",&PID0,&run0);
        EnQueue(buffer,PID0,arrive0,run0,i);
    }
    FCFS(buffer);
    showInfo(buffer);
    return 0;
}