数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究先到先服务 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 总体上是一种广泛使用的调度算法，尽管根据系统的特定需求和限制，它可能并不总是最佳选择。在某些情况下，其他调度算法（如循环轮询、优先级调度和最短作业优先）可能会表现更好。
575 次浏览
