Repository: TheAlgorithms/Java
Pull request #5535 (2024-10-03 05:12:49)

Add `NonPreemptivePriorityScheduling` new algorithm with unit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5535?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `74.28571%` with `9 lines` in your changes missing coverage. Please review.
> Project coverage is 52.65%. Comparing base [(`013d122`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/013d122e7dcb302bc47aca78f451f0ed043b6a45?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`b841d57`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/b841d57ee4a4a023ddae5a2f262c3c6636639fe0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5535?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...ms/scheduling/NonPreemptivePriorityScheduling.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5535?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fscheduling%2FNonPreemptivePriorityScheduling.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9zY2hlZHVsaW5nL05vblByZWVtcHRpdmVQcmlvcml0eVNjaGVkdWxpbmcuamF2YQ==) | 74.28% | [9 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5535?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5535      +/-   ##
============================================
+ Coverage     52.60%   52.65%   +0.05%     
- Complexity     3287     3294       +7     
============================================
  Files           528      529       +1     
  Lines         15324    15359      +35     
  Branches       2913     2918       +5     
============================================
+ Hits           8061     8088      +27     
- Misses         6931     6940       +9     
+ Partials        332      331       -1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5535?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

Hardvan: I have added the `startTime` attribute to the scheduling code and modified the Junit tests to reflect the same.
Hardvan: I added another variable called `arrivalTime` to keep track of this.
Hardvan: I have added a `waitingQueue` variable to address the above change.

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 32a084d9..f1a53148 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -505,6 +505,7 @@
             * [HighestResponseRatioNextScheduling](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/HighestResponseRatioNextScheduling.java)
             * [JobSchedulingWithDeadline](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/JobSchedulingWithDeadline.java)
             * [MLFQScheduler](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/MLFQScheduler.java)
+            * [NonPreemptivePriorityScheduling](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/NonPreemptivePriorityScheduling.java)
             * [PreemptivePriorityScheduling](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/PreemptivePriorityScheduling.java)
             * [RRScheduling](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/RRScheduling.java)
             * [SJFScheduling](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/SJFScheduling.java)
@@ -1039,6 +1040,7 @@
             * [HighestResponseRatioNextSchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/HighestResponseRatioNextSchedulingTest.java)
             * [JobSchedulingWithDeadlineTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/JobSchedulingWithDeadlineTest.java)
             * [MLFQSchedulerTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/MLFQSchedulerTest.java)
+            * [NonPreemptivePrioritySchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/NonPreemptivePrioritySchedulingTest.java)
             * [PreemptivePrioritySchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/PreemptivePrioritySchedulingTest.java)
             * [RRSchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/RRSchedulingTest.java)
             * [SJFSchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/SJFSchedulingTest.java)
diff --git a/src/main/java/com/thealgorithms/scheduling/NonPreemptivePriorityScheduling.java b/src/main/java/com/thealgorithms/scheduling/NonPreemptivePriorityScheduling.java
new file mode 100644
index 00000000..1d8e2c51
--- /dev/null
+++ b/src/main/java/com/thealgorithms/scheduling/NonPreemptivePriorityScheduling.java
@@ -0,0 +1,134 @@
+package com.thealgorithms.scheduling;
+
+import java.util.LinkedList;
+import java.util.PriorityQueue;
+import java.util.Queue;
+
+/**
+ * This class implements the Non-Preemptive Priority Scheduling algorithm.
+ * Processes are executed in order of their priority. The process with the
+ * highest priority (lower priority number) is executed first,
+ * and once a process starts executing, it cannot be preempted.
+ */
+public final class NonPreemptivePriorityScheduling {
+
+    private NonPreemptivePriorityScheduling() {
+    }
+
+    /**
+     * Represents a process with an ID, burst time, priority, arrival time, and start time.
+     */
+    static class Process implements Comparable<Process> {
+        int id;
+        int arrivalTime;
+        int startTime;
+        int burstTime;
+        int priority;
+
+        /**
+         * Constructs a Process instance with the specified parameters.
+         *
+         * @param id          Unique identifier for the process
+         * @param arrivalTime Time when the process arrives in the system
+         * @param burstTime   Time required for the process execution
+         * @param priority    Priority of the process
+         */
+        Process(int id, int arrivalTime, int burstTime, int priority) {
+            this.id = id;
+            this.arrivalTime = arrivalTime;
+            this.startTime = -1;
+            this.burstTime = burstTime;
+            this.priority = priority;
+        }
+
+        /**
+         * Compare based on priority for scheduling. The process with the lowest
+         * priority is selected first.
+         * If two processes have the same priority, the one that arrives earlier is selected.
+         *
+         * @param other The other process to compare against
+         * @return A negative integer, zero, or a positive integer as this process
+         *         is less than, equal to, or greater than the specified process.
+         */
+        @Override
+        public int compareTo(Process other) {
+            if (this.priority == other.priority) {
+                return Integer.compare(this.arrivalTime, other.arrivalTime);
+            }
+            return Integer.compare(this.priority, other.priority);
+        }
+    }
+
+    /**
+     * Schedules processes based on their priority in a non-preemptive manner, considering their arrival times.
+     *
+     * @param processes Array of processes to be scheduled.
+     * @return Array of processes in the order they are executed.
+     */
+    public static Process[] scheduleProcesses(Process[] processes) {
+        PriorityQueue<Process> pq = new PriorityQueue<>();
+        Queue<Process> waitingQueue = new LinkedList<>();
+        int currentTime = 0;
+        int index = 0;
+        Process[] executionOrder = new Process[processes.length];
+
+        for (Process process : processes) {
+            waitingQueue.add(process);
+        }
+
+        while (!waitingQueue.isEmpty() || !pq.isEmpty()) {
+            // Add processes that have arrived to the priority queue
+            while (!waitingQueue.isEmpty() && waitingQueue.peek().arrivalTime <= currentTime) {
+                pq.add(waitingQueue.poll());
+            }
+
+            if (!pq.isEmpty()) {
+                Process currentProcess = pq.poll();
+                currentProcess.startTime = currentTime;
+                executionOrder[index++] = currentProcess;
+                currentTime += currentProcess.burstTime;
+            } else {
+                // If no process is ready, move to the next arrival time
+                currentTime = waitingQueue.peek().arrivalTime;
+            }
+        }
+
+        return executionOrder;
+    }
+
+    /**
+     * Calculates the average waiting time of the processes.
+     *
+     * @param processes      Array of processes.
+     * @param executionOrder Array of processes in execution order.
+     * @return Average waiting time.
+     */
+    public static double calculateAverageWaitingTime(Process[] processes, Process[] executionOrder) {
+        int totalWaitingTime = 0;
+
+        for (Process process : executionOrder) {
+            int waitingTime = process.startTime - process.arrivalTime;
+            totalWaitingTime += waitingTime;
+        }
+
+        return (double) totalWaitingTime / processes.length;
+    }
+
+    /**
+     * Calculates the average turn-around time of the processes.
+     *
+     * @param processes      Array of processes.
+     * @param executionOrder Array of processes in execution order.
+     * @return Average turn-around time.
+     */
+    public static double calculateAverageTurnaroundTime(Process[] processes, Process[] executionOrder) {
+        int totalTurnaroundTime = 0;
+
+        for (Process process : executionOrder) {
+            int turnaroundTime = process.startTime + process.burstTime - process.arrivalTime;
+            totalTurnaroundTime += turnaroundTime;
+        }
+
+        return (double) totalTurnaroundTime / processes.length;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/scheduling/NonPreemptivePrioritySchedulingTest.java b/src/test/java/com/thealgorithms/scheduling/NonPreemptivePrioritySchedulingTest.java
new file mode 100644
index 00000000..d28dcfea
--- /dev/null
+++ b/src/test/java/com/thealgorithms/scheduling/NonPreemptivePrioritySchedulingTest.java
@@ -0,0 +1,70 @@
+package com.thealgorithms.scheduling;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class NonPreemptivePrioritySchedulingTest {
+
+    @Test
+    public void testCalculateAverageWaitingTime() {
+        NonPreemptivePriorityScheduling.Process[] processes = {new NonPreemptivePriorityScheduling.Process(1, 0, 10, 2), // id, arrivalTime, burstTime, priority
+            new NonPreemptivePriorityScheduling.Process(2, 0, 5, 1), new NonPreemptivePriorityScheduling.Process(3, 0, 8, 3)};
+        NonPreemptivePriorityScheduling.Process[] executionOrder = NonPreemptivePriorityScheduling.scheduleProcesses(processes);
+
+        double expectedAvgWaitingTime = (0 + 5 + 15) / 3.0; // Waiting times: 0 for P2, 5 for P1, 15 for P3
+        double actualAvgWaitingTime = NonPreemptivePriorityScheduling.calculateAverageWaitingTime(processes, executionOrder);
+
+        assertEquals(expectedAvgWaitingTime, actualAvgWaitingTime, 0.01, "Average waiting time should be calculated correctly.");
+    }
+
+    @Test
+    public void testCalculateAverageTurnaroundTime() {
+        NonPreemptivePriorityScheduling.Process[] processes = {new NonPreemptivePriorityScheduling.Process(1, 0, 10, 2), // id, arrivalTime, burstTime, priority
+            new NonPreemptivePriorityScheduling.Process(2, 0, 5, 1), new NonPreemptivePriorityScheduling.Process(3, 0, 8, 3)};
+
+        NonPreemptivePriorityScheduling.Process[] executionOrder = NonPreemptivePriorityScheduling.scheduleProcesses(processes);
+
+        double expectedAvgTurnaroundTime = (5 + 15 + 23) / 3.0; // Turnaround times: 5 for P2, 15 for P1, 23 for P3
+        double actualAvgTurnaroundTime = NonPreemptivePriorityScheduling.calculateAverageTurnaroundTime(processes, executionOrder);
+
+        assertEquals(expectedAvgTurnaroundTime, actualAvgTurnaroundTime, 0.01, "Average turnaround time should be calculated correctly.");
+    }
+
+    @Test
+    public void testStartTimeIsCorrect() {
+        NonPreemptivePriorityScheduling.Process[] processes = {new NonPreemptivePriorityScheduling.Process(1, 0, 10, 2), // id, arrivalTime, burstTime, priority
+            new NonPreemptivePriorityScheduling.Process(2, 0, 5, 1), new NonPreemptivePriorityScheduling.Process(3, 0, 8, 3)};
+        NonPreemptivePriorityScheduling.Process[] executionOrder = NonPreemptivePriorityScheduling.scheduleProcesses(processes);
+
+        // Check that the start time for each process is correctly set
+        assertEquals(0, executionOrder[0].startTime, "First process (P2) should start at time 0."); // Process 2 has the highest priority
+        assertEquals(5, executionOrder[1].startTime, "Second process (P1) should start at time 5.");
+        assertEquals(15, executionOrder[2].startTime, "Third process (P3) should start at time 15.");
+    }
+
+    @Test
+    public void testWithDelayedArrivalTimes() {
+        NonPreemptivePriorityScheduling.Process[] processes = {new NonPreemptivePriorityScheduling.Process(1, 0, 4, 1), // id, arrivalTime, burstTime, priority
+            new NonPreemptivePriorityScheduling.Process(2, 2, 3, 2), new NonPreemptivePriorityScheduling.Process(3, 4, 2, 3)};
+        NonPreemptivePriorityScheduling.Process[] executionOrder = NonPreemptivePriorityScheduling.scheduleProcesses(processes);
+
+        // Test the start times considering delayed arrivals
+        assertEquals(0, executionOrder[0].startTime, "First process (P1) should start at time 0.");
+        assertEquals(4, executionOrder[1].startTime, "Second process (P2) should start at time 4."); // After P1 finishes
+        assertEquals(7, executionOrder[2].startTime, "Third process (P3) should start at time 7."); // After P2 finishes
+    }
+
+    @Test
+    public void testWithGapsInArrivals() {
+        NonPreemptivePriorityScheduling.Process[] processes = {new NonPreemptivePriorityScheduling.Process(1, 0, 6, 2), // id, arrivalTime, burstTime, priority
+            new NonPreemptivePriorityScheduling.Process(2, 8, 4, 1), new NonPreemptivePriorityScheduling.Process(3, 12, 5, 3)};
+
+        NonPreemptivePriorityScheduling.Process[] executionOrder = NonPreemptivePriorityScheduling.scheduleProcesses(processes);
+
+        // Test the start times for processes with gaps in arrival times
+        assertEquals(0, executionOrder[0].startTime, "First process (P1) should start at time 0.");
+        assertEquals(8, executionOrder[1].startTime, "Second process (P2) should start at time 8."); // After P1 finishes, arrives at 8
+        assertEquals(12, executionOrder[2].startTime, "Third process (P3) should start at time 12."); // After P2 finishes, arrives at 12
+    }
+}