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