Tijdens de Mars Pathfinder-missie traden herhaaldelijke systeemresets op door een zogenaamde priority inversion bug in het VxWorks RTOS. Dit probleem ontstond wanneer een taak met lage prioriteit een gedeelde resource (mutex) vasthield, waardoor een taak met hoge prioriteit moest wachten. Omdat een taak met gemiddelde prioriteit de taak met lage prioriteit kon preempten, bleef de taak met hoge prioriteit te lang blokkeren, wat leidde tot een watchdog timeout en een volledige reset.
Engineers losten dit op door priority inheritance te activeren. Bij deze methode erft de taak die de resource vasthoudt tijdelijk de prioriteit van de wachtende taak met hoge prioriteit, waardoor preemptie door taken met gemiddelde prioriteit wordt voorkomen. De fix werd op afstand doorgevoerd door middel van een C-interpreter in het systeem. De casus onderstreept het belang van gedetailleerde systeemtraces, debugging-faciliteiten en grondige tests van synchronisatieprotocollen in embedded systemen.
De Mars Pathfinder Priority Inversion Bug: Wat er echt gebeurde
Belangrijkste punten
- De Mars Pathfinder-missie kampte met herhaaldelijke systeemresets veroorzaakt door een priority inversion bug.
- Een taak met lage prioriteit hield een gedeelde mutex vast terwijl een taak met hoge prioriteit wachtte, wat leidde tot een watchdog timeout.
- De oplossing was het inschakelen van priority inheritance in de mutex-configuratie van het VxWorks RTOS.
- Deze praktijkcasus laat zien waarom inzicht in RTOS-scheduling en priority inversion cruciaal is.
De Mars Pathfinder werd op 4 december 1996 gelanceerd door NASA aan boord van een Delta II-booster en landde op 4 juli 1997 in Ares Vallis op Mars, in een regio genaamd Chryse Planitia in het Oxia Palus-kwadrant. De lander opende zich vervolgens en liet de rover vrij, die diverse experimenten op het Martianse oppervlak uitvoerde.
De Mars Pathfinder landde tot veel media-aandacht en begon gegevens naar de aarde te verzenden. Enkele dagen later werd de stroom van informatie en beelden echter onderbroken door een reeks totale systeemresets. De bron van het probleem was priority inversion, wat vervolgens leidde tot het missen van een deadline van een kritieke taak. Dit werd gedetecteerd door een watchdog timer, waarna de actie in dit foutscenario was om het ruimtevaartuig te resetten.
Hoe dit probleem is gediagnosticeerd en opgelost, is een fascinerend verhaal en een belangrijke les voor embedded engineers.
Het diagnosticeren van het probleem
De applicaties van de Pathfinder werden gescheduld door het VxWorks RTOS. Omdat VxWorks pre-emptive priority scheduling van threads biedt, werden taken uitgevoerd als threads met prioriteiten die waren bepaald op basis van hun relatieve urgentie.
De taak voor het verzamelen van meteorologische gegevens draaide als een infrequent thread met lage prioriteit en maakte gebruik van de informatiebus die gesynchroniseerd was met semaforen. Andere threads met een hogere prioriteit kregen voorrang wanneer dat nodig was, waaronder een busmanagementtaak met een zeer hoge prioriteit, die ook toegang tot de bus kreeg door de semafoor te verwerven. Helaas werd in dit geval de uitvoering belemmerd door een langlopende communicatietaak, die een hogere prioriteit had dan de meteorologische taak, maar een lagere dan de busmanagementtaak.
Al snel merkte een watchdog timer op dat de busmanagementtaak al enige tijd niet was uitgevoerd. De timer concludeerde dat er iets mis was en beval een totale systeemreset. (Engineers bekenden later dat er tijdens de pre-flight tests ook systeemresets hadden plaatsgevonden. Zij schreven dit toe aan een hardwarefout en richtten zich vervolgens weer op de missiekritieke landingssoftware.)
Het vinden van een oplossing
Engineers werkten koortsachtig op een laboratoriumreplica om het probleem te diagnosticeren en op te lossen, waarbij ze uiteindelijk een priority inversion ontdekten. Een priority inversion treedt op wanneer een taak met hoge prioriteit indirect wordt gepreempt door een taak met gemiddelde prioriteit, waardoor de relatieve prioriteiten van de twee taken worden "omgekeerd" (zie Figuur 1). Dit is een duidelijke schending van het prioriteitsmodel, dat stelt dat taken met hoge prioriteit alleen kunnen worden tegengehouden door taken met een nog hogere prioriteit, of kortstondig door taken met lage prioriteit die snel hun gebruik van een resource beëindigen die door zowel de hoge als de lage prioriteitstaak wordt gedeeld.
Figuur 1: Priority inversion
Om het probleem op te lossen, schakelden ze een booleaanse parameter of vlag in. Deze vlag geeft aan of priority inheritance voor de taak met lage prioriteit moet worden uitgevoerd door de semafoor. De betreffende semafoor was geïnitialiseerd met deze parameter uitgeschakeld (dit was de standaardinstelling); als deze ingeschakeld was geweest, zou de priority inversion zijn voorkomen.
Bij priority inheritance erft de taak die de semafoor vasthoudt de prioriteit van een taak met hogere prioriteit zodra die laatste de semafoor aanvraagt. In Figuur 1 zou taak "low" de prioriteit van taak "high" erven wanneer die taak de semafoor aanvraagde. Hierdoor kan "low" de taak "medium" preempten.
Een globale variabele sloeg de initialisatieparameter op voor de semafoor die het probleem veroorzaakte. Omdat VxWorks een C-taalinterpreter bevat—bedoeld om ontwikkelaars in staat te stellen C-expressies en functies in te typen voor uitvoering tijdens het debuggen van het systeem—was het mogelijk om een kort C-programma naar het ruimtevaartuig te uploaden. Wanneer dit werd geïnterpreteerd, werden de waarden van deze variabelen gewijzigd van FALSE naar TRUE. Dit maakte een einde aan de systeemresets.
Wat hebben we hiervan geleerd?
- Alleen gedetailleerde traces van het werkelijke systeemgedrag maakten het mogelijk om de foutieve uitvoeringsvolgorde vast te leggen en te identificeren. Een diagnose via een "black box" zonder traces zou onmogelijk zijn geweest.
- De aanwezigheid van "debugging"-faciliteiten in het systeem was uiterst belangrijk. Het probleem had niet kunnen worden gecorrigeerd zonder de mogelijkheid om het systeem aan te passen.
- Het besteden van extra tijd om de correctheid van priority inheritance in de testfase te garanderen, zelfs tegen wat extra prestatiekosten, zou onschatbaar zijn geweest.
Het probleem was al vóór dit incident geïdentificeerd
Toen de keynote speaker verwees naar een paper waarin het priority inversion-probleem voor het eerst werd geïdentificeerd en een oplossing werd voorgesteld, gebeurde er iets bijzonders: verbazingwekkend genoeg waren de auteurs allemaal in de zaal aanwezig en werden zij hartelijk ontvangen. Het oorspronkelijke paper was:
L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. In IEEE Transactions on Computers, vol. 39, pp. 1175-1185, Sep. 1990.
De Mars Pathfinder Priority Inversion Bug: Wat er echt gebeurde
Belangrijkste punten
- De Mars Pathfinder-missie kampte met herhaaldelijke systeemresets veroorzaakt door een priority inversion bug.
- Een taak met lage prioriteit hield een gedeelde mutex vast terwijl een taak met hoge prioriteit wachtte, wat leidde tot een watchdog timeout.
- De oplossing was het inschakelen van priority inheritance in de mutex-configuratie van het VxWorks RTOS.
- Deze praktijkcasus laat zien waarom inzicht in RTOS-scheduling en priority inversion cruciaal is.
De Mars Pathfinder werd op 4 december 1996 gelanceerd door NASA aan boord van een Delta II-booster en landde op 4 juli 1997 in Ares Vallis op Mars, in een regio genaamd Chryse Planitia in het Oxia Palus-kwadrant. De lander opende zich vervolgens en liet de rover vrij, die diverse experimenten op het Martianse oppervlak uitvoerde.
De Mars Pathfinder landde tot veel media-aandacht en begon gegevens naar de aarde te verzenden. Enkele dagen later werd de stroom van informatie en beelden echter onderbroken door een reeks totale systeemresets. De bron van het probleem was priority inversion, wat vervolgens leidde tot het missen van een deadline van een kritieke taak. Dit werd gedetecteerd door een watchdog timer, waarna de actie in dit foutscenario was om het ruimtevaartuig te resetten.
Hoe dit probleem is gediagnosticeerd en opgelost, is een fascinerend verhaal en een belangrijke les voor embedded engineers.
Het diagnosticeren van het probleem
De applicaties van de Pathfinder werden gescheduld door het VxWorks RTOS. Omdat VxWorks pre-emptive priority scheduling van threads biedt, werden taken uitgevoerd als threads met prioriteiten die waren bepaald op basis van hun relatieve urgentie.
De taak voor het verzamelen van meteorologische gegevens draaide als een infrequent thread met lage prioriteit en maakte gebruik van de informatiebus die gesynchroniseerd was met semaforen. Andere threads met een hogere prioriteit kregen voorrang wanneer dat nodig was, waaronder een busmanagementtaak met een zeer hoge prioriteit, die ook toegang tot de bus kreeg door de semafoor te verwerven. Helaas werd in dit geval de uitvoering belemmerd door een langlopende communicatietaak, die een hogere prioriteit had dan de meteorologische taak, maar een lagere dan de busmanagementtaak.
Al snel merkte een watchdog timer op dat de busmanagementtaak al enige tijd niet was uitgevoerd. De timer concludeerde dat er iets mis was en beval een totale systeemreset. (Engineers bekenden later dat er tijdens de pre-flight tests ook systeemresets hadden plaatsgevonden. Zij schreven dit toe aan een hardwarefout en richtten zich vervolgens weer op de missiekritieke landingssoftware.)
Het vinden van een oplossing
Engineers werkten koortsachtig op een laboratoriumreplica om het probleem te diagnosticeren en op te lossen, waarbij ze uiteindelijk een priority inversion ontdekten. Een priority inversion treedt op wanneer een taak met hoge prioriteit indirect wordt gepreempt door een taak met gemiddelde prioriteit, waardoor de relatieve prioriteiten van de twee taken worden "omgekeerd" (zie Figuur 1). Dit is een duidelijke schending van het prioriteitsmodel, dat stelt dat taken met hoge prioriteit alleen kunnen worden tegengehouden door taken met een nog hogere prioriteit, of kortstondig door taken met lage prioriteit die snel hun gebruik van een resource beëindigen die door zowel de hoge als de lage prioriteitstaak wordt gedeeld.
Figuur 1: Priority inversion
Om het probleem op te lossen, schakelden ze een booleaanse parameter of vlag in. Deze vlag geeft aan of priority inheritance voor de taak met lage prioriteit moet worden uitgevoerd door de semafoor. De betreffende semafoor was geïnitialiseerd met deze parameter uitgeschakeld (dit was de standaardinstelling); als deze ingeschakeld was geweest, zou de priority inversion zijn voorkomen.
Bij priority inheritance erft de taak die de semafoor vasthoudt de prioriteit van een taak met hogere prioriteit zodra die laatste de semafoor aanvraagt. In Figuur 1 zou taak "low" de prioriteit van taak "high" erven wanneer die taak de semafoor aanvraagde. Hierdoor kan "low" de taak "medium" preempten.
Een globale variabele sloeg de initialisatieparameter op voor de semafoor die het probleem veroorzaakte. Omdat VxWorks een C-taalinterpreter bevat—bedoeld om ontwikkelaars in staat te stellen C-expressies en functies in te typen voor uitvoering tijdens het debuggen van het systeem—was het mogelijk om een kort C-programma naar het ruimtevaartuig te uploaden. Wanneer dit werd geïnterpreteerd, werden de waarden van deze variabelen gewijzigd van FALSE naar TRUE. Dit maakte een einde aan de systeemresets.
Wat hebben we hiervan geleerd?
- Alleen gedetailleerde traces van het werkelijke systeemgedrag maakten het mogelijk om de foutieve uitvoeringsvolgorde vast te leggen en te identificeren. Een diagnose via een "black box" zonder traces zou onmogelijk zijn geweest.
- De aanwezigheid van "debugging"-faciliteiten in het systeem was uiterst belangrijk. Het probleem had niet kunnen worden gecorrigeerd zonder de mogelijkheid om het systeem aan te passen.
- Het besteden van extra tijd om de correctheid van priority inheritance in de testfase te garanderen, zelfs tegen wat extra prestatiekosten, zou onschatbaar zijn geweest.
Het probleem was al vóór dit incident geïdentificeerd
Toen de keynote speaker verwees naar een paper waarin het priority inversion-probleem voor het eerst werd geïdentificeerd en een oplossing werd voorgesteld, gebeurde er iets bijzonders: verbazingwekkend genoeg waren de auteurs allemaal in de zaal aanwezig en werden zij hartelijk ontvangen. Het oorspronkelijke paper was:
L. Sha, R. Rajkumar, and J. P. Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. In IEEE Transactions on Computers, vol. 39, pp. 1175-1185, Sep. 1990.
Groetjes,