操作系统调度算法详解：先来先服务调度算法(FCFS)的C语言实现

创作时间:

作者:

@小白创作中心

操作系统调度算法详解：先来先服务调度算法(FCFS)的C语言实现

引用

CSDN

https://m.blog.csdn.net/m0_69550216/article/details/143130598

操作系统调度算法是操作系统中非常重要的一个部分，其中先来先服务调度算法（FCFS）是最基本也是最简单的调度算法之一。本文将详细介绍FCFS调度算法的原理、特点以及其C语言实现。

一、算法原理

先来先服务调度算法按照作业或进程到达的先后次序来进行调度。具体过程如下：

作业调度：当作业调度中采用该算法时，每次调度都是从后备队列中选择一个最先进入该队列的作业，将它调入内存，为其创建进程、分配相应的资源，并将该作业的进程放入就绪队列。
进程调度：在进程调度中采用该算法时，每次调度是从就绪队列中选择一个最新进入该队列的进程，并给它分配处理机。进程会一直运行下去，直到该进程完成工作或者因为等待某事件发生而不能继续运行时才释放处理机。

二、算法特点

非抢占式：先来先服务调度算法是一种非抢占式的算法，即先进入就绪队列的进程先分配处理机运行。一旦一个进程占有了处理机，它就会一直运行下去，直到该进程完成工作或者因为等待某事件发生而不能继续运行时才释放处理机。
公平性：该算法相当公平，因为每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。
简单易行：该算法只需要一个队列（FIFO），易于理解和实现。

三、算法时间计算

开始时间 = 如果提交时间早于等于上一个完成时间，则开始时间为上一个完成时间；（第一个作业的开始时间=提交时间，也就是下标为0）
完成时间 = 开始时间+运行时间；
周转时间 = 完成时间- 提交时间；
带权周转时间 = 周转时间 / 运行时间；
平均周转时间 = 周转时间总和 / 作业个数
平均带权周转时间 = 带权周转时间总和/ 作业个数

四、算法代码实现

1.结构体及结构体数组

struct JCB
{
    int id;              //作业号 
    double submittime;   //提交时间 
    double runtime;      //运行时间 
    double starttime;    //开始时间 
    double finishtime;   //完成时间 
    double cycletime;    //周转时间 
    double qtt;          //带权周转时间 
};
struct JCB jcb[10];

2.排序算法函数

//直接插入排序
void InsertSort(int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        struct JCB tmp = jcb[end + 1];
        while (end >= 0 && jcb[end].submittime > tmp.submittime)
        {
            jcb[end + 1] = jcb[end];//将大于要插入的数往后移
            end--;
        }
        jcb[end + 1] = tmp;//插入到最后一位移动前的位置
    }
}

3.FCFS算法函数

通俗易懂版：

//通俗易懂版本
void FCFS(int num)
{
    for (int i = 0; i < num; i++)
    {
        if (i == 0)
        {
            jcb[i].starttime = jcb[i].submittime;//如果是第一个，则开始时间就等于提交时间
            jcb[i].finishtime = jcb[i].starttime + jcb[i].runtime;//完成时间 =开始时间+运行时间 ；
            jcb[i].cycletime = jcb[i].finishtime - jcb[i].submittime;//周转时间 = 完成时间- 提交时间 ；
            jcb[i].qtt = jcb[i].cycletime / jcb[i].runtime;//周转时间 / 运行时间 ；
        }
        else
        {
            //如果提交时间早于等于上一个完成时间，则开始时间为上一个完成时间
            if (jcb[i].submittime <= jcb[i - 1].finishtime)
            {
                jcb[i].starttime = jcb[i - 1].finishtime;
            }
            else
            {
                jcb[i].starttime = jcb[i].submittime;
            }
            jcb[i].finishtime = jcb[i].starttime + jcb[i].runtime;//完成时间 =开始时间+运行时间 ；
            jcb[i].cycletime = jcb[i].finishtime - jcb[i].submittime;//周转时间 = 完成时间- 提交时间 ；
            jcb[i].qtt = jcb[i].cycletime / jcb[i].runtime;//周转时间 / 运行时间 ；
        }
    }
}

简洁优化版：

//代码简洁优化版
void FCFS(int num)
{
    for (int i = 0; i < num; i++)
    {
        if (i != 0 && jcb[i].submittime <= jcb[i - 1].finishtime)
        {
            jcb[i].starttime = jcb[i - 1].finishtime;
        }
        else
        {
            jcb[i].starttime = jcb[i].submittime;
        }
        jcb[i].finishtime = jcb[i].starttime + jcb[i].runtime;
        jcb[i].cycletime = jcb[i].finishtime - jcb[i].submittime;
        jcb[i].qtt = jcb[i].cycletime / jcb[i].runtime;
    }
}

4.信息展示函数

void showinfo(int num)
{
    double acycletime = 0.0;
    double aqtt = 0.0;
    printf("作业号\t提交时间\t运行时间\t开始时间\t完成时间\t周转时间\t带权周转时间\n");
    for (int i = 0; i < num; i++)
    {
        printf("%d\t  %0.2lf\t\t   %0.2lf\t\t   %0.2lf\t\t   %0.2lf\t\t   %0.2lf\t\t   %0.2lf\n", jcb[i].id, jcb[i].submittime, jcb[i].runtime, jcb[i].starttime, jcb[i].finishtime, jcb[i].cycletime, jcb[i].qtt);
        acycletime += jcb[i].cycletime;
        aqtt += jcb[i].qtt;
    }
    printf("平均周转时间:%0.2lf\n", acycletime/num);
    printf("平均带权周转时间:%0.2lf\n", aqtt/num);
}

5.main函数

int main()
{
    int num;
    printf("请输入进程个数：\n");
    scanf("%d", &num);
    printf("依次输入：\n作业号  到达时间 运行时间\n");
    for (int i = 0; i < num; i++)
    {
        scanf("%d\t%lf\t%lf", &jcb[i].id, &jcb[i].submittime, &jcb[i].runtime);
    }
    InsertSort(num);
    FCFS(num);
    showinfo(num);
    return 0;
}