先到先服務 CPU 排程 | （非搶佔式）

---

FCFS CPU 排程（先到先服務）是一種基本的 CPU 排程機制，它按照程序加入就緒佇列的順序執行程式。換句話說，第一個到達的程序將首先執行，依此類推。由於它使用非搶佔式排程技術，因此分配給 CPU 的程序將一直執行，直到它完成或進入等待狀態。

場景 1

讓我們來看一個例子，以便更詳細地瞭解 FCFS CPU 排程。假設我們有三個程序，它們具有以下到達時間和突發時間

程序	到達時間	突發時間
P1	0	5
P2	1	3
P3	2	4

FCFS 排程的甘特圖如下所示

0-----5-----8-----12
|     |     |     |
P1    P2   P3   Idle

從甘特圖中可以看出，P1 在時間 0 到達並首先獲得 CPU。它執行 5 個時間單位，並在時間 5 完成。然後 P2 在時間 1 到達，但它必須等待 P1 完成才能開始執行。P2 執行 3 個時間單位，並在時間 8 完成。最後，P3 在時間 2 到達，但它必須等待 P2 完成才能開始執行。P3 執行 4 個時間單位，並在時間 12 完成。

總的來說，FCFS 排程易於實現，並確保每個程序獲得公平的 CPU 時間份額。但是，它可能會導致突發時間較長的程序等待時間過長。此外，它不適合響應時間至關重要的即時系統。

FCFS CPU 排程是一種基本的排程演算法，它按照程序到達就緒佇列的順序執行程序。雖然它易於實現且對所有程序公平，但在所有情況下它可能都不是最有效或最合適的排程演算法。

場景 2

讓我們再看一個例子，假設我們有四個程序，它們具有以下到達時間和突發時間

程序	到達時間	突發時間
P1	0	6
P2	2	4
P3	4	2
P4	6	5

FCFS 排程的甘特圖如下所示

0-----6-----10-----12-----17
|     |     |      |      |
P1   P2     P3     P4    Idle

從甘特圖中可以看出，P1 在時間 0 到達並首先獲得 CPU。它執行 6 個時間單位，並在時間 6 完成。然後 P2 在時間 2 到達，但它必須等待 P1 完成才能開始執行。

• P2 執行 4 個時間單位，並在時間 10 完成。然後 P3 在時間 4 到達，但它必須等待 P2 完成才能開始執行。P3 執行 2 個時間單位，並在時間 12 完成。最後，P4 在時間 6 到達，但它必須等待 P3 完成才能開始執行。P4 執行 5 個時間單位，並在時間 17 完成。

• 在這個例子中，我們可以看到，突發時間最長的程序（P1）必須首先執行，導致其他程序的等待時間更長。這是 FCFS 排程的一個缺點，因為它可能不會優先考慮突發時間較短的程序，這會導致更長的等待時間，並可能影響系統的整體效能。

總的來說，FCFS 排程是一種簡單的排程演算法，在某些情況下可能很有用，在這些情況下，簡單性和公平性比效率更重要。但是，對於具有不同程序需求和優先順序的系統，其他排程演算法（如迴圈輪詢或最短作業優先）可能更合適。

FCFS 的虛擬碼

以下是 FCFS CPU 排程演算法的虛擬碼

queue = empty queue
clock = 0
while (processes not finished)
    if (new process arrives at clock time)
        add the process to the end of the queue
    if (CPU is idle and queue is not empty)
        remove the first process from the queue
        set the start time of the process to the current clock time
        run the process for its burst time
        set the finish time of the process to the current clock time
    increment the clock by 1

Java 實現

以下是上述虛擬碼的 Java 實現

示例

import java.util.*;
class Process {
    public int pid;
    public int arrivalTime;
    public int burstTime;
    public int startTime;
    public int finishTime;

    public Process(int pid, int arrivalTime, int burstTime) {
        this.pid = pid;
        this.arrivalTime = arrivalTime;
        this.burstTime = burstTime;
    }
}

public class FCFSScheduling {
    public static void main(String[] args) {
        // Create a list of processes
        List<Process> processes = new ArrayList<>();
        processes.add(new Process(1, 0, 6));
        processes.add(new Process(2, 2, 4));
        processes.add(new Process(3, 4, 2));
        processes.add(new Process(4, 6, 5));

        // Sort processes by arrival time
        processes.sort(Comparator.comparing(p -> p.arrivalTime));

        // Initialize variables
        int clock = 0;
        Queue<Process> queue = new LinkedList<>();
        List<Process> completedProcesses = new ArrayList<>();

        // Execute processes in FCFS order
        while (!processes.isEmpty() || !queue.isEmpty()) {
            // Add new arrivals to the queue
            while (!processes.isEmpty() && processes.get(0).arrivalTime == clock) {
                queue.add(processes.get(0));
                processes.remove(0);
            }

            // Execute the first process in the queue
            if (!queue.isEmpty()) {
                Process currentProcess = queue.remove();
                currentProcess.startTime = clock;
                clock += currentProcess.burstTime;
                currentProcess.finishTime = clock;
                completedProcesses.add(currentProcess);
            } else {
                // CPU is idle
                clock++;
            }
        }

        // Print results
        for (Process p : completedProcesses) {
            System.out.println("Process " + p.pid + ": start time = " + p.startTime
                    + ", finish time = " + p.finishTime);
        }
    }
}

輸出

Process 1: start time = 0, finish time = 6
Process 2: start time = 2, finish time = 6
Process 3: start time = 4, finish time = 6
Process 4: start time = 6, finish time = 11

在這種方法中，每個程序由一個 Process 類表示，所有程序都儲存在一個列表中。然後根據到達時間對列表進行排序。就緒佇列由一個隊列表示，任務按照 FCFS 順序執行。記錄每個程序的開始時間和結束時間，並將已完成的程序儲存在單獨的列表中。最後，我們輸出每個程序的開始時間和結束時間。

請記住，此實現僅是一個示例，可以根據系統的特定需求進行增強或修改。

結論

總之，先到先服務 (FCFS) CPU 排程是一種簡單易懂的排程技術，它按照程序出現在就緒佇列中的順序執行程序。儘管易於使用，但它可能並不總是最有效的排程演算法，因為它無法處理優先順序任務或短作業。

FCFS 適用於週轉時間不是首要考慮因素的系統，例如具有有限程序數量的單使用者系統。但是，它可能不適用於即時應用程式或必須快速響應的系統。

由於其簡單易用，FCFS 總體上是一種廣泛使用的排程演算法，儘管根據系統的特定需求和限制，它可能並不總是最佳選擇。在某些情況下，其他排程演算法（如迴圈輪詢、優先順序排程和最短作業優先）可能會表現更好。