FCFS,SJF以及PSA进程调度算法的比较
实现
下面是用 Java 程序比较 FCFS，SJF 和 PSA 算法效率的示例代码：
FCFS
思路
对于 FCFS 算法，我们可以定义一个 Process 类来表示一个进程，其中包含进程名称、到达时间和执行时间三个属性。然后我们可以定义一个 FCFS 类，其中包含一个 ArrayList 来存储所有的进程，并实现调度算法的逻辑。
源码
`
public class FCFS {
private ArrayList<Process> processList;
public FCFS(ArrayList<Process> processList) {
this.processList = processList;
}
public void schedule() {
// 按照进程的到达时间升序排序
Collections.sort(processList, (p1, p2) -> p1.arrivalTime - p2.arrivalTime);
int currentTime = 0;
int waitingTime = 0;
int turnaroundTime = 0;
for (Process p : processList) {
if (currentTime < p.arrivalTime) {
currentTime = p.arrivalTime;
}
waitingTime += currentTime - p.arrivalTime;
turnaroundTime += currentTime - p.arrivalTime + p.executionTime;
currentTime += p.executionTime;
}
double averageWaitingTime = (double) waitingTime / processList.size();
double averageTurnaroundTime = (double) turnaroundTime / processList.size();
System.out.println("平均等待时间：" + averageWaitingTime);
System.out.println("平均周转时间：" + averageTurnaroundTime);
}
}
复制代码
`
解释
在 FCFS 算法的示例代码中，我们定义了一个 Process 类来表示一个进程，包含进程名称、到达时间和执行时间三个属性。然后我们定义了一个 FCFS 类，其中包含一个 ArrayList 来存储所有的进程，并实现调度算法的逻辑。
调度算法的逻辑如下：
-
首先，将进程列表按照到达时间升序排序。
-
然后，遍历每一个进程
-
如果当前时刻小于进程的到达时间，则将当前时刻更新为进程的到达时间。
-
然后，计算等待时间和周转时间：
- 等待时间 = 当前时刻 - 进程的到达时间
- 周转时间 = 当前时刻 - 进程的到达时间 + 进程的执行时间
-
最后，将当前时刻更新为当前时刻 + 进程的执行时间。
在遍历完所有的进程之后，我们可以计算平均等待时间和平均周转时间，以此来评估 FCFS 算法的性能。
最后，调用 FCFS 类的 schedule 方法来执行调度算法即可。
SJF
思路
对于 FCFS 算法，我们可以定义一个 Process 类来表示一个进程，其中包含进程名称、到达时间和执行时间三个属性。然后我们可以定义一个 FCFS 类，其中包含一个 ArrayList 来存储所有的进程，并实现调度算法的逻辑。
源码
`
public class SJF {
private ArrayList<Process> processList;
public SJF(ArrayList<Process> processList) {
this.processList = processList;
}
public void schedule() {
int currentTime = 0;
int waitingTime = 0;
int turnaroundTime = 0;
while (!processList.isEmpty()) {
// 找到当前时刻最先到达的，执行时间最短的进程
Process p = processList.stream()
.filter(process -> process.arrivalTime <= currentTime)
.min((p1, p2) -> p1.executionTime - p2.executionTime)
.get();
waitingTime += currentTime - p.arrivalTime;
turnaroundTime += currentTime - p.arrivalTime + p.executionTime;
currentTime += p.executionTime;
processList.remove(p);
}
double averageWaitingTime = (double) waitingTime / processList.size();
double averageTurnaroundTime = (double) turnaroundTime / processList.size();
System.out.println("平均等待时间：" + averageWaitingTime);
System.out.println("平均周转时间：" + averageTurnaroundTime);
}
}
复制代码
`
解释
在 SJF 算法的示例代码中，我们定义了一个 Process 类来表示一个进程，包含进程名称、到达时间和执行时间三个属性。然后我们定义了一个 SJF 类，其中包含一个 ArrayList 来存储所有的进程，并实现调度算法的逻辑。
调度算法的逻辑如下：
-
使用 stream API 的 filter 和 min 方法来找到当前时刻最先到达的，执行时间最短的进程。
-
然后，计算等待时间和周转时间：
- 等待时间 = 当前时刻 - 进程的到达时间
- 周转时间 = 当前时刻 - 进程的到达时间 + 进程的执行时间
-
最后，将当前时刻更新为当前时刻 + 进程的执行时间。
在遍历完所有的进程之后，我们可以计算平均等待时间和平均周转时间，以此来评估 SJF 算法的性能。
最后，调用 SJF 类的 schedule 方法来执行调度算法即可。
PSA
思路
对于 PSA 算法，我们需要在 Process 类中增加一个优先级的属性，并在调度算法的逻辑上进行相应的修改。
如果进程在等待 CPU 时间的时间越长，就将它的优先级设为越高。这样，当进程获得 CPU 时间的机会时，就能够优先执行。这种算法能够有效地应对突发性的高优先级作业。
- 首先，为每个进程设定一个初始优先级。
- 然后，每当进程等待 CPU 时间超过一定的阈值，就将进程的优先级提高。
- 当进程获得 CPU 时间时，按照优先级的高低进行调度。
需要注意的是，当进程执行完成后，需要将进程的优先级恢复为初始值。
源码
`
public class PSA {
private ArrayList<Process> processList;
public PSA(ArrayList<Process> processList) {
this.processList = processList;
}
public void schedule() {
int currentTime = 0;
int waitingTime = 0;
int turnaroundTime = 0;
while (!processList.isEmpty()) {
// 找到当前时刻最先到达的，优先级最高的进程
Process p = processList.stream()
.filter(process -> process.arrivalTime <= currentTime)
.max((p1, p2) -> p1.priority - p2.priority)
.get();
waitingTime += currentTime - p.arrivalTime;
turnaroundTime += currentTime - p.arrivalTime + p.executionTime;
currentTime += p.executionTime;
processList.remove(p);
}
double averageWaitingTime = (double) waitingTime / processList.size();
double averageTurnaroundTime = (double) turnaroundTime / processList.size();
System.out.println("平均等待时间：" + averageWaitingTime);
System.out.println("平均周转时间：" + averageTurnaroundTime);
}
}
复制代码
`
解释
首先，在示例代码中，我们定义了一个 Process 类来表示一个进程，包含进程名称、到达时间、执行时间和剩余执行时间四个属性。然后我们定义了一个 PSA 类，其中包含一个 ArrayList 来存储所有的进程，并实现调度算法的逻辑。
调度算法的逻辑如下：
-
首先，将进程列表按照到达时间升序排序。
-
然后，循环执行以下步骤，直到进程列表为空：
- 从进程列表中取出第一个进程，并将其从列表中移除。
- 如果当前时刻小于进程的到达时间，则将当前时刻更新为进程的到达时间。
- 如果进程的剩余执行时间大于时间片，则执行时间片的长度；否则，执行进程剩余的所有时间。
-
计算等待时间和周转时间：
- 等待时间 = 当前时刻 - 进程的到达时间
- 周转时间 = 当前时刻 - 进程的到达时间 + 进程的执行时间
-
如果进程的剩余执行时间为 0，则将进程从进程列表中移除；否则，将进程插入进程列表的末尾。
-
将当前时刻更新为当前时刻 + 执行的时间。
在遍历完所有的进程之后，我们可以计算平均等待时间和平均周转时间，以此来评估 PSA 算法的性能。
最后，调用 PSA 类的 schedule 方法来执行调度算法即可。
三种方法效率比较
都以相同的开始时间、进行时间、以及优先级进行比较
arr[0]={0,20,2};
arr[1]={5,15,1};
arr[2]={10,5,4};
arr[3]={15,10,3};
优先级是为了比较PSA的两种抢占效率（抢占式、非抢占式）.
FCFS
image.png
SJF
image.png
PSA
抢占式
image.png
非抢占式
image.png
片上传失败...(image-53f1d1-1671588281610)]
总结：
FCFS
算法是一种简单的调度算法，它按照进程的到达时间顺序依次执行进程，不考虑进程的执行时间。由于不能有效地应对短作业，因此 FCFS 算法的效率并不高。
SJF 算法是一种较高效的调度算法，它优先执行执行时间较短的进程，能够有效地应对短作业。但是，SJF 算法不能有效地应对突发性的高优先级作业。
PSA 算法是一种动态调度算法，它根据进程的等待时间动态调整进程的优先级，能够有效地应对突发性的高优先级作业。但是，PSA 算法的实现较为复杂，因此其运行效率略低于 SJF 算法。
总的来说，SJF 算法的效率略高于 PSA 算法，而 FCFS 算法的效率较低。不同的调度算法适用于不同的场景，应根据实际需要选择合适的调度算法。
