Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Planificación round-robin

La planificación round-robin asigna tiempo de CPU por turnos a los trabajos listos, durante como máximo un cuanto cada uno. El ejemplo en C simula esta política y calcula el tiempo de espera y el tiempo de retorno con una regla explícita para el orden de llegada.

Versión: C23; repository compiler flag, production runtime not attested

Sintaxis

slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burst

La planificación round-robin (RR) atiende una cola de trabajos listos. El trabajo que está al principio se ejecuta durante como máximo un quantum, es decir, un intervalo de tiempo positivo. Si sigue listo y no ha terminado, pasa al final de la cola; los trabajos completados salen, mientras que los bloqueados esperan fuera de la cola de listos. Un quantum más corto favorece la capacidad de respuesta, pero aumenta el coste de los cambios de contexto; RR no minimiza, en general, el tiempo medio de retorno.

El orden de llegada requiere una regla explícita: añadir los trabajos nuevos al final de la cola y resolver los empates de forma determinista. Una llegada durante un quantum no interrumpe por sí sola ese intervalo. En los límites del quantum, hay que especificar si se procesan primero las nuevas llegadas o la reinserción del trabajo actual. Aquí todos los trabajos llegan en el instante 0, en el orden P1, P2, P3; recorrer el array de forma cíclica solo basta para esta simplificación.

El tiempo de retorno es completion - arrival. El tiempo de espera suma el tiempo pasado en la cola de listos, no solo la espera antes de la primera ejecución. En el modelo supuesto, sin E/S ni sobrecostes, equivale a turnaround - burst. El ejemplo usa quantum = 2 y necesidades de CPU de 5, 3, 1; los tiempos de finalización son, respectivamente, 9, 8, 5.

Esta es una simulación determinista de una sola CPU en unidades de tiempo abstractas, no una configuración del planificador de un sistema operativo ni una prueba del comportamiento de los hilos de C. Ámbito de versión: C23; repository compiler flag, production runtime not attested. No se acredita su ejecución en un entorno de producción.

Ejemplos

#include <stdio.h>

int main(void)
{
    const int quantum = 2;
    const int burst[3] = {5, 3, 1};
    int remaining[3] = {5, 3, 1};
    int completion[3] = {0};
    int time = 0;
    int unfinished = 3;

    while (unfinished > 0) {
        for (int i = 0; i < 3; ++i) {
            if (remaining[i] == 0) {
                continue;
            }
            int slice = remaining[i] < quantum
                      ? remaining[i] : quantum;
            printf("P%d [%d,%d)\n", i + 1, time, time + slice);
            time += slice;
            remaining[i] -= slice;
            if (remaining[i] == 0) {
                completion[i] = time;
                --unfinished;
            }
        }
    }

    puts("job waiting turnaround");
    for (int i = 0; i < 3; ++i) {
        int turnaround = completion[i]; /* arrival = 0 */
        int waiting = turnaround - burst[i];
        printf("P%d %d %d\n", i + 1, waiting, turnaround);
    }
    return 0;
}

Resultado

P1 [0,2)
P2 [2,4)
P3 [4,5)
P1 [5,7)
P2 [7,8)
P1 [8,9)
job waiting turnaround
P1 4 9
P2 5 8
P3 4 5

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes