Multitasking mit AVR RISC-Controllern

Lösungsansätze und praktische Beispiele für Multitasking-Programme

Prof. Dr. Ernst Forgber

• Publisher: Franzis Verlag
• Year: 2014
• Print ISBN: 9783645652704
• eBook ISBN: 9783645270557
• Topic: Computer Science
• Subtopic: Hardware
• Index: Computer Science

Das Buch stellt anhand praktischer Beispiele für die Atmel-8-Bit-Controller mehrere Ansätze für Multitasking-Programme vor. Ausgehend von der Lösung mit einer einfachen Programmschleife werden Multitasking- und Echtzeitkonzepte erläutert - bis hin zur Entwicklung eines echtzeitfähigen, prioritätsgesteuerten, präemptiven Tasking-Systems. Die Ausführungen der verschiedenen Konzepte erfolgen anhand durchgehender Beispiele. Dabei wird zunächst immer die grundlegende Idee vorgestellt, die dann mithilfe der praktischen Beispielen konkretisiert und in einem anschließenden Blick auf die Details vertieft wird. Aufbau des Buchs: Multitasking, Kontext, Real-Time & Co. Begriffliche Erklärungen und grundlegende Mechanismen. Experimentierumgebung Beschreibung der Hard- und Software. AVR-Controller in C programmieren Besonderheiten bei der Programmierung von AVR-Controllern. Multitasking, die Erste: Die Minimalversion Klassischer Ansatz zum Multitasking unter komplettem Verzicht auf einen Scheduler und dem Versuch, alles über Interrupts und eine große Programmschleife zu realisieren. Betrachtung verschiedener Scheduler mit wachsender Komplexität in Theorie und Praxis. Multitasking, die Zweite: Ein Scheduler im Eigenbau Darstellung der Funktionsweise eines einfachen prioritätsgesteuerten Schedulers für zyklische Funktionen. Multitasking, die Dritte: Kooperation ist gefragt Zeigt die Funktionsweise eines kooperativen Schedulers auf der Basis von Dunkels' Protothreads. Multitasking, die Vierte: Präemptives Tasking Vorstellung eines vollständig prioritätsgesteuerten RTOS-Schedulers mit Präemption.

1Multitasking, Kontext, Real-Time & Co.

Das Zielsystem in diesem Buch sind Mikrocontroller. Dennoch soll der Einstieg in das Multitasking an einem weitaus mächtigeren Rechnersystem betrachtet werden. Jeder PC-Benutzer kennt bereits mindestens ein Multitasking-System, denn das PC-Betriebssystem erlaubt die Ausführung mehrerer Programme nebeneinander.

Wenn ein Programm gestartet wird, entsteht als Laufzeitumgebung für dieses Programm ein sogenannter Prozess. Der physikalische Speicher wird vom Betriebssystem an die laufenden Prozesse vergeben, jedoch hat jeder Prozess einen eigenen virtuellen Adressraum, in dem das Programm läuft. Die verfügbare Rechenzeit verteilt das Betriebssystem mithilfe des Schedulers an die vorhandenen Prozesse.

Der separate virtuelle Adressraum sorgt dafür, dass jedes Programm isoliert von den anderen laufen kann, ohne dass sich Programme gegenseitig beeinflussen. Innerhalb dieses virtuellen Adressraums werden der Programmcode und alle Variablen des Programms gespeichert.

1.1Kontext

Wenn man sich von einem Programm eine Momentaufnahme vorstellt, erhält man dessen augenblicklichen Kontext mit den Werten aller Variablen, den Inhalten der CPU-Register, dem aktuell bearbeiteten Programmbefehl und der Liste der Rücksprungadressen aus den aufgerufenen Unterprogrammen.

Der Scheduler verteilt die CPU-Zeit auf die vorhandenen Programme. Ein »Kontextwechsel« wird eingeleitet, indem der Scheduler den aktuellen Programmkontext speichert, aus der Liste der lauffähigen Programme eines auswählt und dessen früher gespeicherten Kontext wiederherstellt. Dieser Wechsel verläuft schnell genug, sodass der Nutzer den Eindruck gewinnt, mehrere Programme liefen gleichzeitig, obwohl tatsächlich immer nur eines die CPU belegt. Nur wenn es mehrere CPUs oder mehrere CPU-Kerne gibt, kann es echte Parallelverarbeitung geben.

Das Umschalten des kompletten virtuellen Adressraums ist eine aufwendige Angelegenheit. Daher bietet das Betriebssystem mit den Threads oder Tasks (hier synonym verwendet) kleinere Einheiten an, deren Kontext sich deutlich schneller umschalten lässt. Ein Programm kann dabei mehrere Tasks besitzen, die alle im virtuellen Adressraum des Programms laufen. Dabei ist in einem C-Programm eine Task nichts anderes als eine Funktion, die auf besondere Weise gestartet wird. Da alle Tasks eines Programms im selben virtuellen Adressraum existieren, sind die globalen Vereinbarungen allen Tasks gemeinsam zugänglich. Beispielsweise können die Tasks auf die globalen Variablen des Programms zugreifen. Dadurch lässt sich eine Kommunikation zwischen Tasks verwirklichen.

Den Kontext einer Task bilden die Inhalte der benutzten CPU-Register, die aktuelle Position im Programmcode, die eigenen lokalen Variablen und die Liste der Rücksprungadressen aus den Unterprogrammen, die die Task aufgerufen hat.

Die Rücksprungadressen und die lokalen Variablen liegen auf dem Stack-Speicher, daher braucht jede Task einen eigenen Stack. Wenn eine Task eine C-Funktion aufruft, läuft diese im Kontext der Task, d. h., die lokalen Variablen der aufgerufenen Funktion liegen auf dem Stack der Task, die die Funktion aufgerufen hat. Eine Funktion kann ohne Weiteres von mehreren Tasks gleichzeitig aufgerufen werden, alle lokalen Variablen existieren dann mehrfach auf verschiedenen Stacks, ohne sich zu stören. (Ausnahme: static-Variablen einer Funktion existieren nur einmal, also greifen alle Tasks auf denselben Speicherplatz zu. Das kann spezielle Schutzmaßnahmen erforderlich machen.)

Vor dem Umschalten auf eine andere Task muss der Scheduler den Task-Kontext abspeichern: Alle CPU-Registerinhalte und die Adresse des nächsten auszuführenden Befehls sowie der private Stack der Task werden gerettet, damit später an derselben Stelle nahtlos weitergemacht werden kann. Der Kontextwechsel bei Tasks ist viel schneller durchführbar als bei Prozessen, da viel weniger Daten gesichert werden müssen.

Auf einem Mikrocontroller kann nur ein Programm zur gleichen Zeit laufen, das aber mehrere Tasks starten kann. Auch wird man ohne komplettes Betriebssystem auskommen. Die Verwaltung der Tasks und das Umschalten zwischen ihnen übernimmt ein Scheduler, der in das eigene Programm integriert wird.

Beispiele für verschiedene Arten solcher Scheduler finden sich in den Kapiteln »Multitasking, die Erste: Die Minimalversion« bis »Multitasking, die Vierte: Präemptives Tasking«.

1.2Zustand einer Task

Jede Task befindet sich in einem von mehreren möglichen Zuständen, die in der nachfolgenden Abbildung dargestellt sind. Die Task, deren Kontext gerade geladen ist, befindet sich im Zustand laufend. Existiert lediglich eine CPU mit nur einem Kern, kann auch nur eine Task gleichzeitig in diesem Zustand sein. Andere Tasks sind bereit, d. h., sie könnten zwar laufen, aber der Scheduler hat sie zurzeit nicht aktiviert. Soll ein Task-Wechsel stattfinden, muss der Scheduler die laufende Task deaktivieren, indem er ihren Kontext speichert und ihren Zustand auf bereit setzt. Aus der Menge der bereiten Tasks wählt er eine andere Task aus und aktiviert sie, indem er ihren Kontext lädt und ihren Zustand auf laufend setzt. Im folgenden Abschnitt »Scheduler« wird auf mögliche Kriterien eingegangen, nach denen der Scheduler seine Auswahl trifft.

Bild 1.1: Zustandsdiagramm einer Task.

Eine laufende Task kann blockieren, wenn sie auf ein Ereignis wartet, z. B. dass eine Wartezeit verstreicht. Einer blockierten Task wird der Scheduler sofort die CPU-Zeit entziehen. Ihr Kontext wird gespeichert, und sie geht in den Zustand blockiert über. Erst wenn das erwartete Ereignis eintrifft, z.B. die Wartezeit vorüber ist, wird die Task wieder lauffähig und darf sich in die Liste der bereiten Tasks einreihen. Zu welchem Zeitpunkt sie dann erneut läuft, entscheidet der Scheduler.

Der letzte Zustand, suspendiert, ist nicht zwingend nötig. Viele Systeme verfügen über ein spezielles Kommando suspend(Task X), um Task x vorübergehend vom Scheduling auszuschließen. Erst mit der Ausführung des Kommandos resume(Task X) wird Task x wieder als bereit markiert.

1.3Scheduler

Die Verteilung der verfügbaren Rechenzeit auf die verschiedenen Tasks kann nach ganz unterschiedlichen Kriterien erfolgen. Stellvertretend für alle anderen sollen hier drei einfache Scheduling-Prinzipien dargestellt werden.

1.3.1Kooperatives Scheduling

Bei diesem Verfahren bleibt die gerade laufende Task ohne Zeitbeschränkung aktiv. Ein Task-Wechsel findet nur statt, wenn die laufende Task blockiert, z.B. indem sie sich selbst für eine gewisse Zeit schlafen legt ('sleep(..)'). Damit alle Tasks Rechenzeit erhalten, müssen sich alle kooperativ verhalten und den anderen freiwillig CPU-Zeit einräumen. Der Scheduler entscheidet bei einem Kontextwechsel, welche Task als Nächstes läuft. Er hat aber keinen Einfluss darauf, wie viel Rechenzeit sie bekommen wird. Auf einen Scheduler nach diesem Prinzip wird im Kapitel 6 »Multitasking, die Dritte: Kooperation ist gefragt« im Detail eingegangen.

1.3.2Round Robin Scheduling

Hier wird die verfügbare Rechenzeit gleichmäßig auf alle Tasks verteilt, wie in der nächsten Abbildung dargestellt. Jede der existierenden Tasks (Te, Ta etc.) erhält eine gleich große Zeitscheibe, die Reihenfolge der Aktivierung ist von Anfang an festgelegt. Es gibt keine unterschiedlichen Prioritäten, alle werden gleichbehandelt.

Bild 1.2: »Round Robin Scheduling« – gleiche Zeitscheiben für alle.

Man kann einerseits eine Systemperiode T_Per vorgeben, dann bekommt jede der n Tasks eine Zeitscheibe der Größe

Bei wachsendem n wird die Zeitscheibe T immer kürzer, und das System beschäftigt sich zunehmend mit den Kontextwechseln und immer weniger mit den eigentlichen Aufgaben der Tasks. Andererseits kann man die Größe der Zeitscheibe T vorgeben. Bei wachsender Task-Anzahl n dauert es dann immer länger, bis die einzelne Task wieder zum Zuge kommt.

1.3.3Präemptives Scheduling

Bei dieser Art Scheduling kann eine Task jederzeit unterbrochen werden, sobald der gerade laufende Maschinenbefehl abgearbeitet ist. Es gibt keine feste Task-Reihenfolge und keine konstanten Zeitscheiben. Stattdessen erhält jede Task eine Priorität zugeordnet. Aus der Menge der bereiten Tasks wird immer die mit der höchsten Priorität aktiviert. Sobald eine Task lauffähig wird, deren Priorität die der gerade laufenden übersteigt, findet sofort ein Kontextwechsel statt – die laufende Task wird verdrängt. Die Abbildung stellt das Prinzip für drei Tasks Ta, Tb, Tc dar.

Bild 1.3: Präemptives Scheduling: Aus den bereiten Tasks läuft die mit der höchsten Priorität.

Zum Zeitpunkt 0 sind Ta und Tc bereit, Tb ist blockiert. Die Priorität von Ta ist höher als die von Tc, daher aktiviert der Scheduler Ta. Zum Zeitpunkt 1 blockiert Ta, und aus der Menge der bereiten Tasks wird die mit der höchsten Priorität aktiviert, hier also Tc. Zum Zeitpunkt 2 wird Tb bereit und verdrängt aufgrund ihrer Priorität sofort Tc. Sobald Ta zum Zeitpunkt 3 lauffähig ist, verdrängt sie Tb.

1.4Multitasking und Echtzeitfähigkeit

Die bisher angesprochenen Scheduling-Verfahren sagen noch nichts über die Echtzeitfähigkeit eines Systems aus. Ein Multitasking-System verwaltet Tasks und teilt ihnen Rechenzeit zu, aber es wird zunächst keine Angabe über die Verzögerungszeit bei der Aktivierung von Tasks gemacht. Ein Echtzeitsystem muss in der Lage sein, bestimmte Anforderungen innerhalb einer maximalen Zeit zu bearbeiten. Es ist z.B. zu garantieren, dass eine hochpriorisierte Task spätestens 10 ms, nachdem sie lauffähig wurde, auch tatsächlich aktiviert wird.

Das Eintreten eines Ereignisses, z.B. der Tritt auf das Bremspedal eines Fahrzeugs, soll eine Task aktivieren, z.B. einen Teil des Bremsassistenten im Fahrzeug. Die folgende Abbildung zeigt die Latenzzeit zwischen dem Tritt auf das Pedal und der Aktivierung der Task, also dem Beginn des Bremsvorgangs. Ein echtzeitfähiges System kann garantieren, dass die Latenzzeit immer kleiner sein wird als eine bestimmte Maximalzeit. Wie groß diese Maximalzeit sein darf, hängt dabei allein von der Anwendung ab. Ein nicht echtzeitfähiges Multitasking-System wird die Task auch aktivieren, sich aber nicht festlegen, wann die Bremse spätestens aktiv wird.

Neben der Latenzzeit ist auch die Antwortzeit bis zur vollständigen Bearbeitung der Task von großer Bedeutung. Die »Zeitschranke« einer Task ist die maximal tolerierbare Antwortzeit, bestehend aus Latenzzeit plus Bearbeitungszeit. Wenn eine Task ihre Zeitschranke immer einhalten kann, spricht man von Rechtzeitigkeit, halten alle Tasks ihre Zeitschranken ein, erreicht man Gleichzeitigkeit.

Bild 1.4: Ein Echtzeitsystem hält vorgegebene Zeitschranken ein.

Die in diesem Buch in den Kapiteln 4 »Multitasking, die Erste: Die Minimalversion« bis 6 »Multitasking, die Dritte: Kooperation ist gefragt« vorgestellten Scheduler sind nicht echtzeitfähig. Ihre maximalen Latenzzeiten hängen vom Anwenderprogramm ab. Mit diesen Schedulern lassen sich Echtzeitanforderungen nur begrenzt über Hardware-Interrupts realisieren. Im Kapitel 7 »Multitasking, die Vierte: Prä...

Table of contents

• Deckblatt
• Worum geht es hier?
• Inhaltsverzeichnis
• 1. Multitasking, Kontext, Real-Time & Co.
• 2. Experimentierumgebung
• 3. AVR-Controller in C programmieren
• 4. Multitasking, die Erste: Die Minimalversion
• 5. Multitasking, die Zweite: Ein Scheduler im Eigenbau
• 6. Multitasking, die Dritte: Kooperation ist gefragt
• 7. Multitasking, die Vierte: Präemptives Tasking
• A Anhang
• Literaturverzeichnis
• Stichwortverzeichnis