El dia 4 de juliol de 1997 la Mars Pathfinder aterra a Mart i a les poques hores comença a enviar les fotos de Mart en alta qualitat que tots coneixem. La missió fins a aquest moment es va qualificar d’èxit. Es desplega la nau que va servir per al viatge i per a l’aterratge –el SpaceCraft/Lander– per deixar sortir la Sojounder Rover.

Foto de cliff1066 / Cliff.
Als pocs dies es detecta que es reinicia contínuament l’ordinador del Lander quan intentava enviar dades meteorològiques i científiques a la Terra. L’ordinador es reiniciava a causa d’una tasca (bc_sched) que verifica si unes altres han acabat, i de no ser així reinicia tot el programari (sense pèrdues de les dades obtingudes, que es mantenen en la RAM).
El maquinari
L’ordinador de la nau era un Power1/RS6000 d’IBM, connectada a un bus VME amb interfícies per a la càmera, la ràdio i un bus 1553. El bus 1553 tenia dues parts, una usada per a navegació espacial (acceleradors, vàlvules, sensor solar i scanner d’estels) i una altra per a l’aterratge amb interfície per a l’acceleròmetre, radar d’altitud i els instruments meteorològics-científics: l’ASI/MET. El maquinari del 1553 va ser heretat de la sonda Cassini i tenia una mode de funcionament simple i obligatori, el programari controlador i de presa de dades havia de planificar-se exactament cada 0.125 segons (o 8 Hz).
El programari
El sistema operatiu usat era el VxWorks adaptat específicament al processador RS600. VxWorks és un Unix de temps real desenvolupat per Wind River i comprada completament per Intel fa pocs dies (el 17 de juliol). L’arquitectura del programari era la següent:
- bc_sched: Era la tasca amb màxima prioritat i s’encarregava de preparar les “transaccions” per al següent cicle de 0.125 segons sobre el bus 1553.
- entry landing: La tasca amb la segona prioritat, ja inactiva.
- bc_dist: La tasca de tercera prioritat, pren dades del 1553 i les col·loca en un doble buffer circular des d’on extreuen informació les altres tasques, excepte les ASI/MET.
- Altres tasques de baixa prioritat de la nau.
- ASI/MET: és la tasca de menor prioritat juntament amb les altres tasques científiques (generació i compressió d’imatges, etc.). A diferència de les altres tasques, l’ASI/MET pren dades al 1553 a través d’un mecanisme de comunicació entre processos usant el pipe() de vxWorks (és estándard d’Unix).
El problema
Després de detectat el problema es van obtenir dades de debug del Mars Pathfinder i es van simular condicions similars amb un sistema bessó a la Terra treballant juntament amb desenvolupadors de VxWorks. Després de 18 hores de simulacions van descobrir el que estava passant: per sobrecàrrega de dades preses –era millor del que s’esperaven– el sistema estava més carregat que el pitjor dels cassos provat a Terra i ocasionava la inversió de prioritats que impedia que la tasca bc_dist pogués acabar… per culpa de l’ASI/MET, encara que aquesta era de menor prioritat.
Inversió de prioritats
Aquest és un tema que ja es coneixia en la “cultureta” informàtica, encara que no hi havia solucions fins a 1980 que es va presentar una solució en l’article Experience with processes and monitors in Mesa. Actualment és un tema molt estudiat en les assignatures de sistemes operatius o concurrència, però sobre el qual no hi ha un consens unànime pel que fa a la millor solució, encara que la més usada i simple és coneguda com herència de prioritats.
La inversió de prioritats és un problema que es pot presentar en tots els sistema de multiprogramació quan s’empren mecanismes per controlar l’exclusió mútua a l’accés de recursos compartits –com els semàfors mutex–. Abans que un procés pugui accedir a aquesta secció crítica ha de fer una operació de wait sobre el semàfor, aquesta operació pot generar que el sistema operatiu bloquegi aquest procés fins que el procés que està en la secció crítica en aquest moment surti d’ella.
Però pot ocórrer el següent.
Suposem que A sigui el procés de major prioritat, B una de prioritat intermèdia i C la de menor prioritat. C entra a una secció crítica, mentre està en ella és “treta” –preempted– de la CPU per executar el procés B que té major prioritat. En aquest moment A s’executa i intenta entrar en la mateixa secció crítica que C, com que C està en ella A és bloquejat i el planificador –el scheduler– del sistema operatiu torna a executar el procés B.
És a dir, C mai surt de la secció crítica perquè hi ha un procés B amb major prioritat, A que té major prioritat que els altres tampoc s’executa perquè està esperant que C surti de la secció crítica… però aquesta no surt perquè B té preferència.
Aquest efecte és el conegut com a inversió de prioritats i és el que va passar en el Mars Pathfinder, bc_dist és equivalent a A, les altres tasques de baixa prioritat de la nau són B i ASI/MET és C. ASI/MET va ser preempted durant la crida a la funció select() (també estàndard d’Unix) que donava “accés” al descriptor del pipe. Aquesta crida entra a una secció crítica mitjançant un semàfor mutex que és el que va ocasionar l’espera infinita de bc_dist.
El diagrama que hi ha a aquest PDF mostra gràficament el que acabo de descriure.
Quan s’executava bc_sched, la de major prioritat de totes les tasques, aquesta detectava que bc_dist no havia acabat el seu cicle i reiniciava el sistema.
Nota: la terminologia més apropiada potser sigui “procés” en comptes de “tasca” (no conec més detalls de com estan implementats), però he preferit respectar la terminologia dels informes oficials.
La solució
VxWorks sí tenia l’opció d’habilitar l’herència de prioritats, però el JPL [Jet Propulsion Laboratory] de la NASA havia decideit no habilitar-la ja que era una variable global que afectava a tots els semàfors. Una vegada confirmat que es tractava d’un problema d’inversió de prioritats van demanar a VxWorks que analitzés l’efecte global. Aquests van respondre que afectaria molt poc al rendiment i que el sistema es comportaria de la mateixa forma sempre que hi hagués un sol procés en les cues d’espera dels semàfors. Com que aquest era el cas van decidir que habilitarien l’herència de prioritats de forma global.
Però no tenien forma de canviar aquesta variable directament en el Mars Pathfinder, el procediment era que s’havia d’enviar un pegat binari amb les diferències entre el programari de Mart amb el que tenien a Terra. Així que van haver de seguir aquest procediment, generar el pegat i enviar-ho per radio a Mart on un programa preparat el valida estrictament i després l’aplica (és similar per exemple al sistema de pegats que s’usa per actualitzar els telèfons amb Android).
Aquesta operació de posar un pegat potser hauria de figurar com l’actualització remota més llunyana realitzada a un sistema operatiu.
Més informació:
[*] Aquest és el “resum oficial” de Glenn Reeves, director de l’equip de programari de Mars Pathfinder en el JPL de la NASA. Va ser una resposta amb correccions a un resum de Mike Jones (de Microsoft Research) sobre una keynote de Dave Wilner (CTO de Wind River).
Curiositat: Com li han “colat” l’herència de prioritats a Linus Torvalds
Linus Torvalds va ser sempre poc partidari d’implementar herència de prioritats a Linux. Ho va deixar bastant clar a un email del 2005:
“Els amics no deixen que els amics usin herència de prioritats”
No ho facis. Si realment ho necessites de totes maneres el teu sistema ja està trencat.
Però resulta que Linux sí suporta l’herència de prioritats des de la versió 2.6.18. Qui ho va aconseguir? El fantàstic Ingo Molnar. Ell havia desenvolupat la nova interfície de semàfors futex, era una optimització important ja que gairebé tot el codi s’executava en mode usuari sense necessitat de fer “costoses” crides de sistema en cada operació de semàfors. Aquestes últimes només es fan en cas de contenció entre diversos processos.
Aquest nou mètode era molt més eficient i va ser acceptat pel kernel. Anys després Ingo va introduir sense massa fanfàrria –però molt ben explicat i argumentat– el PI-futex, o lightweight userspace priority inheritance. Així tenim a Linux un sistema de semàfors amb rendiment similar als sistemes de temps real, a més amb herència de prioritats… malgrat que Linus ho havia prohibit expressament tres mesos abans. Ingo, genial com sempre 