Repository: TheAlgorithms/Java
Pull request #5575 (2024-10-05 05:04:58)

Add `MLFQScheduler.java` new algorithm
<!--
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/5575?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 `95.23810%` with `2 lines` in your changes missing coverage. Please review.
> Project coverage is 54.09%. Comparing base [(`842ff52`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/842ff5294f5e97dfd1e4c09f9d9e01a89ac16e32?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`e45ea52`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/e45ea526bef5eed51df542c80e608abfc59f7cd0?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 20 commits behind head on master.

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5575?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...va/com/thealgorithms/scheduling/MLFQScheduler.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5575?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fscheduling%2FMLFQScheduler.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9zY2hlZHVsaW5nL01MRlFTY2hlZHVsZXIuamF2YQ==) | 95.23% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5575?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    #5575      +/-   ##
============================================
+ Coverage     52.31%   54.09%   +1.78%     
- Complexity     3259     3401     +142     
============================================
  Files           526      536      +10     
  Lines         15205    15471     +266     
  Branches       2892     2950      +58     
============================================
+ Hits           7954     8369     +415     
+ Misses         6924     6749     -175     
- Partials        327      353      +26     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5575?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).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 1bad5d3b..d93dde3d 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -42,6 +42,7 @@
             * [AES](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/AES.java)
             * [AESEncryption](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/AESEncryption.java)
             * [AffineCipher](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/AffineCipher.java)
+            * [Autokey](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/Autokey.java)
             * [Blowfish](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/Blowfish.java)
             * [Caesar](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/Caesar.java)
             * [ColumnarTranspositionCipher](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/ciphers/ColumnarTranspositionCipher.java)
@@ -203,6 +204,7 @@
               * [SameTreesCheck](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/SameTreesCheck.java)
               * [SegmentTree](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/SegmentTree.java)
               * [SplayTree](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/SplayTree.java)
+              * [Treap](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/Treap.java)
               * [TreeRandomNode](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TreeRandomNode.java)
               * [TrieImp](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/TrieImp.java)
               * [VerticalOrderTraversal](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversal.java)
@@ -457,6 +459,7 @@
             * [GenerateSubsets](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/Recursion/GenerateSubsets.java)
           * scheduling
             * [FCFSScheduling](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/FCFSScheduling.java)
+            * [MLFQScheduler](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/scheduling/MLFQScheduler.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)
@@ -618,6 +621,7 @@
           * ciphers
             * a5
               * [LFSRTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/a5/LFSRTest.java)
+            * [AutokeyTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/AutokeyTest.java)
             * [BlowfishTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/BlowfishTest.java)
             * [CaesarTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/CaesarTest.java)
             * [DESTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/DESTest.java)
@@ -728,6 +732,7 @@
               * [PreOrderTraversalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/PreOrderTraversalTest.java)
               * [SameTreesCheckTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/SameTreesCheckTest.java)
               * [SplayTreeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/SplayTreeTest.java)
+              * [TreapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/TreapTest.java)
               * [TreeTestUtils](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/TreeTestUtils.java)
               * [TrieImpTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/TrieImpTest.java)
               * [VerticalOrderTraversalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversalTest.java)
@@ -911,6 +916,7 @@
             * [GenerateSubsetsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/Recursion/GenerateSubsetsTest.java)
           * scheduling
             * [FCFSSchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/FCFSSchedulingTest.java)
+            * [MLFQSchedulerTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/MLFQSchedulerTest.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/MLFQScheduler.java b/src/main/java/com/thealgorithms/scheduling/MLFQScheduler.java
new file mode 100644
index 00000000..75840a5c
--- /dev/null
+++ b/src/main/java/com/thealgorithms/scheduling/MLFQScheduler.java
@@ -0,0 +1,148 @@
+package com.thealgorithms.scheduling;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+
+/**
+ * The Multi-Level Feedback Queue (MLFQ) Scheduler class.
+ * This class simulates scheduling using multiple queues, where processes move
+ * between queues depending on their CPU burst behavior.
+ */
+public class MLFQScheduler {
+    private List<Queue<Process>> queues; // Multi-level feedback queues
+    private int[] timeQuantum; // Time quantum for each queue level
+    private int currentTime; // Current time in the system
+
+    /**
+     * Constructor to initialize the MLFQ scheduler with the specified number of
+     * levels and their corresponding time quantums.
+     *
+     * @param levels       Number of queues (priority levels)
+     * @param timeQuantums Time quantum for each queue level
+     */
+    public MLFQScheduler(int levels, int[] timeQuantums) {
+        queues = new ArrayList<>(levels);
+        for (int i = 0; i < levels; i++) {
+            queues.add(new LinkedList<>());
+        }
+        timeQuantum = timeQuantums;
+        currentTime = 0;
+    }
+
+    /**
+     * Adds a new process to the highest priority queue (queue 0).
+     *
+     * @param p The process to be added to the scheduler
+     */
+    public void addProcess(Process p) {
+        queues.get(0).add(p);
+    }
+
+    /**
+     * Executes the scheduling process by running the processes in all queues,
+     * promoting or demoting them based on their completion status and behavior.
+     * The process continues until all queues are empty.
+     */
+    public void run() {
+        while (!allQueuesEmpty()) {
+            for (int i = 0; i < queues.size(); i++) {
+                Queue<Process> queue = queues.get(i);
+                if (!queue.isEmpty()) {
+                    Process p = queue.poll();
+                    int quantum = timeQuantum[i];
+
+                    // Execute the process for the minimum of the time quantum or the remaining time
+                    int timeSlice = Math.min(quantum, p.remainingTime);
+                    p.execute(timeSlice);
+                    currentTime += timeSlice; // Update the system's current time
+
+                    if (p.isFinished()) {
+                        System.out.println("Process " + p.pid + " finished at time " + currentTime);
+                    } else {
+                        if (i < queues.size() - 1) {
+                            p.priority++; // Demote the process to the next lower priority queue
+                            queues.get(i + 1).add(p); // Add to the next queue level
+                        } else {
+                            queue.add(p); // Stay in the same queue if it's the last level
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /**
+     * Helper function to check if all the queues are empty (i.e., no process is
+     * left to execute).
+     *
+     * @return true if all queues are empty, otherwise false
+     */
+    private boolean allQueuesEmpty() {
+        for (Queue<Process> queue : queues) {
+            if (!queue.isEmpty()) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Retrieves the current time of the scheduler, which reflects the total time
+     * elapsed during the execution of all processes.
+     *
+     * @return The current time in the system
+     */
+    public int getCurrentTime() {
+        return currentTime;
+    }
+}
+
+/**
+ * Represents a process in the Multi-Level Feedback Queue (MLFQ) scheduling
+ * algorithm.
+ */
+class Process {
+    int pid;
+    int burstTime;
+    int remainingTime;
+    int arrivalTime;
+    int priority;
+
+    /**
+     * Constructor to initialize a new process.
+     *
+     * @param pid         Process ID
+     * @param burstTime   CPU Burst Time (time required for the process)
+     * @param arrivalTime Arrival time of the process
+     */
+    Process(int pid, int burstTime, int arrivalTime) {
+        this.pid = pid;
+        this.burstTime = burstTime;
+        this.remainingTime = burstTime;
+        this.arrivalTime = arrivalTime;
+        this.priority = 0;
+    }
+
+    /**
+     * Executes the process for a given time slice.
+     *
+     * @param timeSlice The amount of time the process is executed
+     */
+    public void execute(int timeSlice) {
+        remainingTime -= timeSlice;
+        if (remainingTime < 0) {
+            remainingTime = 0;
+        }
+    }
+
+    /**
+     * Checks if the process has finished execution.
+     *
+     * @return true if the process is finished, otherwise false
+     */
+    public boolean isFinished() {
+        return remainingTime == 0;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/scheduling/MLFQSchedulerTest.java b/src/test/java/com/thealgorithms/scheduling/MLFQSchedulerTest.java
new file mode 100644
index 00000000..d7d27e9b
--- /dev/null
+++ b/src/test/java/com/thealgorithms/scheduling/MLFQSchedulerTest.java
@@ -0,0 +1,46 @@
+package com.thealgorithms.scheduling;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class MLFQSchedulerTest {
+
+    @Test
+    void testMLFQScheduling() {
+        // Create MLFQ Scheduler with 3 levels and time quantum for each level
+        int[] timeQuantums = {4, 8, 12}; // Example of different quantum for each queue
+        MLFQScheduler scheduler = new MLFQScheduler(3, timeQuantums);
+
+        // Add processes to the scheduler
+        scheduler.addProcess(new Process(1, 10, 0)); // pid=1, burstTime=10, arrivalTime=0
+        scheduler.addProcess(new Process(2, 15, 0)); // pid=2, burstTime=15, arrivalTime=0
+        scheduler.addProcess(new Process(3, 25, 0)); // pid=3, burstTime=25, arrivalTime=0
+
+        // Run the scheduler
+        scheduler.run();
+
+        // Check current time after all processes are finished
+        assertEquals(50, scheduler.getCurrentTime());
+    }
+
+    @Test
+    void testProcessCompletionOrder() {
+        int[] timeQuantums = {3, 6, 9};
+        MLFQScheduler scheduler = new MLFQScheduler(3, timeQuantums);
+
+        Process p1 = new Process(1, 10, 0);
+        Process p2 = new Process(2, 5, 0);
+        Process p3 = new Process(3, 20, 0);
+
+        scheduler.addProcess(p1);
+        scheduler.addProcess(p2);
+        scheduler.addProcess(p3);
+
+        scheduler.run();
+
+        // After running, current time should match the total burst time for all
+        // processes
+        assertEquals(35, scheduler.getCurrentTime());
+    }
+}