Programación de CPU con la relación de respuesta más alta siguiente (HRRN) – Part 1

Dados N procesos con sus tiempos de llegada y tiempos de ráfaga , la tarea es encontrar el tiempo de espera promedio y el tiempo de respuesta promedio utilizando el algoritmo de programación HRRN. 

El propio nombre indica que necesitamos encontrar la relación de respuesta de todos los procesos disponibles y seleccionar el que tenga la relación de respuesta más alta. Un proceso una vez seleccionado se ejecutará hasta su finalización.

Características de la programación de CPU HRRN:

• Ratio de respuesta más alto Next es un algoritmo de programación de CPU no preventivo y se considera uno de los algoritmos de programación más óptimos.
• El criterio para HRRN es el índice de respuesta y el modo es no preventivo. 
• HRRN se considera básicamente como la modificación de Shortest Job First para reducir el problema del hambre .
• En comparación con SJF, durante el algoritmo de programación HRRN, la CPU se asigna al siguiente proceso que tiene la tasa de respuesta más alta y no al proceso que tiene menos tiempo de ráfaga.

 Relación de respuesta = (W + S)/S

Aquí, W es el tiempo de espera del proceso hasta el momento y S es el tiempo de ráfaga del proceso.

Ventajas de la programación de CPU HRRN

• El algoritmo de programación HRRN generalmente brinda un mejor rendimiento que la programación inicial del trabajo más corto .
• Hay una reducción en el tiempo de espera para trabajos más largos y también fomenta trabajos más cortos.

Desventajas de la programación de CPU HRRN

• La implementación sobre el terreno de la programación HRRN no es posible ya que no es posible conocer el tiempo de ráfaga de cada trabajo por adelantado.
• En esta programación, puede ocurrir una sobrecarga en la CPU.

Desempeño de HRRN –  

• Se favorecen los procesos más cortos.
• El envejecimiento sin servicio aumenta la proporción, los trabajos más largos pueden superar a los trabajos más cortos.

Consideremos los siguientes ejemplos. 

Ejemplo-1: considere la siguiente tabla de tiempo de llegada y tiempo de ráfaga para cuatro procesos P1, P2, P3, P4 y P5.  

El siguiente algoritmo de programación de CPU con la relación de respuesta más alta funcionará según los pasos que se mencionan a continuación:

En el tiempo= 0,

• Procesos disponibles: P1, por lo tanto, P1 comienza a ejecutarse hasta su finalización.

En el tiempo = 2,

• Procesos Disponibles: P1, P2
• Pero P1 sigue ejecutándose ya que HRRN es un algoritmo no preventivo y, por lo tanto, terminará su ejecución.

En el tiempo = 3,

• El proceso P1 termina su ejecución
• El proceso P2 comienza a ejecutarse ya que es el único proceso disponible.

En el tiempo = 4,

• Llega el proceso P3 y espera a que se ejecute el proceso P2
• El proceso P2 continúa su ejecución

En el tiempo = 6,

• Llega el proceso P4 y espera a que se ejecute el proceso P2

En el tiempo = 8,

• Llega el proceso P5 y espera su ejecución en la cola de listos

En el tiempo = 9,

• El proceso P2 completa su ejecución 
• Ahora hay 3 procesos disponibles, P3, P4 y P5. Ya que, P3, P4, P5 estuvieron disponibles después de 4, 6 y 8 unidades respectivamente.
• Por lo tanto, el tiempo de espera para P3, P4 y P5 es (9 – 4 =)5, (9 – 6 =)3 y (9 – 8 =)1 unidad respectivamente.
• Usando la fórmula dada arriba, (Relación de Respuesta = (W + S)/S) calcule las Relaciones de Respuesta de P3, P4 y P5 respectivamente como 2.25, 1.6 y 1.5.
• Claramente, P3 tiene la tasa de respuesta más alta y, por lo tanto, se programa

En el tiempo = 13,

• Procesos Disponibles: P4 y P5
• Las proporciones de respuesta de P4 y P5 son 2,4 y 3,5 respectivamente utilizando la fórmula anterior.
• Claramente, P5 tiene la tasa de respuesta más alta y, por lo tanto, se programa

En el tiempo = 15,

• Después de completar el proceso P5, el proceso P4 se selecciona por fin y se ejecuta hasta que finaliza

En el tiempo = 20,

• El proceso P4 terminará su ejecución.
• La ejecución global de los procesos será como se muestra a continuación:

Gráfico de gantt – 

Dado que el tiempo de finalización (CT) se puede determinar directamente mediante el diagrama de Gantt, y  

Tiempo de vuelta (TAT)
= (Tiempo de finalización) – (Hora de llegada)

Además, Tiempo de espera (WT)
= (Tiempo de respuesta) – (Tiempo de ráfaga) 

Por lo tanto, la mesa final parece,  

Producción:  

Tiempo de respuesta total = 40 ms
Entonces, Tiempo de respuesta promedio = 40/4 = 10,00 ms

Y, Tiempo total de espera = 20 ms
Entonces, Tiempo promedio de espera = 20/4 = 5,00 ms 

Implementación de Programación HRRN –  

• Ingrese el número de procesos, sus tiempos de llegada y tiempos de ráfaga.
• Ordenarlos de acuerdo a sus tiempos de llegada.
• En cada momento calcule los ratios de respuesta y seleccione el proceso adecuado a programar.
• Calcule el tiempo de vuelta como tiempo de finalización – tiempo de llegada.
• Calcule el tiempo de espera como tiempo de respuesta – tiempo de ráfaga.
• El tiempo de respuesta dividido por el tiempo de ráfaga da el tiempo de respuesta normalizado.
• Sume los tiempos de espera y respuesta de todos los procesos y divídalos por la cantidad de procesos para obtener el tiempo promedio de espera y respuesta.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for Highest Response Ratio Next (HRRN)
// Scheduling
#include <bits/stdc++.h>
using namespace std;
// Defining process details
struct process {
    char name;
    int at, bt, ct, wt, tt;
    int completed;
    float ntt;
} p[10];
 
int n;
 
// Sorting Processes by Arrival Time
void sortByArrival()
{
    struct process temp;
    int i, j;
 
    // Selection Sort applied
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
 
            // Check for lesser arrival time
            if (p[i].at > p[j].at) {
 
                // Swap earlier process to front
                temp = p[i];
                p[i] = p[j];
                p[j] = temp;
            }
        }
    }
}
 
int main()
{
    int i, j, t, sum_bt = 0;
    char c;
    float avgwt = 0, avgtt = 0;
    n = 5;
 
    // predefined arrival times
    int arriv[] = { 0, 2, 4, 6, 8 };
 
    // predefined burst times
    int burst[] = { 3, 6, 4, 5, 2 };
 
    // Initializing the structure variables
    for (i = 0, c = 'A'; i < n; i++, c++) {
        p[i].name = c;
        p[i].at = arriv[i];
        p[i].bt = burst[i];
 
        // Variable for Completion status
        // Pending = 0
        // Completed = 1
        p[i].completed = 0;
 
        // Variable for sum of all Burst Times
        sum_bt += p[i].bt;
    }
 
    // Sorting the structure by arrival times
    sortByArrival();
    cout << "PN\tAT\tBT\tWT\tTAT\tNTT";
    for (t = p[0].at; t < sum_bt;) {
 
        // Set lower limit to response ratio
        float hrr = -9999;
 
        // Response Ratio Variable
        float temp;
 
        // Variable to store next process selected
        int loc;
        for (i = 0; i < n; i++) {
 
            // Checking if process has arrived and is
            // Incomplete
            if (p[i].at <= t && p[i].completed != 1) {
 
                // Calculating Response Ratio
                temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
 
                // Checking for Highest Response Ratio
                if (hrr < temp) {
 
                    // Storing Response Ratio
                    hrr = temp;
 
                    // Storing Location
                    loc = i;
                }
            }
        }
 
        // Updating time value
        t += p[loc].bt;
 
        // Calculation of waiting time
        p[loc].wt = t - p[loc].at - p[loc].bt;
 
        // Calculation of Turn Around Time
        p[loc].tt = t - p[loc].at;
 
        // Sum Turn Around Time for average
        avgtt += p[loc].tt;
 
        // Calculation of Normalized Turn Around Time
        p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
 
        // Updating Completion Status
        p[loc].completed = 1;
 
        // Sum Waiting Time for average
        avgwt += p[loc].wt;
        cout << "\n" << p[loc].name << "\t" << p[loc].at;
        cout << "\t" << p[loc].bt << "\t" << p[loc].wt;
        cout << "\t" << p[loc].tt << "\t" << p[loc].ntt;
    }
    cout << "\nAverage waiting time: " << avgwt / n << endl;
    cout << "Average Turn Around time:" << avgtt / n;
}
// This code is contributed by shivi_Aggarwal

// C program for Highest Response Ratio Next (HRRN) Scheduling
#include <stdio.h>
 
// Defining process details
struct process {
    char name;
    int at, bt, ct, wt, tt;
    int completed;
    float ntt;
} p[10];
 
int n;
 
// Sorting Processes by Arrival Time
void sortByArrival()
{
    struct process temp;
    int i, j;
 
    // Selection Sort applied
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
 
            // Check for lesser arrival time
            if (p[i].at > p[j].at) {
 
                // Swap earlier process to front
                temp = p[i];
                p[i] = p[j];
                p[j] = temp;
            }
        }
    }
}
 
void main()
{
    int i, j, t, sum_bt = 0;
    char c;
    float avgwt = 0, avgtt = 0;
    n = 5;
 
    // predefined arrival times
    int arriv[] = { 0, 2, 4, 6, 8 };
 
    // predefined burst times
    int burst[] = { 3, 6, 4, 5, 2 };
 
    // Initializing the structure variables
    for (i = 0, c = 'A'; i < n; i++, c++) {
        p[i].name = c;
        p[i].at = arriv[i];
        p[i].bt = burst[i];
 
        // Variable for Completion status
        // Pending = 0
        // Completed = 1
        p[i].completed = 0;
 
        // Variable for sum of all Burst Times
        sum_bt += p[i].bt;
    }
 
    // Sorting the structure by arrival times
    sortByArrival();
    printf("\nName\tArrival Time\tBurst Time\tWaiting Time");
    printf("\tTurnAround Time\t Normalized TT");
    for (t = p[0].at; t < sum_bt;) {
 
        // Set lower limit to response ratio
        float hrr = -9999;
 
        // Response Ratio Variable
        float temp;
 
        // Variable to store next process selected
        int loc;
        for (i = 0; i < n; i++) {
 
            // Checking if process has arrived and is Incomplete
            if (p[i].at <= t && p[i].completed != 1) {
 
                // Calculating Response Ratio
                temp = (p[i].bt + (t - p[i].at)) / p[i].bt;
 
                // Checking for Highest Response Ratio
                if (hrr < temp) {
 
                    // Storing Response Ratio
                    hrr = temp;
 
                    // Storing Location
                    loc = i;
                }
            }
        }
 
        // Updating time value
        t += p[loc].bt;
 
        // Calculation of waiting time
        p[loc].wt = t - p[loc].at - p[loc].bt;
 
        // Calculation of Turn Around Time
        p[loc].tt = t - p[loc].at;
 
        // Sum Turn Around Time for average
        avgtt += p[loc].tt;
 
        // Calculation of Normalized Turn Around Time
        p[loc].ntt = ((float)p[loc].tt / p[loc].bt);
 
        // Updating Completion Status
        p[loc].completed = 1;
 
        // Sum Waiting Time for average
        avgwt += p[loc].wt;
        printf("\n%c\t\t%d\t\t", p[loc].name, p[loc].at);
        printf("%d\t\t%d\t\t", p[loc].bt, p[loc].wt);
        printf("%d\t\t%f", p[loc].tt, p[loc].ntt);
    }
    printf("\nAverage waiting time:%f\n", avgwt / n);
    printf("Average Turn Around time:%f\n", avgtt / n);
}

# Python3 program for Highest Response Ratio
# Next (HRRN) Scheduling
 
# Function to sort process by arrival time
def sortByArrival(at, n):
     
    # Selection Sort applied 
    for i in range(0, n - 1):
        for j in range(i + 1, n):
             
            # Check for lesser arrival time 
            if at[i] > at[j]:
                 
                # Swap earlier process to front
                at[i], at[j] = at[j], at[i]
 
# Driver code
if __name__ == '__main__':
     
    sum_bt = 0
    avgwt = 0
    avgTT = 0
    n = 5
     
    completed =[0] * n
    waiting_time = [0] * n
    turnaround_time = [0] * n
    normalised_TT = [0] * n
     
    # Predefined arrival times 
    arrival_time = [ 0, 2, 4, 6, 8 ]
     
    # Predefined burst times 
    burst_time = [ 3, 6, 4, 5, 2 ]
    process = []
     
    # Initializing the structure variables 
    for i in range(0, n):
        process.append(chr(65 + i))
        sum_bt += burst_time[i]
         
    # Sorting the structure by arrival times 
    sortByArrival(arrival_time, n)
    print("Name", "Arrival time",
          "Burst time", "Waiting Time",
          "Turnaround ", "Normalized TT")
    t = arrival_time[0]
     
    while(t < sum_bt):
         
        # Set lower limit to response ratio 
        hrr = -9999
        temp, loc = 0, 0
         
        for i in range(0, n):
             
            # Checking if process has arrived
            # and is Incomplete 
            if arrival_time[i] <= t and completed[i] != 1:
                 
                # Calculating Response Ratio 
                temp = ((burst_time[i] +
                        (t - arrival_time[i])) /
                         burst_time[i])
                          
                # Checking for Highest Response Ratio 
                if hrr < temp:
                     
                    # Storing Response Ratio 
                    hrr = temp
                     
                    # Storing Location
                    loc = i
                     
        # Updating time value 
        t += burst_time[loc]
         
        # Calculation of waiting time
        waiting_time[loc] = (t - arrival_time[loc] -
                                 burst_time[loc])
         
        # Calculation of Turn Around Time 
        turnaround_time[loc] = t - arrival_time[loc]
         
        # Sum Turn Around Time for average 
        avgTT += turnaround_time[loc]
         
        # Calculation of Normalized Turn Around Time 
        normalised_TT = float(turnaround_time[loc] /
                              burst_time[loc])
         
        # Updating Completion Status
        completed[loc] = 1
         
        # Sum Waiting Time for average 
        avgwt += waiting_time[loc]
         
        print(process[loc], "\t\t", arrival_time[loc],
              "\t\t", burst_time[loc], "\t\t",
              waiting_time[loc], "\t\t",
              turnaround_time[loc], "\t\t",
              "{0:.6f}".format(normalised_TT))
 
    print("Average waiting time: {0:.6f}".format(avgwt / n))
    print("Average Turn Around time:  {0:.6f}".format(avgTT / n))
 
# This code is contributed by etcharla revanth rao

PN    AT    BT    WT    TAT    NTT
A    0    3    0    3    1
B    2    6    1    7    1.16667
C    4    4    5    9    2.25
E    8    2    5    7    3.5
D    6    5    9    14    2.8
Average waiting time: 4
Average Turn Around time:8

Este artículo es una contribución de Siddhant Bajaj . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.