Tiempo de retorno y tiempo de espera

1. Por qué estas dos métricas son las centrales

En el tema 6 viste cinco criterios. De ellos, dos dominan la comparación de algoritmos: el tiempo de retorno (turnaround) y el tiempo de espera (waiting). La razón es que son las únicas que dependen directamente del orden en que el planificador da la CPU. El uso de la CPU y el throughput dependen sobre todo de cuántos procesos hay en memoria y de si se bloquean en E/S; el tiempo de respuesta depende de cuándo se da el primer turno. El turnaround y el waiting, en cambio, resumen toda la experiencia de un proceso con la cola de listos.

Además, las dos están ligadas por una identidad sencilla: para un proceso que no hace entrada/salida, el tiempo de retorno es exactamente el tiempo de espera más el tiempo que usó la CPU. Eso significa que, cuando el trabajo de cada proceso es fijo, minimizar el tiempo de espera promedio es lo mismo que minimizar el tiempo de retorno promedio. El planificador no puede reducir el trabajo, pero sí puede reducir la espera.

Por eso, cuando en un examen o en un artículo se dice «este algoritmo es mejor», casi siempre se refiere a que baja el tiempo de espera (y con él el de retorno) promedio, o a que lo baja para los procesos cortos. Las secciones siguientes te enseñan a calcularlo sin ambigüedad.

2. Definiciones y fórmulas

El tiempo de retorno (turnaround time) de un proceso es el tiempo total que pasa en el sistema, desde que llega hasta que termina. El tiempo de espera (waiting time) es la parte de ese tiempo que el proceso pasa en la cola de listos, listo para ejecutarse pero sin CPU.

Para un proceso P_i se usan estos símbolos:

Las fórmulas son:

Tiempo de retorno: T_i = F_i − A_i.

Tiempo de espera (un solo bloque de CPU, sin E/S): W_i = T_i − B_i = S_i − A_i.

Tiempo de espera (caso general, con E/S): W_i = T_i − B_i − I_i.

Y los promedios, que son los que se comparan entre algoritmos:

Promedio de retorno: T̄ = (Σ T_i) / n.   Promedio de espera: W̄ = (Σ W_i) / n.

Observa que la fórmula del caso general se reduce a la del caso simple cuando I_i = 0. En los temas de algoritmos clásicos (bloques 3 a 7) se trabaja casi siempre con un solo bloque de CPU por proceso, así que W_i = S_i − A_i es la forma más usada.

3. El significado de cada término

Es fácil memorizar las fórmulas y equivocarse al aplicarlas. Estas son las confusiones más frecuentes y cómo evitarlas:

• La llegada no es el inicio. A_i es cuando el proceso entra en el sistema; S_i es cuando recibe la CPU por primera vez. Si llega y la CPU está ocupada, S_i > A_i y la diferencia es espera.
• La ráfaga es trabajo, no tiempo de pared. B_i es el tiempo de CPU que el programa necesita. Si el proceso se interrumpe, su ráfaga se reparte en varios turnos, pero la suma sigue siendo B_i.
• El turnaround incluye la E/S. Un proceso que espera 5 s al disco tiene al menos 5 s de turnaround aunque la CPU le haya dado 0 s de espera. Por eso, para comparar planificadores, conviene separar la espera de CPU de la espera de E/S.
• El tiempo de espera no es el tiempo de respuesta. La espera W_i suma todos los turnos en la cola; el tiempo de respuesta (tema 8) mide solo el primer turno. Un proceso puede tener respuesta rápida y espera total alta.
• El promedio no cuenta toda la historia. Dos planificaciones con el mismo promedio pueden tener máximos muy distintos. Un proceso que espera 30 unidades «paga» lo mismo en el promedio que tres que esperan 10, pero para el usuario es muy diferente.

4. Cómo se calculan paso a paso

El método es siempre el mismo, sea cual sea el algoritmo. Lo único que cambia es el orden en que se ejecutan los procesos:

1. Anota los datos de cada proceso. Para cada uno: llegada A_i y ráfaga B_i (y I_i si tiene E/S). datos
2. Decide el orden de ejecución. FCFS por llegada, SJF por ráfaga más corta entre los que ya llegaron, por prioridad, Round Robin en turnos... algoritmo
3. Recorre la línea de tiempo. Mantén un reloj t. Para cada proceso en orden: si t < A_i, la CPU está ociosa y t salta a A_i; el inicio es S_i = t; la terminación es F_i = t + B_i; avanza t = F_i. timeline
4. Calcula T_i y W_i. T_i = F_i − A_i; W_i = T_i − B_i (o − B_i − I_i si hay E/S). métricas
5. Suma y divide por n. Obtienes los promedios que se comparan entre algoritmos. promedios

5. Ejemplo 1: todos llegan en cero

Es el caso más sencillo y el más frecuente en los ejercicios. Cuatro procesos, todos listos en t = 0, con ráfagas 8, 4, 2 y 1:

5.1 Orden FCFS: P1, P2, P3, P4

El proceso largo va primero y hace esperar a todos los demás: P4, que solo necesitaba 1 unidad, espera 14. Es el efecto convoy, que se estudia en el tema 11.

5.2 Orden SJF: P4, P3, P2, P1

El mismo trabajo total (15 unidades) termina en el mismo instante, pero el promedio de espera baja de 8,50 a 2,75. Los procesos cortos salen primero; solo el largo espera (7 unidades). Este es el motivo por el que SJF minimiza el tiempo de espera promedio cuando todos llegan en cero: se demuestra intercambiando dos procesos adyacentes y viendo que poner el más corto antes siempre reduce (o no aumenta) la suma de esperas.

6. Ejemplo 2: llegadas distintas

Cuando los procesos no llegan todos en cero, hay que respetar la llegada: no se puede ejecutar un proceso antes de que exista. Tomemos este conjunto:

Con FCFS por orden de llegada (que coincide con el orden de la tabla), la línea de tiempo es:

Fíjate en P2: llegó en 1, pero la CPU estaba ocupada con P1 hasta 5, así que esperó 4 unidades. P4 llegó en 4 y esperó 8. La CPU no quedó ociosa en ningún momento porque siempre había algún proceso listo. Si la llegada de P2 hubiera sido 6 en lugar de 1, la CPU habría estado ociosa entre 5 y 6, y el reloj habría saltado.

7. Ejemplo 3: SJF con llegadas distintas

Cuando las llegadas son distintas, SJF no ordena todos los procesos al principio: en cada decisión elige el más corto entre los que ya han llegado. Tomemos:

En t = 0 solo ha llegado P1, así que se ejecuta aunque sea el más largo (duración 8). Al terminar, en t = 8, ya han llegado todos; se elige el más corto (P4), luego P3, luego P2:

Para comparar, el mismo conjunto en FCFS por llegada da promedios de turnaround 11,75 y espera 7,00. SJF mejora ambos, pero la mejora es menor que cuando todos llegan en cero, porque el proceso largo P1 ya estaba ejecutándose cuando llegaron los cortos y, al ser no apropiativo, no se le puede quitar la CPU. Con SRTF (SJF con apropiación, tema 14) se interrumpiría P1 y los promedios bajarían todavía más.

8. Turnaround, CPU y entrada/salida

Cuando un proceso hace E/S, su turnaround se descompone en tres partes: tiempo de CPU, tiempo de espera de E/S y tiempo de espera en la cola de listos. Solo la última la controla el planificador. La fórmula general lo refleja:

T_i = B_i (CPU) + I_i (E/S) + W_i (cola de listos).

Un proceso con ráfagas de CPU de 3 y 2 y una E/S de 5 entre ellas, que empieza en 0 y no compite con nadie, termina en 10: 3 de CPU, 5 de E/S, 2 de CPU. Su turnaround es 10, su tiempo de CPU es 5, su espera de E/S es 5 y su espera en la cola es 0. Si se le hubiera hecho esperar 2 unidades en la cola antes de la segunda ráfaga, el turnaround habría sido 12.

Veamos un caso con dos procesos para ver cómo la E/S permite solapamiento:

Una planificación razonable ejecuta primero la ráfaga de CPU de P1 (0–3), luego la de P2 (3–7) mientras P1 hace E/S (3–8), y finalmente la segunda ráfaga de P1 (8–10):

La CPU no queda ociosa (P2 la usa mientras P1 espera al disco), y el turnaround promedio es menor que si se ejecutaran los procesos uno tras otro sin solapar (que sería 5 + 9 = 14 de turnaround total). En los simuladores de los bloques siguientes se modela cada proceso con una sola ráfaga de CPU; la E/S se introduce en los bloques 8 y 9.

9. Métricas derivadas

A partir de T_i y W_i se calculan otras magnitudes útiles:

• Promedios. T̄ y W̄. Son los que se comparan entre algoritmos. Conviene dar también el máximo, porque un promedio bueno puede esconder un proceso que esperó mucho.
• Turnaround normalizado. T_i / B_i. Vale 1 si el proceso no esperó nada (terminó en cuanto recibió CPU suficiente) y crece con la espera. Permite comparar procesos de distinta duración: una espera de 5 unidades es mucho para un proceso de 2 y poco para uno de 50.
• Throughput. n / (F_último − A_primero). Procesos terminados por unidad de tiempo. Para procesos sin E/S no depende del orden: el trabajo total es el mismo.
• Utilización de la CPU. Tiempo de CPU ocupada / tiempo total. En los ejemplos con todos los procesos listos y sin E/S es del 100 %; baja cuando hay huecos sin procesos listos.

10. Un programa que calcula las métricas

El siguiente programa en C calcula turnaround y espera para FCFS, respetando las llegadas y los huecos de CPU ociosa. Usa el conjunto del ejemplo 2:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>

struct proceso {
    int pid;
    int llegada;
    int rafaga;
    int inicio;
    int fin;
};

static void ordenar_por_llegada(struct proceso *p, int n)
{
    for (int i = 1; i < n; i++) {
        struct proceso tmp = p[i];
        int j = i - 1;
        while (j >= 0 && p[j].llegada > tmp.llegada) {
            p[j + 1] = p[j];
            j--;
        }
        p[j + 1] = tmp;
    }
}

static void fcfs(struct proceso *p, int n)
{
    int t = 0;
    double suma_t = 0, suma_w = 0;
    ordenar_por_llegada(p, n);

    for (int i = 0; i < n; i++) {
        if (t < p[i].llegada)          /* CPU ociosa hasta la llegada */
            t = p[i].llegada;
        p[i].inicio = t;
        p[i].fin = t + p[i].rafaga;
        t = p[i].fin;
        int turnaround = p[i].fin - p[i].llegada;
        int espera = turnaround - p[i].rafaga;
        suma_t += turnaround;
        suma_w += espera;
        printf("P%d: llegada=%d rafaga=%d inicio=%d fin=%d turnaround=%d espera=%d\n",
               p[i].pid, p[i].llegada, p[i].rafaga,
               p[i].inicio, p[i].fin, turnaround, espera);
    }
    printf("Promedio: turnaround=%.2f espera=%.2f\n", suma_t / n, suma_w / n);
}

int main(void)
{
    struct proceso p[4] = {
        {1, 0, 5, 0, 0},
        {2, 1, 3, 0, 0},
        {3, 2, 4, 0, 0},
        {4, 4, 2, 0, 0}
    };
    fcfs(p, 4);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o metricas_fcfs metricas_fcfs.c
$ ./metricas_fcfs
P1: llegada=0 rafaga=5 inicio=0 fin=5 turnaround=5 espera=0
P2: llegada=1 rafaga=3 inicio=5 fin=8 turnaround=7 espera=4
P3: llegada=2 rafaga=4 inicio=8 fin=12 turnaround=10 espera=6
P4: llegada=4 rafaga=2 inicio=12 fin=14 turnaround=10 espera=8
Promedio: turnaround=8.00 espera=4.50

La salida reproduce exactamente la tabla del ejemplo 2. Cambiar el algoritmo consiste en cambiar el orden en que se recorren los procesos; las fórmulas de turnaround y espera no cambian.

11. Resumen

• El tiempo de retorno T_i = F_i − A_i mide todo el tiempo que el proceso pasa en el sistema.
• El tiempo de espera W_i mide lo que pasa en la cola de listos: T_i − B_i (sin E/S) o T_i − B_i − I_i (con E/S).
• Para procesos sin E/S se cumple T_i = W_i + B_i: el planificador solo puede reducir W_i.
• El cálculo tiene cinco pasos: datos, orden, línea de tiempo, métricas, promedios. Si no hay proceso listo, la CPU queda ociosa y el reloj salta a la próxima llegada.
• Cuando todos llegan en cero, SJF minimiza el promedio de espera y de retorno.
• Con llegadas distintas, SJF elige el más corto entre los que ya llegaron; un proceso largo que ya se ejecuta no se interrumpe (eso es SRTF).
• Con E/S, el turnaround suma CPU, E/S y cola; solo la cola la controla el planificador, y la E/S permite solapar trabajo.
• El turnaround normalizado T_i/B_i permite comparar procesos de distinta duración.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Calcula a mano turnaround y espera para los procesos P1(8), P2(4), P3(2), P4(1) en orden SJF y compara con FCFS.
2. Repite el ejemplo 2 pero con P2 llegando en 6 en lugar de 1. ¿Queda la CPU ociosa? ¿Cuánto?
3. Para el conjunto del ejemplo 3, calcula las métricas de SRTF (interrumpe P1 cuando llega P4) y compáralas con las de SJF no apropiativo.
4. Modifica metricas_fcfs.c para imprimir también el turnaround normalizado de cada proceso.
5. Diseña un conjunto de 3 procesos en el que FCFS y SJF den el mismo promedio de espera. ¿Qué propiedad deben tener?
6. Calcula las métricas de un proceso con ráfagas CPU 4, E/S 6, CPU 3 que empieza en 0 y no compite con nadie.