Programa para la programación de Round Robin | Serie 1

 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *