1. Por qué cambia el problema
Con un solo procesador, el planificador decide a quién le toca la CPU. Con varios procesadores, decide también dónde se ejecuta cada proceso. Esto introduce nuevas decisiones y nuevos problemas:
- Balanceo de carga: si un núcleo está ocupado y otro está ocioso, hay que migrar procesos para equilibrar la carga.
- Afinidad de caché: un proceso que se ha ejecutado en un núcleo tiene datos en la caché de ese núcleo. Migrarlo a otro núcleo pierde esa caché.
- Escalabilidad: con muchos núcleos, el planificador debe ser eficiente para no convertirse en un cuello de botella.
- Sincronización: varias colas requieren bloqueos (locks) para evitar condiciones de carrera.
Los algoritmos de un solo procesador (FCFS, SJF, Round Robin) no se aplican directamente: hay que adaptarlos al contexto multiprocesador.
Con N procesadores, el número de decisiones se multiplica por N. El planificador debe decidir no solo qué proceso ejecutar, sino también en qué procesador, y debe hacerlo de forma eficiente para no convertirse en un cuello de botella.
2. Multiprocesamiento asimétrico (AMP)
En el multiprocesamiento asimétrico (AMP, Asymmetric Multi-Processing), un procesador (el maestro) ejecuta el código del sistema operativo y los demás (los esclavos) ejecutan código de usuario. El maestro planifica; los esclavos ejecutan.
AMP fue el primer modelo de multiprocesamiento. Es simple de implementar porque solo hay un planificador (en el maestro), y no hay problemas de sincronización (los esclavos no acceden a las estructuras del núcleo).
Ventajas:
- Simplicidad: un solo planificador, sin sincronización.
- Sin condiciones de carrera: los esclavos no acceden a las estructuras del núcleo.
Desventajas:
- Cuello de botella: el maestro puede saturarse si hay muchos procesos.
- Desperdicio: si el maestro está ocupado planificando, los esclavos están ociosos.
- No escalable: no funciona bien con muchos procesadores.
AMP se usa en sistemas embebidos y en arquitecturas heterogéneas (big.LITTLE en ARM), pero no en servidores ni en escritorios.
3. Multiprocesamiento simétrico (SMP)
En el multiprocesamiento simétrico (SMP, Symmetric Multi-Processing), todos los procesadores son iguales y cualquiera puede ejecutar código del sistema operativo o de usuario. Cada procesador tiene su propio planificador (o comparten uno global).
SMP es el modelo usado en todos los sistemas modernos (x86, ARM multi-core). Es más complejo que AMP porque requiere sincronización (bloqueos) para acceder a las estructuras compartidas del núcleo, pero es mucho más escalable.
Ventajas:
- Escalabilidad: funciona bien con muchos procesadores.
- Sin cuello de botella: no hay un procesador maestro que se sature.
- Mejor utilización: todos los procesadores pueden ejecutar cualquier tarea.
Desventajas:
- Complejidad: requiere sincronización (bloqueos, atomic operations).
- Condiciones de carrera: si no se sincroniza correctamente, los datos se corrompen.
- Overhead de sincronización: los bloqueos consumen tiempo.
Todos los sistemas modernos (Linux, Windows, macOS) usan SMP. AMP se usa solo en sistemas embebidos y arquitecturas heterogéneas.
4. Cola global (una cola para todos)
En la arquitectura de cola global, todos los procesos listos se almacenan en una única cola compartida. Cuando un procesador queda libre, toma el siguiente proceso de la cola global.
Ventajas:
- Balanceo automático: los procesos se distribuyen automáticamente entre los procesadores.
- Simplicidad: una sola cola, un solo algoritmo.
- Sin inanición: todo proceso en la cola global será ejecutado por algún procesador.
Desventajas:
- Contención: todos los procesadores compiten por la misma cola. Se necesita un bloqueo (lock) para proteger la cola.
- No escalable: con muchos procesadores, el lock se convierte en un cuello de botella.
- Pérdida de afinidad: un proceso puede ejecutarse en un procesador diferente cada vez, perdiendo la caché.
La cola global es simple pero no escala bien. Se usa en sistemas con pocos procesadores o cuando la simplicidad es más importante que el rendimiento.
5. Cola por núcleo (una cola por CPU)
En la arquitectura de cola por núcleo, cada procesador tiene su propia cola de listos. Un proceso se asigna a una cola (y a un procesador) cuando llega, y se ejecuta en ese procesador.
Ventajas:
- Sin contención: cada procesador accede solo a su cola. No hay lock compartido.
- Escalable: funciona bien con muchos procesadores.
- Afinidad de caché: un proceso tiende a ejecutarse en el mismo procesador, preservando la caché.
Desventajas:
- Desbalanceo: si un procesador tiene muchos procesos y otro pocos, la carga está desequilibrada.
- Necesita balanceo: hay que migrar procesos entre colas para equilibrar la carga.
- Complejidad: más complejo de implementar y mantener.
La cola por núcleo es el modelo usado en sistemas modernos (Linux, Windows). El balanceo de carga se hace periódicamente o cuando se detecta un desequilibrio.
6. Comparación
| Aspecto | Cola global | Cola por núcleo |
|---|---|---|
| Contención | Alta (lock compartido) | Baja (sin lock compartido) |
| Escalabilidad | Baja | Alta |
| Balanceo de carga | Automático | Necesita balanceo explícito |
| Afinidad de caché | Baja | Alta |
| Complejidad | Baja | Alta |
| Uso real | Sistemas pequeños | Sistemas modernos (Linux, Windows) |
7. Los nuevos problemas
El multiprocesamiento introduce tres problemas nuevos que no existen en un solo procesador:
- Balanceo de carga. Si un procesador tiene muchos procesos y otro pocos, hay que migrar procesos para equilibrar. El balanceo puede ser periódico (cada cierto tiempo) o por evento (cuando se detecta un desequilibrio). balanceo
- Afinidad de caché. Un proceso que se ha ejecutado en un procesador tiene datos en la caché de ese procesador. Migrarlo a otro procesador pierde esa caché (cache miss). Hay que equilibrar el balanceo con la afinidad. afinidad
- Escalabilidad. Con muchos procesadores, el planificador debe ser eficiente. Las estructuras compartidas (colas globales, locks) se convierten en cuellos de botella. escala
Estos problemas se estudian en detalle en los temas 29 (afinidad y balanceo) y 30 (hilos de hardware, NUMA).
8. Cómo lo hace Linux
Linux usa una arquitectura de cola por núcleo con balanceo de carga. Cada CPU tiene su propia cola de ejecución (runqueue). El planificador (CFS) selecciona el proceso con menor vruntime en la cola del CPU actual.
El balanceo de carga se hace a través de los dominios de planificación (scheduling domains): grupos de CPUs que se balancean entre sí. El balanceo es periódico (cada cierto tiempo) y por evento (cuando un CPU queda ocioso).
Linux también mantiene la afinidad de caché: intenta mantener un proceso en el mismo CPU, y solo lo migra si el desequilibrio es significativo.
9. Simulador interactivo
Este simulador compara la cola global con la cola por núcleo para 2 CPUs. Observa cómo se distribuyen los procesos:
Simulador · multiprocesador (2 CPUs)
CPU 0
CPU 1
| Proceso | Llegada | Ráfaga | CPU | Inicio | Fin | Retorno |
|---|---|---|---|---|---|---|
10. Resumen
- Con varios procesadores, el planificador decide también dónde ejecutar cada proceso.
- AMP: un maestro planifica, los esclavos ejecutan. Simple pero no escalable.
- SMP: todos los procesadores son iguales. Escalable pero requiere sincronización.
- Cola global: una cola compartida. Balanceo automático pero contención y pérdida de afinidad.
- Cola por núcleo: una cola por CPU. Escalable y con afinidad, pero necesita balanceo explícito.
- Los nuevos problemas son: balanceo de carga, afinidad de caché y escalabilidad.
- Linux usa cola por núcleo con balanceo de carga periódico y por evento.
11. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es AMP?
Multiprocesamiento asimétrico: un procesador maestro planifica, los demás ejecutan.
2. ¿Qué es SMP?
Multiprocesamiento simétrico: todos los procesadores son iguales y pueden ejecutar cualquier código.
3. ¿Cuál es la ventaja principal de la cola global?
Balanceo automático: los procesos se distribuyen automáticamente entre los procesadores.
4. ¿Cuál es la desventaja principal de la cola global?
Contención: todos los procesadores compiten por la misma cola (lock compartido).
5. ¿Cuál es la ventaja principal de la cola por núcleo?
Sin contención y con afinidad de caché.
6. ¿Cuál es la desventaja principal de la cola por núcleo?
Necesita balanceo explícito de carga.
7. ¿Qué es la afinidad de caché?
Un proceso que se ejecuta en un procesador tiene datos en su caché. Migrarlo pierde esa caché.
8. ¿Cómo balancea la carga Linux?
Periódicamente y por evento (cuando un CPU queda ocioso), migrando procesos entre colas.
9. ¿Qué modelo usa Linux?
Cola por núcleo con balanceo de carga.
10. ¿Qué es un dominio de planificación?
Un grupo de CPUs que se balancean entre sí.
Para practicar
- Ejecuta el simulador en modo global y por núcleo y compara los Gantt.
- Diseña un caso donde el desbalanceo sea evidente en modo por núcleo.
- Explica por qué la cola global no escala bien.
- Implementa el balanceo de carga en el simulador por núcleo.
- Investiga cómo Linux implementa los dominios de planificación.
- Explica el trade-off entre balanceo y afinidad de caché.