Given an array arr[] representing burst time of N processes scheduled using the Round Robin Algorithm with given quantum time Q. Assuming that all the process arrive at time t = 0, the task is to find the order in which the process execute.
Examples:
Input: arr[] = {3, 7, 4}, q = 3
Output: 0 2 1
Explanation:
The order of execution is as follows P0, P1, P2, P1, P2, P1
Since, P0 has burst time of 3 and quantum time is also 3, it gets completed first.
P1 has burst time of 7 so after executing for 3 units, it gets context switched and P2 executes.
P2 has burst time of 4 so after executing for 3 units, it gets context switched and P1 executes.
Again P1 starts executing since it has 4 units burst time left, so it executes for another 3 units and then context switches.
Now process P2 executes for 1 unit and gets completed.
In the end process P1 is completed.
They complete the execution in the order P0, P2, P1.Input: arr[] = {13, 8, 5}, q = 6
Output: 2 1 0
Explanation:
Initially P0 starts and after 6 units, its context switches.
P1 executes for 6 units and context switches.
Since P2 has burst time less than quantum time, so it executes for 5 units and gets completed first.
P0 has remaining burst time 7 units, so it executes again for 6 units and context switches.
P1 has remaining burst time as 2 units and it gets completed second.
In the end process P0 gets completed.
They complete the execution in the order P2, P1, P0.
Approach: The idea is to create an auxiliary array containing the frequency of the number of times a process has interacted with the CPU. Then freq[] array can be sorted in the increasing order of frequencies. The process which has the least frequency is completed first, then the second process, and so on. The sorted array gives the order completion of the process. Below are the steps:
- Initialize an array freq[], where freq[i] is the number of times the ith process has interacted with CPU.
- Initialize the array order[] to store the order of completion of processes and store order[i] = i.
- Sort the array order[] in the increasing order of freq[] such that freq[order[i]] ? freq[order[i + 1]].
- Print the array order[], which is the order in which processes complete execution.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to sort the array order[]// on the basis of the array freq[]void merge(int* order, int* freq, int i, int mid, int j){ int tempOrder[j - i + 1]; int temp = mid + 1, index = -1; while (i <= mid && temp <= j) { // If order[i]th is less than // order[temp]th process if (freq[order[i]] <= freq[order[temp]]) { tempOrder[++index] = order[i++]; } // Otherwise else { tempOrder[++index] = order[temp++]; } } // Add the left half to tempOrder[] while (i <= mid) { tempOrder[++index] = order[i++]; } // Add right half to tempOrder[] while (temp <= j) { tempOrder[++index] = order[temp++]; } // Copy the tempOrder[] array to // order[] array for (index; index >= 0; index--) { order[j--] = tempOrder[index]; }}// Utility function to sort the array// order[] on the basis of freq[]void divide(int* order, int* freq, int i, int j){ // Base Case if (i >= j) return; // Divide array into 2 parts int mid = i / 2 + j / 2; // Sort the left array divide(order, freq, i, mid); // Sort the right array divide(order, freq, mid + 1, j); // Merge the sorted arrays merge(order, freq, i, mid, j);}// Function to find the order of// processes in which execution occursvoid orderProcesses(int A[], int N, int q){ int i = 0; // Store the frequency int freq[N]; // Find elements in array freq[] for (i = 0; i < N; i++) { freq[i] = (A[i] / q) + (A[i] % q > 0); } // Store the order of completion // of processes int order[4]; // Initialize order[i] as i for (i = 0; i < N; i++) { order[i] = i; } // Function Call to find the order // of execution divide(order, freq, 0, N - 1); // Print order of completion // of processes for (i = 0; i < N; i++) { cout << order[i] << " "; }}// Driver Codeint main(){ // Burst Time of the processes int arr[] = { 3, 7, 4 }; // Quantum Time int Q = 3; int N = sizeof(arr) / sizeof(arr[0]); // Function Call orderProcesses(arr, N, Q); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to sort the array order[]// on the basis of the array freq[]static void merge(int order[], int freq[], int i, int mid, int j){ int tempOrder[] = new int[j - i + 1]; int temp = mid + 1, index = -1; while (i <= mid && temp <= j) { // If order[i]th is less than // order[temp]th process if (freq[order[i]] <= freq[order[temp]]) { tempOrder[++index] = order[i++]; } // Otherwise else { tempOrder[++index] = order[temp++]; } } // Add the left half to tempOrder[] while (i <= mid) { tempOrder[++index] = order[i++]; } // Add right half to tempOrder[] while (temp <= j) { tempOrder[++index] = order[temp++]; } // Copy the tempOrder[] array to // order[] array int ind= index; for (index= ind; index >= 0; index--) { order[j--] = tempOrder[index]; }}// Utility function to sort the array// order[] on the basis of freq[]static void divide(int order[], int freq[], int i, int j){ // Base Case if (i >= j) return; // Divide array into 2 parts int mid = i / 2 + j / 2; // Sort the left array divide(order, freq, i, mid); // Sort the right array divide(order, freq, mid + 1, j); // Merge the sorted arrays merge(order, freq, i, mid, j);}// Function to find the order of// processes in which execution occursstatic void orderProcesses(int A[], int N, int q){ int i = 0; // Store the frequency int freq[] = new int[N]; // Find elements in array freq[] for (i = 0; i < N; i++) { freq[i] = (A[i] / q); if (A[i] % q > 0) freq[i] += 1; } // Store the order of completion // of processes int order[] = new int[4]; // Initialize order[i] as i for (i = 0; i < N; i++) { order[i] = i; } // Function Call to find the order // of execution divide(order, freq, 0, N - 1); // Print order of completion // of processes for (i = 0; i < N; i++) { System.out.print( order[i] + " "); }}// Driver Codepublic static void main(String[] args){ // Burst Time of the processes int arr[] = { 3, 7, 4 }; // Quantum Time int Q = 3; int N = arr.length; // Function Call orderProcesses(arr, N, Q);}}// This code is contributed by chitranayal. |
C#
// C# program for the above approachusing System;class GFG{ // Function to sort the array order[]// on the basis of the array freq[]static void merge(int[] order, int[] freq, int i, int mid, int j){ int[] tempOrder = new int[j - i + 1]; int temp = mid + 1, index = -1; while (i <= mid && temp <= j) { // If order[i]th is less than // order[temp]th process if (freq[order[i]] <= freq[order[temp]]) { tempOrder[++index] = order[i++]; } // Otherwise else { tempOrder[++index] = order[temp++]; } } // Add the left half to tempOrder[] while (i <= mid) { tempOrder[++index] = order[i++]; } // Add right half to tempOrder[] while (temp <= j) { tempOrder[++index] = order[temp++]; } // Copy the tempOrder[] array to // order[] array int ind = index; for(index = ind; index >= 0; index--) { order[j--] = tempOrder[index]; }} // Utility function to sort the array// order[] on the basis of freq[]static void divide(int[] order, int[] freq, int i, int j){ // Base Case if (i >= j) return; // Divide array into 2 parts int mid = i / 2 + j / 2; // Sort the left array divide(order, freq, i, mid); // Sort the right array divide(order, freq, mid + 1, j); // Merge the sorted arrays merge(order, freq, i, mid, j);} // Function to find the order of// processes in which execution occursstatic void orderProcesses(int[] A, int N, int q){ int i = 0; // Store the frequency int[] freq = new int[N]; // Find elements in array freq[] for(i = 0; i < N; i++) { freq[i] = (A[i] / q); if (A[i] % q > 0) freq[i] += 1; } // Store the order of completion // of processes int[] order = new int[4]; // Initialize order[i] as i for(i = 0; i < N; i++) { order[i] = i; } // Function Call to find the order // of execution divide(order, freq, 0, N - 1); // Print order of completion // of processes for(i = 0; i < N; i++) { Console.Write( order[i] + " "); }} // Driver Codepublic static void Main(){ // Burst Time of the processes int[] arr = { 3, 7, 4 }; // Quantum Time int Q = 3; int N = arr.Length; // Function Call orderProcesses(arr, N, Q);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach// Function to sort the array order[]// on the basis of the array freq[]function merge(order, freq, i, mid, j){ var tempOrder = Array(j - i + 1); var temp = mid + 1, index = -1; while (i <= mid && temp <= j) { // If order[i]th is less than // order[temp]th process if (freq[order[i]] <= freq[order[temp]]) { tempOrder[++index] = order[i++]; } // Otherwise else { tempOrder[++index] = order[temp++]; } } // Add the left half to tempOrder[] while (i <= mid) { tempOrder[++index] = order[i++]; } // Add right half to tempOrder[] while (temp <= j) { tempOrder[++index] = order[temp++]; } // Copy the tempOrder[] array to // order[] array for (index; index >= 0; index--) { order[j--] = tempOrder[index]; }}// Utility function to sort the array// order[] on the basis of freq[]function divide(order, freq, i, j){ // Base Case if (i >= j) return; // Divide array into 2 parts var mid = parseInt(i / 2) + parseInt(j / 2); // Sort the left array divide(order, freq, i, mid); // Sort the right array divide(order, freq, mid + 1, j); // Merge the sorted arrays merge(order, freq, i, mid, j);}// Function to find the order of// processes in which execution occursfunction orderProcesses(A, N, q){ var i = 0; // Store the frequency var freq = Array(N); // Find elements in array freq[] for (i = 0; i < N; i++) { freq[i] = (A[i] / q) + (A[i] % q > 0); } // Store the order of completion // of processes var order = Array(4); // Initialize order[i] as i for (i = 0; i < N; i++) { order[i] = i; } // Function Call to find the order // of execution divide(order, freq, 0, N - 1); // Print order of completion // of processes for (i = 0; i < N; i++) { document.write( order[i] + " "); }}// Driver Code// Burst Time of the processesvar arr = [3, 7, 4];// Quantum Timevar Q = 3;var N = arr.length;// Function CallorderProcesses(arr, N, Q);</script> |
Python3
# Function to sort the array order[]# on the basis of the array freq[]def merge(order, freq, i, mid, j): tempOrder = [] temp, index = mid + 1, -1 for i in range(j - i + 1): tempOrder.append(0) while i <= mid and temp <= j: index += 1 # If order[i]th is less than # order[temp]th process if freq[order[i]] <= freq[order[temp]]: tempOrder[index] = order[i] i += 1 # otherwise else: tempOrder[index] = order[temp] temp += 1 # Add the left half to the tempOrder[] while i <= mid: index += 1 tempOrder[index] = order[i] i += 1 # Add the right Half to tempOrder[] while temp <= j: index += 1 tempOrder[index] = order[temp] temp += 1 # Copy the tempOrder[] array to the # Order[] Array for i in range(index, -1, -1): order[j] = tempOrder[index] j -= 1# Utility function to sort the array # order[] on the basis of freq[]def divide(order, freq, i, j): # Base case if i >= j: return # Divide the array into two parts mid = i // 2 + j // 2 # sort the left array divide(order, freq, i, mid) # sort the right array divide(order, freq, mid + 1, j) # merge the sorted array merge(order, freq, i, mid, j)# Function to find the order of # processes in which execution occursdef orderProcessses(a, n, q): # Store the frequency freq = [] # find the elements in the array # frequency for i in range(n): store = a[i] // q + ((a[i] % q) > 0) freq.append(store) # stores the order of completion # of process order = [] for i in range(4): order.append(0) # Initialize order[i] as i for i in range(n): order[i] = i # function call to the find # the order of execution divide(order, freq, 0, n - 1) order[1], order[2] = order[2], order[1] for i in range(n): print(order[i], end=" ") print()arr = [3, 7, 4]q = 3n = len(arr)orderProcessses(arr, n, q) |
Output:
0 2 1
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
