Round Robin es un algoritmo de programación de CPU en el que a cada proceso se le asigna un intervalo de tiempo fijo de forma cíclica. Es básicamente la versión preventiva del algoritmo de programación de CPU por orden de llegada .
- El algoritmo de CPU Round Robin generalmente se enfoca en la técnica de tiempo compartido.
- El período de tiempo durante el cual se permite que un proceso o trabajo se ejecute en un método preventivo se denomina cantidad de tiempo .
- A cada proceso o trabajo presente en la cola de espera se le asigna la CPU para ese tiempo, si la ejecución del proceso se completa durante ese tiempo, el proceso finalizará ; de lo contrario, el proceso volverá a la mesa de espera y esperará el siguiente . gire para completar la ejecución.
Características del algoritmo de programación de CPU Round Robin:
- Es simple, fácil de implementar y libre de hambre, ya que todos los procesos obtienen una parte justa de la CPU.
- Una de las técnicas más utilizadas en la programación de CPU como núcleo.
- Es preventivo ya que a los procesos se les asigna CPU solo durante un período de tiempo fijo como máximo.
- La desventaja de esto es más gastos generales de cambio de contexto.
Ventajas del algoritmo de programación de CPU Round Robin:
- Hay equidad ya que cada proceso obtiene la misma parte de la CPU.
- El proceso recién creado se agrega al final de la cola lista.
- Un planificador de turnos generalmente emplea el tiempo compartido, dando a cada trabajo un intervalo de tiempo o cantidad.
- Al realizar una programación por turnos, se asigna una cantidad de tiempo particular a diferentes trabajos.
- Cada proceso tiene la oportunidad de reprogramarse después de un tiempo cuántico particular en esta programación.
Desventajas del algoritmo de programación de CPU Round Robin:
- Hay mayor tiempo de espera y tiempo de respuesta.
- Hay un rendimiento bajo.
- Hay cambios de contexto.
- El diagrama de Gantt parece ser demasiado grande (si el tiempo cuántico es menor para la programación. Por ejemplo: 1 ms para una programación grande).
- Programación que requiere mucho tiempo para pequeños cuantos.
Ejemplos para mostrar el funcionamiento del algoritmo de programación Round Robin :
Ejemplo-1: considere la siguiente tabla de tiempo de llegada y tiempo de ráfaga para cinco procesos P1, P2, P3 y P4 y dado Time Quantum = 2
C++
// C++ program for implementation of RR scheduling #include<iostream> using namespace std; // Function to find the waiting time for all // processes void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum) { // Make a copy of burst times bt[] to store remaining // burst times. int rem_bt[n]; for (int i = 0 ; i < n ; i++) rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round robin manner // until all of them are not done. while (1) { bool done = true; // Traverse all processes one by one repeatedly for (int i = 0 ; i < n; i++) { // If burst time of a process is greater than 0 // then only need to process further if (rem_bt[i] > 0) { done = false; // There is a pending process if (rem_bt[i] > quantum) { // Increase the value of t i.e. shows // how much time a process has been processed t += quantum; // Decrease the burst_time of current process // by quantum rem_bt[i] -= quantum; } // If burst time is smaller than or equal to // quantum. Last cycle for this process else { // Increase the value of t i.e. shows // how much time a process has been processed t = t + rem_bt[i]; // Waiting time is current time minus time // used by this process wt[i] = t - bt[i]; // As the process gets fully executed // make its remaining burst time = 0 rem_bt[i] = 0; } } } // If all processes are done if (done == true) break; } } // Function to calculate turn around time void findTurnAroundTime(int processes[], int n, int bt[], int wt[], int tat[]) { // calculating turnaround time by adding // bt[i] + wt[i] for (int i = 0; i < n ; i++) tat[i] = bt[i] + wt[i]; } // Function to calculate average time void findavgTime(int processes[], int n, int bt[], int quantum) { int wt[n], tat[n], total_wt = 0, total_tat = 0; // Function to find waiting time of all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with all details cout << "PN\t "<< " \tBT " << " WT " << " \tTAT\n"; // Calculate total waiting time and total turn // around time for (int i=0; i<n; i++) { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; cout << " " << i+1 << "\t\t" << bt[i] <<"\t " << wt[i] <<"\t\t " << tat[i] <<endl; } cout << "Average waiting time = " << (float)total_wt / (float)n; cout << "\nAverage turn around time = " << (float)total_tat / (float)n; } // Driver code int main() { // process id's int processes[] = { 1, 2, 3}; int n = sizeof processes / sizeof processes[0]; // Burst time of all processes int burst_time[] = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); return 0; }
Java
// Java program for implementation of RR scheduling public class GFG { // Method to find the waiting time for all // processes static void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum) { // Make a copy of burst times bt[] to store remaining // burst times. int rem_bt[] = new int[n]; for (int i = 0 ; i < n ; i++) rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round robin manner // until all of them are not done. while(true) { boolean done = true; // Traverse all processes one by one repeatedly for (int i = 0 ; i < n; i++) { // If burst time of a process is greater than 0 // then only need to process further if (rem_bt[i] > 0) { done = false; // There is a pending process if (rem_bt[i] > quantum) { // Increase the value of t i.e. shows // how much time a process has been processed t += quantum; // Decrease the burst_time of current process // by quantum rem_bt[i] -= quantum; } // If burst time is smaller than or equal to // quantum. Last cycle for this process else { // Increase the value of t i.e. shows // how much time a process has been processed t = t + rem_bt[i]; // Waiting time is current time minus time // used by this process wt[i] = t - bt[i]; // As the process gets fully executed // make its remaining burst time = 0 rem_bt[i] = 0; } } } // If all processes are done if (done == true) break; } } // Method to calculate turn around time static void findTurnAroundTime(int processes[], int n, int bt[], int wt[], int tat[]) { // calculating turnaround time by adding // bt[i] + wt[i] for (int i = 0; i < n ; i++) tat[i] = bt[i] + wt[i]; } // Method to calculate average time static void findavgTime(int processes[], int n, int bt[], int quantum) { int wt[] = new int[n], tat[] = new int[n]; int total_wt = 0, total_tat = 0; // Function to find waiting time of all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with all details System.out.println("PN " + " B " + " WT " + " TAT"); // Calculate total waiting time and total turn // around time for (int i=0; i<n; i++) { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; System.out.println(" " + (i+1) + "\t\t" + bt[i] +"\t " + wt[i] +"\t\t " + tat[i]); } System.out.println("Average waiting time = " + (float)total_wt / (float)n); System.out.println("Average turn around time = " + (float)total_tat / (float)n); } // Driver Method public static void main(String[] args) { // process id's int processes[] = { 1, 2, 3}; int n = processes.length; // Burst time of all processes int burst_time[] = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); } }
Python3
# Python3 program for implementation of # RR scheduling # Function to find the waiting time # for all processes def findWaitingTime(processes, n, bt, wt, quantum): rem_bt = [0] * n # Copy the burst time into rt[] for i in range(n): rem_bt[i] = bt[i] t = 0 # Current time # Keep traversing processes in round # robin manner until all of them are # not done. while(1): done = True # Traverse all processes one by # one repeatedly for i in range(n): # If burst time of a process is greater # than 0 then only need to process further if (rem_bt[i] > 0) : done = False # There is a pending process if (rem_bt[i] > quantum) : # Increase the value of t i.e. shows # how much time a process has been processed t += quantum # Decrease the burst_time of current # process by quantum rem_bt[i] -= quantum # If burst time is smaller than or equal # to quantum. Last cycle for this process else: # Increase the value of t i.e. shows # how much time a process has been processed t = t + rem_bt[i] # Waiting time is current time minus # time used by this process wt[i] = t - bt[i] # As the process gets fully executed # make its remaining burst time = 0 rem_bt[i] = 0 # If all processes are done if (done == True): break # Function to calculate turn around time def findTurnAroundTime(processes, n, bt, wt, tat): # Calculating turnaround time for i in range(n): tat[i] = bt[i] + wt[i] # Function to calculate average waiting # and turn-around times. def findavgTime(processes, n, bt, quantum): wt = [0] * n tat = [0] * n # Function to find waiting time # of all processes findWaitingTime(processes, n, bt, wt, quantum) # Function to find turn around time # for all processes findTurnAroundTime(processes, n, bt, wt, tat) # Display processes along with all details print("Processes Burst Time Waiting", "Time Turn-Around Time") total_wt = 0 total_tat = 0 for i in range(n): total_wt = total_wt + wt[i] total_tat = total_tat + tat[i] print(" ", i + 1, "\t\t", bt[i], "\t\t", wt[i], "\t\t", tat[i]) print("\nAverage waiting time = %.5f "%(total_wt /n) ) print("Average turn around time = %.5f "% (total_tat / n)) # Driver code if __name__ =="__main__": # Process id's proc = [1, 2, 3] n = 3 # Burst time of all processes burst_time = [10, 5, 8] # Time quantum quantum = 2; findavgTime(proc, n, burst_time, quantum) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program for implementation of RR // scheduling using System; public class GFG { // Method to find the waiting time // for all processes static void findWaitingTime(int []processes, int n, int []bt, int []wt, int quantum) { // Make a copy of burst times bt[] to // store remaining burst times. int []rem_bt = new int[n]; for (int i = 0 ; i < n ; i++) rem_bt[i] = bt[i]; int t = 0; // Current time // Keep traversing processes in round // robin manner until all of them are // not done. while(true) { bool done = true; // Traverse all processes one by // one repeatedly for (int i = 0 ; i < n; i++) { // If burst time of a process // is greater than 0 then only // need to process further if (rem_bt[i] > 0) { // There is a pending process done = false; if (rem_bt[i] > quantum) { // Increase the value of t i.e. // shows how much time a process // has been processed t += quantum; // Decrease the burst_time of // current process by quantum rem_bt[i] -= quantum; } // If burst time is smaller than // or equal to quantum. Last cycle // for this process else { // Increase the value of t i.e. // shows how much time a process // has been processed t = t + rem_bt[i]; // Waiting time is current // time minus time used by // this process wt[i] = t - bt[i]; // As the process gets fully // executed make its remaining // burst time = 0 rem_bt[i] = 0; } } } // If all processes are done if (done == true) break; } } // Method to calculate turn around time static void findTurnAroundTime(int []processes, int n, int []bt, int []wt, int []tat) { // calculating turnaround time by adding // bt[i] + wt[i] for (int i = 0; i < n ; i++) tat[i] = bt[i] + wt[i]; } // Method to calculate average time static void findavgTime(int []processes, int n, int []bt, int quantum) { int []wt = new int[n]; int []tat = new int[n]; int total_wt = 0, total_tat = 0; // Function to find waiting time of // all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time // for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with // all details Console.WriteLine("Processes " + " Burst time " + " Waiting time " + " Turn around time"); // Calculate total waiting time and total turn // around time for (int i = 0; i < n; i++) { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; Console.WriteLine(" " + (i+1) + "\t\t" + bt[i] + "\t " + wt[i] +"\t\t " + tat[i]); } Console.WriteLine("Average waiting time = " + (float)total_wt / (float)n); Console.Write("Average turn around time = " + (float)total_tat / (float)n); } // Driver Method public static void Main() { // process id's int []processes = { 1, 2, 3}; int n = processes.Length; // Burst time of all processes int []burst_time = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); } } // This code is contributed by nitin mittal.
Javascript
<script> // JavaScript program for implementation of RR scheduling // Function to find the waiting time for all // processes const findWaitingTime = (processes, n, bt, wt, quantum) => { // Make a copy of burst times bt[] to store remaining // burst times. let rem_bt = new Array(n).fill(0); for (let i = 0; i < n; i++) rem_bt[i] = bt[i]; let t = 0; // Current time // Keep traversing processes in round robin manner // until all of them are not done. while (1) { let done = true; // Traverse all processes one by one repeatedly for (let i = 0; i < n; i++) { // If burst time of a process is greater than 0 // then only need to process further if (rem_bt[i] > 0) { done = false; // There is a pending process if (rem_bt[i] > quantum) { // Increase the value of t i.e. shows // how much time a process has been processed t += quantum; // Decrease the burst_time of current process // by quantum rem_bt[i] -= quantum; } // If burst time is smaller than or equal to // quantum. Last cycle for this process else { // Increase the value of t i.e. shows // how much time a process has been processed t = t + rem_bt[i]; // Waiting time is current time minus time // used by this process wt[i] = t - bt[i]; // As the process gets fully executed // make its remaining burst time = 0 rem_bt[i] = 0; } } } // If all processes are done if (done == true) break; } } // Function to calculate turn around time const findTurnAroundTime = (processes, n, bt, wt, tat) => { // calculating turnaround time by adding // bt[i] + wt[i] for (let i = 0; i < n; i++) tat[i] = bt[i] + wt[i]; } // Function to calculate average time const findavgTime = (processes, n, bt, quantum) => { let wt = new Array(n).fill(0), tat = new Array(n).fill(0); let total_wt = 0, total_tat = 0; // Function to find waiting time of all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with all details document.write(`Processes Burst time Waiting time Turn around time<br/>`); // Calculate total waiting time and total turn // around time for (let i = 0; i < n; i++) { total_wt = total_wt + wt[i]; total_tat = total_tat + tat[i]; document.write(`${i + 1} ${bt[i]} ${wt[i]} ${tat[i]}<br/>`); } document.write(`Average waiting time = ${total_wt / n}`); document.write(`<br/>Average turn around time = ${total_tat / n}`); } // Driver code // process id's processes = [1, 2, 3]; let n = processes.length; // Burst time of all processes let burst_time = [10, 5, 8]; // Time quantum let quantum = 2; findavgTime(processes, n, burst_time, quantum); // This code is contributed by rakeshsahni </script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA