Introduction to Round-Robin Scheduling

Board Infinity
Board Infinity
Introduction to Round-Robin Scheduling

    Advanced Algorithms and Problem Solving Techniques

    How To Start Competitive Programming - A Complete Guide

    A Quick Guide to Breadth-First Search

    Depth First Search (DFS) with Explanation and Code

    Difference Between BFS and DFS (with code and diagrams)

    How to Perform Level Order Traversal?

    A Quick Guide to Backtracking Algorithm

    Solving N Queens Problem using Backtracking

    Quick Guide to Divide and Conquer Algorithm

    Longest Increasing Subsequence Problem

    Quick Note - Greedy Programming v/s Dynamic Programming

    Coin Change Problem: DP and Recursion Approach

    A Definitive Guide to Knapsack Problem

    How to Solve Subset Sum Problem?

    Understanding Huffman Coding in detail

    Understand the working of KMP Algorithm

    Longest Common Substring Problem

    Longest Common Subsequence problem: solved

    A Quick Guide to Manacher's Algorithm

    Learning About Bipartite Graphs

    Graph Coloring Problem: Explained

    Detect Cycle in Direct Graph

    Directed Acyclic Graph: Representation

    Prim's Algorithm: Explanation, Code, and Applications

    Working of Kruskal's Algorithm

    Prims and Kruskal algorithm for Maximum Spanning Tree

    Bellman Ford Algorithm in detail with code

    Floyd-Warshall Algorithm and its Implementation

    Understand Travelling Salesman Problem

    Branch And Bound Algorithm: Explained

    How to Evaluate Postfix Expression

    Introduction to Round-Robin Scheduling

    Disjoint set (Union find Algorithm)

    State Space Reduction in Algorithms

    Apriori Algorithm

    What is A* Search Algorithm?

What is Round-Robin Scheduling?

This algorithm takes its name from the round-robin principle, which distributes something equally among all participants. This is the oldest, most straightforward scheduling algorithm used for multitasking. During round-robin scheduling, each ready task runs cyclically for a limited period. As a result of this algorithm, processes also run without starvation.

The Round Robin Algorithm Working Process

  1. A ready queue gets established for all processes.
  2. Each process' burst time gets compared to the CPU's time quantum.
  3. The Round Robin scheduling algorithm executes the process within the time quantum if the burst time is less than or equal to the time quantum.
  4. When a process' burst time exceeds a time quantum, the process gets executed until it reaches the time quantum (TQ).
  5. The time quantum expires, and the process checks to see if it has finished.
  6. As soon as the process is complete, it terminates. Otherwise, the process returns to the ready state.

Characteristics of Round Robin Scheduling

Round Robin Scheduling has the following essential characteristics:

  • First, a Round Robin algorithm works on a preemptive basis.
  • During time quantum/time slice, a fixed interval time allows moving to the following process on the CPU.
  • In the queue, the preempted process appears at the end.
  • It would be beneficial to have a minimum time slice for each task that needs to get completed. Nevertheless, it may differ from one OS to another.
  • This algorithm responds to an event in real time within a given period.

Advantages

  • Considering that it doesn't depend on the burst time, the system can use it.
  • It is not affected by starvation or convoy effects.
  • CPU resources are made available to all jobs on a fair basis.

Disadvantages

  • The system's response time increases as the time quantum increases.
  • Context switching is more expensive in systems with lower time quantum.
  • It is challenging to determine a perfect time quantum in the system.

Important Terms

  • Completion Time: refers to when a process is completed.
  • Turn Around Time: represents the difference between completion and arrival times. To calculate the same, use this formula: Turn Around Time = Completion Time – Arrival Time.
  • Waiting Time(W.T): It measures the time difference between turnaround time and burst time. As a result, Waiting Time = Turn Around Time – Burst Time

Code Sample

The following code demonstrates how Round Robin Scheduling Algorithm works in Java.

import java.util.Scanner;
public class RoundRobinExample {
    public static void main(String args[]) {
        int n,x,q_t,count=0,temp,sq=0,b_t[],w_t[],ta_t[],rem_bt[];
        float aw_t=0,ata_t=0;
        b_t = new int[10];
        w_t = new int[10];
        ta_t = new int[10];
        rem_bt = new int[10];
        Scanner sc=new Scanner(System.in);
        System.out.print("Number of processes(maximum 10) = ");
        n = sc.nextInt();
        System.out.print("Enter process burst time\n");
        for (x=0; x<n; x++) {
            System.out.print("P"+x+" = ");
            b_t[x] = sc.nextInt();
            rem_bt[x] = b_t[x];
        }
        System.out.print("Enter the quantum time: ");
        q_t = sc.nextInt();
        while(true) {
            for (x=0,count=0; x<n; x++) {
                temp = q_t;
                if(rem_bt[x] == 0) {
                    count++;
                    continue;
                }
                if(rem_bt[x]>q_t)
                    rem_bt[x]= rem_bt[x] - q_t;
                else if(rem_bt[x]>=0) {
                    temp = rem_bt[x];
                    rem_bt[x] = 0;
                }
                sq = sq + temp;
                ta_t[x] = sq;
            }
            if(n == count)
                break;
        }
        System.out.print("*********************************************************************************");
        System.out.print("\nProcess\t      Burst Time\t       Turnaround Time\t          Waiting Time\n");
        System.out.print("*********************************************************************************");
        for(x=0; x<n; x++) {
            w_t[x]=ta_t[x]-b_t[x];
            aw_t=aw_t+w_t[x];
            ata_t=ata_t+ta_t[x];
            System.out.print3("\n "+(x+1)+"\t "+b_t[x]+"\t\t "+ta_t[x]+"\t\t "+w_t[x]+"\n");
        }
        aw_t=aw_t/n;
        ata_t=ata_t/n;
        System.out.println("\nThe Average waiting Time = "+aw_t+"\n");
        System.out.println("The Average turnaround time = "+ata_t);
    }
}
Output

Number of processes (maximum 10) = 4
Enter the burst time of the process
P0 = 1
P1 = 2
P2 = 3
P3 = 6
Enter the quantum time: 8
*********************************************************************************Process   Burst Time Turnaround Time Waiting Time
*********************************************************************************
 1 1 1     0

 2 2 3 1

 3 3 6 3

 4 6 12 6
The Average waiting Time = 2.5

The Average turnaround time = 5.5


write your code here: Coding Playground