Tiempo de respuesta y diagramas de Gantt

1. Qué mide el tiempo de respuesta

El tiempo de respuesta (response time) de un proceso es el tiempo que pasa desde que llega al sistema hasta que recibe la CPU por primera vez. Es la métrica de la interactividad: cuánto tarda el sistema en reaccionar ante el usuario.

Cuando escribes un comando en la terminal, cuando haces clic en un botón o cuando una petición llega a un servidor, lo primero que quieres saber no es cuándo terminará el proceso, sino cuándo empezará a ejecutarse. Un editor de texto que tarda 200 ms en responder a una tecla se siente lento aunque termine en 1 s; un compilador que tarda 5 s en empezar pero termina en 6 s se siente aceptable, porque no estás esperando activamente.

Por eso, los sistemas interactivos (escritorio, shell, servidor web) se juzgan por el tiempo de respuesta, mientras que los sistemas por lotes se juzgan por el tiempo de retorno. Un mismo algoritmo puede ser excelente para uno y pésimo para el otro.

2. Definición y fórmula

Para un proceso P_i con llegada A_i y primera ejecución S_i:

Tiempo de respuesta: R_i = S_i − A_i.

Y el promedio, que es el que se compara entre algoritmos:

Promedio de respuesta: R̄ = (Σ R_i) / n.

Observa que S_i es el instante en que el proceso recibe la CPU por primera vez, no cada vez. Si un proceso recibe la CPU en t = 2, luego es expulsado y vuelve en t = 7, su tiempo de respuesta sigue siendo 2 − A_i, no 7. Ese detalle es el que lo distingue del tiempo de espera, que sí acumula todas las esperas.

Si el proceso está listo en el instante en que llega y la CPU está libre, R_i = 0: responde al instante. Si llega y la CPU está ocupada, tendrá que esperar al menos hasta que el proceso en ejecución termine o sea expulsado.

3. Respuesta, espera y retorno: las diferencias

Las tres métricas se calculan sobre el mismo proceso, pero miden cosas distintas. Esta tabla las compara:

Las tres están relacionadas. Para un proceso con un solo bloque de CPU y sin E/S:

• R_i ≤ W_i ≤ T_i: el tiempo de respuesta es siempre menor o igual que la espera, que es menor o igual que el retorno.
• Si el proceso recibe la CPU una sola vez y la usa hasta terminar (sin apropiación), entonces R_i = W_i: no hay segunda espera.
• Si el proceso se ejecuta en varios turnos (Round Robin, SRTF), entonces R_i < W_i: recibe CPU pronto, pero espera más en total entre turnos.

4. El diagrama de Gantt

Un diagrama de Gantt es la representación gráfica de la línea de tiempo de la CPU: una barra horizontal dividida en segmentos, donde cada segmento es un intervalo en que un proceso (o la CPU ociosa) tiene el procesador.

Es la herramienta universal de la planificación. Todo algoritmo se explica con un Gantt, todo examen pide dibujarlo, y los simuladores del curso lo generan automáticamente. Sin él, comparar dos algoritmos es hacer aritmética a ciegas.

Un Gantt tiene estas partes:

• Eje horizontal: el tiempo, creciente de izquierda a derecha. Las marcas (ticks) indican los instantes en que cambia el proceso en ejecución.
• Segmentos (bloques): cada uno representa un intervalo [inicio, fin) en que un proceso usa la CPU. Su longitud es proporcional a la duración.
• Etiqueta: dentro de cada segmento se escribe el nombre del proceso (P1, P2…) o «ociosa» si la CPU está libre.
• Color: opcional, para distinguir procesos. En el curso se usa un color por proceso.

Este es un ejemplo de Gantt para tres procesos ejecutados en FCFS, P1(6), P2(4), P3(2), todos llegando en 0:

La longitud de cada bloque es proporcional a su duración: P1 ocupa la mitad del tiempo total (6 de 12), P2 un tercio (4 de 12) y P3 un sexto (2 de 12). Esa proporcionalidad es lo que hace que el Gantt sea legible de un vistazo.

5. Cómo leer un Gantt

Leer un Gantt consiste en traducir la barra a números. Para cada proceso se identifican cuatro datos:

1. Llegada (A_i). No aparece en el Gantt directamente; viene de la tabla de procesos. Es el instante a partir del cual el proceso puede aparecer en la barra. datos
2. Primera ejecución (S_i). El instante en que empieza el primer bloque del proceso. Es el borde izquierdo de su primer segmento. gantt
3. Terminación (F_i). El instante en que acaba su último bloque. Es el borde derecho del último segmento del proceso. gantt
4. Turnos. Si el proceso aparece en varios segmentos, cada uno es un turno de CPU. La suma de sus longitudes es la ráfaga B_i. gantt

Con esos datos se calculan las tres métricas:

R_i = S_i − A_i (respuesta).  W_i = T_i − B_i (espera).  T_i = F_i − A_i (retorno).

Además, el Gantt permite ver de un vistazo:

• La utilización de la CPU: si hay huecos (bloques «ociosa»), la CPU no estuvo al 100 %.
• El throughput: cuántos procesos terminaron y en qué instantes.
• La equidad: si un proceso tiene bloques muy largos y otros muy cortos, el reparto es desigual.
• El tiempo de respuesta máximo: el segmento más a la derecha del primer bloque de cada proceso.

6. Cómo dibujar un Gantt paso a paso

Dibujar un Gantt a mano es la habilidad que se evalúa en un examen. El método es el mismo que el de calcular métricas, pero con el dibujo como resultado:

1. Prepara la tabla de procesos. Anota para cada uno: nombre, llegada y ráfaga (y quantum si aplica). datos
2. Traza el eje del tiempo. Marca los instantes 0, 1, 2… hasta el final. Usa una escala razonable (cada unidad = 1 cm o 1 cuadro). papel
3. Simula el algoritmo. Mantén un reloj t y una cola de listos. En cada instante de decisión (llegada, terminación o fin de quantum) elige el proceso según el algoritmo y dibuja su bloque desde t hasta t + duración. algoritmo
4. Marca los huecos. Si no hay proceso listo, dibuja un bloque «ociosa» (o déjalo en blanco) y salta el reloj a la próxima llegada. ociosa
5. Etiqueta cada bloque. Escribe el nombre del proceso dentro. Añade las marcas de tiempo debajo. etiquetas
6. Verifica. La suma de las longitudes de los bloques de un proceso debe igualar su ráfaga; el último instante debe igualar el tiempo total de CPU usada (más huecos). check

7. Calcular las tres métricas sobre un Gantt

Una vez dibujado el Gantt, el cálculo es mecánico. Para cada proceso:

1. Lee S_i y F_i del Gantt. S_i es el borde izquierdo del primer bloque del proceso; F_i es el borde derecho de su último bloque. gantt
2. Toma A_i y B_i de la tabla. La llegada y la ráfaga no se leen del Gantt. datos
3. Calcula las tres métricas. R_i = S_i − A_i; T_i = F_i − A_i; W_i = T_i − B_i. fórmulas
4. Promedia. Suma cada métrica y divide por n. promedios

El orden de las columnas en la tabla de resultados suele ser: proceso, llegada, ráfaga, inicio, terminación, respuesta, espera, retorno. Ese orden sigue el orden de cálculo y evita errores.

8. Ejemplo 1: FCFS con llegadas distintas

Cuatro procesos con llegadas distintas:

FCFS los ejecuta en orden de llegada. El Gantt es:

Leyendo el Gantt y aplicando las fórmulas:

Como es FCFS sin apropiación, cada proceso recibe la CPU una sola vez: respuesta y espera coinciden. El tiempo de respuesta promedio es 4,50, bastante alto porque los procesos cortos que llegan tarde esperan a que terminen los largos.

9. Ejemplo 2: Round Robin con quantum

Aquí es donde el tiempo de respuesta se separa de la espera. Tres procesos, todos en 0, con ráfagas 8, 4 y 2, y un quantum de 3:

El Gantt es:

Leyendo el Gantt (el inicio de cada proceso es el borde izquierdo de su primer bloque; la terminación es el borde derecho de su último bloque):

Compara con FCFS para el mismo conjunto (P1, P2, P3): respuesta promedio 0 + 8 + 10 = 6,00; espera 0 + 8 + 10 = 6,00; retorno 8 + 12 + 14 = 11,33. Round Robin empeora la espera y el retorno, pero mejora la respuesta de P2 y P3 (de 8 y 10 a 3 y 6). P1, que era el primero, empeora en respuesta (de 0 a 0, igual) pero su espera sube. Este es el compromiso típico de Round Robin.

10. Ejemplo 3: Gantt con entrada/salida

Los Gantt también representan la E/S, aunque de forma distinta. Un proceso que hace E/S deja la CPU y la libera para otros; en el Gantt se dibuja un bloque «ociosa» o directamente el bloque del siguiente proceso. La E/S del proceso se anota debajo o se dibuja en una fila aparte.

Dos procesos: P1 con ráfagas CPU 3, E/S 5, CPU 2; P2 con ráfaga CPU 4. Ambos llegan en 0. Una planificación razonable:

Las métricas de respuesta se calculan igual: la primera ejecución de P1 es 0 (su primer bloque CPU empieza en 0), y la de P2 es 3. El turnaround de P1 es 10, el de P2 es 7. La espera en la cola de P1 es 0 (no esperó a la CPU) y la de P2 es 3.

Observa que el Gantt con E/S tiene un hueco de CPU (7–8) porque P2 terminó antes de que P1 saliera de la E/S. Ese hueco es inevitable: la CPU no tiene nada que ejecutar. En un sistema con más procesos, ese hueco se aprovecharía.

11. Un programa que dibuja y calcula

El siguiente programa en C toma una lista de procesos, simula FCFS, imprime el Gantt como texto y calcula las tres métricas. Es la base de los simuladores que construirás en el tema 9:

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

struct proceso {
    int pid;
    int llegada;
    int rafaga;
    int inicio;   /* primera ejecucion */
    int fin;      /* terminacion */
};

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;
    }
}

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}
    };
    int n = 4;
    ordenar_por_llegada(p, n);

    /* Simular FCFS */
    int t = 0;
    for (int i = 0; i < n; i++) {
        if (t < p[i].llegada) t = p[i].llegada;   /* CPU ociosa */
        p[i].inicio = t;
        p[i].fin = t + p[i].rafaga;
        t = p[i].fin;
    }

    /* Dibujar Gantt en texto */
    printf("Gantt: ");
    for (int i = 0; i < n; i++) {
        if (i > 0 && p[i].inicio > p[i-1].fin)
            printf("[ociosa %d-%d] ", p[i-1].fin, p[i].inicio);
        printf("[P%d %d-%d] ", p[i].pid, p[i].inicio, p[i].fin);
    }
    printf("\n\n");

    /* Calcular las tres metricas */
    double sr = 0, sw = 0, st = 0;
    printf("%-4s %8s %8s %8s %10s %8s %8s\n",
           "Proc", "Llegada", "Rafaga", "Inicio", "Fin", "Resp", "Espera", "Retorno");
    for (int i = 0; i < n; i++) {
        int resp = p[i].inicio - p[i].llegada;
        int turn = p[i].fin - p[i].llegada;
        int esp = turn - p[i].rafaga;
        sr += resp; sw += esp; st += turn;
        printf("P%-3d %8d %8d %8d %10d %8d %8d %8d\n",
               p[i].pid, p[i].llegada, p[i].rafaga,
               p[i].inicio, p[i].fin, resp, esp, turn);
    }
    printf("\nPromedios: respuesta=%.2f espera=%.2f retorno=%.2f\n",
           sr / n, sw / n, st / n);
    return 0;
}

$ gcc -std=c17 -Wall -Wextra -o gantt_fcfs gantt_fcfs.c
$ ./gantt_fcfs
Gantt: [P1 0-5] [P2 5-8] [P3 8-12] [P4 12-14]

Proc Llegada  Rafaga  Inicio     Fin    Resp  Espera  Retorno
P1        0       5       0       5       0       0       5
P2        1       3       5       8       4       4       7
P3        2       4       8      12       6       6      10
P4        4       2      12      14       8       8      10

Promedios: respuesta=4.50 espera=4.50 retorno=8.00

El programa reproduce la tabla del ejemplo 1. Cambiar el algoritmo consiste en cambiar el orden en que se asignan los bloques; el dibujo del Gantt y el cálculo de las métricas no cambian. En el tema 9 convertirás esta lógica en una función JavaScript reutilizable para todos los algoritmos.

12. Resumen

• El tiempo de respuesta R_i = S_i − A_i mide cuánto tarda un proceso en recibir la CPU por primera vez.
• Es la métrica de la interactividad: por debajo de 100 ms se percibe como instantáneo.
• Respuesta ≤ espera ≤ retorno. Si no hay apropiación, respuesta = espera.
• Round Robin mejora la respuesta a costa de empeorar la espera y el retorno.
• Un diagrama de Gantt es la línea de tiempo de la CPU: bloques proporcionales a la duración, con marcas de tiempo.
• Para leer un Gantt: S_i es el borde izquierdo del primer bloque del proceso; F_i es el borde derecho de su último bloque.
• Para dibujar un Gantt: simula el algoritmo, marca los huecos como «ociosa» y verifica que las longitudes sumen las ráfagas.
• Sobre un Gantt se calculan las tres métricas con las mismas fórmulas: respuesta, espera y retorno.
• Los Gantt con E/S usan una fila aparte para la E/S y dejan huecos de CPU cuando no hay trabajo listo.

13. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Dibuja el Gantt para los procesos P1(0,6), P2(1,4), P3(2,2) en FCFS y calcula las tres métricas.
2. Dibuja el Gantt para el mismo conjunto con Round Robin y quantum 2. Compara las respuestas.
3. Dibuja un Gantt con E/S para un proceso con ráfagas CPU 2, E/S 4, CPU 3 y otro con CPU 5. Calcula las métricas.
4. Modifica gantt_fcfs.c para simular SJF en lugar de FCFS y compara los Gantt.
5. Dado un Gantt, identifica qué algoritmo lo generó y justifica.
6. Calcula el throughput y la utilización de la CPU para el ejemplo 1.