Skip to content

refactor: Refactor SJFScheduling and Tests #6372

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 6 commits into from
Jul 13, 2025
Merged

refactor: Refactor SJFScheduling and Tests #6372

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
9252fe6
refactor: Refactor SJFScheduling and Tests
alxkm Jul 12, 2025
dee1d84
refactor: fix checkstyle
alxkm Jul 12, 2025
c1be739
refactor: add full imports
alxkm Jul 12, 2025
c779fa0
refactor: add full imports
alxkm Jul 12, 2025
e3afbe8
refactor: remove redundant newline
alxkm Jul 12, 2025
750ecea
refactor: fix indexed list iteration
alxkm Jul 12, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
109 changes: 43 additions & 66 deletions src/main/java/com/thealgorithms/scheduling/SJFScheduling.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,78 +2,62 @@

import com.thealgorithms.devutils.entities.ProcessDetails;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

/**
* Implementation of Shortest Job First Algorithm: The algorithm allows the waiting process with the
* minimal burst time to be executed first. see more here:
* https://www.guru99.com/shortest-job-first-sjf-scheduling.html
* Shortest Job First (SJF) Scheduling Algorithm:
* Executes processes with the shortest burst time first among the ones that have arrived.
*/

public class SJFScheduling {
protected ArrayList<ProcessDetails> processes;
protected ArrayList<String> schedule;

private static void sortProcessesByArrivalTime(List<ProcessDetails> processes) {
for (int i = 0; i < processes.size(); i++) {
for (int j = i + 1; j < processes.size() - 1; j++) {
if (processes.get(j).getArrivalTime() > processes.get(j + 1).getArrivalTime()) {
final var temp = processes.get(j);
processes.set(j, processes.get(j + 1));
processes.set(j + 1, temp);
}
}
}
}
private final List<ProcessDetails> processes;
private final List<String> schedule;

/**
* a simple constructor
* @param processes a list of processes the user wants to schedule
* it also sorts the processes based on the time of their arrival
*/
SJFScheduling(final ArrayList<ProcessDetails> processes) {
this.processes = processes;
schedule = new ArrayList<>();
public SJFScheduling(final List<ProcessDetails> processes) {
this.processes = new ArrayList<>(processes);
this.schedule = new ArrayList<>();
sortProcessesByArrivalTime(this.processes);
}
protected void sortByArrivalTime() {
sortProcessesByArrivalTime(processes);

private static void sortProcessesByArrivalTime(List<ProcessDetails> processes) {
processes.sort(Comparator.comparingInt(ProcessDetails::getArrivalTime));
}

/**
* this functions returns the order of the executions
* Executes the SJF scheduling algorithm and builds the execution order.
*/

public void scheduleProcesses() {
ArrayList<ProcessDetails> ready = new ArrayList<>();

List<ProcessDetails> ready = new ArrayList<>();
int size = processes.size();
int runtime;
int time = 0;
int executed = 0;
int j;
int k = 0;
ProcessDetails running;

if (size == 0) {
return;
Iterator<ProcessDetails> processIterator = processes.iterator();

// This will track the next process to be checked for arrival time
ProcessDetails nextProcess = null;
if (processIterator.hasNext()) {
nextProcess = processIterator.next();
}

while (executed < size) {
while (k < size && processes.get(k).getArrivalTime() <= time) // here we find the processes that have arrived.
{
ready.add(processes.get(k));
k++;
// Load all processes that have arrived by current time
while (nextProcess != null && nextProcess.getArrivalTime() <= time) {
ready.add(nextProcess);
if (processIterator.hasNext()) {
nextProcess = processIterator.next();
} else {
nextProcess = null;
}
}

running = findShortestJob(ready);
ProcessDetails running = findShortestJob(ready);
if (running == null) {
time++;
} else {
runtime = running.getBurstTime();
for (j = 0; j < runtime; j++) {
time++;
}
time += running.getBurstTime();
schedule.add(running.getProcessId());
ready.remove(running);
executed++;
Expand All @@ -82,30 +66,23 @@ public void scheduleProcesses() {
}

/**
* this function evaluates the shortest job of all the ready processes (based on a process
* burst time)
* Finds the process with the shortest job of all the ready processes (based on a process
* @param readyProcesses an array list of ready processes
* @return returns the process' with the shortest burst time OR NULL if there are no ready
* processes
*/
private ProcessDetails findShortestJob(List<ProcessDetails> readyProcesses) {
if (readyProcesses.isEmpty()) {
return null;
}
int i;
int size = readyProcesses.size();
int minBurstTime = readyProcesses.get(0).getBurstTime();
int temp;
int positionOfShortestJob = 0;
private ProcessDetails findShortestJob(Collection<ProcessDetails> readyProcesses) {
return readyProcesses.stream().min(Comparator.comparingInt(ProcessDetails::getBurstTime)).orElse(null);
}

for (i = 1; i < size; i++) {
temp = readyProcesses.get(i).getBurstTime();
if (minBurstTime > temp) {
minBurstTime = temp;
positionOfShortestJob = i;
}
}
/**
* Returns the computed schedule after calling scheduleProcesses().
*/
public List<String> getSchedule() {
return schedule;
}

return readyProcesses.get(positionOfShortestJob);
public List<ProcessDetails> getProcesses() {
return List.copyOf(processes);
}
}
117 changes: 28 additions & 89 deletions src/test/java/com/thealgorithms/scheduling/SJFSchedulingTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,107 +4,46 @@
import static org.junit.jupiter.api.Assertions.assertTrue;

import com.thealgorithms.devutils.entities.ProcessDetails;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Stream;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

class SJFSchedulingTest {
private ArrayList<ProcessDetails> process;
void initialisation0() {

process = new ArrayList<>();
process.add(new ProcessDetails("1", 0, 6));
process.add(new ProcessDetails("2", 1, 2));
private static Stream<Arguments> schedulingTestData() {
return Stream.of(Arguments.of(List.of(new ProcessDetails("1", 0, 6), new ProcessDetails("2", 1, 2)), List.of("1", "2")),
Arguments.of(List.of(new ProcessDetails("1", 0, 6), new ProcessDetails("2", 1, 2), new ProcessDetails("3", 4, 3), new ProcessDetails("4", 3, 1), new ProcessDetails("5", 6, 4), new ProcessDetails("6", 5, 5)), List.of("1", "4", "2", "3", "5", "6")),
Arguments.of(List.of(new ProcessDetails("1", 0, 3), new ProcessDetails("2", 1, 2), new ProcessDetails("3", 2, 1)), List.of("1", "3", "2")), Arguments.of(List.of(new ProcessDetails("1", 0, 3), new ProcessDetails("2", 5, 2), new ProcessDetails("3", 9, 1)), List.of("1", "2", "3")),
Arguments.of(Collections.emptyList(), List.of()));
}
void initialisation1() {

process = new ArrayList<>();
process.add(new ProcessDetails("1", 0, 6));
process.add(new ProcessDetails("2", 1, 2));
process.add(new ProcessDetails("3", 4, 3));
process.add(new ProcessDetails("4", 3, 1));
process.add(new ProcessDetails("5", 6, 4));
process.add(new ProcessDetails("6", 5, 5));
}

void initialisation2() {

process = new ArrayList<>();
process.add(new ProcessDetails("1", 0, 3));
process.add(new ProcessDetails("2", 1, 2));
process.add(new ProcessDetails("3", 2, 1));
}
void initialisation3() {
process = new ArrayList<>();
process.add(new ProcessDetails("1", 0, 3));
process.add(new ProcessDetails("2", 5, 2));
process.add(new ProcessDetails("3", 9, 1));
}
@Test
void constructor() {
initialisation0();
SJFScheduling a = new SJFScheduling(process);
assertEquals(6, a.processes.get(0).getBurstTime());
assertEquals(2, a.processes.get(1).getBurstTime());
@ParameterizedTest(name = "Test SJF schedule: {index}")
@MethodSource("schedulingTestData")
void testSJFScheduling(List<ProcessDetails> inputProcesses, List<String> expectedSchedule) {
SJFScheduling scheduler = new SJFScheduling(inputProcesses);
scheduler.scheduleProcesses();
assertEquals(expectedSchedule, scheduler.getSchedule());
}

@Test
void sort() {
initialisation1();
SJFScheduling a = new SJFScheduling(process);
a.sortByArrivalTime();
assertEquals("1", a.processes.get(0).getProcessId());
assertEquals("2", a.processes.get(1).getProcessId());
assertEquals("3", a.processes.get(3).getProcessId());
assertEquals("4", a.processes.get(2).getProcessId());
assertEquals("5", a.processes.get(5).getProcessId());
assertEquals("6", a.processes.get(4).getProcessId());
}
@DisplayName("Test sorting by arrival order")
void testProcessArrivalOrderIsSorted() {
List<ProcessDetails> processes = List.of(new ProcessDetails("1", 0, 6), new ProcessDetails("2", 1, 2), new ProcessDetails("4", 3, 1), new ProcessDetails("3", 4, 3), new ProcessDetails("6", 5, 5), new ProcessDetails("5", 6, 4));
SJFScheduling scheduler = new SJFScheduling(processes);
List<String> actualOrder = scheduler.getProcesses().stream().map(ProcessDetails::getProcessId).toList();

@Test
void scheduling() {
initialisation1();
SJFScheduling a = new SJFScheduling(process);
a.scheduleProcesses();
assertEquals("1", a.schedule.get(0));
assertEquals("4", a.schedule.get(1));
assertEquals("2", a.schedule.get(2));
assertEquals("3", a.schedule.get(3));
assertEquals("5", a.schedule.get(4));
assertEquals("6", a.schedule.get(5));
assertEquals(List.of("1", "2", "4", "3", "6", "5"), actualOrder);
}

@Test
void schedulingOfTwoProcesses() {
initialisation0();
SJFScheduling a = new SJFScheduling(process);
a.scheduleProcesses();
assertEquals("1", a.schedule.get(0));
assertEquals("2", a.schedule.get(1));
}

@Test
void schedulingOfAShortestJobArrivingLast() {
initialisation2();
SJFScheduling a = new SJFScheduling(process);
a.scheduleProcesses();
assertEquals("1", a.schedule.get(0));
assertEquals("3", a.schedule.get(1));
assertEquals("2", a.schedule.get(2));
}
@Test
void schedulingWithProcessesNotComingBackToBack() {
initialisation3();
SJFScheduling a = new SJFScheduling(process);
a.scheduleProcesses();
assertEquals("1", a.schedule.get(0));
assertEquals("2", a.schedule.get(1));
assertEquals("3", a.schedule.get(2));
}
@Test
void schedulingOfNothing() {
process = new ArrayList<>();
SJFScheduling a = new SJFScheduling(process);
a.scheduleProcesses();
assertTrue(a.schedule.isEmpty());
void testSchedulingEmptyList() {
SJFScheduling scheduler = new SJFScheduling(Collections.emptyList());
scheduler.scheduleProcesses();
assertTrue(scheduler.getSchedule().isEmpty());
}
}
Loading