www.mikrocontroller.net

Multitasking

Multitasking bedeutet ein quasi paralleles Ausführen von mehreren Prozessen auf einem Prozessor.

Inhaltsverzeichnis

[Bearbeiten] Einleitung

Da eine echte parallele Ausführung von mehreren Prozessen (Programmen, Funktionen) auf einem einzelnen CPU-Kern nicht möglich ist, wird ein "Trick" verwendet. Dabei werden die einzelnen Prozesse jeweils nur für kurze Zeit (1..50 ms) bearbeitet und danach auf einen anderen Prozess umgeschaltet. Man spricht auch von einer verschachtelten Bearbeitung (engl. interleaving).

Das Herz jedes Multitasking-Systems ist der Scheduler. Dieses Programm beinhaltet einen Algorithmus, der überprüft, welcher Prozess als nächstes die CPU (also Rechenzeit) zugeteilt bekommt. Es gibt verschiedene Schedulingalgorithmen:

  • First come first served: Teilt den Prozessen in der Reihenfolge Rechenzeit zu, in der sie rechenbereit werden
  • Shortest Job first: Der Prozess mit der kürzesten Rechenzeit wird als erstes bearbeitet. Dazu muss die Rechenzeit natürlich im Voraus bekannt sein
  • Shortest remaining time next: Der Prozess mit der kürzesten verbleibenden Rechenzeit wird jeweils als nächstes bearbeitet. Auch hier muss diese Zeit natürlich bekannt sein
  • Round Robin: Alle Prozesse bekommen eine gleich große Zeitscheibe zugeteilt. Der Scheduler lässt jeden Prozess für die Dauer einer Zeitscheibe rechnen, und übergibt die CPU dann an den nächsten Prozess
  • Priority Scheduling: Anders als beim Round Robin Verfahren sind die Prozesse hier nicht gleichwertig. Prozesse haben Prioritäten, der Scheduler sorgt dafür, dass höher priorisierte Prozesse bevorzugt behandelt werden

Natürlich sind Scheduler in freier Wildbahn nicht immer so einfach zu charakterisieren, da sie oftmals komplizierte Hybriden der genannten Techniken implementieren. Die Scheduler der "echten" Betriebsysteme (Windows, Linux, MacOS, *BSD) sind im Prinzip prioritäten-basierende Round Robin Scheduler. Generell hat ein Betriebsystem 2 Möglichkeiten, Multitasking zu realisieren, kooperativ oder präemtiv.

[Bearbeiten] Kooperatives Multitasking

Beim kooperativen Multitasking gibt der Scheduler die Kontrolle komplett an den Prozess ab. D.h., das Betriebsystem ist darauf angewiesen, dass der Prozess die Kontrolle wieder abgibt. Geschieht das nicht, wird der Scheduler nicht wieder aufgerufen und damit auch kein anderer Prozess mehr ausgeführt - das System "hängt". Das OS ist also auf die Kooperation der Prozesse angewiesen. Bekannte Beispiele für Betriebssysteme mit kooperativem Multitasking sind Windows 3.x und MacOS vor Version 10.

Dennoch ist kooperatives Multitasking keineswegs überholt oder schlecht. Gerade im Bereich der Mikrocontroller und Echtzeitanwendungen gibt es viele Argumente, die für ein kooperatives Multitasking sprechen: Kooperatives Multitasking ist deterministischer (zeitlich und logisch vorhersagbar). Es ist besser simulierbar, d.h. für ein gegebenes System ist leichter nachweisbar, dass es funktioniert. Da es sich um geschlossene Systeme handelt, tritt das Problem, dass "irgendein" Prozess das System anhält, nicht auf. Es laufen ja im Gegensatz zum PC nicht "irgendwelche" Prozesse, sondern nur die, deren Korrektheit (hoffentlich) verifiziert & validiert wurde.

[Bearbeiten] Ein einfaches Beispiel für den AVR

Hier soll ein einfaches Beispiel den Weg in die Programmierung von parallel bearbeiteten Aufgaben zeigen.

Wichtigster Grundsatz ist die Herangehensweise! Viele Programmieranfänger haben damit Schwierigkeiten, was u.a. an den schlecht vermittelten Grundlagen liegt. Oft sieht man Funktionen zum Warten in Form von 

while(1) {
    PORTD ^= (1<<PD0);
    _delay_ms(500);
}

um beispielsweise eine LED blinken zu lassen. Will man dann noch andere Dinge erledigen, wundert sich der Programmierer, warum der Mikrocontroller so langsam reagiert, trotz 16 MHz Taktfrequenz.

[Bearbeiten] Einfacher Ansatz

Stellen wir uns vor, wir wollen drei Dinge gleichzeitig tun.

  • Eine Taste abfragen
  • Eine LED blinken lassen, in Abhängigkeit der gedrückten Taste
  • Daten vom UART empfangen und zum PC zurücksenden

Ein einfacher Ansatz für die drei Dinge sieht etwa so aus. Die Beispiele wurden mit WinAVR Version 20081006 in der Optimierungsstufe -Os kompiliert. 

/*
 
Multitasking Demo, erster Versuch
 
ATmega32 @ 3,6864 MHz
 
LED + 1KOhm Vorwiderstand an PB0
Taster nach GND an PA0
UART an RXD und TXD
 
*/
 
#define F_CPU 3686400
// Baudrate, das L am Ende ist wichtig, NICHT UL verwenden!
#define BAUD 9600L          
 
#include "avr/io.h"
#include "util/delay.h"
 
// Berechnungen
// clever runden
#define UBRR_VAL  ((F_CPU+BAUD*8)/(BAUD*16)-1)  
// Reale Baudrate
#define BAUD_REAL (F_CPU/(16*(UBRR_VAL+1)))     
// Fehler in Promille 
#define BAUD_ERROR ((BAUD_REAL*1000)/BAUD-1000) 
 
#if ((BAUD_ERROR>10) || (BAUD_ERROR<-10))
  #error Systematischer Fehler der Baudrate grösser 1% und damit zu hoch! 
#endif
 
uint8_t taste_lesen(void) {
    if (PINA & (1<<PA0))
        return 1;
    else 
        return 0;
}
 
void led_blinken(uint8_t taste) {
 
    PORTB ^= (1<<PB0);
    if (taste) 
        _delay_ms(1000);    // 1 s warten
    else
        _delay_ms(100);     // 0,1 s warten
}
 
void uart_lesen(void) {
    uint8_t tmp;
    while (!(UCSRA & (1<<RXC)));            // Warte auf empfangenes Zeichen vom UART
    tmp = UDR;
    while (!(UCSRA & (1<<UDRE)));           // Warte auf freien Sendepuffer vom UART
    UDR = tmp;
}
 
int main(void) {
    int8_t taste;
 
    // IOs initialisieren
    
    PORTA = 1;              // Pull Up für PA0
    DDRB  = 1;              // PC0 ist Ausgang
 
    // UART initialisieren
    
    UBRRH = UBRR_VAL >> 8;
    UBRRL = UBRR_VAL & 0xFF;
    UCSRB = (1<<RXEN) | (1<<TXEN);
    
    // Endlose Hauptschleife
 
    while (1) {
        taste = taste_lesen();
        led_blinken(taste);
        uart_lesen();
    }
}

Wenn man das Programm nun laufen lässt, wird man feststellen daß

  • das Hyperterminal sehr langsam reagiert und bisweilen Zeichen verschluckt
  • die LED auf Tastendrücke nur dann reagiert, wenn man per Hyperterminal Zeichen eingibt

Dieser Ansatz ist also untauglich. Egal wie schnell unser AVR auch ist, er reagiert sehr langsam.

[Bearbeiten] Verbesserter Ansatz

Will man mehrere Dinge gleichzeitig bearbeiten, muss man die Aufgaben in kleinste Häppchen zerteilen. Diese kleinsten Häppchen werden dann verschachtelt abgearbeitet, also ein Häppchen von Aufgabe A, ein Häppchen von Aufgabe B, ein Häppchen von Aufgabe C.

Das Auslesen der Taste geht immer sehr schnell, kein Ansatz zum optimieren. Das Blinken der LED dauer entweder 1s oder 100ms, eine Ewigkeit für einen Mikrocontroller! Hier muss man was ändern. Am schlimmsten ist die UART-Nutzung. Der AVR wartet solange, bis ein Zeichen empfangen wurde! Das kann ewig dauern! Unser Programm steht! Das darf nicht sein! 

/*
 
Multitasking Demo, zweiter Versuch
 
ATmega32 @ 3,6468 MHz
 
LED + 1KOhm Vorwiderstand an PB0
Taster nach GND an PA0
UART an RXD und TXD
 
*/
 
#define F_CPU 3686400
// Baudrate, das L am Ende ist wichtig, NICHT UL verwenden!
#define BAUD 9600L          
 
#include "avr/io.h"
#include "util/delay.h"
 
// Berechnungen
// clever runden
#define UBRR_VAL  ((F_CPU+BAUD*8)/(BAUD*16)-1)  
// Reale Baudrate
#define BAUD_REAL (F_CPU/(16*(UBRR_VAL+1)))     
// Fehler in Promille 
#define BAUD_ERROR ((BAUD_REAL*1000)/BAUD-1000) 
 
#if ((BAUD_ERROR>10) || (BAUD_ERROR<-10))
  #error Systematischer Fehler der Baudrate grösser 1% und damit zu hoch! 
#endif
 
uint8_t taste_lesen(void) {
    if (PINA & (1<<PA0))
        return 1;
    else 
        return 0;
}
 
void led_blinken(uint8_t taste) {
    static uint16_t zaehler=0;
 
    if (taste) {
        if (zaehler>=999) {
            PORTB ^= (1<<PB0);
            zaehler=0;
        }
    }
    else {
        if (zaehler>=99) {
            PORTB ^= (1<<PB0);
            zaehler=0;
        }
    }
 
    zaehler++;
    _delay_ms(1);       // 1 ms warten
}
 
void uart_lesen(void) {
    uint8_t tmp;
    if((UCSRA & (1<<RXC))) {                // empfangenes Zeichen abholbereit im UART ?
        tmp = UDR;
        while (!(UCSRA & (1<<UDRE)));       // Warte auf freien Sendepuffer vom UART
        UDR = tmp;
    }
}
 
int main(void) {
    int8_t taste;
 
    // IOs initialisieren
    
    PORTA = 1;              // Pull Up für PA0
    DDRB  = 1;              // PB0 ist Ausgang
 
    // UART initialisieren
    
    UBRRH = UBRR_VAL >> 8;
    UBRRL = UBRR_VAL & 0xFF;
    UCSRB = (1<<RXEN) | (1<<TXEN);
    
    // Endlose Hauptschleife
 
    while (1) {
        taste = taste_lesen();
        led_blinken(taste);
        uart_lesen();
    }
}

Dieses Programm reagiert ganz anders! Schnell wie der Wind und vollkommen unabhängig von anderen, parallel laufenden Prozessen. Warum ist das so ?

Die einzelnen kleinen Häppchen sind verdaulicher als die grossen. Die maximale Durchlaufzeit der einzelnen Funktionen ist drastisch reduziert. Anstatt in der LED-Ausgabe einmal 1000 ms zu warten wird nun 1000x1ms gewartet. Zwischendurch werden aber 1000 mal die anderen Prozesse bearbeitet. Echte Demokratie sozusagen. Noch viel besser ist die Handhabung des UARTs. Anstatt eine Ewigkeit auf ein ankommendes Zeichen zu warten, wird nur dann etwas bearbeitet, wenn auch wirklich etwas zur Bearbeitung vorliegt. Klingt eigentlich logisch. Also nur dann, wenn schon ein Zeichen empfangen wurde wird es auch bearbeitet, ansonsten geht es zurück zur Hauptschleife. Das ist eigentlich der ganze "Trick" eines kooperativen Multitaskings. Auch wenn die Verwendung von _delay_ms(1) noch ein kleiner Schönheitsfehler ist, den die Profis lieber mit einem Timer erledigen, so wird das Prinzip klar.

  • Prozesse eines kooperativen Multitaskingsystems warten nicht auf das Eintreten von Ereignissen, sondern bearbeiten nur bereits eingetretene Ereignisse.
  • Grössere Aufgaben werden in kleine Teilaufgaben zerlegt, welche nur durch mehrfaches Aufrufen der Funktion abgearbeitet werden.
  • Prozesse eines kooperativen Multitaskings haben eine garantierte, maximale Durchlaufzeit, welche möglichst klein ist.

Damit ähneln die Prozesse einem Interrupt, auch wenn sie als ganz normale Funktionen ausserhalb eines Interrupts ausgeführt werden. An diesem Beispiel erkennt man die Vor- und Nachteile des kooperativen Multitaskings

Vorteile

  • einfacher Scheduler mit geringster CPU Belastung
  • Deterministische Arbeitsweise, damit einfach prüfbar und strenges Timing möglich

Nachteile

  • eine andere Programmierweise zur Zerlegung größerer Aufgaben in kleine Teilaufgaben muss manuell vorgenommen werden

[Bearbeiten] Message passing Framework

Im vorangegangenen Abschnitt wird erklärt, wie man die einzelnen "Tasks" in kleine Häppchen Zerlegen kann und diese alle innerhalb der Main Loop aufruft. Dieses kooperative System hat aber noch einige Nachteile:

  • Alle Häppchen werden gleich oft aufgerufen und nicht nur bei Bedarf
  • Für die Timeouts gibt es noch keine befriedigende Lösung

Wenn man diese beiden Nachteile auch noch lösen möchte, wird das ganze noch ein klein wenig komplizierter. Da man das Grundprinzip aber für viele Mikrocontroller Projekte immer wieder verwenden kann, lohnt es sich und man kann die Entwicklung für diese Art des Multitasking in einem Framework zusammenfassen.

Ein Framework, das sind einige Dateien, die den Rahmen (Frame=Rahmen) für ein Programm bilden und den Teil enthalten, den man immer wieder braucht.

[Bearbeiten] Message

Die Basis des Frameworks bildet die "Message". Immer wenn wir für einen unserer "Tasks" etwas zu tun haben, schicken wir eine "Message". Die "Messages" werden in eine Warteschlange einsortiert und der Reihe nach abgearbeitet. Dadurch kommt ein Task der viel zu tun hat (viele Messages bekommt) öfter dran, als ein "Task" der nicht so viel zu tun hat. Außerdem kann eine Message noch Daten enthalten (z.B. ein empfangenes Zeichen). So können die einzelnen Tasks sogar Daten austauschen.

[Bearbeiten] Message Receiver

Unsere "Tasks" werden immer dann aufgerufen, wenn Arbeit für sie da ist. Das wissen wir, weil sie eine Message empfangen sollen. Deshalb heißen die "Tasks" ab jetzt "Message Receiver"

[Bearbeiten] Timeout

In diesem System wird jeder Message Receiver aufgerufen, wenn jemand Arbeit für ihn hat und er deshalb eine Message bekommt. Was aber, wenn keine Message kommt, oder ein Message Receiver selbst aktiv werden soll?

Aus diesem Grund braucht es die Timeouts. Mit Hilfe eines Hardware Timers wird eine "Systemzeit" programmiert. Jeder Message Receiver kann die Zeit angeben, wann er wieder aufgerufen werden muss. Das Framework verwaltet alle Timer und sendet den Message Receivern eine "Timeout" message, wenn ihre Zeit gekommen ist.

[Bearbeiten] Beispiel

Hier der Sourcecode eines solchen Framework Datei:ACF.zip Das Framework implementiert die Message Warteschlange und die Timer Warteschlange. Die Prozessor spezifischen Dinge sind in der Datei "ACF_Hal.c" zusammengefasst und für Linux Desktop und atMega128 implementiert. In dieser Datei kann man das ganze auch auf andere Prozessoren anpassen.

Ein "main" sieht dann z.B. so aus: 

#include "ACF.h"
 
int main(int argc, char** argv)
{
    ACF_init();
    ACF_loop();
    return 0; // we will never arrive here
}
[Bearbeiten] Tracing

Es gibt noch einen weiteren Grund, sich ein "Framework" zu erarbeiten, oder ein fertiges Framework zu verwenden. Da der Ablauf der Software und der Aufruf aller Teile vom Framework bestimmt wird, kann das Framework auch einen sehr detaillierten Trace über das Verhalten des Codes anfertigen. Das Framework aus vorstehendem Beispiel enthält bereits entsprechenden Code.

Solche Traces von laufendem Code können gerade dann sehr hilfreich sein, wenn viele Dinge gleichzeitig ablaufen (und das war schließlich der Sinn des ganzen).

Nachstehendes Bild Zeigt den Trace eines Reglers, der mit dem Framework realisiert wurde. Sequenz Diagram

[Bearbeiten] Präemptives Multitasking

Beim präemptiven Multitasking gibt das OS die Kontrolle zu keinem Zeitpunkt auf. Ein Prozess, der gerade die CPU nutzt, kann jederzeit wieder vom Betriebssystem unterbrochen werden. Daher muss bei der Entwicklung für ein präemptives System immer damit gerechnet werden, dass ein Prozess jederzeit unterbrochen werden kann. Das kann z. B. zu Problemen beim Zugriff auf limitierte Betriebsmittel führen. Beispiel:

  • Prozess A sucht freien Speicher und findet einen freien Block
  • Prozess B wird vom Scheduler gestartet und sucht ebenfalls einen Speicherblock. Der gefundene Block wird von Prozess B reserviert und benutzt
  • Der Scheduler teilt wieder Prozess A die CPU zu. Prozess A wird fortgeführt, d.h. er reserviert jetzt den im letzten Systemcall gefundenen Speicherblock

Jetzt haben also beide Prozesse den gleichen Speicherblock reserviert. Entweder arbeiten jetzt beide Prozesse mit dem gleichen Speicher, und überschreiben daher gegenseitig die Daten, oder das Betriebsystem hat etwas gemerkt und zieht die Notbremse. In jedem Fall passieren schreckliche Dinge. Sowas nennt man eine Race-Condition.

Die Lösung nennt sich Semaphore: Dieser Mechanismus wird vom Betriebsystem bereitgestellt und erlaubt es einem Prozess eine bestimmte Ressource zu sperren. Wenn also Prozess A aus obigem Beispiel Speicher haben möchte, setzt er vor Beginn der sogenannten "Kritischen Sektion" eine Semaphore für "Speicher reservieren". Diese Semaphore wird erst wieder aufgehoben, sobald Prozess A den Speicher für sich reserviert hat. Wenn der Prozess B zwischendurch gestartet wird und ebenfalls versucht die Semaphore zu setzen, wird er solange warten müssen, bis Prozess A die Semaphore wieder freigibt. Speziell für derartige Locking Mechanismen bieten die meisten Prozessoren sogenannte TAS-Befehle (Test And Set), die in einem Prozessorbefehl eine Variable testen und je nach Ergebnis setzen können. Das ist nötig um das Setzen von Semaphoren unteilbar (atomar) zu machen. Könnte der Scheduler das Setzen einer Semaphore unterbrechen, wäre ja der ganze Aufwand umsonst.

Präemptive Multitasking Systeme sind sehr flexibel und kommen mit einer Vielzahl an Tasks klar. Amok laufende Prozesse können das System bei korrekter Implementierung nicht blockieren. Damit aber das System crash-sicher ist, muss es Systemresourcen geben, die nur der Scheduler verteilen kann (z. B. kein anderer Prozess darf in den Speicherbereich des Schedulers schreiben; kein anderer Prozess darf den Timerinterrupt des Schedulers ändern). Diese Möglichkeiten sind in Mikrocontrollern normalerweise gar nicht vorhanden, wodurch dieser Vorteil des Präemptiven MT weniger ins Gewicht fällt. Beispiele für Systeme mit präemptivem Multitasking sind Linux, *BSD und Windows XP.

Vorteile

  • sehr flexibel in der Verwaltung von dynamisch ausgeführten Prozessen
  • einzelne Prozesse können einfach linear programmiert werden, ohne die Aufgabe in kleine Teile zerlegen zu müssen

Nachteile

  • Der Scheduler ist aufwändiger und benötigt mehr CPU-Zeit
  • Höherer Resourcenbedarf zu Verwaltung des Systems und Bereitstellung der Semaphoren etc.
  • nicht streng deterministisch, somit kann kein festes Timing garantiert werden
  • nicht explizit debug- und prüfbar, da die Prozesse nicht fest gekoppelt sind

[Bearbeiten] Multithreading

Multithreading ist eine meist softwarebasierende Möglichkeit moderner Betriebssysteme, innerhalb eines Prozesses mehrere Tasks (threads) parallel auszuführen. Der Vorteil dieser weiteren Unterteilung ist, dass sich die Threads eines Tasks den Speicherbereich teilen können und eine Aufteilung in logische nebeneinander laufende Teile möglich ist. Je nach Betriebssystem kann der Übergang von Multithreading zu Multiprocessing fliessend bis starr sein.

Das Hyperthreading eines Intel Pentium 4 folgt dem Konzept des Multithreadings auf Hardwarebasis und teilt den CPU-Kern zeitlich in zwei logische Prozessoren ein.

[Bearbeiten] Weblinks

Von „http://www.mikrocontroller.net/articles/Multitasking“
webmaster@mikrocontroller.net – Impressum – Nutzungsbedingungen – Werbung auf Mikrocontroller.net