Java实现非抢占式短作业优先调度算法详解
本文介绍如何使用Java语言模拟操作系统中的短作业优先（SJF）进程调度算法。通过分析到达时间和服务时间，核心逻辑在于每次从就绪队列中选择服务时间最短的进程执行。文章提供完整代码示例，展示如何计算周转时间和带权周转时间等关键性能指标。
短作业优先调度算法原理
短作业优先（Shortest Job First, SJF）是一种常用的CPU调度算法，其核心思想是优先调度估计运行时间（服务时间）最短的作业。这种算法旨在减少平均等待时间，提高系统吞吐量。在实现中通常分为两种：非抢占式和抢占式（最短剩余时间优先 SRTF）。以下示例主要模拟非抢占式的场景，即一旦进程开始执行，直到结束才释放CPU。
准备条件与数据结构
为了模拟这一过程，我们需要定义进程的基本属性，包括：
- arrivetime：进程到达系统的时间。
- starttime：进程开始执行的时间。
- finishtime：进程完成执行的时间。
- 服务时间（Service Time）：进程执行所需的时间长度。
调度算法需要维护两个数组或列表：
1. 原始服务时间数组，用于保持进程的初始顺序或特定关联。
2. 排序后的服务时间数组，用于快速定位当前可选的最短作业。
实现步骤
第1步：定义进程类与初始化数据
首先创建一个简单的类来封装进程信息或直接使用静态变量。为了方便演示，我们手动定义三个虚拟进程的到达时间和服务时间。
假设我们有三个进程，它们的到达时间分别为 0, 3, 3，服务时间分别为 1, 3, 2（注意：实际SJF中，如果同时到达多个进程，通常按到达先后或ID顺序处理，或者再次比较服务时间）。在下面的代码逻辑中，我们将简化输入数据以匹配特定的测试用例。
package com;
import java.util.Arrays;
public class sjf {
int starttime;
int arrivetime;
int finishtime;
int zhouzhuan; // 周转时间
float weightzhouzhuan; // 带权周转时间
public static void main(String[] args) {
sjf SJF = new sjf();
SJF.fun1();
}
// ... 后续方法见下文
}第2步：处理第一个到达的进程
在非抢占式SJF中，CPU必须从第一个到达的进程开始执行，因为没有更早的进程可供调度。通常这个进程的到达时间为0或最小值。
- 获取当前时间作为起始时间。
- 更新完成时间：finishTime = arrivalTime + serviceTime。 - 计算周转时间：周转时间 = 完成时间 - 到达时间。
- 计算带权周转时间：带权周转时间 = 周转时间 / 服务时间。 - 输出该进程的调度结果。
在代码中，我们初始化第一个进程的服务时间为最小值（例如1），并设定其到达时间为0。此时：
finishtime = a[0] （假设a[0]为服务时间且到达时间为0，此处代码逻辑需结合具体输入调整，示例中输入数据较为简略）。
第3步：循环处理后续进程
对于剩余的进程，我们需要根据当前的finishtime来判断接下来该调度哪个进程。
- 查找就绪队列：找出所有已到达（
arrivetime <= currentFinishtime）且未执行的进程。 - 选择最短进程：在这些就绪进程中，选择服务时间最短的一个。
- 边界情况处理：如果当前没有进程到达（即
currentFinishtime < nextArrivalTime），则CPU空闲，直到下一个进程到达。此时，直接将当前时间设为下一个进程的到达时间，并开始执行该进程。
以下是完整的代码实现，包含详细的注释和计算逻辑：
package com;
import java.util.Arrays;
public class sjf {
int starttime;
int arrivetime;
int finishtime;
int zhouzhuan;
float weightzhouzhuan;
public void fun1() {
// 模拟输入数据：服务时间数组
int[] serviceTimes = {1, 3, 2};
// 备份一份用于排序比较
int[] sortedServices = new int[serviceTimes.length];
for (int i = 0; i < serviceTimes.length; i++) {
sortedServices[i] = serviceTimes[i];
}
// 对服务时间进行升序排序，以便快速找到最短者
Arrays.sort(sortedServices);
// 模拟到达时间数组
int[] arriveTimes = {0, 3, 3};
// 标记哪些进程已经执行过，避免重复调度（本示例通过索引控制流程简化处理，实际复杂情况需更完善的对象管理）
boolean[] executed = new boolean[arriveTimes.length];
int currentTime = 0; // 当前系统时间
int remainingProcesses = 3; // 剩余待调度进程数
System.out.println("\t开始时间\t到达时间\t完成时间\t周转时间\t服务时间\t带权周转时间");
while (remainingProcesses > 0) {
int shortestIndex = -1;
int minServiceTime = Integer.MAX_VALUE;
// 1. 找出所有已到达且未执行的进程中，服务时间最短的
for (int i = 0; i < arriveTimes.length; i++) {
if (!executed[i] && arriveTimes[i] <= currentTime) {
if (serviceTimes[i] < minServiceTime) {
minServiceTime = serviceTimes[i];
shortestIndex = i;
}
}
}
if (shortestIndex == -1) {
// 如果没有已到达的进程，寻找下一个最早到达的进程
int nextArrival = Integer.MAX_VALUE;
for (int i = 0; i < arriveTimes.length; i++) {
if (!executed[i] && arriveTimes[i] < nextArrival) {
nextArrival = arriveTimes[i];
}
}
// CPU空闲，跳到下一个进程到达时刻
currentTime = nextArrival;
continue;
}
// 2. 执行选中的进程
arrivedtime = arriveTimes[shortestIndex];
starttime = currentTime;
finishtime = currentTime + serviceTimes[shortestIndex];
zhouzhuan = finishtime - arrivedtime;
weightzhouzhuan = (float) zhouzhuan / serviceTimes[shortestIndex];
// 输出结果
System.out.print((shortestIndex + 1) + "号进程: ");
System.out.println(starttime + "\t" + arrivedtime + "\t" + finishtime + "\t" + zhouzhuan + "\t" + serviceTimes[shortestIndex] + "\t" + weightzhouzhuan);
// 更新状态
executed[shortestIndex] = true;
currentTime = finishtime;
remainingProcesses--;
}
}
}
关键计算逻辑说明
在上面的通用实现中，我们修正了原草稿中可能存在的逻辑缺陷（如直接使用硬编码索引而非动态查找最短者）。以下是核心公式的解释：
- 周转时间（Turnaround Time）：进程从提交到完成所用的总时间。
周转时间 = 完成时间 - 到达时间 - 带权周转时间（Weighted Turnaround Time）：周转时间与服务时间的比值，越小越好。
带权周转时间 = 周转时间 / 服务时间
总结
通过上述Java代码，我们实现了基于短作业优先策略的进程调度模拟。该算法能够有效降低系统的平均等待时间，特别适合批处理系统。在实际操作系统内核中，还会涉及上下文切换开销、I/O操作阻塞等更复杂的因素，但基本的调度优先级逻辑与此示例一致。以上就是Java实现短作业优先（SJF）进程调度算法的详细内容，更多关于操作系统进程调度的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
