1. Qué es SRTF
SRTF (Shortest Remaining Time First) es la versión apropiativa de SJF. En lugar de elegir el proceso con la ráfaga más corta al empezar, elige el proceso con el tiempo restante más corto en cada instante. Si llega un proceso cuyo tiempo restante es menor que el del que se está ejecutando, el planificador interrumpe al proceso en curso (le quita la CPU) y le da la CPU al nuevo.
La diferencia entre SJF y SRTF está en la apropiación:
- SJF (no apropiativo): una vez que un proceso recibe la CPU, la conserva hasta que termina su ráfaga.
- SRTF (apropiativo): el planificador puede quitarle la CPU a un proceso en cualquier momento si llega uno con menos tiempo restante.
SRTF es el algoritmo que minimiza el tiempo de espera promedio incluso con llegadas distintas. Es el límite teórico: ningún otro algoritmo (sin conocer el futuro) puede hacerlo mejor en términos de tiempo de espera promedio.
SRTF debe saber, en cada instante, cuánto tiempo le queda a cada proceso. Eso requiere conocer las ráfagas completas de antemano y actualizar el tiempo restante cada vez que un proceso recibe CPU. En la práctica, esto es aún más difícil que en SJF.
2. Cómo funciona
SRTF se basa en un evento que SJF no tiene: la llegada de un proceso mientras otro se está ejecutando. En ese momento, el planificador compara el tiempo restante del proceso en ejecución con la ráfaga del recién llegado:
- Llega un proceso. Se añade a la cola de listos. llegada
- Se compara. Si la ráfaga del nuevo proceso es menor que el tiempo restante del proceso en ejecución, se interrumpe al proceso en curso. comparar
- Se cambia de contexto. El proceso interrumpido vuelve a la cola de listos con su tiempo restante actualizado. El nuevo proceso recibe la CPU. contexto
- Se repite. En cada llegada (y en cada terminación) se reevalúa. bucle
El tiempo restante de un proceso se actualiza cada vez que recibe CPU: si un proceso con ráfaga 8 recibe 3 unidades y luego es interrumpido, su tiempo restante es 5. Cuando vuelva a ejecutarse, continuará desde donde se quedó.
La clave es que SRTF no reinicia los procesos: un proceso interrumpido conserva su progreso. Eso lo diferencia de Round Robin, donde cada proceso recibe un quantum completo y luego se interrumpe, independientemente de cuánto le quede.
3. Un ejemplo desarrollado
Cuatro procesos con llegadas distintas:
| Proceso | Llegada | Ráfaga |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 2 |
| P4 | 3 | 1 |
Simulación paso a paso:
- t = 0: llega P1. La CPU está libre, se le da. Tiempo restante de P1: 8. llegada
- t = 1: llega P2 (ráfaga 4). Tiempo restante de P1: 7. Como 4 < 7, se interrumpe P1. P2 recibe la CPU. interrupción
- t = 2: llega P3 (ráfaga 2). Tiempo restante de P2: 3. Como 2 < 3, se interrumpe P2. P3 recibe la CPU. interrupción
- t = 3: llega P4 (ráfaga 1). Tiempo restante de P3: 1. Como 1 no es menor que 1 (empate), no se interrumpe. P3 sigue. empate
- t = 4: P3 termina (ráfaga 2, empezó en 2). Se elige el proceso con menos tiempo restante entre los listos: P4 (1), P2 (3), P1 (7). P4 recibe la CPU. decisión
- t = 5: P4 termina. Se elige entre P2 (3) y P1 (7). P2 recibe la CPU. decisión
- t = 8: P2 termina. P1 recibe la CPU con tiempo restante 7. decisión
- t = 15: P1 termina. fin
El Gantt resultante es:
Las métricas (leyendo el Gantt: S es el borde izquierdo del primer bloque, F es el borde derecho del último bloque):
| Proceso | Llegada | Ráfaga | Primer bloque | Último bloque | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 0-1 | 8-15 | 0 | 7 | 15 |
| P2 | 1 | 4 | 1-2 | 5-8 | 0 | 3 | 7 |
| P3 | 2 | 2 | 2-4 | 2-4 | 0 | 0 | 2 |
| P4 | 3 | 1 | 4-5 | 4-5 | 1 | 1 | 2 |
| Promedio | 0,25 | 2,75 | 6,50 |
El tiempo de respuesta promedio es 0,25: casi instantáneo, porque cada proceso recibe la CPU poco después de llegar. El tiempo de espera promedio es 2,75, igual que SJF no apropiativo para el mismo conjunto (con llegadas distintas, SJF no apropiativo daba espera 5,50; ver tema 13). SRTF mejora significativamente.
4. SRTF vs SJF no apropiativo
Comparemos SRTF con SJF no apropiativo para el mismo conjunto del ejemplo anterior (P1(0,8), P2(1,4), P3(2,2), P4(3,1)):
| Métrica | SJF no apropiativo | SRTF |
|---|---|---|
| Tiempo de respuesta promedio | 4,50 | 0,25 |
| Tiempo de espera promedio | 5,50 | 2,75 |
| Tiempo de retorno promedio | 9,25 | 6,50 |
| Cambios de contexto | 3 | 5 |
SRTF mejora todas las métricas, pero a costa de más cambios de contexto (5 en lugar de 3). El proceso P1 se interrumpe dos veces (en t=1 y t=2) y P2 una vez (en t=2).
La diferencia clave está en los procesos que llegan mientras uno largo se ejecuta. SJF no apropiativo no puede interrumpir al largo, así que los procesos cortos que llegan después esperan. SRTF sí interrumpe, lo que reduce drásticamente la espera y la respuesta.
Si todos los procesos llegan en 0, SJF y SRTF coinciden: no hay llegadas durante la ejecución, así que no hay interrupciones. La diferencia solo aparece con llegadas distintas.
5. Optimalidad con llegadas distintas
SRTF minimiza el tiempo de espera promedio incluso con llegadas distintas. La demostración es una extensión del argumento de intercambio del tema 13:
Si en un instante t se está ejecutando un proceso con tiempo restante r y llega un proceso con ráfaga b < r, interrumpir al proceso en curso y ejecutar el nuevo reduce la suma de esperas. La razón es la misma: el proceso nuevo es más corto, así que ponerlo primero (aunque sea a mitad de la ejecución del otro) reduce la espera total.
Por eso, SRTF es el algoritmo óptimo para el tiempo de espera promedio, incluso con llegadas distintas. Ningún otro algoritmo (sin conocer el futuro) puede hacerlo mejor.
La optimalidad se refiere al tiempo de espera promedio, no al tiempo de respuesta ni a la equidad. SRTF puede tener un tiempo de respuesta peor que Round Robin para algunos procesos, y puede ser injusto con los procesos largos.
6. El costo: cambios de contexto
Cada interrupción en SRTF implica un cambio de contexto: guardar el estado del proceso interrumpido, actualizar su tiempo restante, cargar el estado del nuevo proceso. Este costo no es gratuito:
- Más cambios de contexto: SRTF interrumpe cada vez que llega un proceso más corto. En el peor caso, cada llegada provoca una interrupción.
- Más overhead: cada cambio de contexto consume tiempo de CPU que no se dedica a los procesos.
- Mayor complejidad: hay que mantener el tiempo restante de cada proceso y actualizarlo en cada ejecución.
En el ejemplo anterior, SRTF hizo 5 cambios de contexto (incluyendo el inicial y el final) frente a 3 de SJF no apropiativo. Si las ráfagas son muy cortas y las llegadas muy frecuentes, el overhead puede ser significativo.
Si los cambios de contexto son muy frecuentes, el tiempo que se gasta en ellos puede superar el ahorro en tiempo de espera. En la práctica, se usa un quantum mínimo: no se interrumpe si el tiempo restante del proceso en curso es solo un poco mayor que el del nuevo.
7. Propiedades de SRTF
| Propiedad | ¿La cumple? | Comentario |
|---|---|---|
| Minimiza espera promedio | Sí | Incluso con llegadas distintas. |
| Minimiza retorno promedio | Sí | Porque retorno = espera + ráfaga. |
| Buen tiempo de respuesta | Sí | Los procesos cortos reciben la CPU rápidamente. |
| Simplicidad | No | Más complejo que SJF: hay que manejar interrupciones y tiempos restantes. |
| Justicia (fairness) | No | Los procesos largos pueden esperar mucho (inanición). |
| Ausencia de inanición | No | Sin envejecimiento, un flujo de procesos cortos posterga a los largos. |
| Overhead | Alto | Cambios de contexto en cada interrupción. |
8. Ventajas
- Minimiza el tiempo de espera promedio: incluso con llegadas distintas, es el algoritmo óptimo.
- Buen tiempo de respuesta: los procesos cortos reciben la CPU rápidamente, aunque lleguen tarde.
- Reduce el efecto convoy: un proceso largo se interrumpe cuando llega uno más corto.
- Mejor que SJF no apropiativo: con llegadas distintas, todas las métricas son mejores.
9. Desventajas
- Necesita conocer las ráfagas: igual que SJF, pero además debe actualizar los tiempos restantes.
- Más cambios de contexto: cada interrupción implica un cambio de contexto.
- Inanición: los procesos largos pueden esperar indefinidamente.
- No es justo: un proceso largo puede ser interrumpido muchas veces.
- Complejidad de implementación: hay que manejar temporizadores y estados de proceso.
Igual que SJF, SRTF no se usa directamente en sistemas reales porque necesita conocer las ráfagas. Pero es el límite teórico: ningún algoritmo puede hacerlo mejor en tiempo de espera promedio. Los algoritmos reales (Round Robin, CFS) se acercan a SRTF sin necesitar conocer las ráfagas.
10. Inanición
SRTF sufre inanición igual que SJF: un flujo continuo de procesos cortos puede postergar indefinidamente a uno largo. De hecho, SRTF es más propenso a la inanición que SJF, porque interrumpe al proceso largo cada vez que llega uno más corto.
La solución es la misma: envejecimiento. Con envejecimiento, el tiempo restante estimado de un proceso que lleva mucho tiempo esperando se reduce, haciéndolo más atractivo para el planificador.
11. Simulador interactivo
Este simulador ejecuta SRTF sobre una carga de trabajo con llegadas distintas. Cambia los parámetros y observa cómo se interrumpen los procesos:
Simulador · SRTF
| Proceso | Llegada | Ráfaga | Inicio | Fin | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|
12. Resumen
- SRTF es la versión apropiativa de SJF: interrumpe al proceso en curso si llega uno con menos tiempo restante.
- Minimiza el tiempo de espera promedio incluso con llegadas distintas.
- Es el límite teórico: ningún algoritmo puede hacerlo mejor en tiempo de espera promedio.
- Mejora todas las métricas respecto a SJF no apropiativo cuando hay llegadas distintas.
- El costo es más cambios de contexto y mayor complejidad.
- Sufre inanición igual que SJF; se evita con envejecimiento.
- No se usa directamente en sistemas reales porque necesita conocer las ráfagas.
- Coincide con SJF cuando todos los procesos llegan en 0.
13. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es SRTF?
La versión apropiativa de SJF: elige el proceso con el tiempo restante más corto y puede interrumpir al proceso en curso.
2. ¿En qué se diferencia SRTF de SJF no apropiativo?
SRTF puede interrumpir a un proceso en ejecución si llega uno con menos tiempo restante. SJF no apropiativo no puede.
3. ¿Minimiza SRTF el tiempo de espera promedio con llegadas distintas?
Sí. Es el algoritmo óptimo para el tiempo de espera promedio, incluso con llegadas distintas.
4. ¿Cuándo coinciden SJF y SRTF?
Cuando todos los procesos llegan en 0: no hay llegadas durante la ejecución, así que no hay interrupciones.
5. ¿Cuál es el principal costo de SRTF?
Más cambios de contexto: cada interrupción implica guardar y restaurar el estado del proceso.
6. ¿Sufre SRTF inanición?
Sí. Un flujo continuo de procesos cortos puede postergar indefinidamente a uno largo.
7. ¿Qué es el tiempo restante de un proceso?
La parte de la ráfaga que aún no se ha ejecutado. Se actualiza cada vez que el proceso recibe CPU.
8. ¿Qué ocurre si un proceso llega con la misma ráfaga que el tiempo restante del proceso en curso?
No se interrumpe (empate). El proceso en curso sigue ejecutándose.
9. ¿Por qué SRTF no se usa directamente en sistemas reales?
Porque necesita conocer las ráfagas de antemano y actualizar los tiempos restantes, lo que es impracticable.
10. ¿Qué algoritmo real se acerca a SRTF sin conocer las ráfagas?
Round Robin (con quantum corto) y CFS (con vruntime). Ambos dan turnos cortos a todos los procesos.
Para practicar
- Calcula las métricas de SRTF para P1(0,6), P2(2,4), P3(4,2) y compara con SJF no apropiativo.
- Dibuja el Gantt de SRTF para el ejemplo del tema 13 con llegadas distintas.
- Explica por qué SRTF tiene más cambios de contexto que SJF no apropiativo.
- Diseña un caso donde el overhead de SRTF anule su ventaja.
- Modifica el simulador para mostrar SRTF y SJF uno encima del otro.
- Calcula cuántos cambios de contexto hace SRTF para 5 procesos con llegadas 0, 1, 2, 3, 4 y ráfagas 10, 1, 1, 1, 1.