Artikel im Linux Magazin ueber den EYCar und andere Themen


Ich habe in der Oktoberausgabe 1997 des deutschen Linux Magazins einen Artikel ueber den EYCar und ueber Echtzeitprozesse publiziert. Dieser steht auch online zur Verfuegung und kann entweder auf den Webseiten des Linux Magazins oder hier eingesehen werden.

Leider haben die Verleger jedoch in der gedruckten Version das mit Abstand wichtigste Bild aus dem Text entfernt und stattdessen einige irrelevante Bilder eingefuegt. In der Online Version wurden zwar keine Bilder hinzugefuegt, jedoch das wichtigste Bild fehlt auch hier. Daher erlaube ich mir, es hier zu zeigen ;)


EYCar: Linux steuert Roboter in Echtzeit

Linuxrobotics

von Erik Thiele


Das Thema Roboter scheint auf den ersten Blick eher etwas für Spielernaturen zu sein, dennoch ist hier profundes Wissen in sehr vielen Bereichen gefragt. So befaßt sich dieser Artikel denn auch in weiten Teilen mit diversen Schedulingstrategien und beweist eindeutig, daß sich mit Linux sicherheitsrelevante und echtzeitkritische Anwendungen erstellen lassen. Nebenbei erfahren wir auch einige Dinge über RT-Linux und Paketradio.

Es ist Mitternacht. In einem mit Elekronik vollgestopften Kellerraum spielt sich folgendes Szenario ab. Es werden Reflektoren aufgestellt. Die Koordinaten der Reflektoren werden dem EYCar, unserem Linux-Roboter eingegeben. Der EYCar sendet einen im Raum rotierenden Laserstrahl aus, der nur beim Überstreichen eines Katzenauges zurückgeworfen wird. Auf diese Weise werden die Winkel, unter denen die Katzenaugen relativ zum Fahrzeug stehen gemessen. Daraus kann das Fahrzeug seine Position errechnen. Es ist nun möglich, dem Fahrzeug eine Position vorzugeben, und es fährt diese an. Der Anwender sitzt am stationären Computer und kann dort über eine ansprechende grafische Oberfläche das Geschehen steuern. Der EYCar und der stationäre Computer kommunizieren über Funkgeräte.

Das ist die absolute Kurzfassung des EYCar-Projektes. Ich werde nun auf die Linux- spezifischen Gegebenheiten eingehen. Das System besteht aus 2 Computern. Einer davon steht auf einem Tisch, hat einen Bildschirm und eine Tastatur. Der andere ist in dem Alugehäuse auf dem EYCar untergebracht und hat weder Tastatur, noch Bildschirm. Beide Maschinen fahren Linux 2.0.30 mit diversen AX.25 Kernelpatches. (Das AX.25 Protokoll wird benutzt, um IP über Funkmodems (Packet Radio) zu realisieren) Der Rechner auf dem Fahrzeug ist ein AMD386SX-40 mit 8 MB Hauptspeicher. Er hat zusätzlich noch den RT-Linux 0.5 Kernel patch installiert. (Damit kann man Echtzeitprozesse auf unterster Ebene realisieren, mit wirklich wahnsinnig kurzen Reaktionszeiten)

Ein kleines Beispiel des Geschehens:

Funk - wie geht das ?

Eigentlich ganz einfach. Man kaufe zwei möglichst billige CB-Funkgeräte und bastle Antennen dazu. Dann kauft man noch das Baycom packet radio modem 1200baud, welches dann in die serielle Schnittstelle gestopft wird. Der Kernel muß nun nur noch AX.25-fähig compiliert werden (im selben Menü wo man auch PPP und SLIP und IPX auswählen kann), und das Baycom-Modul muß compiliert werden. Nach einem insmod baycom und einigen kleineren Konfigurationsbefehlen erreicht man sein Gegenüber mit ping 30.0.0.1. Man kann mit diesem Funkmodem ein ganzes Netzwerk aufbauen, ich habe jedoch nur Peer-to-peer gemacht. Die Pingtimes sind 2 Sekunden ;-) Naja, das war's! Sobald die Lust es zuläßt, kann man mal eben das Ethernet rausziehen und alles über Funk machen. Auf der Vorführung verging viel Zeit, nur um zu erklären, daß es bei Linux keinen Unterschied macht, ob man Ethernet oder Funkmodems benutzt.

Baycom Funkmodem und CB-Funkgerät

Das offene Ende wird direkt auf die serielle Schnittstelle gesteckt. Alles was so aussieht wie dieser kleine schwarze Klotz ist ein Baycom Modem, auch wenn es weder draufsteht, noch das Gerät unter diesem Namen verkauft wurde, wie dies hier zum Beispiel auch der Fall war (Dies ist die Packet Radio Komplettlösung von Conrad Electronic).

Was macht denn der Computer auf dem EYCar ?

Nun. Er hat eine kleine Digital-IO Karte (die parallele Schnittstelle hat nicht genügend Pins). Daran angeschlossen sind 3 Schrittmotoren, (2 Motoren zum Antrieb, ein Motor dreht das Laserrohr), ein Laser und eine Gabellichtschranke zur Referenzierung des Motors des Laserrohres. Die verwendeten Schrittmotorsteuerungen sind eigentlich nur Verstärker. Der Computer muß also die Spulen der Motoren direkt ansteuern. Das heißt, daß bei einer Lauffrequenz von 100 Hertz der Computer auch 100 mal in der Sekunde die Spulen der Motoren neu einstellen muß. Die beiden Antriebsmotoren werden getrennt voneinander geregelt, die Geschwindigkeit ist frei wählbar, und die Motoren beschleunigen und bremsen geregelt. Letztendlich bekommt das Programm nur den Befehl "Fahre 100 Schritte mit dem rechten und -100 Schritte mit dem linken Motor", daraufhin beschleunigt es selbstständig die Motoren und bremst sie rechtzeitig wieder ab. Um die verschiedenen Drehzahlen zu realisieren braucht man verschiedene Frequenzen. Da ich aber den Timer nicht so genau einstellen kann (man kann seine Frequenz immer nur verdoppeln) benutze ich Interpolationstechniken wie bei Modplayern. Die Trägerfrequenz beträgt 8192 Hz. Man kommt also in Bereiche, wo normale Prozesse, die ihr Timing mit nanosleep()-Befehlen realisieren, absolut untauglich sind. Ein kleiner Festplatteninterrupt oder ein bischen FTP, und schon ist das Timing absolut im Eimer.

Außerdem können normale Prozesse auf der Festplatte ausgelagert werden, und das ist absolut indiskutabel. Ich habe daher den Regler als RT-Linux Echtzeitkernelmodul implementiert. Der gesamte Linuxkernel läuft nur noch nebenher, selbst wenn Teile des Kernels die Interrupts sperren, so tun sie dies nicht wirklich (dafür sorgt der RT-Linux Kernelpatch). Absolute Priorität haben die Echtzeitkernelmodule! Auf diese Weise laufen die Motoren einwandfrei, egal wieviele Compiler, Funkgeräte, Netscapes (auch noch ständig auf der Platte ausgelagert und wieder reingeladen) laufen.

Die nächste Aufgabe des Echtzeitmoduls ist die Vermessung der Winkel unter denen das Fahrzeug die Katzenaugen sieht. Hierfür steuert es den Motor für das Laserrohr auf eine konstante Drehzahl. Trifft nun der Laser auf ein Katzenauge, so wird über eine Elektronik ein IRQ10 ausgelöst. Die Echtzeitinterruptroutine meines Moduls liest SOFORT (und wirklich SOFORT !) die Systemuhr mit rt_get_time() aus. Warum mache ich das, ich weiß doch die Position des Rohres auch durch den Schrittmotor, der es ansteuert? Richtig, aber die Zeitmessung ist genauer. Ich benutze den Schrittmotor lediglich zur Erzeugung einer konstanten Drehzahl, den Winkel errechne ich aus der Zeit. Auch hier ist wieder jede noch so geringe Verzögerung beim IRQ10 tödlich. Ein normaler Kernelmodul könnte zum Beispiel durch einen Festplatteninterrupt verzögert werden, nicht jedoch ein RT-Linux Kernelmodul.

Linux und Realtime - taugt das was ?

Ja! Es ist eine total geniale Angelegenheit. Mit den RT-Linux Echtzeitkernelmodulen kann man auf allerunterster Ebene wirklich absolut exakte Echtzeitanwendungen schreiben. Es bleiben natürlich die üblichen Nachteile von Kernelmodulen. (ANSI C, keine Bibliotheken etc.) Daher habe ich auch beim EYCar nur die untersten Steuerungsroutinen im Echtzeitmodul untergebracht. Das Modul wird dann von einem normalen Userlevelprogramm über /dev/erikyyyIOmodule kontrolliert. Dieses Programm ist dann auch nicht zeitkritisch.

In letzter Zeit habe ich zufällig noch eine weitere Methode entdeckt, Realtime mit Linux zu machen. Gegen Realtime sprechen bei anständigen Betriebssystemen immer zwei Dinge:

Gegen beide Dilemmas habe ich per Zufall sehr elegante Lösungen gefunden. Ich denke, das ist ab Linux-2.0 implementiert. Hmm. Was ist nun der Unterschied zwischen RT-Linux und einer Kombination aus mlock() und sched_setscheduler()? Ganz einfach. RT-Linux operiert auf unterster Ebene. Dadurch hat man zum Beispiel Zugriff auf Interrupts, was mit normalen Prozessen ja nicht möglich ist. Und vor allem ist bei der setscheduler()-Variante der Kernel nicht tot, sondern arbeitet munter weiter. Das heißt, pings werden replied, TCP Connections angenommen, der Audiopuffer wird auf die Soundkarte übertragen und was der Kernel halt sonst noch so treibt. Und der Kernel treibt mit höherer Priorität als der setscheduler() Realtime-Task. Somit leidet die Reaktionszeit ein wenig. Besonders schlimm ist der Festplatteninterrupt. (auch wenn man das mit hdparm() ändern kann...). NUR bei RT-Linux hat man genau dann die absolute Kontrolle über das System, wenn man sie haben will.

Wann soll ich jetzt welche Art von Realtime machen?

RT-Linux Echtzeitkernelmodule

Diese muß man immer dann einsetzen, wenn es zeitlich wirklich sehr kritisch wird. Zum Beispiel wurde damit schon ein Funktionsgenerator programmiert. Man geht unter X her, zeichnet den zeitlichen Verlauf der Spannung ein, und das Echtzeitkernelmodul erzeugt dann diese Spannung am Ausgang eines DA-Wandlers, und das ist WIRKLICH total (!) unabhängig von der Systemlast etc. Das glaubt man erst, wenn man es gesehen hat. Man könnte auch endlich mal den Quickcam Treiber auf diese Weise implementieren, da es mir auf den Keks geht, daß bei hoher Systemlast die Bilder gewiße Störungen aufweisen. Der große Nachteil von RT-Linux ist, daß ein Patch im Kernel benötigt wird, den leider leider fast niemand eingespielt hat.

Echtzeit mit normalen Tasks (mlockall + sched_setscheduler)

Nun. Funktionsgeneratoren sollte man damit nicht machen. Aber es gibt meiner Meinung nach ein Paradebeispiel für diese Anwendung: Modplayer! CD-Brenner!!! Beide Anwendungen verzeihen es ABSOLUT nicht, wenn sie zu lange unterbrochen werden. (Modplayer: die Musik unterbricht unschön, CD-Brenner: die CD ist Abfall). Ich habe spasseshalber den gängigen MikMod Modplayer gepatcht. Er war dann in der Lage bei 95% Swap-Auslastung (Mein Swap ist größer als deiner ;-) 20 facher Cpu- Load und sowieso andauerndem Rumgerattere auf der Platte als einzige noch total flüssig bedienbare Anwendung das Lied zuverlässig abzuspielen.

An alle, die jetzt enthusiastisch zu programmieren beginnen, noch eine wichtige Warnung im voraus: lässt man den Modplayer in einem XTerm laufen, so nutzt das ganze Realtime nichts. Wenn der XTerm den stdout blockiert (und das ist bei etwas Load recht schnell der Fall), so stoppt der Modplayer (die linux-console hingegen blockiert so schnell nicht !). Ihr müsst also eure Anwendungen aufteilen! Zur Kommunikation der Programmteile ist NICHT Mutex-Locking zu empfehlen!!! Denn wenn das nicht-Realtime-Programm den Mutex lockt und dann ausgelagert wird und das nächste Mal in 10 Sekunden ein bischen CPU bekommt, so wird auch hier das Realtime Programm blockiert. Daher muß die Kommunikation zwischen Realtime und nicht-Realtime mittels Pipes realisiert werden! Da kann man sich nicht gegenseitig blockieren. Ein Riesenvorteil ist übrigens, daß dieses Verfahren bei jedermann funktioniert. Es ist ein Standard-Feature des Linuxsystems. Nachteil: Zum Einstellen der Realtime Prorität muß man root sein. Dies kann jedoch am Programmstart erledigt werden, und danach kann man sich zu nobody umwandeln.

Da ich mich sehr für Computermusik interressiere, überlege ich oft, wie man einen 100% ausfallsicheren Soundserver programmieren kann, der trotzdem eine geringe Reaktionszeit besitzt. Will man das kurzzeitige Stoppen der Audioausgabe unterbinden, vergrößert man normalerweise einfach den Audiopuffer und erledigt die Arbeit so weit im voraus, daß selbst eine längere Unterbrechung des Programms durch Swapping oder hohe Systemlast zu keinem Ausfall führt (selbiges Verfahren bei CD-Brenner Software!). Soll der Soundserver aber zum Beispiel einen "Gong" ausgeben, wenn der Anwender die Maustaste drückt, so kann der Audiopuffer nicht mehr groß gewählt werden, sondern er muss sehr klein gemacht werden, damit man den Mausgong auch zum richtigen Zeitpunkt und nicht erst 3 Sekunden danach vernimmt.

Nun aber wirkt sich wieder jede noch so kleine Pause des Soundservers unterbrechend auf die Audioausgabe aus. Es liegt also nahe, mit mlockall() den Speicher gegen Swappen zu schützen und mit sched_setscheduler() eine höhere Priorität anzulegen. Leider hat diese Sache einen Haken. Die höhere Priorität ist gewährleistet, das funktioniert auch prima, aber das Swappen ist problematisch. Angenommen das Programm macht einen malloc(), so muß das System dem Programm neuen Speicher zur Verfügung stellen. Dies kann unter Umständen sehr lange dauern, dann nämlich wenn kein weiterer freier Speicher da ist. Es gilt dann, einen anderen Prozess auszulagern, und währenddessen ist unser Soundserver dann blockiert. Ähnliche Probleme bekommt man, wenn man zuviel Stack (zum Beispiel durch Programmieren allzuvieler Rekursionen) benutzt (daher empfiehlt die Manpage von mlockall(), einmal zu Beginn eine sinnlose Stackbenutzung zu absolvieren, damit später kein neuer Stack mehr angefordert werden muss) Für das malloc()-Problem gibt es jedoch keine Lösung. (Man könnte natürlich am Programmbeginn mal eben 20 MB RAM malloc()en und dann einen eigenen malloc() programmieren, der innerhalb der 20 MB eine eigene Speicherverwaltung realisiert, und somit niemals RAM vom Kernel braucht, die Nachteile sind jedoch gravierend: erstens sind die 20 MB wirklich weg, man hat danach wirklich 20 MB weniger RAM in seinem Rechner, und zweitens kann man niemals mehr als 20 MB RAM im Soundserver benutzen)

Nun es gibt aber noch ähnliche Probleme ohne direkte Lösung: open() zum Beispiel benötigt Zeit. Bei der Netzwerkprogrammierung existieren einige Möglichkeiten, die entsprechenden Systemcalls (connect, accept, read, write) so einzustellen, daß sie niemals blockieren. Der Befehl zum Öffnen einer Datei jedoch blockiert, bis die Datei offen ist. (Man stelle sich eine 300 Baud Verbindung zu einem NFS Server vor und denke darüber nach, wie lange der open()-Befehl dann braucht :-)

Für mich ist das open() Problem identisch dem malloc() Problem. In beiden Fällen möchte ein Prozess, der seine Hauptschleife ständig durchlaufen MUSS, und sich keine Unterbrechung erlauben DARF, eine Aktion ausführen, die eben blockiert. Was liegt also näher, als einem anderen Prozess diese Arbeit aufzuladen. Sprich, der Soundserver befiehlt seinem Sklavenprozess, eine Datei zu öffnen, und der Sklave meldet irgendwann die Vollendung des Befehls. Meines Wissens ist jedoch das Öffnen einer Datei und das darauffolgende Übergeben des Handles bei normalen Prozessen NICHT möglich, höchstens bei malloc() könnte ich mir irgendwelche Trickreiche Shared Memory (SHM) Tricks denken.

Um trotzdem jemand anderem als mir selbst die Arbeit des Dateiöffnens aufzubürden, kommen also nur POSIX Threads in Frage. Dann steht nichts mehr im Wege. Ein Thread kann die Datei öffnen, während ein anderer in aller Ruhe weiterhin sein Realtime Gehabe treibt. Es ist sogar möglich, die verschiedenen Threads auf unterschiedlicher Priorität laufen zu lassen. So kann der Sklave zum Beispiel auf normaler Priorität laufen, während der eigentliche Soundserverthread in Echtzeit läuft. OK, das Problem mit dem Öffnen von Dateien währe also gelöst, und mit dem malloc() gehts genauso.

Der Soundserver wird so sehr komplex. Immerhin sind malloc() und open() nun plötzlich gespaltene Befehle, die irgendwann gestartet, und irgendwann später asynchron fertig sind, aber immerhin kann man hiermit einen wunderbaren Soundserver schreiben. (oder einen CD-Brenner, der braucht aber weder malloc(), noch open(), ist somit ein Kinderspiel.

Ganz normale Prozesse

Diesen kann man ja mittels renice, nice und ähnlicher Shell-Befehle eine Priorität zuweisen. Aber eben nur eine Priorität. Außerdem werden normale Prozesse irgendwann ausgelagert. Wir sollten uns endlich abgewöhnen, alles als normale Prozesse zu programmieren. Modplayer zum Beispiel gehören wirklich nicht in diese Kategorie. (und CD-Brenner schon dreimal nicht!)

QNX-Style Scheduling v1.06 für Linux 2.0

Dies ist was Neues. Ich habe es noch nicht getestet, klingt aber sehr interressant (URL in der Infobox). Es ist ein Kernelpatch, der eine andere Art von Scheduler implementiert. Damit ist es zum Beispiel möglich, Tasks als wirkliche Idle-eating Tasks laufen zu lassen, das heißt sie laufen NUR dann, wenn NIEMAND sonst laufen möchte. Dies wäre zum Beispiel für die RSA Passworthack-Kampagne der richtige Modus für das Crack-Programm gewesen. Man hätte vom erhöhten Stromverbrauch abgesehen dann von dem Task überhaupt nichts gemerkt.

esep (Evolution Scheduling and Evolving Processes)

Dies ist ein Kernelpatch (sieh URL in der Infobox), der verspricht, die Rechenzeit an die Tasks intelligenter zu verteilen. Er tut dies durch genetische, evolutionäre Algorithmen. Wie das genau funktioniert, was es für Vorteile bringt etc. habe ich noch nicht ganz verstanden, ich verweise daher auf die Homepage des Projekts. Es ist aber mit Sicherheit interressant.

Weitere Entwicklungen

Die Schedulerei ist also noch lange nicht perfekt. Es gibt so viele Probleme, Möglichkeiten und andere Aspekte, die zu berücksichtigen sind. Mal sehen, wie sich das alles entwickelt. Gut ist aber, daß bereits jetzt die mlockall + sched_setscheduler Methode auf jedem Linux-2.0 System läuft. Aber Vorsicht! Ein Programmierfehler endet immer mit dem Drücken des RESET-Knopfes! Das ist eine böse Vorstellung, aber ein Echtzeittask in einer Endlosschleife ist eben nicht der Weisheit letzter Schluss. Auch hier ist noch Raum für Verbesserungen, eventuelle Watchdogs gegen diese Form des System lockings, oder eine generelle Reservecpu von 1% oder ähnliches wären denkbar.

Weiterhin sei gesagt, daß die von mir beschriebenen Dinge sehr gut in den Manpages der entsprechenden Befehle erklärt sind. Als Einstieg sei auf mlockall, sched_setscheduler und pthread_attr_setschedpolicy verwiesen. WAS? Diese Manpages existieren auf deinem System nicht? Dann wird es Zeit, daß Du auf Debian-1.3.1 umsteigst, das ist sowieso die beste aller Distributionen *räusper* ;-)

Ich muss noch etwas über die vielseitig gelobte libQT erzählen. Wie gesagt habe ich sie für mein EYCar Projekt verwendet, um eine GUI unter X zu realisieren. Dabei fand ich einen Bug, der binnen nur zwei Tagen von den Autoren intern gefixt war. Aber einen offiziellen Bugfix wollen sie definitiv nicht machen. Mittlerweile sind einige Bugs in der Bibliothek entdeckt worden (im Prinzip nichts Schlimmes, ganz normal) aber es werden keine neuen Releases gemacht. Das nächste Release wird neben den Fixes auch neue Features also wieder neue Bugs enthalten. Auf diese Weise wird die Lib niemals zuverlässig funktionieren. Die aktuelle Version ist nutzlos sofern einen die Bugs direkt betreffen. Einer ist so schlimm, daß die Arbeit an einem IRC Client kurzfristig eingestellt wurde. Selber fixen darf man die Bugs nicht, das ist aufgrund der Lizenz illegal. Da eine GUI eine grundlegende Angelegenheit ist (so wie der Linux Kernel) darf dies alles so nicht sein. Leider ist die libQT (ohne die Bugs) eine sehr gute Bibliothek mit einigen guten Gedanken, und sinnvolle Konkurrenz gibt es bisher wenig. Jedoch stecken auch in dem Prinzip der Bibliothek ein paar (meiner Meinung nach grundlegende) Haken, die mir persönlich etwas die Begeisterung genommen haben.

Was ist denn das für ein Kraut und Rüben Artikel ?

Hehe, ich bin wohl etwas vom Thema abgewichen. Wer mehr über den EYCar wissen möchte, findet das auf meiner Homepage. Ich habe alles äusserst detailreich dargestellt und viele Photos verwendet. Zu allen im Artikel disktutierten Dingen habe ich unten entsprechende URLs beigefügt, so daß man sich beliebig tief in die Materie einlesen kann.

Weitere Infos

http://www.erikyyy.de/ Homepage des Autors
http://www.erikyyy.de/eycar/ Homepage des EYCar. Die Sourcecodes sind auch downloadbar. Enthalten auch Scripte zum Einrichten der Funkmodems
http://www.troll.no/ Die libQT zur Erstellung grafischer Oberflächen
http://luz.cs.nmt.edu/~rtlinux/ RT-Linux Webpage
http://sunsite.unc.edu/LDP/HOWTO/AX25-HOWTO.html AX25-Howto
http://www.linuxhq.com/patch/20-p0768.html QNX-style scheduling v1.06 for Linux 2.0
http://www.iit.edu/~linjinl/esep.html esep (Evolution Scheduling and Evolving Processes)

Der Autor

Erik Thiele hält nichts von Umlauten in der deutschen Sprache (sorry, daß wir sie ihm trotzdem untergejubelt haben), beschäftigt sich schon längere Zeit mit Linux, ist davon total begeistert und freut sich stets über Spenden ;-)
Zu erreichen ist er unter (erikyyy at erikyyy dot de, Erik Thiele) oder im IRC als erikyyy.

Copyright © 1997 Linux-Magazin Verlag



EYCar Homepage