LinuxParty

El hardware

El ordenador de la nave era un Power1/RS6000 de IBM, conectada a un bus VME con interfaces para la cámara, la radio y un bus 1553. El bus 1553 tenía dos partes, una usada para navegación espacial (aceleradores, válvulas, sensor solar y scanner de estrellas) y otra para el aterrizaje  con interfaz para el acelerómetro, radar de altitud y lo sinstrumentos meteorológicos-científicos: el ASI/MET. El hardware del 1553 fue heredado de la sonda Cassini y tenía un modo de funcionamiento simple y obligatorio, el software controlador y toma de datos debía planificarse exactamente cada 0.125 segundos (u 8 Hz).

El software

El sistema operativo usado era el VxWorks, adaptado específicamente al procesador RS600. VxWorks es un Unix de tiempo real desarrollado por Wind River y comprada completamente por Intel hace pocos días (el 17 de julio). La arquitectura del software era la siguiente:

1. bc_sched: Era la tarea con máxima prioridad y se encargaba de preparar las “transacciones” para el siguiente ciclo de 0.125 segs sobre el bus 1553.
2. entry+landing: La tarea con la segunda prioridad, ya inactiva.
3. bc_dist: La tarea de tercera prioridad, toma datos del 1553 y las coloca en un doble buffer circular desde donde extraen información las otras tareas, salvo las ASI/MET.
4. Otras tareas de baja prioridad de la nave.
5. ASI/MET: es la tarea de menor prioridad junto con las otras tareas científicas (generación y compresión de imágenes, etc.). A diferencia de las otras tareas, la ASI/MET toma datos al 1553 a través de un mecanismo de comunicación entre procesos usando el pipe() de vxWorks (es estándard de Unix).

El problema

Luego de detectado el problema se obtuvieron datos de debug del Mars Pathfinder y se simularon condiciones similares con un sistema gemelo en la Tierra trabajando junto con desarrolladores de VxWorks.  Luego de 18 horas de simulaciones descubrieron lo que estaba pasando: por sobrecarga de tomas de datos –era mejor de lo que se esperaban– el sistema estaba más cargado que el peor caso probado en Tierra y ocasionaba la inversión de prioridades que impedía que la tarea bc_dist pudiese acabar… por culpa de la ASI/MET, aunque esta era de menor prioridad.

Inversión de prioridades

Este es un tema que ya se conocía en la “culturilla” informática, aunque no había nada forma ni soluciones hasta 1980 que se presentó una solución en el artículo Experience with processes and monitors in Mesa. Actualmente es un tema muy estudiado en las asignaturas de sistemas operativo o concurrencia, pero sobre la cuál no hay un consenso unánime sobre la mejor solución, aunque la más usada y simple es conocida como herencia de prioridades.

La inversión de prioridades es un problema que se pueden presentar en todos los sistema de multiprogramación cuando se usan mecanismos para controlar la exclusión mutua al acceso de recursos compartidos –como los semáforos mutex–. Antes que un proceso pueda acceder a esa sección crítica debe hacer una operación de wait sobre el semáforo, esta operación puede generar que el sistema operativo bloquee a ese proceso hasta que el proceso que está en la sección crítica en ese momento salga de ella.

Pero puede ocurrir lo siguiente.

Supongamos que A sea el proceso de mayor prioridad, B una de prioridad intermedia y C la de menor prioridad. C entra a una sección crítica, mientras está en ella es “quitada” –preempted– de la CPU para ejecutar el proceso B que tiene mayor prioridad. En ese momento A se ejecuta e intenta entrar en la misma sección crítica que C, como C está en ella A es bloqueado y el planificador del –el scheduler– sistema operativo vuelve a ejecutar el proceso B.

Es decir, C nunca sale de la sección crítica porque hay un proceso B con mayor prioridad, A que tiene mayor prioridad que los demás tampoco se ejecuta porque está esperando que C salga de la sección crítica… pero ésta no sale porque B tiene preferencia.

Este efecto es el conocido como inversión de prioridades y es lo que pasó en el Mars Pathfinder, bc_dist es equivalente a A, las otras tareas de baja prioridad de la nave son B y ASI/MET es C. ASI/MET fue preempted durante  la llamada a la función select() (también estándar de Unix) que daba “acceso” al descriptor del pipe. Esta llama entra a una sección crítica mediante un semáforo mutex que es el que ocasionó la espera infinita de bc_dist.

El diagrama siguiente (obtenido de este PDF) muestra gráficamente lo que acabo de describir:

Cuando se ejecutaba bc_sched, la de mayor prioridad de todas las tareas, ésta detectaba que bc_dist no había acabado su ciclo y reiniciaba el sistema.

Nota: la terminología más apropiada quizás sea “proceso” en vez de “tarea” (no conozco más detalles de cómo están implementados), pero preferí respetar la terminología de los informes oficiales.

La solución

VxWorks sí tenía la opción de habilitar la herencia de prioridades, pero el JPL de la NASA había decido no habilitarla ya que era una variable global que afectaba a todos los semáforos. Una vez confirmado que se trataba de un problema de inversión de prioridades pidieron a VxWorks que analice el efecto global, estos respondieron que afectaría muy poco al rendimiento y que el sistema se comportaría de la misma forma siempre que hubiese un sólo proceso en las colas de espera de los semáforos. Como éste era el caso decidieron que habilitarían la herencia de prioridades de forma global.

Pero no tenían forma de cambiar esa variable directamente en el Mars Pathfinder, el procedimiento era que se debía enviar un parche binario con las diferencias entre el software de Marte con el que tenían en Tierra. Así que tuvieron que seguir este procedimiento, generar el parche y enviarlo por radio a Marte donde un programa preparado lo valida estrictamente y luego lo aplica (es similar  por ejemplo al sistema de parches que se usa para actualizar los teléfonos con Android).

Este “parchado” quizás debería figurar como la actualización remota más lejana realizada a un sistema operativo.

Más información:

• ¿Qué pasó realmente en Marte? [*]
• Página web del Mars Pathfinder

[*] Este es el “resumen oficial” de Glenn Reeves, director del equipo de software de Mars Pathfinder en el JPL de la NASA. Fue una respuesta con correcciones a un resumen de Mike Jones (de Microsoft Research) sobre una keynote de Dave Wilner (CTO de Wind River).

Curiosidad: Como le han “colado” la herencia de prioridades a Linus Torvalds

Linus Torvalds fue siempre reacio a implementar herencia de prioridades en Linux. Lo dejó bastante claro en un email del 2005:

“Los amigos no dejan que los amigos usen herencia de prioridades”
No lo hagas. Si realmente lo necesitas de todas formas tu sistema ya está roto.

Pero resulta que Linux sí soporta la herencia de prioridades desde la versión 2.6.18. ¿Quién lo logró? El fantástico Ingo Molnar. Éste había desarrollado la nueva interfaz de semáforos futex, era una optimización importante ya que casi todo el código se ejecutaba en modo usuario sin necesidad de hacer “costosas” llamadas de sistema en cada operación de semáforos. Estas últimas sólo se hacen en caso de contención entre varios procesos.

Este nuevo método era mucho más eficiente y fue aceptado para el kernel. Años después Ingo introdujo sin demasiada fanfarria –pero muy bien explicado y argumentado– el PI-futex, o lightweight userspace priority inheritance. Así tenemos en Linux un sistema de semáforos con rendimiento similar a los sistemas de tiempo real, además con herencia de prioridades… a pesar que Linus lo había prohibido expresamente tres meses antes. Ingo, genial como siempre

Vía, el blog de ricardo galli.