Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Round-Robin Scheduler

Problem Statement

Write a Java program that simulates a round-robin scheduler using a circular linked list. Each node in the list represents a task with a string name. The scheduler should support adding tasks (insert at tail), cycling to the next task (move head to next node), and removing the current task (delete head), maintaining the circular structure. The program should track the current task (head) and handle operations in a round-robin fashion, where cycling moves to the next task in sequence. Test the implementation with sequences of operations, including adding tasks, cycling through them, removing tasks, and handling edge cases like empty lists and single-task lists. You can visualize this as a circular queue of tasks in a CPU scheduler, where tasks are processed one after another in a loop, and completed tasks are removed.

Input:

  • A sequence of operations, where each operation is:
    • addTask(task): Add a task (string) at the tail of the list.
    • cycle(): Move to the next task, return its name or "null" if empty.
    • removeTask(): Remove the current task (head), return its name or "null" if empty.
    • printTasks(): Print the list of tasks from the current head until just before it cycles. Output: For each operation, print the action performed (e.g., "Added task", "Cycled to task", "Removed task", or the task list). Return "null" for cycle or remove on an empty list. Constraints:
  • The list size is between 0 and 10^5.
  • Task names are non-empty strings of length up to 100 characters.
  • The list may be empty. Example:
  • Input: Operations = [addTask("Task1"), addTask("Task2"), addTask("Task3"), printTasks, cycle, printTasks, removeTask, printTasks]
  • Output: 
    Added Task1
Added Task2
Added Task3
Tasks: Task1 Task2 Task3
Cycled to Task2
Tasks: Task2 Task3 Task1
Removed Task2
Tasks: Task3 Task1
  • Input: Operations = [cycle, printTasks]
  • Output: 
    Cycled to null
Tasks: []

Pseudocode

CLASS Node
    SET task to string
    SET next to Node (null by default)
ENDCLASS

CLASS RoundRobinScheduler
    SET head to null

    FUNCTION addTask(task)
        CREATE newNode as new Node(task)
        IF head is null THEN
            SET head to newNode
            SET newNode.next to head
        ELSE
            SET current to head
            WHILE current.next is not head
                SET current to current.next
            ENDWHILE
            SET current.next to newNode
            SET newNode.next to head
        ENDIF
    ENDFUNCTION

    FUNCTION cycle()
        IF head is null THEN
            RETURN "null"
        ENDIF
        SET head to head.next
        RETURN head.task
    ENDFUNCTION

    FUNCTION removeTask()
        IF head is null THEN
            RETURN "null"
        ENDIF
        IF head.next is head THEN
            SET task to head.task
            SET head to null
            RETURN task
        ENDIF
        SET task to head.task
        SET current to head
        WHILE current.next is not head
            SET current to current.next
        ENDWHILE
        SET current.next to head.next
        SET head to head.next
        RETURN task
    ENDFUNCTION

    FUNCTION toString()
        IF head is null THEN
            RETURN "[]"
        ENDIF
        CREATE result as new StringBuilder
        SET current to head
        SET visited as new Set
        WHILE current is not null AND current not in visited
            ADD current to visited
            APPEND current.task to result
            IF current.next is not head THEN
                APPEND " " to result
            ENDIF
            SET current to current.next
        ENDWHILE
        RETURN result as string
    ENDFUNCTION
ENDCLASS

FUNCTION testScheduler(operations)
    CREATE scheduler as new RoundRobinScheduler
    FOR each operation in operations
        IF operation.type equals "addTask" THEN
            CALL scheduler.addTask(operation.task)
            PRINT added task
        ELSE IF operation.type equals "cycle" THEN
            SET task to scheduler.cycle()
            PRINT cycled to task
        ELSE IF operation.type equals "removeTask" THEN
            SET task to scheduler.removeTask()
            PRINT removed task
        ELSE IF operation.type equals "print" THEN
            PRINT tasks using scheduler.toString
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL testScheduler(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a Node class with: a. A string task for the task name. b. A next pointer to the next node.
  2. Define a RoundRobinScheduler class with: a. A head pointer to track the current task. b. addTask: Add node at tail, connect to head to maintain cycle. c. cycle: Move head to next node, return task name or "null". d. removeTask: Remove head, update cycle, return task name or "null". e. toString: Print tasks from head until cycle, return "[]" if empty.
  3. In testScheduler: a. Create a RoundRobinScheduler. b. For each operation:
    • addTask: Call addTask, print action.
    • cycle: Call cycle, print task name.
    • removeTask: Call removeTask, print task name.
    • print: Call toString, print task list.
  4. In main, test with sequences including adds, cycles, removes, and edge cases.

Java Implementation

import java.util.*;

public class RoundRobinScheduler {
    // Node class for the circular linked list
    static class Node {
        String task;
        Node next;

        Node(String task) {
            this.task = task;
            this.next = null;
        }
    }

    // RoundRobinScheduler class to simulate task scheduling
    static class Scheduler {
        private Node head;

        public void addTask(String task) {
            Node newNode = new Node(task);
            if (head == null) {
                head = newNode;
                newNode.next = head;
            } else {
                Node current = head;
                while (current.next != head) {
                    current = current.next;
                }
                current.next = newNode;
                newNode.next = head;
            }
        }

        public String cycle() {
            if (head == null) {
                return "null";
            }
            head = head.next;
            return head.task;
        }

        public String removeTask() {
            if (head == null) {
                return "null";
            }
            String task = head.task;
            if (head.next == head) {
                head = null;
                return task;
            }
            Node current = head;
            while (current.next != head) {
                current = current.next;
            }
            current.next = head.next;
            head = head.next;
            return task;
        }

        public String toString() {
            if (head == null) {
                return "[]";
            }
            StringBuilder result = new StringBuilder();
            Node current = head;
            Set<Node> visited = new HashSet<>();
            while (current != null && !visited.contains(current)) {
                visited.add(current);
                result.append(current.task);
                if (current.next != head) {
                    result.append(" ");
                }
                current = current.next;
            }
            return result.toString();
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        String task;

        Operation(String type, String task) {
            this.type = type;
            this.task = task;
        }
    }

    // Tests round-robin scheduler operations
    public void testScheduler(List<Operation> operations) {
        Scheduler scheduler = new Scheduler();
        for (Operation op : operations) {
            if (op.type.equals("addTask")) {
                scheduler.addTask(op.task);
                System.out.println("Added " + op.task);
            } else if (op.type.equals("cycle")) {
                String task = scheduler.cycle();
                System.out.println("Cycled to " + task);
            } else if (op.type.equals("removeTask")) {
                String task = scheduler.removeTask();
                System.out.println("Removed " + task);
            } else if (op.type.equals("print")) {
                System.out.println("Tasks: " + scheduler.toString());
            }
        }
    }

    // Main method to test round-robin scheduler
    public static void main(String[] args) {
        RoundRobinScheduler manager = new RoundRobinScheduler();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal operations
        testCases.add(Arrays.asList(
            new Operation("addTask", "Task1"),
            new Operation("addTask", "Task2"),
            new Operation("addTask", "Task3"),
            new Operation("print", null),
            new Operation("cycle", null),
            new Operation("print", null),
            new Operation("removeTask", null),
            new Operation("print", null)
        ));
        
        // Test case 2: Empty list
        testCases.add(Arrays.asList(
            new Operation("cycle", null),
            new Operation("removeTask", null),
            new Operation("print", null)
        ));
        
        // Test case 3: Single task
        testCases.add(Arrays.asList(
            new Operation("addTask", "Task1"),
            new Operation("print", null),
            new Operation("cycle", null),
            new Operation("print", null),
            new Operation("removeTask", null),
            new Operation("print", null)
        ));
        
        // Test case 4: Multiple cycles and removes
        testCases.add(Arrays.asList(
            new Operation("addTask", "Task1"),
            new Operation("addTask", "Task2"),
            new Operation("addTask", "Task3"),
            new Operation("cycle", null),
            new Operation("cycle", null),
            new Operation("print", null),
            new Operation("removeTask", null),
            new Operation("print", null)
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            manager.testScheduler(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Added Task1
Added Task2
Added Task3
Tasks: Task1 Task2 Task3
Cycled to Task2
Tasks: Task2 Task3 Task1
Removed Task2
Tasks: Task3 Task1

Test case 2:
Cycled to null
Removed null
Tasks: []

Test case 3:
Added Task1
Tasks: Task1
Cycled to Task1
Tasks: Task1
Removed Task1
Tasks: []

Test case 4:
Added Task1
Added Task2
Added Task3
Cycled to Task2
Cycled to Task3
Tasks: Task3 Task1 Task2
Removed Task3
Tasks: Task1 Task2

Explanation:

  • Test case 1: Adds Task1, Task2, Task3, prints "Task1 Task2 Task3", cycles to Task2, prints "Task2 Task3 Task1", removes Task2, prints "Task3 Task1".
  • Test case 2: Cycles and removes on empty list, prints "null" and "[]".
  • Test case 3: Adds Task1, prints "Task1", cycles to Task1, prints "Task1", removes Task1, prints "[]".
  • Test case 4: Adds Task1, Task2, Task3, cycles twice to Task3, prints "Task3 Task1 Task2", removes Task3, prints "Task1 Task2".

How It Works

  • Node: Stores a string task name and a next pointer.
  • Scheduler:
    • addTask: Adds node at tail, connects to head, O(n).
    • cycle: Moves head to next node, returns task or "null", O(1).
    • removeTask: Removes head, updates cycle, returns task or "null", O(n).
    • toString: Traverses from head, uses Set to prevent cycling, returns space-separated string or "[]".
  • testScheduler: Executes operations, printing actions and results.
  • Example Trace (Test case 1):
    • addTask("Task1"): head=Task1→Task1.
    • addTask("Task2"): head=Task1→Task2→Task1.
    • addTask("Task3"): head=Task1→Task2→Task3→Task1.
    • print: "Task1 Task2 Task3".
    • cycle: head=Task2, returns "Task2".
    • print: "Task2 Task3 Task1".
    • removeTask: Removes Task2, head=Task3→Task1→Task3, returns "Task2".
    • print: "Task3 Task1".
  • Main Method: Tests normal operations, empty list, single task, and multiple cycles/removes.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Add TaskO(n)O(1)
CycleO(1)O(1)
Remove TaskO(n)O(1)
To StringO(n)O(n)

Note:

  • n is the number of nodes in the list.
  • Time complexity: O(n) for addTask and removeTask (traverse to tail); O(1) for cycle; O(n) for toString (traverse list).
  • Space complexity: O(1) for addTask, cycle, removeTask (constant pointers); O(n) for toString (StringBuilder and Set).
  • Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: Use a circular linked list to naturally model the round-robin cycling behavior. Maintain the head pointer to track the current task and ensure the tail connects to the head for circularity.

⚠ Warning: Update next pointers carefully during task removal to maintain the circular structure. Handle edge cases like empty lists and single-task lists to avoid null pointer issues.