调度算法对比实现 |
您所在的位置：网站首页 › 多核调度算法是什么 › 调度算法对比实现 |
|
提要 在计算机科学领域，进程调度是指操作系统决定执行哪个进程以及在什么时候执行进程的过程。进程调度算法是用来控制进程执行的算法，其中 FCFS（先来先服务），SJF（短作业优先）和 PSA（动态优先级调度）是常见的三种算法。 FCFS 调度算法是按照进程加入队列的顺序进行调度的算法。它的优点是实现简单，但是缺点是不能有效地满足短作业优先的要求。 SJF 调度算法是按照进程执行时间的短长进行调度的算法。它的优点是能够有效地满足短作业优先的要求，但是缺点是需要事先知道进程的执行时间，而且不能有效应对突发性的高优先级作业。 PSA 调度算法是按照进程的动态优先级进行调度的算法。它的优点是能够有效地应对突发性的高优先级作业，但是缺点是实现复杂，需要维护进程的优先级信息。 实现下面是用 Java 程序比较 FCFS，SJF 和 PSA 算法效率的示例代码： FCFS思路对于 FCFS 算法，我们可以定义一个 Process 类来表示一个进程，其中包含进程名称、到达时间和执行时间三个属性。然后我们可以定义一个 FCFS 类，其中包含一个 ArrayList 来存储所有的进程，并实现调度算法的逻辑。 源码 public class FCFS { private ArrayList processList; public FCFS(ArrayList 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 processList; public SJF(ArrayList 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 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 processList; public PSA(ArrayList 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 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 方法来执行调度算法即可。 总结：FCFS 算法是一种简单的调度算法，它按照进程的到达时间顺序依次执行进程，不考虑进程的执行时间。由于不能有效地应对短作业，因此 FCFS 算法的效率并不高。 SJF 算法是一种较高效的调度算法，它优先执行执行时间较短的进程，能够有效地应对短作业。但是，SJF 算法不能有效地应对突发性的高优先级作业。 PSA 算法是一种动态调度算法，它根据进程的等待时间动态调整进程的优先级，能够有效地应对突发性的高优先级作业。但是，PSA 算法的实现较为复杂，因此其运行效率略低于 SJF 算法。 总的来说，SJF 算法的效率略高于 PSA 算法，而 FCFS 算法的效率较低。不同的调度算法适用于不同的场景，应根据实际需要选择合适的调度算法。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |