作業系統FCFS排程算法C語言實作

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;
}           

複制

結果