Tag: round robin scheduling

  • RR Scheduling Algorithm: Complete Guide with 5 Powerful Examples

    The Round Robin (RR) Scheduling Algorithm is one of the simplest and most widely used CPU scheduling algorithms in operating systems. It ensures that every process gets an equal share of CPU time, making it fair and efficient for time-sharing systems.

    In this algorithm, each process is assigned a fixed time slot called a time quantum or time slice. The CPU executes a process for this specific time. If the process is not completed within that period, it is moved to the back of the ready queue, and the CPU is allocated to the next process.

    How Round Robin Scheduling Works

    Here’s a step-by-step explanation of how the RR scheduling algorithm works:

    1. All processes are placed in a ready queue (FIFO order).
    2. The CPU scheduler picks the first process from the queue.
    3. The process runs for a fixed time quantum.
    4. If the process finishes within that time, it leaves the queue.
    5. If not, it is sent back to the end of the queue, and the next process gets the CPU.
    6. This cycle continues until all processes are complete.

    This way, every process gets a fair chance to execute, preventing starvation in os.

    Example of Round Robin Scheduling

    Let’s take a simple example:

    ProcessBurst TimeTime Quantum = 3 ms
    P15 ms
    P23 ms
    P38 ms

    Execution Order:
    P1 (3 ms) → P2 (3 ms) → P3 (3 ms) → P1 (2 ms) → P3 (5 ms)

    Here, every process runs for 3 milliseconds before moving to the next one.

    C Program : RR Scheduling Algorithm

    #include <stdio.h>
    
    int main() {
        int n, quantum;
        int bt[20], wt[20], tat[20], rem_bt[20];
        int i, t = 0, total_wt = 0, total_tat = 0;
    
        printf("Enter total number of processes: ");
        scanf("%d", &n);
    
        printf("Enter burst time for each process:\n");
        for (i = 0; i < n; i++) {
            printf("P%d: ", i + 1);
            scanf("%d", &bt[i]);
            rem_bt[i] = bt[i]; // store remaining burst time
        }
    
        printf("Enter Time Quantum: ");
        scanf("%d", &quantum);
    
        while (1) {
            int done = 1;
            for (i = 0; i < n; i++) {
                if (rem_bt[i] > 0) {
                    done = 0; // There is a pending process
    
                    if (rem_bt[i] > quantum) {
                        t += quantum;
                        rem_bt[i] -= quantum;
                    } else {
                        t += rem_bt[i];
                        wt[i] = t - bt[i];
                        rem_bt[i] = 0;
                    }
                }
            }
    
            if (done == 1)
                break;
        }
    
        // Calculate Turnaround Time
        for (i = 0; i < n; i++) {
            tat[i] = bt[i] + wt[i];
            total_wt += wt[i];
            total_tat += tat[i];
        }
    
        printf("\nProcess\tBurst Time\tWaiting Time\tTurnaround Time\n");
        for (i = 0; i < n; i++) {
            printf("P%d\t\t%d\t\t%d\t\t%d\n", i + 1, bt[i], wt[i], tat[i]);
        }
    
        printf("\nAverage Waiting Time = %.2f", (float)total_wt / n);
        printf("\nAverage Turnaround Time = %.2f\n", (float)total_tat / n);
    
        return 0;
    }
    

    Sample Output

    Enter total number of processes: 3
    Enter burst time for each process:
    P1: 5
    P2: 3
    P3: 8
    Enter Time Quantum: 3
    
    Process	Burst Time	Waiting Time	Turnaround Time
    P1		5		6		11
    P2		3		3		6
    P3		8		9		17
    
    Average Waiting Time = 6.00
    Average Turnaround Time = 11.33
    

    Advantages of RR Scheduling Algorithm

    • Fair Allocation: Each process gets equal CPU time.
    • Good for Time-Sharing Systems: Best suited for multitasking environments.
    • Responsive: Short processes finish quickly without long waiting times.
    • Simple and Easy to Implement: Works on a straightforward queue-based approach.

    Disadvantages of RR Scheduling Algorithm

    • Context Switching Overhead: Frequent switching can reduce performance.
    • Time Quantum Selection: Choosing the right quantum is tricky—too small increases overhead, too large reduces responsiveness.
    • Not Ideal for Long Tasks: Processes with longer burst times might take longer to complete.

    Characteristics of RR Scheduling Algorithm

    • Scheduling Type: Preemptive
    • CPU Utilization: Moderate to High
    • Starvation: Not possible
    • Best Suited For: Time-sharing systems and interactive users

    Formula to Calculate Waiting Time and Turnaround Time

    • Waiting Time (WT): Turnaround Time – Burst Time
    • Turnaround Time (TAT): Completion Time – Arrival Time

    These formulas help calculate performance metrics in CPU scheduling problems.

    Real-World Use of RR Scheduling Algorithm

    Round Robin scheduling is widely used in time-sharing operating systems, such as UNIX and Linux, where each user or process gets equal CPU attention for short bursts.

    Final Thoughts

    The Round Robin (RR) Scheduling Algorithm is one of the easiest and most fair scheduling methods. It ensures equal CPU distribution, low waiting time for short processes, and efficient multitasking. However, its performance highly depends on the time quantum selection.

    Interview Questions You May Face on RR Scheduling Algorithm

    When preparing for Operating System or Embedded Software interviews, you might face questions like:

    1. What is the main idea behind the RR scheduling algorithm?
    2. How is Round Robin different from FCFS or SJF scheduling?
    3. Why is RR considered preemptive?
    4. What is the effect of choosing a small or large time quantum?
    5. Can starvation occur in RR scheduling? Why or why not?
    6. Write a program to simulate RR scheduling in C.
    7. Explain the formula for waiting time and turnaround time in RR.
    8. What kind of systems use RR scheduling in real life?
    9. How do context switches affect CPU performance?
    10. What are the advantages and disadvantages of RR compared to Priority Scheduling?

    Frequently Asked Questions (FAQs) about RR Scheduling Algorithm

    1. What is the RR Scheduling Algorithm in Operating System?

    The RR (Round Robin) Scheduling Algorithm is a preemptive CPU scheduling technique where each process gets an equal fixed time to execute, known as a time quantum. If a process doesn’t finish in that time, it goes to the back of the queue.

    2. Why is it called Round Robin?

    It’s called Round Robin because CPU time is given to each process in a circular order, like players taking turns in a game — ensuring fair CPU allocation.

    3. What is a Time Quantum in RR Scheduling?

    A time quantum (or time slice) is the fixed amount of CPU time allocated to each process. After this time expires, the CPU switches to the next process.

    4. Is Round Robin Scheduling Preemptive or Non-Preemptive?

    Round Robin Scheduling is preemptive because the CPU forcibly switches from one process to another after the time quantum expires, even if the current process isn’t finished.

    5. What are the main advantages of RR Scheduling?

    • Fair CPU sharing among processes
    • No starvation (every process gets CPU time)
    • Suitable for time-sharing systems
    • Good response time for interactive tasks

    6. What are the disadvantages of RR Scheduling?

    • Too many context switches if the time quantum is too small
    • Hard to select the ideal time quantum
    • Performance decreases with long burst-time processes

    7. How do you calculate waiting time and turnaround time in RR?

    • Waiting Time (WT) = Turnaround Time – Burst Time
    • Turnaround Time (TAT) = Completion Time – Arrival Time

    These metrics help measure CPU efficiency and responsiveness.

    8. What is the best time quantum for Round Robin?

    There’s no universal best value. However, a smaller quantum improves responsiveness but increases context switches. A larger quantum reduces context switches but may cause longer waiting times.

    9. Where is Round Robin Scheduling used in real life?

    Round Robin is used in time-sharing operating systems, like UNIX and Linux, where multiple users or processes share CPU time equally.

    10. What is the main difference between RR and FCFS Scheduling?

    • FCFS (First Come First Serve) runs each process until it finishes.
    • RR (Round Robin) gives each process a fixed time and switches tasks regularly — making it more fair and interactive.
  • Master Circular Linked List Tutorials with Examples 2026

    Complete guide to mastering Circular Linked Lists in 2025 with this beginner-to-advanced tutorial! Learn how circular linked lists work, their types, operations, and real-life applications through clear explanations, code examples in C, C++, Java, Python, and JavaScript, and step-by-step implementations. This post also covers time and space complexity, interview FAQs, help you crack coding interviews and academic exams. Perfect for students, developers, and data structure enthusiasts!

    What is a Circular Linked List?

    A Circular Linked List is a variation of the linked list in which the last node points back to the first node instead of pointing to NULL. This creates a looped structure where you can traverse endlessly through the list starting from any node.

    🔁 In a circular linked list, you can go from tail to head seamlessly — it’s like a roundabout with no end!

    Why Learn Circular Linked Lists?

    Learning about Circular Linked Lists is crucial for understanding how dynamic data structures work in memory. They are especially useful for:

    • Circular buffers (ring buffers)
    • Multiplayer game round-robin scheduling
    • Task scheduling algorithms
    • Data streaming

    Types of Circular Linked List

    1. Singly Circular Linked List
      Each node has a data and a next pointer, and the next of the last node points to the first node.
    2. Doubly Circular Linked List
      Each node has data, next, and prev pointers. The next of the last node connects to the first node and the prev of the first node connects to the last.

    Circular Linked List Operations

    1. Insertion

    • At the beginning
    • At the end
    • After a specific node

    2. Deletion

    • From the beginning
    • From the end
    • A specific node

    3. Traversal

    • Start from any node and keep moving until you’re back to the same node.
    // Example: Circular Linked List Traversal in C
    void traverse(struct Node* head) {
        struct Node* temp = head;
        if (head != NULL) {
            do {
                printf("%d ", temp->data);
                temp = temp->next;
            } while (temp != head);
        }
    }
    

    C Implementation CLL

    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
        int data;
        struct Node* next;
    };
    
    void traverse(struct Node* head) {
        if (head == NULL) return;
        struct Node* temp = head;
        do {
            printf("%d ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
    
    struct Node* insertEnd(struct Node* head, int data) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        if (!head) {
            newNode->next = newNode;
            return newNode;
        }
        struct Node* temp = head;
        while (temp->next != head) temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        return head;
    }
    

    ✅ C++ Implementation CLL

    #include <iostream>
    using namespace std;
    
    class Node {
    public:
        int data;
        Node* next;
        Node(int val) {
            data = val;
            next = nullptr;
        }
    };
    
    void traverse(Node* head) {
        if (!head) return;
        Node* temp = head;
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
    }
    
    Node* insertEnd(Node* head, int val) {
        Node* newNode = new Node(val);
        if (!head) {
            newNode->next = newNode;
            return newNode;
        }
        Node* temp = head;
        while (temp->next != head) temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        return head;
    }
    

    ✅ Java Implementation CLL

    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    public class CircularLinkedList {
        Node head;
    
        void traverse() {
            if (head == null) return;
            Node temp = head;
            do {
                System.out.print(temp.data + " ");
                temp = temp.next;
            } while (temp != head);
        }
    
        void insertEnd(int data) {
            Node newNode = new Node(data);
            if (head == null) {
                newNode.next = newNode;
                head = newNode;
                return;
            }
            Node temp = head;
            while (temp.next != head) temp = temp.next;
            temp.next = newNode;
            newNode.next = head;
        }
    }
    

    ✅ Python Implementation CLL

    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    class CircularLinkedList:
        def __init__(self):
            self.head = None
    
        def traverse(self):
            if not self.head:
                return
            temp = self.head
            while True:
                print(temp.data, end=' ')
                temp = temp.next
                if temp == self.head:
                    break
    
        def insert_end(self, data):
            new_node = Node(data)
            if not self.head:
                new_node.next = new_node
                self.head = new_node
                return
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head
    

    ✅ JavaScript Implementation CLL

    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }
    
    class CircularLinkedList {
        constructor() {
            this.head = null;
        }
    
        traverse() {
            if (!this.head) return;
            let temp = this.head;
            do {
                console.log(temp.data);
                temp = temp.next;
            } while (temp !== this.head);
        }
    
        insertEnd(data) {
            const newNode = new Node(data);
            if (!this.head) {
                newNode.next = newNode;
                this.head = newNode;
                return;
            }
            let temp = this.head;
            while (temp.next !== this.head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = this.head;
        }
    }
    

    Time & Space Complexity of Circular Linked List

    OperationTime ComplexitySpace Complexity
    Insert at EndO(n)O(1)
    TraverseO(n)O(1)
    Delete NodeO(n)O(1)
    SearchO(n)O(1)

    ⚠️ Note: You can make insertion O(1) by maintaining a tail pointer.

    Advantages of Circular Linked List

    • No NULL value at the end
    • Ideal for implementing circular queues
    • Efficient for round-robin scheduling
    • Can traverse from any node

    Disadvantages of Circular Linked List

    • Slightly more complex insertion/deletion logic
    • Risk of infinite loops if not handled properly

    Circular Linked List vs Singly Linked List

    FeatureSingly Linked ListCircular Linked List
    End PointerPoints to NULLPoints to head node
    TraversalEnds at NULLLoops back to start
    Use CaseLinear dataCircular scheduling

    Real-world Use Cases of Circular Linked List

    • Music playlist apps (loop through songs)
    • Task scheduling in OS
    • Live data streams
    • Circular queues

    1.What is the use of circular linked list?

    It is mainly used in applications that require a continuous traversal like CPU scheduling, music players, or multiplayer games.

    2.What is the time complexity of circular linked list operations?

    Insertion: O(1) (beginning), O(n) (end/after a node)
    Deletion: O(1) (beginning), O(n) (specific node)
    Traversal: O(n)

    3.Can we implement a stack or queue using a circular linked list?

    Yes! Circular linked lists are great for queues, especially when a circular buffer is needed.

    4.How to detect a circular linked list?

    Use Floyd’s Cycle Detection Algorithm (Tortoise and Hare method).

    5.What is a Circular Linked List in Data Structures?

    A Circular Linked List is a type of linked list where the last node is connected back to the first node, forming a closed loop. Unlike a singly linked list where the last node points to NULL, a circular linked list enables continuous traversal from any point in the list. This structure is highly useful in circular queues, CPU scheduling, and real-time applications.

    6.What are the types of Circular Linked Lists?

    There are two main types of Circular Linked Lists:
    Singly Circular Linked List: Each node has one pointer pointing to the next node, and the last node points to the head.
    Doubly Circular Linked List: Each node has two pointers (prev and next), and both the first and last nodes are connected circularly in both directions.
    Both types are used based on the complexity of operations needed and memory constraints.

    7.What are the real-life applications of Circular Linked List?

    Circular Linked Lists are widely used in:
    Round-robin CPU scheduling
    Music or video playlists that auto-repeat
    Circular buffers in embedded systems
    Real-time data stream processing
    Traffic light simulation systems
    Multiplayer games for turn rotation
    These applications benefit from the list’s looping behavior, which avoids end-condition checks.

    8.What is the time complexity of Circular Linked List operations?

    Insertion at end/head: O(n) / O(1) (if tail maintained)
    Deletion at head: O(n)
    Search: O(n)
    Traversal: O(n)
    Maintaining a tail pointer can reduce insertion time at the end to O(1).

    9.How do you detect a circular linked list in a program?

    To detect a circular linked list, you can use Floyd’s Cycle Detection Algorithm (Tortoise and Hare Algorithm):
    Use two pointers moving at different speeds.
    If they ever meet, a cycle exists.
    If the fast pointer reaches NULL, it’s not circular.
    This is the most efficient method with O(n) time and O(1) space.

    10.Can a Circular Linked List be used to implement a queue?

    Yes, Circular Linked Lists are perfect for circular queues, especially when:
    Memory usage is fixed (as in embedded systems).
    You need constant-time insertion and deletion.
    It avoids shifting elements (like in arrays) and supports continuous enqueuing and dequeuing.

    A Circular Linked List offers flexibility, especially when your use case involves continuous looping or round-based tasks. While it can be a bit more complex than a regular linked list, it brings efficiency and circular logic into dynamic data structures.

    If you’re preparing for coding interviews, learning circular linked lists will give you an edge!

    Circular Linked List
    Master Circular Linked List Tutorials with Examples 2025