Planificación de Procesos en Linux y Windows

Fichas de vocabulario que cubren las políticas y fórmulas de planificación en Linux monoprocesador/multiprocesador (incluyendo CFS y EEVDF) y las características del planificador de Windows.

Rango de prioridades de tiempo real (Linux)

Rango que va de $1$ a $99$, organizado en una cola independiente por cada nivel de prioridad bajo un planificador apropiativo.

SCHED_FIFO

Política de tiempo real en Linux sin rodaja de tiempo, donde los procesos se ejecutan hasta terminar, bloquearse o ser desalojados por uno de mayor prioridad (permaneciendo en la cabeza de su cola tras el desalojo).

SCHED_RR

Política de tiempo real en Linux con rodaja de tiempo predefinida; si un proceso es desalojado por otro de mayor prioridad antes de agotar su rodaja, la completa al recuperar la CPU.

SCHED_DEADLINE

Política de tiempo real en Linux orientada a procesos que se activan periódicamente y exigen un plazo máximo de finalización (deadline) en cada periodo.

Políticas NO de tiempo real (Linux)

Conjunto de políticas (SCHED_OTHER/SCHED_NORMAL, SCHED_BATCH y SCHED_IDLE) que operan con prioridad $0$ y no se ejecutan mientras exista algún proceso de tiempo real listo.

Nice value

Parámetro que modula el reparto de tiempo en SCHED_OTHER / SCHED_NORMAL dentro de un rango de $-20$ (mayor prioridad) a $19$ (menor prioridad).

SCHED_BATCH

Política derivada de SCHED_OTHER pensada para procesos no interactivos con uso intensivo de CPU que busca reducir los cambios de contexto al no requerir baja latencia.

SCHED_IDLE

Política en Linux destinada a procesos que se ejecutan con la mínima prioridad del sistema, por debajo del valor nice $19$ de SCHED_OTHER o SCHED_BATCH.

Procesador ideal

Modelo teórico de procesador capaz de repartir cualquier periodo de tiempo infinitesimal entre un conjunto de procesos listos de forma ponderada según su peso.

Tiempo virtual

Métrica empleada para normalizar el paso del tiempo y desacoplar la planificación de la cantidad de procesos listos en cada instante.

Unidad de tiempo virtual

Tiempo necesario bajo las premisas del procesador ideal para ejecutar, de cada proceso, un número de unidades de tiempo real igual a su peso.

VTRT

Tiempo virtual transcurrido en $rt$ unidades de tiempo real, calculado como: $VTRT = \frac{rt}{\sum_{j=1}^{N} Peso_j}$.

RTPT

Tiempo real que tarda en ejecutarse un proceso $P_i$ durante un tiempo de procesador $pt$, definido como: $RTPT = pt \times \frac{\sum Peso_j}{Peso_i}$.

VTPT

Tiempo virtual transcurrido al ejecutar un proceso $P_i$ durante un tiempo $pt$, definido como: $VTPT = \frac{pt}{Peso_i}$. Es invariante ya que solo depende del peso de dicho proceso.

CFS

Planificador cuyo principio consiste en lograr que, dentro de un horizonte temporal determinado, todos los procesos ejecuten exactamente la misma cantidad de tiempo virtual.

EEVDF

Earliest Eligible Virtual Deadline First; algoritmo de planificación por defecto para SCHED_OTHER/NORMAL desde Linux 6.6 (2023), basado en un artículo científico de 1995.

Proceso elegible (EEVDF)

Estado de un proceso en EEVDF cuyo tiempo de elegibilidad es menor o igual al tiempo virtual del sistema.

VTENS

Tiempo virtual de fin de la próxima rodaja de un proceso $P_i$, calculado como: $VTENS(P_i) = \text{tiempo elegible } P_i + \frac{\text{tamaño rodaja } P_i}{Peso_i}$. Si no consume la rodaja completa, se usa la duración de su ráfaga.

Planificación particionada con migración

Esquema multiprocesador de Linux que asigna una cola por CPU para reducir la contención y el acceso simultáneo, aplicando criterios de migración para equilibrar la carga.

NUMA

Non-Uniform Memory Access; arquitectura surgida por la complejidad de mantener la coherencia de cachés donde cada CPU tiene acceso directo y eficiente solo a una fracción de la memoria total.

Planificación en Windows

Mecanismo apropiativo que actúa a nivel de hebras utilizando colas con algoritmo Round Robin para prioridades del rango $0$ al $31$.

Prioridades de tiempo real (Windows)

Rango de prioridades fijas comprendido entre $16$ y $31$ dentro del esquema de planificación de Windows.

Prioridades Dynamic (Windows)

Rango de prioridades normales comprendido entre $1$ y $15$ que admite ajustes dinámicos de prioridad para reducir latencia o evitar inanición.

Prioridad 0 (Windows)

Nivel de prioridad reservado de manera exclusiva para el sistema operativo en Windows.