在Java中用各种方法去实现SJF算法
时间: 2024-03-18 08:42:23 浏览: 9
下面是在Java中用多种方法实现SJF算法的示例代码:
方法一:使用数组实现
```java
public class SJF {
public static void main(String[] args) {
// 进程列表
String[] processNames = {"P1", "P2", "P3", "P4", "P5"};
int[] runTimes = {3, 2, 1, 4, 2};
int[] arriveTimes = {0, 1, 2, 3, 4};
int n = processNames.length; // 进程数量
int[] status = new int[n]; // 进程状态,0表示未到达,1表示已到达,2表示已完成
int[] remainTimes = new int[n]; // 剩余运行时间
// 初始化
for (int i = 0; i < n; i++) {
status[i] = 0;
remainTimes[i] = runTimes[i];
}
int currTime = 0; // 当前时间
int finishedCount = 0; // 已完成进程数量
// 运行进程
while (finishedCount < n) {
int shortestJob = -1; // 最短作业的进程编号
int shortestTime = Integer.MAX_VALUE; // 最短作业的运行时间
for (int i = 0; i < n; i++) {
if (status[i] == 1 && remainTimes[i] < shortestTime) {
shortestJob = i;
shortestTime = remainTimes[i];
}
}
if (shortestJob == -1) {
currTime++;
continue;
}
System.out.println("Time " + currTime + ": " + processNames[shortestJob] + " is running");
remainTimes[shortestJob]--;
currTime++;
if (remainTimes[shortestJob] == 0) {
System.out.println("Time " + currTime + ": " + processNames[shortestJob] + " is finished");
status[shortestJob] = 2;
finishedCount++;
} else if (arriveTimes[shortestJob+1] <= currTime) {
status[shortestJob+1] = 1;
}
}
}
}
```
方法二:使用链表实现
```java
public class SJF {
static class Process {
String name;
int runTime;
int arriveTime;
Process(String name, int runTime, int arriveTime) {
this.name = name;
this.runTime = runTime;
this.arriveTime = arriveTime;
}
}
static class Node {
Process process;
Node next;
Node(Process process) {
this.process = process;
this.next = null;
}
}
static class LinkedList {
Node head;
LinkedList() {
this.head = null;
}
// 插入节点
void insert(Process process) {
Node newNode = new Node(process);
if (head == null) {
head = newNode;
return;
}
if (process.runTime < head.process.runTime) {
newNode.next = head;
head = newNode;
return;
}
Node curr = head;
while (curr.next != null && curr.next.process.runTime < process.runTime) {
curr = curr.next;
}
newNode.next = curr.next;
curr.next = newNode;
}
// 删除节点
void delete(Node node) {
if (node == head) {
head = head.next;
return;
}
Node curr = head;
while (curr.next != node) {
curr = curr.next;
}
curr.next = node.next;
}
}
public static void main(String[] args) {
// 进程列表
Process[] processes = {
new Process("P1", 3, 0),
new Process("P2", 2, 1),
new Process("P3", 1, 2),
new Process("P4", 4, 3),
new Process("P5", 2, 4)
};
LinkedList processList = new LinkedList();
// 初始化
for (Process process : processes) {
processList.insert(process);
}
int currTime = 0; // 当前时间
int finishedCount = 0; // 已完成进程数量
Node currNode = processList.head; // 当前进程节点
// 运行进程
while (finishedCount < processes.length) {
if (currNode == null) {
currTime++;
continue;
}
System.out.println("Time " + currTime + ": " + currNode.process.name + " is running");
currNode.process.runTime--;
currTime++;
if (currNode.process.runTime == 0) {
System.out.println("Time " + currTime + ": " + currNode.process.name + " is finished");
processList.delete(currNode);
finishedCount++;
} else if (currNode.next != null && currNode.next.process.arriveTime <= currTime) {
Node nextNode = currNode.next;
processList.delete(nextNode);
processList.insert(nextNode.process);
}
currNode = processList.head;
}
}
}
```
方法三:使用优先队列实现
```java
import java.util.PriorityQueue;
public class SJF {
static class Process implements Comparable<Process> {
String name;
int runTime;
int arriveTime;
Process(String name, int runTime, int arriveTime) {
this.name = name;
this.runTime = runTime;
this.arriveTime = arriveTime;
}
@Override
public int compareTo(Process o) {
return Integer.compare(runTime, o.runTime);
}
}
public static void main(String[] args) {
// 进程列表
Process[] processes = {
new Process("P1", 3, 0),
new Process("P2", 2, 1),
new Process("P3", 1, 2),
new Process("P4", 4, 3),
new Process("P5", 2, 4)
};
PriorityQueue<Process> processQueue = new PriorityQueue<>();
for (Process process : processes) {
processQueue.offer(process);
}
int currTime = 0; // 当前时间
int finishedCount = 0; // 已完成进程数量
// 运行进程
while (finishedCount < processes.length) {
if (processQueue.isEmpty()) {
currTime++;
continue;
}
Process currProcess = processQueue.poll();
System.out.println("Time " + currTime + ": " + currProcess.name + " is running");
currProcess.runTime--;
currTime++;
if (currProcess.runTime == 0) {
System.out.println("Time " + currTime + ": " + currProcess.name + " is finished");
finishedCount++;
} else {
for (Process process : processes) {
if (process.arriveTime <= currTime && !processQueue.contains(process)) {
processQueue.offer(process);
}
}
processQueue.offer(currProcess);
}
}
}
}
```
以上三种方法都可以实现SJF算法,方法一使用数组,方法二使用链表,方法三使用优先队列。其中,使用优先队列实现最简单,但是需要重写进程类的 `compareTo` 方法。使用数组和链表实现需要手动实现进程的排序和插入操作,但是可以更灵活地控制进程的顺序。