1. Qué es la planificación por prioridades
La planificación por prioridades asigna a cada proceso un número de prioridad (un entero). La CPU se da al proceso listo con la mayor prioridad (el número más alto o más bajo, según la convención). Si hay varios con la misma prioridad, se desempata por FCFS o por otro criterio.
La planificación por prioridades es más general que SJF: SJF es un caso particular donde la prioridad es la ráfaga inversa (más corta = mayor prioridad). Las prioridades permiten expresar criterios arbitrarios: importancia del usuario, tipo de proceso, tiempo de espera, etc.
Las prioridades se usan en todos los sistemas operativos reales. En Linux, por ejemplo, los procesos tienen una prioridad interna (prio) que depende del valor nice y de la clase de planificación. Las políticas de tiempo real (SCHED_FIFO, SCHED_RR) usan prioridades del 1 al 99.
La convención varía. En Unix/Linux, una prioridad más baja (menor número) significa mayor prioridad. En Windows, una prioridad más alta (mayor número) significa mayor prioridad. En este curso usaremos la convención de que mayor número = mayor prioridad, que es la más intuitiva.
2. Cómo se asignan las prioridades
Las prioridades se pueden asignar de varias formas:
- Por el usuario: el usuario indica la prioridad al lanzar el proceso (por ejemplo,
niceen Unix). - Por el sistema: el sistema asigna la prioridad según el tipo de proceso (interactivo vs por lotes, sistema vs usuario).
- Por el proceso: el proceso solicita una prioridad al sistema operativo.
- Por parámetros: la prioridad depende de parámetros medibles (tiempo de espera, uso de CPU, memoria).
En la práctica, las prioridades suelen ser una combinación: el sistema asigna una prioridad base según el tipo de proceso, y el usuario o el proceso puede ajustarla dentro de un rango.
3. Prioridades estáticas
Las prioridades estáticas se asignan al crear el proceso y no cambian durante su vida. El proceso mantiene la misma prioridad desde que nace hasta que muere.
Ventajas:
- Simplicidad: no hay que actualizar las prioridades.
- Predecibilidad: el comportamiento del proceso es estable.
- Bajo overhead: no hay cálculos de prioridad en tiempo de ejecución.
Desventajas:
- Inflexibilidad: si un proceso necesita más prioridad temporalmente, no se la puede dar.
- Inanición: un proceso de baja prioridad puede esperar indefinidamente si siempre hay procesos de alta prioridad.
- No se adapta: no tiene en cuenta el comportamiento del proceso (cuánto CPU ha usado, cuánto ha esperado).
Las prioridades estáticas se usan en sistemas de tiempo real (SCHED_FIFO, SCHED_RR en Linux), donde la prioridad es fija y el programador es responsable de asignarla correctamente.
4. Prioridades dinámicas
Las prioridades dinámicas cambian durante la vida del proceso, según su comportamiento o según parámetros del sistema. El planificador ajusta la prioridad automáticamente.
Ejemplos de ajuste dinámico:
- Por uso de CPU: un proceso que usa mucha CPU baja su prioridad; uno que usa poca sube. Esto favorece a los procesos interactivos.
- Por tiempo de espera: un proceso que espera mucho sube su prioridad (envejecimiento).
- Por tipo de ráfaga: un proceso con ráfagas cortas sube su prioridad; uno con ráfagas largas baja.
- Por nice: el usuario puede ajustar la prioridad con nice/renice.
Las prioridades dinámicas resuelven el problema de la inanición (con envejecimiento) y se adaptan al comportamiento del proceso. Son más complejas de implementar pero más justas y eficientes.
Linux usa prioridades dinámicas en la clase normal (SCHED_OTHER): la prioridad interna cambia según el uso de CPU y el nice. Los procesos que usan mucha CPU bajan su prioridad; los interactivos suben.
5. Versión no apropiativa
En la versión no apropiativa, una vez que un proceso recibe la CPU, la conserva hasta que termina su ráfaga o se bloquea en E/S. El planificador no interrumpe al proceso en ejecución, aunque llegue un proceso con mayor prioridad.
El algoritmo es:
- Llega un proceso. Se añade a la cola de listos con su prioridad. llegada
- La CPU queda libre. Se busca el proceso listo con la mayor prioridad. decisión
- El proceso se ejecuta. Conserva la CPU hasta que termina o se bloquea. ejecución
- Se repite. bucle
La versión no apropiativa es más simple (no hay que manejar interrupciones), pero menos responsive: un proceso de alta prioridad que llega mientras uno de baja prioridad se ejecuta debe esperar.
6. Versión apropiativa
En la versión apropiativa, si llega un proceso con mayor prioridad que el que se está ejecutando, el planificador interrumpe al proceso en curso y le da la CPU al nuevo.
El algoritmo es:
- Llega un proceso. Se añade a la cola de listos. llegada
- Se compara. Si la prioridad del nuevo proceso es mayor que la del proceso en ejecución, se interrumpe al proceso en curso. comparar
- Se cambia de contexto. El proceso interrumpido vuelve a la cola con su tiempo restante. El nuevo proceso recibe la CPU. contexto
- Se repite. bucle
La versión apropiativa es más responsive (un proceso de alta prioridad se ejecuta inmediatamente), pero tiene más overhead (cambios de contexto) y es más compleja.
La apropiación por prioridad interrumpe cuando llega un proceso de mayor prioridad. SRTF interrumpe cuando llega un proceso con menos tiempo restante. Son criterios distintos: uno se basa en la importancia, el otro en la duración.
7. Desempate entre prioridades iguales
Cuando varios procesos tienen la misma prioridad, hay que desempatar. Las opciones más comunes son:
| Método de desempate | Cómo funciona | Ventaja | Desventaja |
|---|---|---|---|
| FCFS | El que llegó primero se ejecuta primero. | Justo, simple. | Puede causar efecto convoy entre procesos de la misma prioridad. |
| SJF | El más corto se ejecuta primero. | Minimiza la espera. | Necesita conocer las ráfagas. |
| Round Robin | Se reparten la CPU en turnos. | Buena respuesta. | Más cambios de contexto. |
| Prioridad secundaria | Se usa otro criterio (por ejemplo, el pid). | Determinista. | Arbitrario. |
En la práctica, Linux usa Round Robin para desempatar procesos de la misma prioridad en la clase de tiempo real (SCHED_RR), y FCFS en la clase normal (SCHED_OTHER, donde la prioridad es dinámica y rara vez hay empates exactos).
8. Cómo se implementa
La implementación de la planificación por prioridades depende de cómo se representan las colas de listos:
- Una sola cola ordenada: la cola de listos se mantiene ordenada por prioridad. Al añadir un proceso, se inserta en la posición correcta (O(n)). Al sacar, se toma el primero (O(1)).
- Varias colas (una por prioridad): cada prioridad tiene su propia cola FIFO. Al sacar, se busca la cola de mayor prioridad no vacía (O(1) si se mantiene un bitmap de colas no vacías). Esta es la implementación más común.
- Heap: la cola de listos es un heap (montículo) ordenado por prioridad. Insertar y sacar son O(log n).
Linux usa una implementación con varias colas: cada prioridad tiene su propia cola, y un bitmap indica qué colas tienen procesos. Esto permite seleccionar el proceso de mayor prioridad en O(1).
9. Propiedades
| Propiedad | ¿La cumple? | Comentario |
|---|---|---|
| Flexibilidad | Sí | Permite expresar criterios arbitrarios. |
| Justicia | Depende | Depende de cómo se asignen las prioridades. |
| Ausencia de inanición | No (sin envejecimiento) | Los procesos de baja prioridad pueden esperar indefinidamente. |
| Minimiza espera promedio | No | SJF es mejor para eso. |
| Minimiza respuesta | No | Round Robin es mejor. |
| Predecibilidad | Sí | El orden depende de las prioridades, que son conocidas. |
10. Ventajas
- Flexibilidad: permite favorecer a procesos importantes sin cambiar el algoritmo.
- Expresividad: las prioridades pueden reflejar criterios arbitrarios (importancia, urgencia, tipo de proceso).
- Uso real: todos los sistemas operativos usan prioridades.
- Combinable: se puede combinar con FCFS, SJF o Round Robin para desempatar.
11. Desventajas
- Inanición: los procesos de baja prioridad pueden esperar indefinidamente.
- Inversión de prioridades: un proceso de alta prioridad puede bloquearse esperando un recurso que tiene un proceso de baja prioridad (tema 35).
- Complejidad: hay que definir, asignar y actualizar las prioridades.
- Subjetividad: la asignación de prioridades es a menudo arbitraria.
12. Simulador interactivo
Este simulador ejecuta la planificación por prioridades (no apropiativa) sobre una carga de trabajo. Cada proceso tiene una prioridad; el de mayor prioridad se ejecuta primero:
Simulador · prioridades (no apropiativo)
| Proceso | Llegada | Ráfaga | Prioridad | Inicio | Fin | Respuesta | Espera | Retorno |
|---|---|---|---|---|---|---|---|---|
13. Resumen
- La planificación por prioridades ejecuta primero el proceso con la mayor prioridad.
- Las prioridades estáticas no cambian; las dinámicas se ajustan según el comportamiento.
- La versión no apropiativa no interrumpe al proceso en ejecución.
- La versión apropiativa interrumpe si llega un proceso de mayor prioridad.
- Los empates se desempatan por FCFS, SJF, Round Robin o prioridad secundaria.
- La implementación más común usa una cola por prioridad.
- Las prioridades estáticas se usan en sistemas de tiempo real.
- Las prioridades dinámicas se usan en sistemas de propósito general (Linux).
- La inanición se evita con envejecimiento.
- La inversión de prioridades es un problema que se estudia en el tema 35.
14. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es la planificación por prioridades?
Asignar a cada proceso un número de prioridad y ejecutar primero el de mayor prioridad.
2. ¿Cuál es la diferencia entre prioridades estáticas y dinámicas?
Las estáticas no cambian durante la vida del proceso; las dinámicas se ajustan según el comportamiento.
3. ¿En qué se diferencia la versión apropiativa de la no apropiativa?
La apropiativa interrumpe al proceso en curso si llega uno de mayor prioridad; la no apropiativa no.
4. ¿Cómo se desempatan procesos con la misma prioridad?
Por FCFS, SJF, Round Robin o prioridad secundaria.
5. ¿Qué es la inanición en la planificación por prioridades?
Un proceso de baja prioridad espera indefinidamente porque siempre hay procesos de mayor prioridad.
6. ¿Cómo se evita la inanición?
Con envejecimiento: aumentar la prioridad de los procesos que llevan mucho tiempo esperando.
7. ¿Qué es la inversión de prioridades?
Un proceso de alta prioridad se bloquea esperando un recurso que tiene un proceso de baja prioridad.
8. ¿Cómo implementa Linux la planificación por prioridades?
Con una cola por prioridad y un bitmap de colas no vacías, para seleccionar en O(1).
9. ¿Qué prioridades usan SCHED_FIFO y SCHED_RR?
Prioridades del 1 al 99 (mayor número = mayor prioridad).
10. ¿Es SJF un caso particular de planificación por prioridades?
Sí: la prioridad es la ráfaga inversa (más corta = mayor prioridad).
Para practicar
- Modifica el simulador para añadir la versión apropiativa y compara.
- Diseña un conjunto de procesos donde la inanición sea evidente.
- Implementa el envejecimiento en el simulador y verifica que evita la inanición.
- Compara la planificación por prioridades con SJF para el mismo conjunto.
- Explica cómo Linux combina prioridades con nice y CFS.
- Diseña un esquema de prioridades dinámicas basado en el tiempo de espera.