Java实现sjf算法需要用到链表表示下一个进程
时间: 2024-04-06 22:28:45 浏览: 13
不一定。SJF算法(Shortest Job First,最短作业优先)是一种调度算法,其主要思想是选取当前可运行的进程中预计运行时间最短的进程先被调度执行。在Java中实现SJF算法,可以使用链表、数组、优先队列等数据结构来存储进程信息和计算预计运行时间,具体实现方式取决于具体的实现需求和场景。如果需要动态地添加、删除进程,链表可能是一个比较方便的选择;如果进程数较少且静态,数组可能更加高效;如果需要自动按照进程预计运行时间进行排序,优先队列则是一个不错的选择。
相关问题
Java实现SJF算法,非抢占式的,并用链表表示
好的,以下是Java实现SJF算法,非抢占式的,并用链表表示的代码示例:
```java
import java.util.LinkedList;
public class SJF {
// 进程类
static class Process {
String name; // 进程名
int arriveTime; // 到达时间
int executeTime; // 执行时间
int waitTime; // 等待时间
public Process(String name, int arriveTime, int executeTime) {
this.name = name;
this.arriveTime = arriveTime;
this.executeTime = executeTime;
this.waitTime = 0;
}
}
// SJF算法实现
public static void sjf(LinkedList<Process> processList) {
int currentTime = 0; // 当前时间
int totalWaitTime = 0; // 总等待时间
while (!processList.isEmpty()) {
Process shortestProcess = null;
int shortestTime = Integer.MAX_VALUE;
// 遍历当前已到达的进程,找到最短执行时间的进程
for (Process process : processList) {
if (process.arriveTime <= currentTime && process.executeTime < shortestTime) {
shortestProcess = process;
shortestTime = process.executeTime;
}
}
// 如果已经找到最短执行时间的进程,则执行该进程
if (shortestProcess != null) {
processList.remove(shortestProcess); // 从链表中移除该进程
shortestProcess.waitTime = currentTime - shortestProcess.arriveTime; // 计算等待时间
totalWaitTime += shortestProcess.waitTime; // 累加总等待时间
currentTime += shortestProcess.executeTime; // 更新当前时间
} else {
currentTime++; // 如果当前没有进程可执行,则时间加1
}
}
// 打印每个进程的等待时间和平均等待时间
for (Process process : processList) {
System.out.println(process.name + " 等待时间:" + process.waitTime);
}
System.out.println("平均等待时间:" + (float) totalWaitTime / processList.size());
}
// 测试
public static void main(String[] args) {
LinkedList<Process> processList = new LinkedList<>();
processList.add(new Process("P1", 0, 5));
processList.add(new Process("P2", 2, 3));
processList.add(new Process("P3", 4, 1));
processList.add(new Process("P4", 5, 2));
sjf(processList);
}
}
```
在上述代码中,我们定义了一个“进程”类,包含进程名、到达时间、执行时间和等待时间等属性。然后,在`sjf()`方法中,我们使用while循环遍历当前已到达的进程,找到最短执行时间的进程,并执行该进程,直到所有进程都执行完为止。在执行每个进程时,我们从链表中移除该进程,并计算出该进程的等待时间。最后,我们打印每个进程的等待时间和平均等待时间。
在`main()`方法中,我们创建了一个包含4个进程的链表,并调用`sjf()`方法进行SJF算法的演示。
需要注意的是,这里的实现是非抢占式的,即一旦进程开始执行,就一直执行到完成。如果需要实现抢占式的SJF算法,可以在执行每个进程时增加判断,如果有新的进程到达并且其执行时间比当前进程短,则抢占当前进程。
写一个Java程式实现FCFS算法、SJF算法|
以下是Java实现FCFS算法和SJF算法的代码:
FCFS算法:
```java
import java.util.Scanner;
public class FCFS {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("输入进程数:");
int n = scanner.nextInt();
int[] arrivalTime = new int[n]; // 到达时间
int[] burstTime = new int[n]; // 服务时间
int[] finishTime = new int[n]; // 完成时间
int[] waitingTime = new int[n]; // 等待时间
int[] turnaroundTime = new int[n]; // 周转时间
System.out.println("输入每个进程的到达时间和服务时间:");
for (int i = 0; i < n; i++) {
System.out.print("进程 " + (i + 1) + " 到达时间:");
arrivalTime[i] = scanner.nextInt();
System.out.print("进程 " + (i + 1) + " 服务时间:");
burstTime[i] = scanner.nextInt();
}
// 计算完成时间、等待时间和周转时间
finishTime[0] = arrivalTime[0] + burstTime[0];
turnaroundTime[0] = finishTime[0] - arrivalTime[0];
waitingTime[0] = 0;
for (int i = 1; i < n; i++) {
finishTime[i] = finishTime[i - 1] + burstTime[i];
turnaroundTime[i] = finishTime[i] - arrivalTime[i];
waitingTime[i] = turnaroundTime[i] - burstTime[i];
}
// 计算平均等待时间和平均周转时间
int totalWaitingTime = 0;
int totalTurnaroundTime = 0;
for (int i = 0; i < n; i++) {
totalWaitingTime += waitingTime[i];
totalTurnaroundTime += turnaroundTime[i];
}
double averageWaitingTime = (double) totalWaitingTime / n;
double averageTurnaroundTime = (double) totalTurnaroundTime / n;
// 输出结果
System.out.println("进程\t到达时间\t服务时间\t完成时间\t等待时间\t周转时间");
for (int i = 0; i < n; i++) {
System.out.println((i + 1) + "\t" + arrivalTime[i] + "\t\t" + burstTime[i] + "\t\t" + finishTime[i] + "\t\t" + waitingTime[i] + "\t\t" + turnaroundTime[i]);
}
System.out.println("平均等待时间:" + averageWaitingTime);
System.out.println("平均周转时间:" + averageTurnaroundTime);
}
}
```
SJF算法:
```java
import java.util.Scanner;
public class SJF {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("输入进程数:");
int n = scanner.nextInt();
int[] arrivalTime = new int[n]; // 到达时间
int[] burstTime = new int[n]; // 服务时间
int[] finishTime = new int[n]; // 完成时间
int[] waitingTime = new int[n]; // 等待时间
int[] turnaroundTime = new int[n]; // 周转时间
boolean[] isFinished = new boolean[n]; // 进程是否完成
System.out.println("输入每个进程的到达时间和服务时间:");
for (int i = 0; i < n; i++) {
System.out.print("进程 " + (i + 1) + " 到达时间:");
arrivalTime[i] = scanner.nextInt();
System.out.print("进程 " + (i + 1) + " 服务时间:");
burstTime[i] = scanner.nextInt();
}
// 计算完成时间、等待时间和周转时间
int currentTime = 0;
int finishedCount = 0;
while (finishedCount < n) {
int shortestIndex = -1;
int shortestBurstTime = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (!isFinished[i] && arrivalTime[i] <= currentTime && burstTime[i] < shortestBurstTime) {
shortestIndex = i;
shortestBurstTime = burstTime[i];
}
}
if (shortestIndex != -1) {
finishTime[shortestIndex] = currentTime + burstTime[shortestIndex];
turnaroundTime[shortestIndex] = finishTime[shortestIndex] - arrivalTime[shortestIndex];
waitingTime[shortestIndex] = turnaroundTime[shortestIndex] - burstTime[shortestIndex];
isFinished[shortestIndex] = true;
currentTime = finishTime[shortestIndex];
finishedCount++;
} else {
currentTime++;
}
}
// 计算平均等待时间和平均周转时间
int totalWaitingTime = 0;
int totalTurnaroundTime = 0;
for (int i = 0; i < n; i++) {
totalWaitingTime += waitingTime[i];
totalTurnaroundTime += turnaroundTime[i];
}
double averageWaitingTime = (double) totalWaitingTime / n;
double averageTurnaroundTime = (double) totalTurnaroundTime / n;
// 输出结果
System.out.println("进程\t到达时间\t服务时间\t完成时间\t等待时间\t周转时间");
for (int i = 0; i < n; i++) {
System.out.println((i + 1) + "\t" + arrivalTime[i] + "\t\t" + burstTime[i] + "\t\t" + finishTime[i] + "\t\t" + waitingTime[i] + "\t\t" + turnaroundTime[i]);
}
System.out.println("平均等待时间:" + averageWaitingTime);
System.out.println("平均周转时间:" + averageTurnaroundTime);
}
}
```