process - sistemas - ¿Cómo calcular el tiempo de espera promedio de la programación Round Robin?

round robin ejemplo

Question

Dada esta tabla:

Esas son las líneas de tiempo (segmento de tiempo = 4):

|p1|p1|p2|p3|p4|p5|p1|p2|p3|p4|p5|p2|p3|p4|p5|p2|p3|p4|p5|p2|p3|p3|
0  4  8 12 16  20 24 28 32 36 40 44 48 52 56 60 64 68 69 72 75 79 80

¿Hay una manera simple de calcular el tiempo promedio de espera?

Gracias

Nota: ¡ hay varios tiempos de finalización para cada proceso!

Nota 2 : esta pregunta también involucraba el algoritmo de prioridad como ejercicio lateral, ignore la columna de prioridad para el algoritmo Round Robin

Answer 1

Puede calcular el tiempo de espera dibujando el Gantt chart modo que el tiempo de espera del i-ésimo proceso sea igual al Completion time - (Arrival time + Burst time ) .

Answer 2

| H | I | J | K | L | H | J | K | L | J | K | L | J | L | L | Es demasiado largo, su respuesta en resumen es esto: 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 tiempo promedio de espera = ((H - hora de llegada) + (I - hora de llegada) + (J - llegada hora) + (K - hora de llegada) + (L - hora de llegada)) / 5 = (24-0) + (8-5) + (52 - 8) + (44-11) + (60 - 15) / 5 = 29.8 m seg. Es demasiado larga, su respuesta en resumen es esta: Aquí está el diagrama de Gantt del algoritmo de programación RR Proceso [tiempo de ráfaga, tiempo cuántico, tiempo de llegada] H [8, 4, 0] I [4, 4, 5] J [16, 4, 8] k [12, 4, 11] L [20, constante = 4, 15]

Answer 3

Mi respuesta es por el tiempo de espera y el tiempo de respuesta

Tiempo de espera: (16 + 51 + 51 + 45 + 42) / 5 = 41 Tiempo de respuesta: (28 + 70 + 72 + 58 + 57) / 5 = 57

Answer 4

Para RR, tiempo de espera = última hora de inicio - hora de llegada - (cuántica de prioridad *)

La última hora de inicio de P1 es 24 (cuando P1 se ejecuta por tercera vez en la tabla de Gannt) P1 se adelantó 2 veces en su vida Quantum = 4, Arrival = 0.

WaitingTime of P1 = 24 - 0 - (2 * 4) = 16 :)

Answer 5

Intenté implementarlo en java:

public static float waitingTimieRobin(int[] arrival, int[] run, int q) {
    Queue<Integer> orderQueue = new LinkedList<>();
    orderQueue.add(0);
    Set<Integer> orderSet = new HashSet<>();
    orderSet.add(0);

    float sumTime = 0.0f;

    int curTime = 0;
    while (!isOver(run)) {

        int order = orderQueue.poll();
        orderSet.remove(order);
        int arrTime = arrival[order];
        int runtime = run[order];
        sumTime += (curTime - arrTime);
        if (runtime <= q) {
            curTime += runtime;
            run[order] = 0;
        } else {
            curTime += q;
            arrival[order] = curTime;
            run[order] = runtime - q;
        }

        for (int i = 0; i < run.length; i++) {
            if (arrival[i] > curTime) {
                break;
            } else if (i != order && run[i] != 0 && !orderSet.contains(i)) {
                orderQueue.add(i);
                orderSet.add(i);
            }
        }

        if(arrival[order] == curTime && run[order] != 0 && !orderSet.contains(order)) {
            orderQueue.add(order);
            orderSet.add(order);
        }
    }

    return sumTime / arrival.length;
}

public static boolean isOver(int[] run) {
    for (int runtime : run) {
        if (runtime > 0) {
            return false;
        }
    }
    return true;
}

Answer 6

Primero tratemos de resolver la versión simple de este problema donde todo el proceso llega en el tiempo 0. Supongamos que tenemos n procesos cada uno con tiempo de ejecución como ei . Deje que el segmento de tiempo sea s . Permita que el número de cortes de tiempo necesarios para cada proceso sea NSPi . Ahora tenemos NSPi = ceiling(ei/s) . Tiempo necesario para un proceso i = NSPi * s . Longitud del programa = sum over i from 1 to n (NSPi) . Tiempo de espera para el proceso i = finish time of i - execution time of i . Pero calcular el tiempo de finalización de cada proceso es complicado ya que cada proceso tiene un tiempo de ejecución diferente. Pero como solo necesita el tiempo de espera promedio del algoritmo RR para una instancia específica, puede calcularlo como: (Length of the schedule - sum of execution time of all processes)/num of processes .

Supongo que ahora tendrías una idea de cómo ha evolucionado esta fórmula. Lo ideal sería que la duración del programa sea igual a la suma del tiempo de ejecución de todos los procesos. Pero no todos los tiempos de ejecución son un factor del tiempo. Entonces en algún segmento de tiempo obtenemos agujeros donde no hay un proceso programado. Entonces, en la práctica, la duración del cronograma es mayor que la suma de los tiempos de ejecución. Ahora tenemos su diferencia como el tiempo total de espera.