Inicio > ciencia, programación > El bug marciano

El bug marciano

julio 23, 2009

mars-pathfinder-roverEl día 4 de julio de 1997 el Mars Pathfinder  aterriza en Marte y a las pocas horas empieza a enviar las fotos de Marte en alta calidad que todos conocemos. La misión hasta ese momento de calificó de éxito. Se despliega la nave que sirvió para el viaje y para el aterrizaje –el SpaceCraft/Lander (diagrama inferior)– para dejar salir al Sojounder Rover (la conocida imagen de la derecha).

A los pocos días se detectan continuos reinicios del ordenador del Lander cuando intentaba enviar datos metereológicos y científicos a la Tierra. Los reinicios del ordenador estaban ocasionados por una tarea (bc_sched) que verifica si otras han acabado, de no ser así reinicia todo el software (sin pérdidas de los datos obtenidos, que se mantienen en la RAM).

Spacecraft/Lander

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:

inversión de prioridades en Mars Pathfinder

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:

[*] 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 :-)

  1. julio 23, 2009 en 8:10 am

    Buen artículo, se echan de menos más como este :)

  2. DN
    julio 23, 2009 en 8:58 am

    Genial. Gracias. Yo también echaba de menos estos geniales posts.

  3. Dingo
    julio 23, 2009 en 9:49 am

    No era un bug. Era un feature.

  4. julio 23, 2009 en 9:54 am

    Muy bueno el artículo. El término de tarea se debe a VxWorks, que denomina Task a su implementación de hilos (con su peculiaridades, como por ejemplo el uso de un solo espacio de direcciones para todas las tareas)
    Yo trabajo actualmente con VxWorks, desarrollando drivers para el bus Milbus 1553, sobre bancos VME, así que este artículo me ha llegado al alma…

  5. _Pablo_
    julio 23, 2009 en 10:11 am

    Es muy interesante que hables de este tema.
    El hardware y software más robusto que se ha creado lo llevan las sondas espaciales.
    Intenté hace tiempo conseguir una copia pirata del vxworks para tratar de furrularlo en un servidor ibm iseries que me regalaron ,que llevan el procesador powerpc5 , pero me desanimé y acabó en el punto limpio.

  6. quicksort
    julio 23, 2009 en 10:17 am

    Comentas que Linux ya soporta ese tipo de mecanismos. Sin embargo, sigue sin ser un sistema de tiempo real. Aún así, ¿sería aceptable para un proyecto así?. Si no, ¿y RTLinux?
    Buen artículo.

  7. Lacho
    julio 23, 2009 en 11:15 am

    En la terminología de Sistemas de Tiempo Real se habla de tareas de tiempo real, no de procesos, aunque yo opino que es simplemente algo aceptado sin más.

  8. Raúl
    julio 23, 2009 en 11:36 am

    Corrección: “a pesar que Linu*s* lo había prohibido expresamente…”
    Saludos.

  9. julio 23, 2009 en 11:43 am

    Muy bien explicado, un gran artículo. Yo también he sufrido ese tipo de problemas programando dispositivos empotrados de Rabbit Systems, aunque a mucha menor escala jeje.

  10. derek
    julio 23, 2009 en 12:26 pm

    Cuando se traduce un articulo, la fuente no se califica como “más información”. Este artículo tiene autor y esta firmado, y lo que aquí se ha escrito es una simple y llana traducción.

    Menciona la fuente como lo que es, no como si fuera una ampliación de tu artículo.

  11. julio 23, 2009 en 12:40 pm

    @derek

    Obviamente la cabeza no te da para distinguir entre una traducción y un informe oficial usado (y citado) como una de las fuentes (que no es la única).

    O eres un troll tan rabioso y tonto que ni has comparado el artículo enlazado y lo que escribí aquí antes de decir semejante barbaridad.

  12. julio 23, 2009 en 1:01 pm

    Un ‘apuntazo’. Te prefiero investigando y compartiendo que aleccionando con las soflamas que acostumbras.

    Saludos

  13. julio 23, 2009 en 1:19 pm

    Me ha parecido curioso el detalle de Linus y la herencia de prioridades en Linux. Un buen ejemplo para hacer que se traguen sus palabras los que nos dicen a los partidarios del software libre que somos unos fanboys de un barbudo y un finés.

    PD: Se la clavaron doblada a Linus…

  14. Mannu
    julio 23, 2009 en 1:35 pm

    Me ha encantado leerlo. Gracias por el artículo ;)

  15. Andy
    julio 23, 2009 en 2:15 pm

    ¿Cómo tú leyendo un foro de Microsoft?
    Espera que llamo al infierno para ver si está comenzando a bajar la temperatura. :)

  16. Nadie
    julio 23, 2009 en 6:12 pm

    Muy interesante el artículo.

  17. valdesensei
    julio 23, 2009 en 11:59 pm

    Bueno el artículo.
    Espero mas temas asi..

    saludos desde Chile.

    DTB

  18. julio 24, 2009 en 5:30 am

    @quicksort
    Te recomendaría que te miraras RTEMS,es software liberado por el ejército norteamericano, originalmente usado para los sistemas de guía de los misiles. Es usado en bastantes proyectos de Software Embarcado, sobre todo en la ESA. Como ejemplo, la misión Herschel/Planck usan este sistema.
    Es un poco engorroso,sobre todo hasta que te acostumbras a su configuración a base de #defines (sic), pero funciona. Yo lo he probado sobre plataformas sparc en FPGAs, pero está portado a una cantidad considerable de procesadores: http://www.rtems.com/wiki/index.php/SupportedCPUs

  19. kota
    julio 26, 2009 en 5:35 pm

    @quicksort
    Si que hay un tree real-time (-rt patch) de Linux, mantenido por Ingo Molnar y Steven Rodstedt.

    http://rt.wiki.kernel.org/index.php/Main_Page

  20. kota
    julio 26, 2009 en 5:36 pm

    s/Rodstedt/Rostedt/

  21. Enrique Castro
    julio 27, 2009 en 9:25 am

    No es “aterriza” esa expresión solamente es aplicable en el planeta Tierra.

    La palabra correcta es “amartiza” de “amartizaje” XD XD XD

  22. julio 28, 2009 en 1:26 am

    Un tema interesante el de los sistemas en tiempo real. Un amigo mío de cuarto tenía la asignatura este año y me contó más o menos esta anécdota.

    No estoy seguro pero me parece que cada transmisión de la Tierra tardaba unos 20 min y otros tantos para recibir la respuesta. Parece increíble que con una comunicación tan lenta fueran capaces de averiguar el problema y parchearlo.

  23. Javier Sampedro
    julio 30, 2009 en 12:43 am

    Hola Ricardo,

    Soy Javier Sampedro, de El Pais. Me gustó tu crítica a mi artículo, creo que estaba bien traída, y que decías cosas interesantes. Te escribo por otra historia. ¿Viste esto en Science la semana pasada?

    Can We Reinvent the Internet? Science 2009 Jul 24;325(5939):396-7

    http://www.ncbi.nlm.nih.gov/pubmed/19628843?ordinalpos=1&itool=EntrezSystem2.PEntrez.Pubmed.Pubmed_ResultsPanel.Pubmed_DefaultReportPanel.Pubmed_RVDocSum

    Acabo de escribir al autor, y también a Ron Burt (http://www.chicagobooth.edu/faculty/bio.aspx?person_id=12824623104) para preguntarles esto:

    1. I had the idea that most spontaneous networks are ‘small worlds’, and small worlds have structural holes, haven’t they? So why social nets haven’t?

    2. Your ideas seem to me quite ‘biological’—the main mechanism of speciation is the ‘allopatric’ model of Sewall Wright, based on small populations which get almost isolated. Diversity in biology also requieres ‘structural holes’. Can I use this image to explain the concept to my readers?

    Si viste el paper, o si le puedes echar un vistazo mañana (jueves), me encantaría citar también tu opinión, o al menos conocerla.

    Gracias por anticipado y saludos,

    Javier

  1. julio 23, 2009 en 3:32 am
  2. julio 23, 2009 en 8:03 am
  3. julio 23, 2009 en 9:15 am
  4. julio 23, 2009 en 1:11 pm
  5. julio 23, 2009 en 2:14 pm
  6. julio 24, 2009 en 2:07 am
Los comentarios están cerrados.
Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 480 seguidores

A %d blogueros les gusta esto: