作业调度算法-先到先服务（FCFS）

关于先到先服务算法，我这里只陈述几个要点：

 

1.为什么缩写是FCFS？

first-come first-served，先到先服务。

 

2.FCFS算法中优先级的评定标准？

优先级根据等待时间来确定，等待时间越长，优先级越高，越优先执行。

 

3.为什么说等待时间越长FCFS算法调度作业的优先级越高？

这个问题开始挺纠结我的，不晓得大家有没有纠结过，给大家做一个比喻，当前一个饭店处于爆满状态（处理机调度作业此时处于忙碌状态），而此时还有好多顾客去吃饭（有好多新的作业进入调度队列），先到的顾客肯定比后到的顾客已经等待的时间要长，因此一旦有位子自然先到的顾客先入座，就是这样。

 

下面给出FCFS算法的执行模拟：

#include <bits/stdc++.h>

using namespace std;
#define     max(x, y)      x >= y ? x : y
#define     min(x, y)      x <= y ? x : y

#define     INF     0x3f3f3f3f


const int maxn = 105;//作业调度的最大数量

/*作业控制块的数据结构*/
typedef struct job_control_block
{

    int priority;    //作业优先级
    int runtime;     //作业预计运行时间
    int Count;       //作业执行计数器
    int waitime;     //等待时间

} JCB;


int font, rear;      //调度队列指针
JCB *Queue[maxn];    //作业调度队列
int number;          //队列中的作业数
long Time;           //模拟时钟


/*添加辅助延时函数*/
void Delay()
{
    for (int i = 0; i < 100000; i++)
        for (int j = 0;j < 10000; j++) ;
}


/*各参数初始化*/
void init()
{
    font = rear = 0;
    number = 0;
    Time = 0;
}


/*作业运行器*/
void RunningJob(JCB *job)
{
    job->Count = 0;   //作业计数器归零

    while (job->Count <= job->runtime) job->Count++;    //执行作业

    delete job;      //释放该作业
}

/*建立作业*/
void MakeJob(int num, JCB *job)
{
    for (int i = 0; i < num; i++) {

        job = new JCB;
        job->runtime = 10000 + rand() % 10001;          //随机化作业的运行时间（10000——20000）
        job->priority = number;
        Queue[rear] = job;
        rear = (rear + 1) % maxn;
        number++;
    }
}

/*作业调度函数*/
void RunJob()
{
    while (number > 0) {

        cout << "Job is running..." << endl;
        while (Queue[font]->Count <= Queue[font]->runtime) Queue[font]->Count++;
        Delay();            //延时等待（为了使作业运行显式化）
        cout <<"Job is finished!" << endl;

        delete Queue[font];

        font = (font + 1) % maxn;

        number--;
    }
}

int main()
{
    init();

    while (Time < LONG_MAX) {

        JCB *job = NULL;

        int num = rand() % 5;      //随机产生作业数量（0——4个）

        cout << "Creat Jobs number = " << num << endl;

        MakeJob(num, job);         //随机创建num个进程并加入作业调度队列

        RunJob();                  //按照FCFS的执行思路调度作业

        Time++;
    }
    return 0;
}

 

执行结果：