Muchos núcleos, una carga

Planificar en un multiprocesador

Tradicionalmente, un multiprocesador era una máquina con varios procesadores físicos. Hoy el término abarca varias arquitecturas: CPU multinúcleo, núcleos con varios hilos de hardware, sistemas NUMA y multiprocesamiento heterogéneo. Con varios núcleos ya no basta decidir quién sigue: también hay que decidir dónde.

AMP y SMP

• Multiprocesamiento asimétrico (AMP): un solo procesador, el maestro, toma todas las decisiones de planificación; los demás solo ejecutan código. Es simple, pero el maestro se vuelve un cuello de botella.
• Multiprocesamiento simétrico (SMP): cada procesador se planifica a sí mismo y elige de la cola de listos. Es el enfoque de casi todos los sistemas operativos.

En SMP, la cola de listos puede ser una sola compartida por todos los núcleos o una por núcleo. La compartida obliga a coordinar el acceso para que dos núcleos no tomen el mismo proceso. Con una cola por núcleo no hay esa competencia, y cada proceso tiende a quedarse en el núcleo donde ya tiene sus datos en caché.

Multinúcleo e hilos de hardware

En un chip multinúcleo, cada núcleo aparece ante el sistema operativo como una CPU lógica. Al acceder a memoria, un núcleo puede pasar mucho tiempo esperando los datos: es la espera de memoria (memory stall). Para no desperdiciar ese tiempo, un núcleo puede tener dos o más hilos de hardware: cuando uno espera a la memoria, el núcleo cambia al otro.

Para el sistema operativo, cada hilo de hardware es una CPU lógica más: esa técnica se llama multihilo en chip (CMT), e Intel la llama hyper-threading. Pero los hilos de un núcleo comparten sus recursos, así que en cada instante solo uno avanza. Por eso hay dos niveles de planificación: el sistema operativo decide qué hilo de software va a cada CPU lógica, y el núcleo decide qué hilo de hardware ejecuta, con Round Robin o por prioridad. Un sistema que conoce los hilos de hardware evita, por ejemplo, poner dos tareas pesadas en el mismo núcleo físico.

Balanceo de carga

Con una cola por núcleo, uno puede quedar saturado mientras otro está libre. El balanceo de carga mantiene la carga parecida en todos. Solo hace falta con colas por núcleo; con una cola compartida, un núcleo libre simplemente toma el siguiente.

• Migración por empuje (push): una tarea revisa periódicamente la carga y mueve procesos de los núcleos cargados a los libres.
• Migración por arrastre (pull): un núcleo que se queda sin trabajo toma un proceso de un núcleo ocupado.

No son excluyentes: el planificador puede usar las dos.

Afinidad de procesador

Mientras un proceso corre en un núcleo, la caché de ese núcleo se llena con sus datos. Si migra a otro núcleo, esa caché ya no le sirve y la del nuevo empieza fría. La afinidad es la tendencia a mantener a un proceso en el mismo núcleo.

• Afinidad suave: el planificador intenta mantenerlo en el mismo núcleo, sin garantía.
• Afinidad dura: el proceso indica en qué núcleos puede correr. Linux ofrece llamadas al sistema para eso.

Las colas por núcleo dan afinidad de forma natural, salvo cuando el balanceo mueve procesos. En los sistemas NUMA, cada procesador tiene su propia zona de memoria y acceder a la de otro es más lento, así que la afinidad importa todavía más.

Multiprocesamiento heterogéneo

En los teléfonos, con arquitectura ARM, es común tener núcleos de distinto tipo: unos más rápidos que gastan más energía y otros más lentos pero eficientes (ARM lo llama big.LITTLE). El planificador lo sabe y lo aprovecha: lo que se muestra en pantalla va a los núcleos rápidos y las tareas de fondo a los eficientes.

El planificador de Linux

• Antes de la versión 2.5, el kernel usaba una variante del planificador de UNIX, que no estaba pensada para varios procesadores.
• La 2.5 introdujo el planificador O(1): soportaba SMP, con afinidad y balanceo de carga, pero respondía mal en sistemas interactivos como los de escritorio.
• Después llegó el CFS (Completely Fair Scheduler), que usa balanceo de carga con afinidad y sabe si el sistema es NUMA.

ampliación CFS no usa un quantum fijo. Lleva para cada tarea un tiempo de ejecución virtual (vruntime) y siempre elige la tarea con el menor, guardando las tareas en un árbol rojo-negro. El vruntime avanza más despacio para las tareas de más prioridad, que se ajusta con el valor nice: un nice menor significa más prioridad y, por lo tanto, más CPU.

Antes de leer la respuesta