Cuando varios Sistemas Operativos/Procesos o Sistemas Operativos/Hilos están listos, el planificador (scheduler) decide cuál se ejecuta, usando un algoritmo de planificación.
Comportamiento de los procesos
- Limitados por CPU (CPU-bound): ráfagas largas de cómputo, poca E/S.
- Limitados por E/S (I/O-bound): ráfagas cortas de CPU, mucha E/S.
A medida que las CPUs se vuelven más rápidas que los discos, los procesos tienden a ser cada vez más limitados por E/S.
¿Cuándo planificar?
- Al crear un proceso.
- Al terminar un proceso.
- Cuando un proceso se bloquea (E/S, semáforo...).
- Al ocurrir una interrupción de E/S.
- En cada interrupción de reloj (si es apropiativo).
- No apropiativo (non-preemptive): el proceso corre hasta que se bloquea o cede la CPU.
- Apropiativo (preemptive): el proceso corre como máximo un tiempo fijo (quantum).
Metas según el entorno
| Todos los sistemas |
Por lotes |
Interactivos |
Tiempo real |
| Equidad |
Rendimiento (trabajos/hora) |
Tiempo de respuesta |
Cumplir plazos |
| Aplicar políticas |
Tiempo de retorno |
Proporcionalidad |
Predictibilidad |
| Balance (todo ocupado) |
Uso de CPU |
|
|
Algoritmos para sistemas por lotes
- FCFS (First-Come, First-Served): una cola FIFO, no apropiativo. Simple, pero un proceso largo retrasa a todos.
- SJF (Shortest Job First): ejecuta primero el trabajo más corto; óptimo en tiempo de retorno promedio cuando todos están disponibles a la vez.
- Con trabajos de 8, 4, 4, 4 min: en orden FCFS el retorno promedio es 14 min; con SJF, 11 min.
- SRTN (Shortest Remaining Time Next): versión apropiativa de SJF.
Algoritmos para sistemas interactivos
- Round Robin: cada proceso recibe un quantum; al agotarse, va al final de la cola. Un quantum muy corto genera demasiados cambios de contexto; uno muy largo empeora la respuesta. Un valor razonable es 20–50 ms.
- Por prioridad: se ejecuta el proceso listo con mayor prioridad. Riesgo de inanición, mitigado reduciendo la prioridad con el tiempo (aging). Asignar prioridad 1/f (f = fracción del quantum usada) favorece a procesos de E/S.
- Múltiples colas: clases de prioridad con quantums crecientes (CTSS).
- Proceso más corto a continuación: estimación por envejecimiento: T = a·T₀ + (1−a)·T₁.
- Planificación garantizada: con n procesos, cada uno recibe 1/n de la CPU.
- Por lotería: cada proceso tiene boletos; se sortea uno en cada decisión. Simple y proporcional.
- Por partes equitativas (fair-share): reparte la CPU por usuario, no por proceso.
Sistemas de tiempo real
- Duro (hard): los plazos son absolutos. Suave (soft): fallar ocasionalmente es tolerable.
- Con m eventos periódicos, cada uno con periodo Pᵢ y CPU Cᵢ, el sistema es planificable si: Σ Cᵢ / Pᵢ ≤ 1.
Política vs mecanismo
El kernel ofrece el mecanismo (p. ej. prioridades); el proceso padre o el usuario puede fijar la política.
Planificación de hilos
Con hilos de usuario, el kernel elige el proceso y la biblioteca el hilo. Con hilos de kernel, el kernel elige directamente el hilo, a mayor coste de cambio de contexto pero con la ventaja de que un hilo bloqueado no detiene al proceso.
En la práctica
Linux usa CFS (Completely Fair Scheduler), un árbol rojo-negro ordenado por tiempo de CPU virtual (y desde 6.6, EEVDF). Windows usa 32 niveles de prioridad con aumentos dinámicos.
#sistemas-operativos #tanenbaum #planificacion
