FCFS调度算法

一、基本介绍

FCFS是操作系统中最简单的调度算法之一，也是一种非抢占式的调度算法。FCFS的全称是First-Come-First-Served，让那些先到达的进程先执行，后到达的进程就放到CPU的队尾等待执行。

相比于其他调度算法，FCFS的实现非常简单，只需要按照进程到达的先后顺序排队即可。FCFS调度算法保证了进程的公平，但是可能导致平均等待时间过长的问题。

二、算法流程

FCFS调度算法的核心思想是先来先服务。当有进程请求CPU时间时，如果此时CPU处于空闲状态，则立即将CPU分配给当前进程；如果CPU正在执行其他进程，则将请求进程添加到CPU请求队列的队尾，等待前面的进程完成后才执行。

下面是FCFS调度算法的代码演示：

struct Process {
    int pid; // 进程id
    int arriveTime; // 进程到达时间
    int burstTime; // 进程需要执行的时间
};

void FCFS(vector& processes) {
    int n = processes.size();
    int curTime = 0; // 当前时间
    int waitTime = 0; // 等待时间
    int turnaroundTime = 0; // 周转时间

    // 按照到达时间排序
    sort(processes.begin(), processes.end(), [](const Process& p1, const Process& p2) {
        return p1.arriveTime < p2.arriveTime;
    });

    for (int i = 0; i < n; i++) {
        // 等待时间
        waitTime += curTime - processes[i].arriveTime;
        // 周转时间
        turnaroundTime += curTime + processes[i].burstTime - processes[i].arriveTime;
        // 更新当前时间
        curTime += processes[i].burstTime;
    }

    // 计算平均等待时间和平均周转时间
    double avgWaitTime = (double)waitTime / n;
    double avgTurnaroundTime = (double)turnaroundTime / n;

    cout << "Average Waiting Time: " << avgWaitTime << endl;
    cout << "Average Turnaround Time: " << avgTurnaroundTime << endl;
}

三、优缺点

1. 优点

（1）实现简单易懂，适用于少量进程的情况；

（2）FCFS调度算法保证了进程的公平性，先来的进程一定先执行；

（3）适合长作业，CPU利用率高，无争抢问题。

2. 缺点

（1）FCFS调度算法可能会导致平均等待时间过长，特别是当长作业在队列的前面时，队首进程会长时间占用CPU时间，导致后面的短作业等待的时间过长；

（2）不适用于短进程，容易产生饥饿现象；

（3）不能处理按照优先级进行调度的任务。

四、应用场景

FCFS调度算法通常应用于没有明显的优先级或者优先级相同的情况，也适用于短进程与长进程混合的情况下，因为对于短进程来说，FCFS调度算法的效果也较好。

例如，在一些实时控制的场景中，由于任务时间不确定，先来的任务需要先执行，FCFS调度算法可以保证任务顺利完成。