Java 先到先服务 CPU 调度

先到先服务（First Come, First Serve）是一种基本的 CPU 调度机制，它按照进程加入就绪队列的顺序来执行程序。换句话说，先来的进程将首先执行，依此类推。由于它使用了非抢占式调度技术，分配给 CPU 的进程将会一直运行，直到它完成或进入等待状态。

场景 1

让我们来看一个示例，更详细地了解先到先服务 CPU 调度。假设我们有三个进程，它们的到达时间和执行时间如下：

Process	Arrival Time	Burst Time
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

让我们看另外一个例子，假设我们有四个进程，它们的到达时间和执行时间如下：

Process	Arrival Time	Burst Time
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

在这种方法中，每个进程都由一个进程类表示，并且所有进程都存储在一个列表中。然后，按到达时间对列表进行排序。就绪队列由一个队列表示，任务按FCFS顺序执行。记录每个进程的开始和结束时间，并将已完成的进程保存在一个单独的列表中。作为最后一步，我们输出每个进程的开始时间和结束时间。

请记住，这个实现只是一个示例，它可以根据系统的特定需求进行改进或修改。