1. Por qué necesitamos criterios
Para comparar dos algoritmos de planificación, necesitamos criterios (métricas) que nos digan cuán bueno es cada uno. Sin criterios, la comparación es subjetiva: "este algoritmo se siente más rápido" no es una medida útil.
Los criterios deben ser:
- Cuantificables: se pueden medir con números.
- Comparables: se pueden comparar entre algoritmos.
- Relevantes: reflejan lo que el usuario o el sistema necesita.
Hay cinco criterios clásicos que se usan en todos los libros de sistemas operativos. Cada uno mide un aspecto diferente de la planificación. Ninguno es perfecto por sí solo, y optimizar uno puede perjudicar a otro.
Sin criterios, no se puede decir si un algoritmo es mejor que otro. Los criterios nos permiten cuantificar la calidad de una planificación y comparar algoritmos de forma objetiva.
2. Uso de la CPU
El uso de la CPU (CPU utilization) es el porcentaje de tiempo que la CPU está ocupada ejecutando procesos (no ociosa). Es la métrica más básica: una CPU que está ociosa el 80 % del tiempo es un desperdicio.
Se calcula como: Uso de CPU = tiempo de CPU ocupada / tiempo total.
El objetivo es maximizar el uso de la CPU. Pero hay un límite: si todos los procesos están bloqueados esperando E/S, la CPU no tiene nada que ejecutar, y el uso baja. La multiprogramación (mantener varios procesos en memoria) ayuda a mantener la CPU ocupada.
En la práctica, un sistema bien dimensionado tiene un uso de CPU del 70-90 %. Por debajo del 50 %, la máquina está infrautilizada. Por encima del 95 %, puede haber contención y los tiempos de respuesta se degradan.
El uso de la CPU se mide con top, mpstat, o /proc/stat:
$ mpstat 1 3
Linux ... (8 CPU)
10:00:00 all %usr %nice %sys %iowait %irq %soft %steal %guest %idle
10:00:01 all 5.0 0.0 2.0 1.0 0.0 0.0 0.0 0.0 92.0
10:00:02 all 8.0 0.0 3.0 0.5 0.0 0.0 0.0 0.0 88.5
10:00:03 all 3.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 96.0
La columna %idle es el tiempo que la CPU estuvo ociosa. El uso de CPU es 100 - %idle (aproximadamente). En este ejemplo, el uso es de ~4-12 %.
3. Rendimiento (throughput)
El rendimiento (throughput) es el número de procesos que terminan por unidad de tiempo. Se mide en procesos/segundo o trabajos/minuto. Es la métrica de productividad: cuánto trabajo se completa.
El objetivo es maximizar el throughput. Pero hay un límite: si se ejecutan demasiados procesos a la vez, el overhead de cambios de contexto reduce el throughput.
El throughput depende de:
- La duración de los procesos: procesos cortos dan más throughput.
- El número de procesos: más procesos pueden dar más throughput (hasta cierto punto).
- El overhead de planificación: cambios de contexto, latencia de despacho.
- La E/S: si los procesos esperan E/S, el throughput baja.
El throughput se mide como: throughput = número de procesos terminados / tiempo total.
En el ejemplo del tema 1, tres procesos de 2 unidades terminaron en 2.09 s, dando un throughput de 3/2.09 = 1.43 procesos/s. Si se ejecutaran secuencialmente, también serían 3/2.10 = 1.43 procesos/s. El throughput no cambió, pero los tiempos de espera sí.
4. Tiempo de retorno (turnaround)
El tiempo de retorno (turnaround time) es el tiempo total que un proceso pasa en el sistema, desde que llega hasta que termina. Incluye el tiempo de espera en la cola de listos, el tiempo de ejecución en la CPU, y el tiempo de espera de E/S.
Se calcula como: turnaround = tiempo de terminación - tiempo de llegada.
El objetivo es minimizar el tiempo de retorno promedio. Pero hay un trade-off: minimizar el promedio puede perjudicar a procesos individuales.
El tiempo de retorno se descompone en:
- Tiempo de espera en la cola: el tiempo que el proceso estuvo listo pero sin CPU.
- Tiempo de ejecución en la CPU: el tiempo que el proceso usó la CPU.
- Tiempo de espera de E/S: el tiempo que el proceso esperó por operaciones de E/S.
El tiempo de ejecución en la CPU y el tiempo de espera de E/S son fijos (los determina el programa). El tiempo de espera en la cola es lo que el planificador puede influir.
Por eso, el tiempo de espera (waiting time) es una métrica más precisa que el tiempo de retorno: mide solo lo que el planificador puede controlar.
5. Tiempo de espera (waiting)
El tiempo de espera (waiting time) es el tiempo que un proceso pasa en la cola de listos, esperando la CPU. No incluye el tiempo de ejecución en la CPU ni el tiempo de espera de E/S. Es la métrica que el planificador puede influir directamente.
Se calcula como: waiting = turnaround - tiempo de CPU - tiempo de E/S.
El objetivo es minimizar el tiempo de espera promedio. Un tiempo de espera bajo significa que los procesos no esperan mucho en la cola.
El tiempo de espera depende del algoritmo:
- FCFS: un proceso largo al principio hace que todos los demás esperen mucho.
- SJF: minimiza el tiempo de espera promedio (ejecutando primero los cortos).
- Round Robin: todos los procesos esperan aproximadamente lo mismo.
El tiempo de espera es la métrica más usada para comparar algoritmos, porque refleja directamente la calidad de la planificación.
6. Tiempo de respuesta (response)
El tiempo de respuesta (response time) es el tiempo desde que un proceso llega al sistema hasta que recibe la CPU por primera vez. Es la métrica de interactividad: cuánto tarda el sistema en responder al usuario.
Se calcula como: response = tiempo de primera ejecución - tiempo de llegada.
El objetivo es minimizar el tiempo de respuesta, especialmente para procesos interactivos. Un tiempo de respuesta bajo significa que el sistema responde rápidamente al usuario.
El tiempo de respuesta es diferente del tiempo de espera: el tiempo de espera es el tiempo total en la cola, mientras que el tiempo de respuesta es solo el tiempo hasta la primera ejecución.
Para procesos interactivos (como un editor de texto o una shell), el tiempo de respuesta es la métrica más importante. Para procesos por lotes (como una compilación), el tiempo de retorno es más importante.
El tiempo de respuesta mide solo el primer turno de CPU. El tiempo de espera mide todo el tiempo en la cola. Un proceso puede tener un tiempo de respuesta bajo (recibe la CPU rápidamente) pero un tiempo de espera alto (espera mucho entre turnos).
7. Por qué no se pueden optimizar todos
Los cinco criterios compiten entre sí. Optimizar uno puede perjudicar a otro. Esto es porque los recursos son limitados: la CPU es un recurso compartido, y dar más a uno significa dar menos a otro.
Los trade-offs principales son:
- Throughput vs response time: para maximizar el throughput, se deben ejecutar procesos largos sin interrupción (FCFS). Pero esto perjudica el response time de los procesos cortos. Para minimizar el response time, se deben cambiar de proceso frecuentemente (Round Robin), lo que reduce el throughput.
- Fairness vs throughput: para ser justo, se debe dar a cada proceso su parte equitativa de CPU. Pero esto puede reducir el throughput si los procesos tienen duraciones muy distintas.
- Waiting time vs response time: minimizar el waiting time promedio (SJF) puede perjudicar el response time de los procesos largos, que esperan más.
- CPU utilization vs response time: mantener la CPU al 100 % (multiprogramación) puede aumentar el tiempo de respuesta si hay demasiados procesos compitiendo.
Por eso, no existe un algoritmo que sea el mejor en todos los criterios. La elección depende de qué criterio es más importante para el caso de uso.
Los criterios compiten. Optimizar uno perjudica a otro. La elección del algoritmo depende de qué criterio es más importante para el caso de uso. No hay un algoritmo "perfecto".
8. Ejemplos de trade-offs
Veamos un ejemplo concreto para ilustrar los trade-offs. Supongamos tres procesos con ráfagas de 24, 3 y 3 (como en el tema 1):
| Algoritmo | Tiempo de espera promedio | Tiempo de retorno promedio | Tiempo de respuesta promedio | Throughput |
|---|---|---|---|---|
| FCFS (orden 24, 3, 3) | 17 | 27 | 17 | 3/30 = 0.10 |
| SJF (orden 3, 3, 24) | 3 | 13 | 3 | 3/30 = 0.10 |
| Round Robin (quantum 4) | 14.7 | 24.7 | 4 | 3/26 = 0.12 |
Observaciones:
- SJF minimiza el tiempo de espera y de retorno promedio: 3 y 13, respectivamente. Pero el proceso de 24 unidades espera 6 (mientras se ejecutan los dos de 3).
- FCFS maximiza el tiempo de espera: 17, porque el proceso de 24 va primero.
- Round Robin tiene el mejor tiempo de respuesta: 4 (el primer proceso recibe la CPU en el primer turno). Pero el tiempo de espera y de retorno son peores que SJF.
- El throughput es similar: todos terminan en ~30 unidades de tiempo.
Este ejemplo muestra que no hay un algoritmo que sea el mejor en todos los criterios. SJF es mejor en waiting y turnaround, pero Round Robin es mejor en response time.
9. Un programa que mide los criterios
El siguiente programa calcula las métricas para un conjunto de procesos con un algoritmo dado:
#define _POSIX_C_SOURCE 200809L
#include
#include
/* Estructura de un proceso */
struct proceso {
int pid;
int llegada;
int rafaga;
int inicio; /* cuando empezo a ejecutarse */
int fin; /* cuando termino */
};
/* Calcular metricas para un orden dado */
static void calcular_metricas(struct proceso *procs, int n)
{
int tiempo = 0;
int suma_espera = 0, suma_retorno = 0, suma_respuesta = 0;
for (int i = 0; i < n; i++) {
procs[i].inicio = tiempo;
procs[i].fin = tiempo + procs[i].rafaga;
tiempo = procs[i].fin;
int espera = procs[i].inicio - procs[i].llegada;
int retorno = procs[i].fin - procs[i].llegada;
int respuesta = procs[i].inicio - procs[i].llegada;
suma_espera += espera;
suma_retorno += retorno;
suma_respuesta += respuesta;
printf("P%d: llegada=%d, rafaga=%d, inicio=%d, fin=%d, espera=%d, retorno=%d, respuesta=%d\n",
procs[i].pid, procs[i].llegada, procs[i].rafaga,
procs[i].inicio, procs[i].fin, espera, retorno, respuesta);
}
printf("Promedio: espera=%.2f, retorno=%.2f, respuesta=%.2f\n",
(double) suma_espera / n,
(double) suma_retorno / n,
(double) suma_respuesta / n);
printf("Throughput: %.4f procesos/unidad\n", (double) n / tiempo);
}
int main(void)
{
/* Tres procesos: P1 (rafaga 24), P2 (rafaga 3), P3 (rafaga 3) */
struct proceso procs[3] = {
{1, 0, 24, 0, 0},
{2, 0, 3, 0, 0},
{3, 0, 3, 0, 0}
};
/* Orden: P1, P2, P3 (FCFS) */
printf("=== Orden: P1, P2, P3 ===\n");
calcular_metricas(procs, 3);
/* Orden: P2, P3, P1 (SJF) */
struct proceso procs2[3] = {
{2, 0, 3, 0, 0},
{3, 0, 3, 0, 0},
{1, 0, 24, 0, 0}
};
printf("\n=== Orden: P2, P3, P1 ===\n");
calcular_metricas(procs2, 3);
return 0;
}
$ gcc -std=c17 -Wall -Wextra -o medir_criterios medir_criterios.c
$ ./medir_criterios
=== Orden: P1, P2, P3 ===
P1: llegada=0, rafaga=24, inicio=0, fin=24, espera=0, retorno=24, respuesta=0
P2: llegada=0, rafaga=3, inicio=24, fin=27, espera=24, retorno=27, respuesta=24
P3: llegada=0, rafaga=3, inicio=27, fin=30, espera=27, retorno=30, respuesta=27
Promedio: espera=17.00, retorno=27.00, respuesta=17.00
Throughput: 0.1000 procesos/unidad
=== Orden: P2, P3, P1 ===
P2: llegada=0, rafaga=3, inicio=0, fin=3, espera=0, retorno=3, respuesta=0
P3: llegada=0, rafaga=3, inicio=3, fin=6, espera=3, retorno=6, respuesta=3
P1: llegada=0, rafaga=24, inicio=6, fin=30, espera=6, retorno=30, respuesta=6
Promedio: espera=3.00, retorno=13.00, respuesta=3.00
Throughput: 0.1000 procesos/unidad
El programa demuestra que el orden P2, P3, P1 (SJF) tiene mucho mejor tiempo de espera y de retorno promedio que el orden P1, P2, P3 (FCFS). El throughput es el mismo (0.10 procesos/unidad) porque el trabajo total es el mismo.
10. Resumen
- Hay cinco criterios clásicos: uso de CPU, throughput, turnaround, waiting, response.
- El uso de CPU mide el porcentaje de tiempo que la CPU está ocupada.
- El throughput mide cuántos procesos terminan por unidad de tiempo.
- El turnaround es el tiempo total que un proceso pasa en el sistema.
- El waiting es el tiempo que un proceso pasa en la cola de listos.
- El response es el tiempo hasta la primera ejecución.
- No se pueden optimizar todos los criterios a la vez: hay trade-offs.
- SJF minimiza waiting y turnaround, pero Round Robin minimiza response.
11. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. Qué mide el uso de la CPU?
El porcentaje de tiempo que la CPU está ocupada ejecutando procesos (no ociosa).
2. Qué mide el throughput?
El número de procesos que terminan por unidad de tiempo.
3. Qué es el turnaround time?
El tiempo total que un proceso pasa en el sistema, desde que llega hasta que termina.
4. Qué es el waiting time?
El tiempo que un proceso pasa en la cola de listos, esperando la CPU. Es la métrica que el planificador puede influir directamente.
5. Qué es el response time?
El tiempo desde que un proceso llega hasta que recibe la CPU por primera vez. Es la métrica de interactividad.
6. Por qué no se pueden optimizar todos los criterios?
Porque compiten: optimizar uno perjudica a otro. Dar más CPU a un proceso significa dar menos a otro.
7. Qué algoritmo minimiza el waiting time promedio?
SJF (Shortest Job First): ejecutar primero los procesos más cortos.
8. Qué algoritmo minimiza el response time?
Round Robin: da a cada proceso un turno corto, por lo que todos reciben la CPU rápidamente.
9. El throughput cambia con el algoritmo?
No (para procesos que no hacen E/S). El trabajo total es el mismo. El throughput depende de la duración de los procesos, no del orden.
10. Cuál es la diferencia entre waiting time y response time?
Waiting time es el tiempo total en la cola. Response time es solo el tiempo hasta la primera ejecución.
Para practicar
- Compila y ejecuta medir_criterios.c. Observa las métricas para ambos órdenes.
- Modifica medir_criterios.c para calcular las métricas de Round Robin.
- Calcula a mano las métricas para 4 procesos con ráfagas 5, 2, 8, 1 en orden FCFS y SJF.
- Explica por qué SJF minimiza el waiting time promedio.
- Compara el response time de FCFS y Round Robin para los mismos procesos.
- Lee la definición de cada criterio en man 7 sched.