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調度算法可以保證任務順利完成。