Crash-bestendige computerbesturing

door Jannigje Gerritzen

Een vliegtuigvleugel bevat verschillende be-weegbare onderdelen die door computers bestuurd worden. De betrouwbaarheid van deze processoren is absoluut noodzakelijk. Een systeem is betrouwbaarder te maken door de foutentolerantie te verhogen. Begin april pro-moveerde Dick Alstein op een dissertatie waar-in hij algoritmen behandelt voor gedistribueer-de fouttolerante systemen. Hij beperkte zich niet alleen tot een vlakke systeemtopologie, maar keek ook naar hiërarchisch opgebouwde systemen. Ook algoritmen voor gemeenschappelijk geheugen komen in zijn proefschrift aan bod. Het onderzoek maakte deel uit van het DEDOS-project (Dependable Distributed Operating Systems) van de faculteit Wiskunde & Informatica.

Een gedistribueerd systeem heeft niet één centrale processor, maar meerdere aparte processoren die onderling in verbinding staan. Dit kan tegenwoordig enkele honderden aantallen bedragen. De afstanden tussen de afzonderlijke processoren kunnen erg groot zijn. Bij een produktielijn in een fabriek is dit zelfs nodig. Elke processor moet zijn eigen geheugen hebben en voert zijn eigen programma uit. Het is eenvoudig de rekenkracht van een bestaand netwerk uit te breiden, door nieuwe processoren toe te voegen. In de klassieke netwerken wordt een vlakke structuur gebruikt; elke processor is rechtstreeks met ŕlle andere verbonden. De processoren wisselen onderling berichten uit over communicatiekanalen. Een voorbeeld van een Hard Real Time (HRT)-systeem is de computerbesturing in een vliegtuigvleugel. De verschillende kleppen worden door verschillende processoren aangestuurd. Deze processoren vormen samen het HRT-systeem. Bij een HRT-systeem is het van levensbelang dat de boodschappen tijdig aankomen; als vleugelkleppen van een vliegtuig niet tijdig bewegen stort het onverbiddelijk neer. Ook is het belangrijk dat het systeem foutentolerant is. Als sommige processoren uitvallen moet het systeem toch blijven werken. Hiervoor zijn gedistribueerde algoritmen nodig, die een aantal beslisproblemen oplossen. In het proefschrift van Alstein worden onder andere algoritmen gegeven voor gedistribueerde en wait-free consensus, reliable multicast en membership.
Bij het algoritme voor gedistribueerde consensus hebben alle processoren in het begin een eigen waarde. Het is de bedoeling dat na uitvoering van het algoritme alle processoren dezelfde waarden hebben en het hierover eens zijn. Er bestaan veel gedistribueerde consensus algoritmen voor systemen met berichtenuitwisseling via communicatiekanalen. Maar het is ook mogelijk om de processoren via een gemeenschappelijk geheugen met elkaar te laten communiceren. Hierdoor wordt niet alleen de snelheid van het systeem verhoogd, het staat ook ‘wait-free’ constructies toe. Dit garandeert dat een processor zijn programma in een beperkt aantal slagen kan uitvoeren, onafhankelijk van de verschillende snelheden van andere processoren. Ook is het hier niet nodig dat alle processoren tegelijkertijd hun algoritme starten. Daarnaast is het wait-free algoritme ongevoelig voor processor-crashes. Er is namelijk weinig verschil tussen een processor die lang wacht en een processor die geheel gestopt is. Alstein toont aan dat deze wait-free consensus bereikt kan worden ondanks de aanwezigheid van processor- en geheugenfouten en geeft hier twee algoritmen voor.
Bij het ‘reliable broadcast’ probleem moet de zendende processor een bericht versturen, zodanig dat alle andere processoren het correct ontvangen, of geen van hen. Bij ‘reliable multicast’ wordt het bericht verzonden naar een deelverzameling van de proces-soren. Dit wordt gebruikt als er informatie niet naar alle proces-soren gestuurd moet worden. Alstein geeft drie reliable multicast algoritmen, achtereenvolgens bestand tegen processor-crashes, omissiefouten en timingfouten. De meeste bekende algoritmen voor broadcast en multicast zijn geschreven voor netwerken met berichtenverzending. Maar Alstein laat ook hier de processoren communiceren via een gemeenschappelijk geheugen. Zijn algoritmen gebruiken een mailbox, die gedupliceerd wordt om geheugencrashes te ondervangen.

Hiërarchische systemen
De meeste algoritmen voor foutentolerante gedistribueerde systemen zijn ontworpen voor systemen met een vlakke opbouw. Het is echter ook mogelijk om een systeem te bouwen met een topologie. Het systeem bestaat dan uit een aantal groepen processoren, die verbonden zijn in een boom-structuur. Binnen een groep kunnen de processoren gewoon berichten naar elkaar sturen. Maar een bericht naar een processor buiten de eigen groep moet via intermediaire processoren gestuurd worden.
Een hiërarchisch systeem heeft een aantal voordelen boven een vlakke topologie. De hardware is goedkoper, omdat er minder verbindingen tussen de proces-soren nodig zijn. Ook kan in een hiërarchisch systeem de afstand tussen de processoren groter zijn. Een gedistribueerd systeem kan bijvoorbeeld toegepast worden bij systemen voor luchtverkeerscontrole. Hierbij moeten grote afstanden tussen alle processoren overbrugd worden, wat erg duur of zelfs onmogelijk is bij grote aantallen. De processoren kunnen bovendien ingedeeld worden in groepen naar functie. De meeste berichten zijn dan alleen relevant voor processoren binnen één groep en zodoende heeft intensief verkeer binnen een groep geen effect op de andere groepen. Alstein toont aan dat een algoritme voor een platte topologie eenvoudig omgezet kan worden naar een algoritme voor een hiërarchische structuur. Hierdoor vermindert het aantal benodigde boodschappen drastisch.

Bottleneck
Het ‘membership’ algoritme zorgt ervoor dat elke processor weet welke andere processoren goed werken en welke niet meer goed functioneren. De ‘meningen’ van de processoren moeten op dit gebied overeenkomen. Alstein geeft eerst twee algoritmen die dit membership probleem oplossen voor een vlakke systeemtopologie. Vervolgens werkt hij het probleem verder uit voor een hiërarchisch opgebouwd netwerk. Al deze algoritmen zijn bovendien immuun voor timingfouten van de processoren. Ook hier geldt dat bij de hiërarchische structuur minder berichten verstuurd hoeven te worden.
Door zijn algoritmen voor een hiërarchische structuur te bewijzen, laat Alstein zien dat het bij de besproken problemen niet nodig is om een dure vlakke structuur toe te passen in gedistribueerde systemen. Er kan volstaan worden met een hiërarchische structuur, die naast een hardwarebesparing ook geschikt is om de communicatie-bottleneck van de klassieke platte topologie op te lossen.
Op het moment zijn de door Alstein beschreven technieken nog vrij geavanceerd. Ze worden vooral gebruikt in toepassingen met hoge eisen aan veiligheid. Langzamerhand worden gedistribueerde HRT-systemen ook toegepast bij produktielijnen en besturing van chemische processen. Alstein verwacht ze in de toekomst ook aan te treffen in auto’s, bijvoorbeeld in een anti-blokkeer-systeem bij remmen.