Una jefa de equipo que tiene la reunión más urgente del día espera la llave de la sala de reuniones. Pero el empleado nuevo que tiene la llave no deja de ser llamado por otros compañeros para pequeños recados y no consigue dejar la sala libre. Esta extraña situación, en la que el trabajo más importante se atiende el último, ocurre exactamente igual dentro de los ordenadores, y se llama «inversión de prioridades» (Priority Inversion).
En pocas palabras, la inversión de prioridades es «el fenómeno por el que una tarea de alta prioridad, mientras espera un recurso compartido que retiene una tarea de baja prioridad, queda en la práctica relegada a una prioridad aún más baja». Es un problema conocido desde hace mucho en los sistemas de tiempo real, donde muchas tareas comparten el procesador según prioridades fijas, y se hizo famoso en 1997, cuando la sonda Mars Pathfinder se reinició una y otra vez en Marte.
En este artículo veremos, por orden, cómo se produce la inversión de prioridades, cómo funciona con tres tareas, el incidente de Pathfinder que ocurrió de verdad en Marte y, por último, las formas de evitarla y las lecciones que deja.
Cuando una prioridad alta espera a una baja
1. ¿Cómo se produce la inversión de prioridades?

En la planificación por prioridades, el procesador siempre va primero a la tarea de mayor prioridad entre las que están listas para ejecutarse. Esta regla tan sencilla empieza a tambalearse cuando varias tareas comparten el mismo recurso.
(1) Recursos compartidos y bloqueos
Si varias tareas modifican a la vez la misma memoria o el mismo dispositivo, los datos se enredan. Por eso el sistema operativo usa bloqueos como el mutex para que solo una tarea a la vez pueda usar el recurso. La tarea que toma primero el bloqueo se queda con el recurso, sea cual sea su prioridad, hasta terminar su trabajo y liberar el bloqueo.
(2) La tarea alta espera
Si una tarea de alta prioridad pide el mismo recurso mientras una tarea de baja prioridad retiene el bloqueo, la tarea alta debe detenerse hasta que este se libere. Como el bloqueo se libera en cuanto la tarea baja termina su breve sección crítica, esta espera es una «inversión acotada», que se puede calcular de antemano.
(3) La tarea media se cuela
El verdadero problema aparece cuando, mientras tanto, se despierta una tarea de prioridad media que no tiene nada que ver con el bloqueo. Como la tarea media tiene más prioridad que la baja, se queda con el procesador, y la tarea baja se detiene sin soltar el bloqueo. Al final, la tarea alta tiene que esperar a que termine la tarea media, que tiene menos prioridad que ella, y si hay muchas tareas medias la espera puede alargarse sin fin.
2. Cómo funciona con tres tareas

La inversión de prioridades suele explicarse con tres tareas: alta, media y baja. Si solo se mira la prioridad, la tarea alta debería terminar la primera, pero basta con que intervenga un bloqueo para que el orden real de ejecución se invierta.

- Planificación por prioridades (Priority Scheduling): método que asigna una prioridad a cada tarea y ejecuta primero la de mayor prioridad entre las que están listas. Cuando una tarea alta se despierta, detiene a la tarea baja y toma el procesador.
- Mutex: abreviatura de exclusión mutua (Mutual Exclusion); es un bloqueo que permite que solo una tarea a la vez use un recurso compartido.
- Sección crítica (Critical Section): tramo de código que trabaja con un recurso compartido mientras retiene un bloqueo. Cuanto más corto es, menos tiempo esperan las demás tareas.
- Inversión acotada e inversión no acotada (Bounded and Unbounded Inversion): si la tarea alta solo espera lo que dura la sección crítica de la tarea baja, se trata de una inversión acotada; si además se cuelan tareas medias y no se puede fijar un límite superior a la espera, es una inversión no acotada.
En los sistemas de tiempo real, la peligrosa es la inversión no acotada, porque ya no hay forma de saber cuándo terminará una tarea que debe acabar sin falta dentro de un tiempo fijo. Lo que hace difícil detectar este problema es que, en apariencia, todas las tareas respetan su prioridad según las reglas, pero el resultado global parece como si las prioridades se hubieran invertido.
3. El incidente de Pathfinder en Marte

El suceso que más dio a conocer la inversión de prioridades ocurrió en Marte. La sonda Mars Pathfinder de la NASA, que aterrizó en Marte el 4 de julio de 1997, empezó a sufrir reinicios repentinos de todo su sistema pocos días después del aterrizaje.
(1) Reinicios repetidos
El ordenador de Pathfinder funcionaba con VxWorks, un sistema operativo de tiempo real de Wind River Systems. El problema apareció más o menos cuando la sonda empezó a recoger datos meteorológicos. Cada reinicio aplazaba al día siguiente el trabajo previsto para ese día, así que el equipo de operaciones en la Tierra tenía que encontrar la causa cuanto antes.
(2) La causa, reproducida en la Tierra
El equipo del Laboratorio de Propulsión a Chorro (JPL) ejecutó la misma situación en un equipo de pruebas en la Tierra con la función de registro activada y, en menos de 18 horas, logró provocar de nuevo el reinicio. La causa era una inversión de prioridades de manual. Mientras una tarea de datos meteorológicos de baja prioridad retenía un bloqueo, se ejecutaban tareas de prioridad media, y la tarea de alta prioridad que gestionaba el bus de información, que esperaba ese bloqueo, no lograba terminar dentro de su ciclo fijado. Una tarea de gestión de nivel superior lo detectó, lo consideró un error grave y provocó el reinicio.
(3) Un arreglo a distancia con una sola variable global
El bloqueo en cuestión se había creado con la configuración predeterminada, en la que la herencia de prioridad estaba desactivada por motivos de rendimiento. El equipo resolvió el problema enviando a la sonda en Marte un parche que cambiaba el valor de una variable global para activar esa función. El caso se hizo muy conocido después de presentarse en un congreso de sistemas de tiempo real en diciembre de ese mismo año, y Glenn Reeves, responsable del software de vuelo, también explicó en persona lo ocurrido.
4. Cómo evitar la inversión de prioridades

Mientras se usen bloqueos, es difícil eliminar del todo la inversión de prioridades, pero sí se puede impedir que la espera se alargue sin fin. Las soluciones más conocidas se recogen en el artículo sobre protocolos de herencia de prioridad (Priority Inheritance Protocols) que Lui Sha, Ragunathan Rajkumar y John Lehoczky publicaron en 1990.
(1) Herencia de prioridad
Cuando una tarea alta empieza a esperar un bloqueo, la tarea baja que lo retiene sube temporalmente a la misma prioridad que la tarea alta. Así, las tareas medias ya no pueden colarse, y la tarea baja termina pronto su sección crítica y vuelve a su prioridad original en cuanto libera el bloqueo. Este fue justamente el método que salvó a Pathfinder.
(2) Protocolo de techo de prioridad
Este método fija de antemano, para cada bloqueo, un «techo»: la prioridad más alta entre las tareas que pueden usarlo. Propuesto en el mismo artículo, permite calcular por adelantado la espera máxima y también evita el interbloqueo, en el que los bloqueos se enganchan entre sí y todo se detiene.
(3) Lecciones para el diseño
También es importante que los tramos que retienen un bloqueo sean cortos y diseñar el sistema para que tareas con prioridades muy distintas no compartan el mismo recurso. Hoy muchos sistemas operativos de tiempo real, y también Linux, ofrecen bloqueos con herencia de prioridad. El caso de Pathfinder muestra además lo importante que es revisar una sola configuración predeterminada y conservar funciones de registro que permitan reproducir un problema.
La sencilla idea de «dar un pequeño empujón a la tarea lenta que bloquea a la urgente para que termine primero» es el primer paso para entender la inversión de prioridades.