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.  

Procesos Hora de llegada  Tiempo quemado
P1   0ms 3ms
P2             2ms 6ms
P3  4ms 4ms
P4      6ms 5ms
P5 8ms 2ms

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.
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
0-2ms P1 0ms   P1 2ms 3ms 1ms

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.
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
2-3ms P1 0ms P2 P1 1ms 1ms 0ms
P2 2ms 0ms 6ms 6ms

En el tiempo = 3,

  • El proceso P1 termina su ejecución
  • El proceso P2 comienza a ejecutarse ya que es el único proceso disponible.
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
3-4ms P2 2ms   P2 1ms 6ms 5ms

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
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
4-6ms P2 2ms P3 P2 2ms 5ms 3ms
P3 4ms 0ms 4ms 4ms

En el tiempo = 6,

  • Llega el proceso P4 y espera a que se ejecute el proceso P2
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
6-8ms P2 2ms P3, P4 P2 2ms 3ms 1ms
P3 4ms 0ms 4ms 4ms
P4 6ms 0ms 5ms 5ms

En el tiempo = 8,

  • Llega el proceso P5 y espera su ejecución en la cola de listos
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
8-9ms P2 2ms P3, P4, P5 P2 1ms 1ms 0ms
P3 4ms 0ms 4ms 4ms
P4 6ms 0ms 5ms 5ms
P5 8ms 0ms 2ms 2ms

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
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
9-13ms P3 4ms P4, P5 P3 4ms 4ms 0ms
P4 6ms 0ms 5ms 5ms
P5 8ms 0ms 2ms 2ms

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
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
13-15ms P4 6ms P4 P5 0ms 5ms 5ms
P5 8ms 2ms 2ms 0ms

En el tiempo = 15,

  • Después de completar el proceso P5, el proceso P4 se selecciona por fin y se ejecuta hasta que finaliza
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
15-20ms P4 6ms   P4 5ms 5ms 0ms

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:
Instancia de tiempo Proceso Hora de llegada Cola lista Cola en ejecución Tiempo de ejecución Tiempo de ráfaga inicial Tiempo de ráfaga restante 
0-2ms P1 0ms   P1 2ms 3ms 1ms
2-3ms P1 0ms P2 P1 1ms 1ms 0ms
P2 2ms 0ms 6ms 6ms
3-4ms P2 2ms   P2 1ms 6ms 5ms
4-6ms P2 2ms P3 P2 2ms 5ms 3ms
P3 4ms 0ms 4ms 4ms
6-8ms P2 2ms P3, P4 P2 2ms 3ms 1ms
P3 4ms 0ms 4ms 4ms
P4 6ms 0ms 5ms 5ms
8-9ms P2 2ms P3, P4, P5 P2 1ms 1ms 0ms
P3 4ms 0ms 4ms 4ms
P4 6ms 0ms 5ms 5ms
P5 8ms 0ms 2ms 2ms
9-13ms P3 4ms P4, P5 P3 4ms 4ms 0ms
P4 6ms 0ms 5ms 5ms
P5 8ms 0ms 2ms 2ms
13-15ms P4 6ms P4 P5 0ms 5ms 5ms
P5 8ms 2ms 2ms 0ms
15-20ms P4 6ms   P4 5ms 5ms 0ms

Gráfico de gantt – 

HRRN Scheduling Example Soolution

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,  

Procesos A BT Connecticut HACER ENCAJE peso
P1 0 3 3 3-0 = 3 3-3 = 0
P2 2 6 9 9-2 = 7 7-6 = 1
P3 4 4 13 13-4 = 9 9-4 = 5
P4 6 5 20 20-6 = 14 14-5 = 9
P5 8 2 15 15-8 = 7 7-2 = 5

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++

// 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

// 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

# 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
Producción

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.

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 *