next -index- prev

A Chorus line

Een gedistribueerd real-time besturingssysteem

Veel toepassingen hebben real-time respons nodig, maar wensen UNIX-standaardisatie. Chorus probeert een brug te slaan tussen de wereld van telefoon en computer.

Hoe zou het ideale besturingssysteem er volgens u uit moeten zien? Chorus heeft een indrukwekkende lijst features: het is een modern gedistribueerd besturingssysteem met implementaties op een reeks machine-architecturen, van embedded boards tot PC-LANs, SMP-machines en massief parallelle systemen. Het kan werken in real-time, is geschikt voor zware multimedia toepassingen, en is binair compatibel met SCO UNIX. Met het meta-operating system COOL worden C++ objecten persistent, geïntegreerd en volgens de CORBA-standaarden beheerd. De clou is dat de klant kan kiezen: de minimale uitvoering van de kernel is op dit moment 30 KB en wordt nog kleiner, en afhankelijk van de functies kan het oplopen tot meer dan 300 KB. Voor eindgebruikers komt er een versie met SCO Open Server R5.

UNIX wordt oud

'UNIX was, is, and will always be the operating system of the future.' Deze kreet is onderhand wel versleten nu Windows het laatst overgebleven gesloten OS is. De eenvoud die UNIX' kracht was raakte zoek tussen alle nuttige features waardoor de resourceconsumptie de groei van de capaciteit van de modale PC steeds voor bleef.
Innovatieve geesten kwamen hierop met de microkernels, een soort `RISC' filosofie voor besturingssystemen, waarin slechts de essentiële functies in de microkernel werden geïmplementeerd, soms als hardware abstraction layer aangeduid. Een voordeel hiervan was dat drivers dynamisch geladen kunnen worden. Een microkernel hoeft niet sneller te zijn dan een monolithische UNIX, want het aanroepen van een externe module kost tijd. Een microkernel kan meer dan een megabyte groot zijn, wat ook niet echt `micro' genoemd kan worden.
UNIX is allang geen eenduidig besturingssysteem meer, maar een Application Programming Interface of OS Personality, uitgevoerd als een subsysteem dat bovenop de microkernel loopt, tegelijk met Real-Time Posix, COOL Object Request Broker en andere subsystemen.
Gedistribueerde besturingssystemen proberen een netwerk aan de gebruiker te presenteren als een enkele computer, maar dat is een stuk moeilijker te realiseren dan voor SMP-machines, waarin parallelle processen gebruik maken van het gezamenlijke geheugen om hun werk te synchroniseren. Gedistribueerde systemen gebruiken meestal het message passing, wat in principe langzamer gaat, maar beter opschaalbaar is naar grote aantallen processoren.

Chorus

Chorus is niet voor niets gebruikt in verschillende massief parallelle systemen, waaronder Cray en Unisys. Aan de andere kant van het spectrum is het licht genoeg voor embedded-systemen en maakt de netwerkfunctionaliteit en UNIX openheid applicatieontwikkeling gemakkelijker en bespaart telecommunicatieleveranciers het onderhoud van zelfontwikkelde besturingssystemen.
In theorie bieden shared memory en message passing dezelfde mogelijkheden. Chorus implementeert de InterProcess Communicatie in de microkernel. Het heeft speciale codesleutels, de capabilities om objecten als message ports en processen te vinden voor intern gebruik. Wanneer twee threads op dezelfde machine willen communiceren plaatst de zender de data in een buffer en doet trap naar de kernel, die enkel de page tables wijzigt, zodat de buffer in de adresseringsruimte van de ontvanger komt; sneller kan niet.
Het besturingssysteem gebruikt intern Chorus IPC; voor de gebruiker is er een System V IPC en Remote Procedure Call en method invocation dankzij de Corba compliant ORB. Onder het motto `voor elk wat wils' is ook Distributed Shared Memory beschikbaar, doordat de geheugenpagina's via speciale boodschappen over het net worden gestuurd. Een Consistency Manager verdeelt de toegangsrechten, zodat er per pagina slechts een exemplaar met schrijfpermissie of meerdere read-only kopie ën bestaat. Alle data zijn toegankelijk ongeacht waar ze zich bevinden. Door pagina's naar een schijf te schrijven worden het file-systeem en de swapspace gecre ëerd. De UNIX-functies worden zo goed mogelijk benaderd door een aantal servers, waarop SCO binaries kunnen draaien. Wie alle mogelijkheden wil benutten maakt ook gebruik van Chorus' API's. Het ideale besturingssysteem? Dat maakt u zelf door uit Chorus' source naar smaak modulen te kiezen en andere naar eigen behoeften te implementeren.

Scheduling

De voornaamste taak van een besturingssysteem is het verdelen van het geheugen en de rekentijd tussen de verschillende taken. Een verschil tussen ruimte en tijd is dat de laatste niet hergebruikt kan worden. Zo krijgt wie het hardst roept vaak de meeste ruimte (demand paging), maar wordt zorgvuldiger omgesprongen met de rekentijd. Daarbij bestaan twee criteria van wat een optimale verdeling is: de totale werklast afwerken in de kortste tijd of de gemiddelde responstijd minimaliseren.
De batch-geori ënteerde besturingssystemen voor de mainframes van gisteren probeerden de dure machine zo veel mogelijk nuttig werk te laten doen terwijl de wachttijd van de gebruikers minder zwaar woog. Pas wanneer een programma niet verder kon werd een volgend gestart. Naarmate computers goedkoper werden, was maximale uitbuiting van minder belang en werden time-sharing systemen gemeengoed. De rekentijd in een batch-systeem kan eenvoudigweg worden toegewezen volgens het principe `wie het eerst komt, die het eerst maalt' (FIFO) of kan worden verdeeld door alle taken een prioriteit toe te kennen, en van de taken die klaar zijn die met de hoogste prioriteit te kiezen en pas te onderbreken als er een taak bijkomt met nog hogere prioriteit. Door de prioriteit van wachtende processen langzaam op te hogen is een min of meer eerlijke verdeling mogelijk.
Hardware gebruikt hetzelfde principe: gebruikers-programma's hebben de laagste prioriteit, gevolgd door Operating System code. Interrupts van randapparaten moeten snel afgehandeld worden, waarbij disks hogere prioriteit hebben dan trage printers. Noodgevallen als stroomuitval gaan altijd voor. Dit gaat alleen goed als er voldoende tijd overblijft voor de taken in de onderste klasse.
De eenvoudigste vorm van timesharing wordt `round-robin' genoemd: zet alle taken die ervoor klaar zijn in een kringetje en geef nummer een de processor. Als diens tijdsquantum op is, wordt hij door een timer geïnterrumpeerd en geeft de scheduler de volgende kandidaat diens quantum. Dit geeft een gelijke verdeling; vaak worden taken die veel CPU-tijd gebruiken gediscrimineerd. Een probleem is, dat wanneer er erg veel taken zijn, een systeem voortdurend omschakelt en de taken nauwelijks meer aan nuttig werk toekomen (thrashing).
Scheduling vindt plaats op verschillende niveaus: op chipniveau bepaalt hardware in welke volgorde machine-instructies worden verwerkt. Het besturingssysteem moet na het afhandelen van een interrupt zo snel mogelijk beslissen wie het volgende tijdsquantum krijgt, maar kan de rekentijd over langere perioden verdelen door de prioriteiten te wijzigen. Op tijdschalen van minuten tot maanden kan een taakverdeling met de hand worden opgegeven aan cron(8).

Real-time

Een derde categorie, de real-time besturingssystemen, wordt gebruikt in de meet- en regeltechniek en voor duizend-en-een computergestuurde apparaten, bijvoorbeeld een kleine computer voor een kernreactor die aan de hand van de gemeten temperatuur en druk en het gewenste vermogen de moderatorstaven moet regelen. Om een kettingreactie te voorkomen moet de computer binnen een bepaalde tijd, de deadline, reageren op signalen (events) van de sensoren.
Hij kan dit doen door in een programmalus alle poorten periodiek te controleren of door de randapparatuur zo in te stellen dat ze een interrupt geeft als een kritische waarde wordt overschreden. Als een systeem steeds dezelfde taken moet verwerken, kan de tijdsindeling ook van te voren berekend worden. Een real-time computer hoeft niet altijd snel te zijn. De scheduler is er niet op gericht om de gemiddelde wachttijd te minimaliseren, maar te garanderen dat ook in de ongunstigste situatie de deadlines gehaald worden. Ook de programmeur zal de looptijd van haar software moeten testen.
De Wet van Murphy is geen grap; de ervaring leert dat ernstige industriële ongelukken vaak ontstaan door een samenloop van omstandigheden. Als meerdere componenten defect raken en de operators in paniek de situatie verergeren, is de kans groot dat de computer een deadline overschrijdt.
Er wordt een onderscheid gemaakt tussen hard en soft real-time. Een definitie is dat in een hard real-time system een overschrijding van een deadline catastrofaal is en in een soft real-time slechts ongewenst, bijvoorbeeld als een beller een bezettoon krijgt zonder dat het nummer in gesprek is. Een andere indeling kan zijn soft real-time taken die de deadline overschrijden zo snel mogelijk te voltooien terwijl voor hard real-time het goede antwoord na de deadline even slecht is als geen antwoord. Een derde definitie is dat soft real-time vertragingen in milliseconden meet en hard real-time in microseconden.
Een eenvoudig scheduling algoritme is `Earliest Deadline First'. De scheduler zal een lijst bijhouden van alle uit te voeren taken, die steeds op volgorde van de deadline gesorteerd is. Na een interrupt hoeft dan slechts de eerste taak van de lijst die niet geblokkeerd is te worden gestart.

Scheduling in Chorus

Een Actor in Chorus is te vergelijken met een UNIX process. Iedere actor heeft een eigen afgeschermde adresruimte plus een hoeveelheid statusinformatie. Actors kunnen zoals gezegd wel bepaalde geheugensegmenten gemeenschappelijk hebben, maar die kunnen verschillende virtuele adressen krijgen. De virtuele adresruimte is verdeeld in User en System delen. De System Space is voor alle actors gelijk en is alleen toegankelijk voor actors die systeemfuncties implementeren. Omdat het overschakelen naar een andere virtuele adresruimte (context switch) tijd kost en het aanmaken van een nieuw process met fork(2) veel tijd, kan een actor uit meerdere threads bestaan, die ongehinderd hetzelfde geheugen gebruiken voor globale variabelen en eigen stacks hebben voor lokale variabelen. Er zijn een aantal synchronisatiemechanismen, zoals Dijkstra's semaforen, waarmee de programmeur conflicten kan voorkomen. Er ontstaat een compatibiliteitsprobleem met de semantiek van signal(2): voor welke thread is een signaal bestemd?
Linux kent een threads package waarmee een gebruikersprogramma de toegewezen rekentijd nog eens kan verdelen onder diens taken. Dit bespaart de overhead van System Calls, maar zou geen real-time respons kunnen garanderen. Daarom schedulet de Chorus Nucleus (kernel) afzonderlijke threads. Om op een systeem zowel real-time als interactieve software te kunnen draaien, worden threads ingedeeld in klassen met prioriteiten tussen 1 (de hoogste) en 255 (de laagste). Threads met prioriteiten tussen tussen 1 en 127 worden slechts door urgenter taken onderbroken en binnen een niveau is de scheduling First-In-First-Out. Interactieve taken worden binnen een prioriteitsklasse onderling getimesliced.
Alle UNIX-processen krijgen prioriteit 128. Server threads van het UNIX Subsysteem lopen met prioriteiten tussen 64 en 68. Ze krijgen de rauwe hardware interrupts te zien. Omdat de volledige afhandeling niet altijd even snel gaat biedt Chorus een `delayed interrupt' mode; de exception handler kan het event doorgeven aan een speciale interrupt thread en de processor weer snel deblokkeren. Als de tijd rijp is, zal de interrupt thread de server bewegen de kwestie alsnog met lagere prioriteit af te handelen, zodat de respons van real-time threads geen gevaar loopt.
Een nadeel van gewoon UNIX is dat system calls lang kunnen duren en niet onderbroken kunnen worden omdat de afhandeling in kernel space plaatsvindt. Chorus werkt met servers buiten de Nucleus die intern multithreaded zijn, zodat system calls onderbroken kunnen worden; ook de Nucleus is multithreaded.
Dankzij de modulaire opbouw kan de klant kiezen uit verschillende schedulers: priority-based, deadline-based of fair share. De urgentie van een taak wordt zowel bepaald door zijn deadline als door zijn importantie. Als een taak zijn deadline mist kunnen minder belangrijke taken worden geannuleerd of naar een minder zwaar belaste machine worden gemigreerd. Voor hard real-time kan de kernel scheduler worden gecombineerd met lichtgewicht threads, geïmplementeerd door een aparte scheduler per actor. Beide schedulers werken samen zodat de user-level scheduler zijn meest urgente thread selecteert en de kernel-level scheduler de actor runt met meest urgente lichtgewicht thread van alle.

ATM-netwerken

De telefoniewereld heeft haar netwerken gebaseerd op een model met virtuele verbindingen, gemultiplext over re ële kanalen. Als een verbinding wordt gemaakt, wordt volgens X.25 of een ander protocol een route vastgelegd voor de duur van het gesprek en een vaste bandbreedte gereserveerd. In de computerwereld hebben packet switching protocollen de overhand, zoals het Internet Protocol, waarin data packets afzonderlijk worden verstuurd zonder afspraken vooraf, die bij alle tussenliggende routers bekend zouden moeten zijn.
Packet switching is flexibel en kan de netwerkcapaciteit redelijk uitbuiten, maar de kwaliteit van de verbindingen kan zeer variabel zijn. Chorus heeft een intern communicatieprotocol met messages tot 64 KB. Protocollen op hoger niveau kunnen packets met verschillende bestemming multiplexen over een verbinding, of een verbinding simuleren door inkomende data in packets op te splitsen.
In snelle netwerken buiten lange packets de bandbreedte beter uit, omdat de tijd die nodig is om een megabit te verzenden korter kan zijn dan de daarop volgende wachttijd op bevestiging van ontvangst. Bovendien moeten headers van de verschillende protocollen worden meegezonden.
Grote packets hebben ook nadelen; zo zal een klein packetje met hoge prioriteit moeten wachten tot een bezette router klaar is met een lange voorganger. Een ander nadeel is de noodzaak routers van grote buffergeheugens te voorzien. Als een bericht van een megabyte eerst in zijn geheel in een buffer moet worden geschreven voor verdere verzending gaat meer tijd verloren dan voor een kilobyte.
Voor ISDN worden datablokken van verschillende verbindingen samengepakt in frames van vaste lengte die met vaste frequentie moeten worden verzonden. De CCITT heeft om de groeiende behoefte aan dataverkeer tegemoet te komen een Asynchronous Transmission Mode vastgelegd, die het datadeel van deze frames gebruikt als een container waarin ATM-cellen van 53 bytes met verschillende bestemmingen zijn samengepakt. Local Area Networks kunnen de cellen los transporteren.
Een ATM-cel bevat 48 bytes data plus een header van 5 bytes. Die 48 is vastgelegd door een commissie waarvan de ene helft 32 bytes voorstelde en de andere voor 64 B was. De minimale header bevat het adres van de virtuele verbinding en CRC. Als de route van te voren is overeengekomen is dit voldoende. Voor dataverkeer kan volgens het ATM Adaption Layer 5 protocol een packet worden opgesplitst in cellen. Een bit in de cel-header wordt gebruikt om aan te geven dat de laatste cel van een packet is ontvangen. De laatste cel bevat een trailer van acht bytes waarmee het packet weer kan worden samengesteld.

ATM Scheduling

Op een CD wordt geluid digitaal vastgelegd met een bemonsteringsfrequentie van 44,1 kHz en 16 bits precisie, dat is 706 kb/s. Digitaal beeld zou meer dan een gigabit per seconde vereisen, vandaar dat er voorlopig gespeculeerd wordt over digitale bioscopen. Voor applicaties die geen hoge beeldkwaliteit vereisen, kan de datastroom wellicht gereduceerd worden tot 20 Mb/s. Dat komt nog altijd neer op een ATM-cel per 19 us; de meeste besturingssystemen hebben langer nodig om op een interrupt te reageren. Bovendien moet de weergave via scherm en luidspreker isochroon gebeuren. Zeker voor geluid geldt dat wanneer een monster slechts een milliseconde te laat (of te vroeg) komt, storende vervorming zou optreden, zodat men liever een monster laat vervallen. Daarom kan men hier wel van hard real-time spreken. De timing wordt pas in het weergavestadium kritiek. Voorafgaande stadia mogen vooruit werken door het begin van de uitzending in een FIFO-buffer te houden die leeg loopt als de datastroom achter raakt. Dat heeft echter een hinderlijke vertraging van de weergave tot gevolg. Een signaalreistijd boven 0,4 s geldt in de telefonie als onaanvaardbaar.
Een besturingssysteem dient behalve geheugen en rekentijd ook de netwerkbandbreedte eerlijk te verdelen. Dit kan met het `leaky bucket' algoritme. De gebruikers mogen data in hun buffers deponeren en het besturingssysteem haalt om beurten een hoeveelheid uit een van de `emmers', zodanig dat elke applicatie de gevraagde stroom geleverd krijgt. Als er een te snel zendt, dan loopt haar emmer over.
De experimentele ATM-implementatie op Chorus deelt datastromen in aan de hand van het gevraagde serviceniveau in drie klassen:
  • I: gegarandeerde isochrone aflevering;
  • W: gegarandeerde aflevering met vooruitwerken;
  • B: zo goed en zo kwaad als het gaat afleveren (Best Effort).
    Eerst wordt de bandbreedte en looptijd van de verbinding getest, die immers over meerdere routers kan lopen, en of het benodigde buffergeheugen beschikbaar is. Aan hand daarvan wordt geprobeerd een periodieke zendtijdverdeling te berekenen. Een proces in de `B'-klasse handelt aperiodieke berichten af.
    Het quantum wordt berekend, dat is de tijd die nodig is om een buffer te verzenden op de volle bandbreedte, en de periode waarin de volgende buffer verzonden moet worden om de gevraagde stroom te bereiken. Een thread wordt gedeblokkeerd aan het begin van zijn periode en voor `I' threads ligt de deadline op het eind van het quantum plus de maximale overschrijding.
    Vervolgens wordt geprobeerd de schedule-cyclus vooruit te berekenen. Daartoe wordt getest of het mogelijk is alle berekende quanta toe te wijzen. Als twee verzoeken op dezelfde tijd zouden vallen (bijvoorbeeld als ze een gelijke periode hebben), dan wordt geprobeerd de starttijd te verschuiven binnen de toegestane afwijking of anders kan een fouttolerantie stroom een steekje laten vallen. Voor een thread uit de `W'-klasse wordt slechts getest of het totaal van de gevraagde stroom de voor deze klasse beschikbare CPU-tijd niet overschrijdt en voor `B' threads is geen toelatingstest vereist.
    De scheduler moet het berekende uitzendschema handhaven en controleren of de doelstellingen zijn gehaald. De `I'-klasse krijgt praktisch de hoogst mogelijke prioriteit, de `W' een stapje lager en de `B' threads kunnen verschillende lagere prioriteiten hebben; hieronder vallen ook non-real-time Chorus servers en gebruikerstaken. Omdat hun tijd van tevoren is ingedeeld kunnen threads uit de `I'-klasse als ze gescheduled worden alleen door de hardware geïnterrumpeerd worden. Threads in de `W'-klasse concurreren met elkaar en `I' threads.
    Het opsplisten van de packets in ATM-cellen en de verzending is een stuk kritischer. Elke stroom krijgt daarvoor een aparte thread. Als de ATM-kaart een cel heeft verzonden, activeert ze de cel-scheduler met een interrupt. Die heeft uit de deadlines van de buffers de eerstvolgende cel deadline uitgerekend en kopieert die cel in de ATM-kaart, met dien verstande dat de `I'-klasse altijd voorgaat. De ontvangstzijde is eenvoudiger en tijdkritischer. Zodra een cel binnenkomt geeft de ATM-kaart een interrupt aan een thread die als de bliksem de FIFO leegt. Als de laatste cel van een AAL5 packet binnen is, wordt de geadresseerde verwittigd met een software interrupt.
    Real-time video vergt geen hele zware processor, maar wel zorgvuldig afgestemde software. Zo is ook het Chorus memory management aangepast, zodat voor `I' threads het nodige geheugen vast gereserveerd is, terwijl dat van de `W'-klasse eventueel door een lid van `I' geconfisceerd kan worden.
    Chorus Systemes heeft zich vooral toegelegd op de ontwikkeling van de kernel en het resultaat heeft zich in de praktijk bewezen. Wie een kant-en-klaar systeem wil, kan een binaire versie met de SCO Open Desktop kopen. Grote klanten nemen een source-licentie en snijden het toe op hun eigen hardware. Gedistribueerde besturingssystemen zijn inmiddels het laboratorium ontgroeid. Concurrenten? Taligent heeft de ontwikkeling van een eigen OS opgegeven en GNU Hurd is nog in het embryonale stadium. DCE is geen echt besturingssysteem.

    Literatuur

    1. P. Robin et. al., "Implementing a QoS Controlled ATM Based Communications System in Chorus", Distributed Multimedia Research Group, Lancaster University, Report MPG-94-5 {verkrijgbaar via ftp.chorus.fr}
    2. A.S. Tanenbaum, "Distributed Operating Systems", Prentice-Hall International, Englewood Cliffs, NJ, 1995 {recensie in UNIX info}
    3. C. Partridge, "Gigabit Networking", Addison-Wesley, Reading, MS, 1994{gerecenseerd in UNIX info}
    4. D. Pountain, "The Chorus Microkernel", BYTE, januari 1994, 131-6
    5. H. Teffer, "OPUS", UNIX info 9 (3), mei 1995, 22-5.
    Inl. Chorus Systemes, 6 Avenue Gustave Eiffel, 78182 Saint-Quentin-en-Ivelines , CEDEX, France, tel: + 33 1 30648216, e-mail: info@chorus.fr

    Daniel von Asmuth