Mikrocontroller.net - Benutzerbeiträge [de]

FPGA Soft Core

2016-02-23T16:34:21Z

134.169.116.105: Bedeutung von soft core

== Einleitung ==
Ein soft core (engl. wörtlich "weicher Kern", sinngemäß "Software-Kern") ist ein Prozessor, ein Mikrocontroller oder ein digitaler Signalprozessor, welche als virtuelle Einheit in einem FPGA oder ASIC-Design integriert wird. Somit kann jeder beliebige Prozessor zum Chip hinzugefügt werden, wobei dieser in einem ASIC de facto zu einem hard core (engl. harter Kern) wird. In FPGA besteht dieser aus reiner Anwenderlogik, die dazu entsprechend konfiguriert wird. Alternativ wird er als echter hard core auf dem Chip platziert oder bei der Überführung eines FPGA-designs in einen ASIC praktisch zu einem hard core gemacht.

Im Regelfall werden soft cores in FPGAs dazu verwendet, komplizierte Aufgaben zu erledigen, die eine klassische state machine überfordern oder ineffektiv werden ließen, die aber gleichzeitig nicht zu hohe Anforderungen an die Geschwindigkeit stellen. Oft werden SCs im Nachhinein in FPGAs integriert, wenn sich im Zuge einer Erweiterung des Funktionsumfangs herausstellt, dass die Aufgaben komplexer werden und intelligente Verwaltung gefordert wird.

=== Vorteile von Soft Cores gegenüber hard cores ===
Vorteile:
* Flexible Anwendung, das FPGA '''kann''' bei Bedarf mit einem SoftCore versehen werden; es wird im Vorhinein jedoch keine Chipfläche für einen eventuell ungenutzen Hard Core verschwendet (Kostenvorteil)
* Einige Softcore sind sehr flexibel konfigurierbar (16/32 Bit Datenpfade, Zusatzmodule, Spezielle Anwenderbefehle etc.)
* Kleine Softcores können je nach Anwendung mehrfach im FPGA parallel platziert und verwendet werden, dadurch erhöht sich die Datenverabreitungskapazität (z. B. ein RX Prozessor und ein TX-Prozessor)

Nachteile:
* Geringere Geschwindigkeit
* Höhere Wärmeverlustleistung

=== Eigenschaften===
Ein soft core wird gern für etwas komplexere Aufgaben verwendet, bei denen es nicht auf allerhöchste Geschwindigkeit ankommt, z. B. eine Displayansteuerung oder die Konfiguration von Peripheriebausteinen über I2C.

Die erreichbaren Taktfrequenzen sind stark vom FPGA-Typ und der FPGA-Auslastung (freie Logikressourcen) abhängig. Mit Softcores können daher typischerweise maximal Datendurchsatzraten in der Größenordnung von 10-20Mbps realisiert werden.

=== Typen ===
Eine große Anzahl frei verfügbarer Soft-CPUs gibt es auf [http://www.opencores.org/browse.cgi/filter/category_microprocessor OpenCores.org]. Die vorhandene Palette reicht von Nachbauten vorhandener Prozessoren, wie des AVR, PIC oder MIPS, bis hin zu eigenen Entwicklungen, wie dem "16 Bit Microcontroller" (c16), der speziell für FPGAs optimiert ist und mit einem eigenen RTOS kommt. Ein anderer ist z. B. der 32-bit OpenRisc 1000, für den eine Version der GNU Tools für die Software Entwicklung zur Verfügung stehen.

Hier soll ein kleiner Überblick über vorhandene Softcores entstehen, für welche Softwarunterstützung existiert und welche Leistungen zu erwarten sind.
Es nützt einem oft der tollste Softcore nicht, wenn er sich nicht entsprechend programmieren läßt. Für LatticeMico32, MicroBlaze und NIOS ist jeweils ein Systembuilder verfügbar. Damit lassen sich leicht und übersichtlich Prozessor und Peripherie konfigurieren.

== 8 Bit Soft Cores ==

{| border="1" class="wikitable sortable" id="softcores"
|-
!Name
!optimiert für
!Quellcode
!max. Programmspeicher
!Programmierung
!Toolchain
!Leistung
!Lizenz/Preis
!Weblink
|-
|AX8
|entfällt
|ja, VHDL
|2k (8k)
|asm, C, Basic, [[Ada]]...
|GCC/WinAVR, ...
|wie AT90S2313 mit 30-50MHz
|
|[http://www.opencores.org/project,ax8 OpenCores]
|-
|T51
|entfällt
|ja, VHDL
|64k
|asm, Basic, C, ...
|sdcc, MCS-Basic, ...
|single cycle 8051, z. B. 40 MHz auf Spartan3
|
|[http://www.opencores.org/projects.cgi/web/t51/overview OpenCores] [[T51-Core]]
|-
|8051 IP Core
|entfällt
|ja, VHDL
|64k
|asm, Basic, C, ...
|sdcc, MCS-Basic, ...
|1-4 cycle 8051
|open IP-Core
|[http://www.oregano.at/ip/8051.htm Oregano Systems]
|-
|LatticeMico8
|Lattice
|ja, Verilog & VHDL
|
|asm, C
|GNU Toolchain
|
|open IP-core
|[http://www.latticesemi.com/products/intellectualproperty/referencedesigns/8bitmicrocontrollermico8.cfm Lattice]
|-
|PicoBlaze
|Xilinx
|ja, VHDL
|2k (1024 Befehle)
|asm (DOS/ dosbox)
|
|lt. Xilinx 100 MIPS
|Xilinx Reference Design License
|[http://www.xilinx.com/picoblaze Xilinx]
|-
|PacoBlaze
|entfällt
|ja, Verilog
|wie PicoBlaze
|asm (geschrieben in Java)
|KCAsm
|wie Picoblaze
|modifizierte BSD Lizenz
|[http://bleyer.org/pacoblaze/ PacoBlaze]
|-
|Panda
|entfällt
|ja, VHDL
|64k
|asm
|HASM, Builder SW
|je nach Konfiguration
|Free IP, Boost
|[http://www.logicsolutions.ch/Download.htm LogicSolutions]
|-
|Proteus
|entfällt
|ja, VHDL
|64k
|asm
|HASM, Builder SW
|je nach Konfiguration
|Free IP, Boost
|[http://www.logicsolutions.ch/Download.htm LogicSolutions]
|-
|embedded Z8 (UB8820)
|XILINX, ASIC syn.
|ja, VHDL
|64k
|asm
|[http://john.ccac.rwth-aachen.de:8000/as/ Makroassembler AS]
|je nach Konfiguration
|Free IP
|[http://www.dynamic-technologies.de/papa/z8/current.tgz embeddedZ8 site]
|-
|bo8
|
|ja, VHDL
|n*64k
|asm
|
|
|Creative Commons
|[http://www.mikrocontroller.net/articles/8bit-CPU:_bo8 bo8]
|}

=== Picoblaze ===

Dabei handelt es sich um einen sehr kleinen, aber dennoch sehr leistungsfähigen Microprozessor.

Eigenschaften:

*nur 76-93 Slices Ressourcenbedarf
*16 8-Bit Register
*1024 Befehle Programmspeicher (Version für Spartan-II nur 256 Befehle)
*18-Bit Befehle, RISC (Version für Spartan-II hat 16-Bit Befehle)
*'''Alle''' Befehle dauern zwei Takte
*Interruptunterstützung
*8-Bit IO-Bus
*Indirekte Addressierung möglich
*Programmspeicher durch Bankumschaltung erweiterbar
*Assembler als Kommandozeilenprogramm verfügbar
*Entwicklungsumgebung pBlazeIDE verfuegbar mit integriertem Assembler
*Schneller Programmdownload über JTAG während der Entwicklung
*37..102 MIPS, abhängig von der FPGA-Familie

=== AX8 ===
Der AX8-Core entspricht fast einem Atmel AT90S2313. Ihm fehlen noch Hardwareeinheiten wie EEPROM, Watchdog und die verschiedenen Powerdown-Modi.

* Ressourcenbedarf: ~ 1400 Xilinx-Slices
* erreichbare Geschwindigkeit auf einem Spartan3-1000: 50 MHz
* als Toolchain kann problemlos WinAVR o.ä. verwendet werden

Die ROM-Beschreibung muss angepasst werden, damit XST einen BlockRAM generieren kann (ein passendes hex2rom gibts hier: [http://www.mikrocontroller.net/topic/91160 hex2rom]).

Der Core lässt sich leicht mit Speicher (8KByte ROM), einem EEPROM (bis zu 64KByte), zwei Ports und einem Watchdog erweitern. Damit entspricht der AX8 dann einem AT90S8535, bis auf die anderen Timer/Counter und die fehlende SPI-Schnittstelle.

Für Entwicklungszwecke lässt sich der ROM-Inhalt - wie beim Picoblaze - per JTAG-Schnittstelle updaten. Somit kann neue Software getestet werden, ohne das Design neu zu synthetisieren. Dafür benötigt man die Werkzeuge hex2svf, svf2xsvf und xsvfplayer. Im FPGA füllt dann eine State-Machine am JTAG-Port einen DualPort-RAM (ROM :-))

Im Gegensatz zu neueren AVR-Controllern wie dem ATMega8, fehlen dem AX8-Core Befehle wie MOVW, MUL und FMUL. Außerdem fehlen Hardwareeinheiten, wie I2C und erweiterte Timer. Die größte Beschränkung aber ist der maximale Programmspeicherplatz von 8KByte. Mehr Speicher macht größere Änderungen am VHDL-Code des Cores erforderlich.

=== AVR8 ===

The AVR8 Soft Processor core is an AVR instruction set compatible processor that is optimized to run on the Butterfly Flight or Butterfly Light FPGA hardware. It is based on the '''ATmega103''' processor and includes a full toolchain to compile and run C code developed with avr-gcc.

http://gadgetfactory.net/gf/project/avr_core/

=== Panda ===
Es steht eine grafische Builder SW zur Verfügung um ein System inklusive Peripheriern zu generieren, ohne VHDL schreiben zu müssen. Einige Peripherieren (Timer, Ports, etc.) sind bereits integriert, eigene Peripherien können in die SW integriert werden.
Der Prozessor ist stark konfigurierbar (z. B. Ein/Ausschalten einzelner Instruktionen).

=== Proteus ===
Der Prozessor kann durch über 20 Generics perfekt an das Projekt angepasst werden. Es lassen sich beispielsweise Wortbreite, Instruktionen, Pipelining und Register anpassen. Es gibt auch eine JTAG Debugging Software zum Prozessor, die es auch ermöglicht mehrere Prozessoren in einem Chip zu Debuggen. Auch benutzerdefinierte Instruktionen werden unterstützt.
Proteus hat für Daten und Instruktionen zwei separate Wishbone Interfaces und ist zu 100% Herstellerunabhängig. In seiner kleinsten Konfiguration benötigt Proteus weniger als 300 LUTs.

=== embedded Z8 (UB8820/UB8840) ===
Frei konfigurierbarer Mikrokontroller Core der sich an der Architekture des UB8820/... orientiert (damit dem z8 entsprechend)

Eigenschaften:

*konfigurierbare Anzahl der Registersets

=== bo8 ===
Die CPU '''bo8''' ist Teil eines auf ''mikrocontroller.net''  vorgestellten Gesamt-Projekts. Sie hat einen vollständigen Befehlssatz mit 256 OpCodes. Die Berechnung der Dauer von Befehlsfolgen durch Abzählen von Zyklen ist sehr einfach. Die CPU kann eine unbestimmte Anzahl von 64KByte-Seiten adressieren. Nachteilig sind die fehlenden Interrupts und die bisher fehlenden Aussagen zur maximalen Taktfrequenz.

== 16 Bit Soft Cores ==
=== Übersicht ===

{| border="1" class="wikitable sortable" id="softcores"
|-
!Name
!optimiert für
!Quellcode
!Programmierung
!Toolchain
!Leistung
!Lizenz/Preis
!Weblink
|-
|NEO430
|entfällt
|Ja, VHDL
|asm, C, C++, ..
|MSPGCC (Windows, Linux/Cygwin)
|5-15 cycles per instruction
|LGPL
|[http://www.opencores.org/project,neo430 neo430 @ OpenCores.org]
|-
|OpenMSP430
|FPGA & ASIC
|Ja, Verilog
|asm, C, C++, ..
|MSPGCC (Windows, Linux/Cygwin)
|1-6 cycles per instruction
|BSD
|[http://opencores.org/project,openmsp430 OpenMSP430 @ OpenCores.org]
|-
|TG68
|
|Ja, VHDL
|asm, C, C++, ..
|GCC, (68k-compatible)
|
|LGPL
|[http://opencores.org/project,tg68 tg68 @ OpenCores.org]
|-
|UCore
|Altera
|VHDL
|Assembler
|Assembler, Emulator
|single cycle per instruction
|
|Artikel [http://www.mikrocontroller.net/articles/16/32Bit_Computer/Konsole] HP [http://www.goldmomo.de]
|}

=== NEO430 ===
* MSP430-ISA-kompatibel (verwendet MSPGCC Compiler), 16-bit RISC
* UART/SPI/Wishbone Bootloader
* Verschiedene Beispielprogramme
* Hardware (anpassbar): Timer, SPI & UART, Parallel IO, Wishbone Interface, ...
* Leistung: 5..15 Taktzyklen pro Instruktion, ~145MHz (Altera Cyclone IV EP4CE22F17C6N)
* Recourcenbedarf: ~1400 LE's auf Altera Cyclone IV
* Datenblatt (auf opencores.org): [http://opencores.org/websvn,filedetails?repname=neo430&path=%2Fneo430%2Ftrunk%2Fdoc%2FNEO430.pdf NEO430.pdf]

=== OpenMSP430 ===
* MSP430 kompatibel (verwendet MSPGCC Compiler), 16-bit RISC
* FPGA und ASIC erprobt
* Hardware (anpassbar): 6x16 Hardware Multiplier, Watchdog, GPIO, TimerA, generic templates
* two-wire Serial Debug Interface mit Unterstützung des MSPGCC GNU Debugger (GDB)
* Leistung: 1..6 Taktzyklen pro Instruktion
* Recourcenbedarf: Xilinx: 1650 LUTs / Altera: 1550 LEs / ASIC: 8k gate
* Datenblatt (auf opencores.org): [http://opencores.org/websvn,filedetails?repname=openmsp430&path=%2Fopenmsp430%2Ftrunk%2Fdoc%2FopenMSP430.pdf openMSP430.pdf]

=== TG68 ===
* 68000 kompatible
* Recourcenbedarf: ~2700 Xilinx Slices, ~4000 LC's auf Altera Cyclone II

== 32 Bit Soft Cores ==
=== Übersicht ===

{| border="1" class="wikitable sortable" id="softcores"
|-
!Name
!optimiert für
!Quellcode
!Programmierung
!Toolchain
!Leistung
!Lizenz/Preis
!Weblink
|-
|HiCoVec Vektorprozessor
|Xilinx Spartan3A
|ja, VHDL
|asm, C
|GCC, HiCoVec Assembler
|Flexible Vektoreinheit
|GPL
|[http://ees.informatik.hs-augsburg.de/hicovec HS-Augsburg]
|-
|LatticeMico32
|Lattice, siehe aber soc-lm32
|ja, Verilog
|asm, C, C++
|GCC, MSB
|
|open IP-core
|[http://www.latticesemi.com/products/intellectualproperty/ipcores/mico32/ Lattice]
|-
|Leon
|
|Ja, VHDL
|asm, C, C++
|GCC (SPARC-compatible)
|
|GPL
|[http://www.gaisler.com Gaisler Research]
|-
|MicroBlaze
|Xilinx
|Nein
|asm, C, C++
|GCC, EDK
|
|EDK $500/Jahr
|[http://www.xilinx.com/products/design_resources/proc_central/microblaze.htm Xilinx] [http://de.wikipedia.org/wiki/MicroBlaze MicroBlaze bei Wikipedia]
|-
|MicroBlaze MCS
|Xilinx
|Nein
|asm, C, C++
|GCC, SDK
|
|kostenfrei
|[http://www.xilinx.com/tools/mb_mcs.htm Xilinx]
|-
|NIOS II
|Altera
|Nein
|asm, C, C++
|GCC, SOPC, EDS
|
|mit Nios II Eval-Kit ab $400, oder $3000 - Nios II/e core free (12/2009)
|[http://www.altera.com/nios2 Altera]
|-
|OpenRISC
|
|Ja, Verilog
|asm, C, C++, ..
|GCC
|
|
|[http://www.opencores.org/projects.cgi/web/or1k/overview OpenCores]
|-
|Plasma
|
|Ja, VHDL
|asm, C, C++
|GCC (MIPS-compatible)
|
|GPL
|[http://www.opencores.org/ OpenCores.org]
|-
|MAIS
|
|Ja, VHDL
|asm, C, C++
|GCC
|
|Creative Commons CC BY-NC 3.0 with exception commercial applicants have to pay a licence fee
|[http://www.dossmatik.de/mais-cpu.html]
|-
|Propeller 2
|
|Ja, VHDL
|C,
|Parallax IDE
|
|GPL3
|[http://www.parallax.com]
|-
|Zylin CPU (ZPU)
|
|Ja, VHDL
|asm, C, C++
|GCC
|
|FreeBSD/GPL
|[http://opensource.zylin.com/zpu.htm Zylin.com]
|}

Einen ersten Eindruck von derLeistungsfähigkeit der 32 Bit SoftCores gibt z. B.
die [http://www.gaisler.com/doc/Evaluation_of_synthesizable_CPU_cores.pdf Master-Arbeit "Evaluation of synthesizable CPU cores"] aus dem Jahr 2004.
Diese Vergleicht den Leon 2, MicroBlaze und OpenRISC 1200 miteinander.

=== Lattice Mico32 und soc-lm32 ===

Mico32 ist eine 32 Bit pipelined RISC CPU. Die steht unter einer OpenSource
Lizenz und liegt komplett im Verilog Quelltext vor. Sowohl die CPU Architektur als auch der Resourcenbedarf ist vergleichbar mit dem MicroBlaze von Xilinx, ist allerdings eine eigenständige Entwicklung von Lattice.

* Recourcenbedarf: ~1600 Slices (Lattice/Xilinx)
* Erreicht ca. 80-116MHz auf ECP2 und XP2 Devices von Lattice und ca. 100 MHz auf Spartan3 Generation FPGAs,
* Konfigurierbare D- und I-Caches (aus BRAM oder Distributed RAM)
* 2 Wishbone-Interfaces: Für Daten-Load&Store und Instruction-Fetch
* Systembuilder mit automatisch erstellten Wishbone Arbitern
* Keine Begrenzung in Anzahl der benutzten Wishbone Busse
* Kompletter GNU Toolchain aus binutils, gcc und gdb
* Eclipse Entwicklungsumgebung, gemanagte C und C++ Entwicklung
* Automatische Treibererstellung durch den Systembuilder
* In Lattice Bausteinen gleichzeitige Benutzung des Logikanalyzers und Debuggers

Neben dem Original, das man von [http://www.latticesemi.com/products/intellectualproperty/ipcores/mico32/index.cfm Lattice] herunterladen kann, und dessen Toolchain erstmal auf Windows mit Lattice FPGAs ausgelegt ist, gibt es noch [http://www.das-labor.org/wiki/Soc-lm32 soc-lm32]. soc-lm32 ist eine Portierung auf Altera und Xilinx Bausteine und benutzt einen Makefile-basierten Workflow.

Eine von Lattice in Auftrag gegebene Portierung von uC-Linux ist verfügbar
(http://www.theobroma-systems.com/mico32/).

Nachteile: bis jetzt gibt es keine Version mit FPU (kann über Wishbone als Peripherie angeflanscht werden) oder MMU.

=== Leon ===

Dieser Prozessorkern ist komplett SPARC V8 kompatibel -- beliebige SPARC Compiler können verwendet werden (z. B. bcc, ). Neben dem Kern selbst steht auch eine breite Auswahl an Peripherie in Form von VHDL-Komponenten zur Vefügung. Als On-Chip Interconnect kommt AMBA (AHB + APB) zum Einsatz.

* Recourcenbedarf: ~4000 Xilinx Slices, 10 BRAMs (minimal-konfiguration)
* Erreicht ca. 50 MHz auf Spartan3 Generation FPGAs

=== MicroBlaze & Nachbauten ===

'''MicroBlaze''' ist ein Core der von der Firma Xilinx speziell für deren FPGAs zur Verfügung gestellt wird. Er ist u.a. mit der XPS-Software instanziier- und konfigurierbar. Die Softwareentwicklung erfolgt in C mittels der Software EDK.

Microblaze ist im Gegensatz zu PicoBlaze kommerziell und erfordert eine Lizenz. Allerdings hat Xilinx beginnend mit der ISE 13.4. einen leichtgewichtigen Microblaze - MicroBlaze MCS - veröffentlicht der kostenfrei für alle Xilinx FPGA's (mglw außer
den prähistorischen Relikten wie Spartan XL?!) verwendbar ist:

http://www.xilinx.com/tools/mb_mcs.htm

Dieser wird mit dem CoreGen statt dem EDK generiert, zum programmieren (C/C++) stellt Xilinx ein SDK bereit.

=== Propeller ===
Komplettes Open Source Paket aus SoftCore, IDE und Debugging des Propeller 2 uCs:
http://de.wikipedia.org/wiki/Parallax_Propeller
http://www.parallax.com/microcontrollers/propeller-1-open-source

=== ZPU ===
http://www.mikrocontroller.net/articles/ZPU:_Softcore_Implementierung_auf_Spartan-3_FPGA

[[Category:FPGA und Co]]

Multitasking

2014-10-27T13:03:05Z

134.169.116.105: /* System ohne real-time OS und Entwicklung in ASM */ Typo

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

== 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äemptiv.

== 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 [http://de.wikipedia.org/wiki/Kooperation 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.

=== 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

<syntaxhighlight lang="c">
while(1) {
PORTD ^= (1<<PD0);
_delay_ms(500);
}
</syntaxhighlight>

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.

==== 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.

<syntaxhighlight lang="c">
/*

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();
}
}
</syntaxhighlight>

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

* 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.

==== 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!

<syntaxhighlight lang="c">
/*

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++;
}

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();
_delay_ms(1); // 1 ms warten
}
}
</syntaxhighlight>

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. Das erreicht man meist am besten mit einer [[statemachine |State machine]].
*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

==== Verbesserter Ansatz mit Timer ====

Zum Abschluss noch einmal die verbesserte Version mit Timer. Diese hat mehrere Vorteile.

* Das Zeitraster der Hauptschleife ist exakt, unabhängig von der Laufzeit der Aufgaben, weil der Timer unabhängig eine feste Interruptfrequenz generiert. Im vorherigen Beispiel war das Zeitraster die Summe aus Laufzeit aller Funktionen/Tasks und dem _delay_ms(1).
* CPU-Rechenleistung wird zu 100% in der Abarbeitung der Task verwendet und nicht für nutzlose Warteschleifen verschwendet.
* Es kann leicht im realen System geprüft werden, ob die Laufzeit der Tasks klein genug ist, um den Anforderungen des Timers zu genügen.

Diese Überprüfung kann an zwei Stellen durchgeführt werden.

* Am Ende der Hauptschleife nach Abarbeitung aller Ausgaben. Wenn hier die Variable flag_1ms schon wieder aktiv ist, dauerte die Abarbeitung länger als 1ms. Wenn man ein sehr strenges Timing sicherstellen möchte, ist das ein Fehler, der erkannt und signalisiert werden kann.
* In der ISR. Wenn hier die Variable immer noch aktiv ist, wurde sie von der Hauptschleife noch nicht erkannt und zurück gesetzt. Das ist definitiv ein Fehler, denn jetzt würde ohne Fehlererkennung ein Timerdurchlauf von der Hauptschleife verschluckt werden. Diese Prüfung ist etwas nachgiebiger, weil zwischenzeitlich ein Durchlauf der Hauptschleife mehr als 1ms, jedoch nicht länger als 2ms dauern darf. Siehe auch den Abschnitt [[Interrupt#Zeitverhalten_eines_Timerinterrupts]]. Sinnvollerweise nutzt man nur eine der beiden Prüfungen, nicht beide zusammen.

<syntaxhighlight lang="c">
/*

Multitasking Demo, dritter Versuch

ATmega32 @ 3,6468 MHz

LED + 1KOhm Vorwiderstand an PB0 und PB1
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"
#include "avr/interrupt.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++;
}

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;
}
}

volatile uint8_t flag_1ms;

int main(void) {
int8_t taste;

// IOs initialisieren

PORTA = 1; // Pull Up für PA0
DDRB = 3; // PB0/1 sind Ausgang

// UART initialisieren

UBRRH = UBRR_VAL >> 8;
UBRRL = UBRR_VAL & 0xFF;
UCSRB = (1<<RXEN) | (1<<TXEN);

// Timer 0 initialisieren, CTC, Presacler 64

TCCR0 = (1<<WGM01) | (1<<CS01) | (1<<CS00);
OCR0 = 56; // 1ms
TIMSK |= (1<<OCIE0);

// Interrupts global freigeben

sei();

// Endlose Hauptschleife

while (1) {
if (flag_1ms) {
flag_1ms=0;
taste = taste_lesen();
led_blinken(taste);
uart_lesen();
if (flag_1ms) {
// Laufzeit der Tasks >1ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
}

}
}

// Interruptserviceroutine für Timer 0
// hier 1ms

ISR(TIMER0_COMP_vect) {
if (flag_1ms) {
// Laufzeit der Tasks >2ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
flag_1ms = 1;
}

</syntaxhighlight>

==== 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.

===== 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.

===== 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"

===== 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.

===== 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:

<syntaxhighlight lang="c">
#include "ACF.h"

int main(int argc, char** argv)
{
ACF_init();
ACF_loop();
return 0; // we will never arrive here
}
</syntaxhighlight>

===== 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.
[http://www.mikrocontroller.net/attachment/74409/ablauf.png Sequenzdiagramm]

== 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" einen Semaphor für "Speicher reservieren". Dieser Semaphor wird erst wieder aufgehoben, sobald Prozess A den Speicher für sich reserviert hat. Wenn der Prozess B zwischendurch gestartet wird und ebenfalls versucht den Semaphor zu setzen, wird er solange warten müssen, bis Prozess A den Semaphor 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 eines Semaphors 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 Semaphore etc.
* nicht streng deterministisch, somit kann kein festes Timing garantiert werden
* nicht explizit debug- und prüfbar, da die Prozesse nicht fest gekoppelt sind

== 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.

== Umsetzung auf Prozessoren ==
Unabhängig davon, ob Multitasking oder -threading auf einem Prozessor konkret unterstützt wird, lässt es sich immer in Form von Software realisieren. Dies wird in modernen Systemen durch das OS geleistet, das standardisierte Funktionen und Strukturen zur Verfügung stellt. Besonders C++ bietet ein stark abstrahiertes Programmiermodell und Methoden-Set an, um effektiv untereinander kompatible Programmmodule erstellen zu können. Nutzt man diese nicht, wie z.B. bei der Programmierung in C, müssen Strukturen manuell erzeugt und gehandhabt werden, was aufwändiger ist, aber auch geringeren overhead bewirkt. Das Programm ist dann fast immer erheblich kleiner, in den meisten Fällen strukturell einfacher, bezüglich komplizierter Änderungen jedoch auch unflexibler und träger.

Bei Mikrocontrollern findet man je nach Komplexität und Struktur der Appliation praktisch alle denkbaren Kombinationen:

=== System mit real-time OS und Entwicklung in C++ ===
* Programmentwicklung stark an abstrakte Interfaces und Standards gebunden
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb gleicher OS-Landschaft gut portierbar
* Sehr geringe Abhängigkeit vom Prozessortyp
* Multitasking muss über OS-Schicht ausprogrammiert werden
* Multithreading muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist niedrig durch relativ hohen Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist niedrig durch sehr viel Arbeit an Formalismen
* Planungsaufwand ist noch überschaubar
* Planungseffizienz ist relaiv hoch durch viele Standards
* Erweiterung um komplexe Module einfach möglich, Timing regelt sich selber

=== System mit real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und weniger an Standards
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb aber auch ausserhalb gleicher OS-Landschaft gut portierbar
* Geringe Abhängig von dem Prozessortyp
* Multitasking muss über OS-Schicht und eigene Strukturen programmiert werden
* Multithreading muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist höher durch geringeren Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist höher durch weniger Arbeit mit Formalien
* Planungsaufwand ist etwas höher, je nach Applikation
* Planungseffizienz ist relaiv niedriger durch weniger Standards
* Erweiterung mit akzeptablem Aufwand möglich, Timing muss beachtet werden

=== System ohne real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und kaum an Standards gebunden
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur ausserhalb von OS-Landschaft portierbar, dafür prinziepiell sehr gut
* Stärkere Abhängig von dem Prozessortyp, kann die Portierbarkeit einschränken
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithreading muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz kann sehr hoch sein, ist aber stark von der Progr. abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark Applikations abhängig, gfs sehr viel grösser
* Planungseffizienz ist gering, da RT Konzept selber optmiert werden muss
* Erweiterung nur möglich, wenn Timing weitestgehend überarbeitet wird

=== System ohne real-time OS und Entwicklung in ASM ===
* Programmentw. nur an physische Interfaces gebunden und frei von Standards
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur innerhalb der Prozessorlandschaft gut portierbar
* Volle Abhängig vom Prozessortyp, Portierbarkeit auf andere aufwändig
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithreading muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz sehr hoch, jedoch stark von Programmierung abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark applikationsabhängig, ggfs. sehr viel grösser
* Planungseffizienz sehr gering, RT Konzept nur für einfache System machbar
* Erweiterung nur möglich, wenn Timing komplett überarbeitet wird

== Weblinks ==

* [http://de.wikipedia.org/wiki/Pr%E4emptives_Multitasking Präemptives Multitasking] bei [http://de.wikipedia.org Wikipedia]
* [http://www.femtoos.org/ Femto OS], ein ultrakompaktes Mulitaskingbetriebssystem für kleine Mikrocontroller
*[http://www.freertos.org/ FreeRTOS], ein freies Echtzeitbetriebssystem für Mikrocontroller
* [http://w3.ualg.pt/~rmarcel/Get%20by%20Without%20an%20RTOS.pdf Get by Without an RTOS] Ein schönes Beispiel wie man ohne ein RTOS auch Multitasking hinbekommt.
* [[TNKernel]], freier Multitasking-Kernel.
* [http://embeddedgurus.com/state-space/2010/04/i-hate-rtoses/ i-hate-rtoses] Blog zum Thema RTOS

[[Kategorie:Betriebssysteme]]

Multitasking

2014-10-27T13:02:43Z

134.169.116.105: /* System ohne real-time OS und Entwicklung in C */ Typo

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

== 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äemptiv.

== 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 [http://de.wikipedia.org/wiki/Kooperation 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.

=== 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

<syntaxhighlight lang="c">
while(1) {
PORTD ^= (1<<PD0);
_delay_ms(500);
}
</syntaxhighlight>

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.

==== 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.

<syntaxhighlight lang="c">
/*

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();
}
}
</syntaxhighlight>

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

* 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.

==== 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!

<syntaxhighlight lang="c">
/*

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++;
}

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();
_delay_ms(1); // 1 ms warten
}
}
</syntaxhighlight>

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. Das erreicht man meist am besten mit einer [[statemachine |State machine]].
*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

==== Verbesserter Ansatz mit Timer ====

Zum Abschluss noch einmal die verbesserte Version mit Timer. Diese hat mehrere Vorteile.

* Das Zeitraster der Hauptschleife ist exakt, unabhängig von der Laufzeit der Aufgaben, weil der Timer unabhängig eine feste Interruptfrequenz generiert. Im vorherigen Beispiel war das Zeitraster die Summe aus Laufzeit aller Funktionen/Tasks und dem _delay_ms(1).
* CPU-Rechenleistung wird zu 100% in der Abarbeitung der Task verwendet und nicht für nutzlose Warteschleifen verschwendet.
* Es kann leicht im realen System geprüft werden, ob die Laufzeit der Tasks klein genug ist, um den Anforderungen des Timers zu genügen.

Diese Überprüfung kann an zwei Stellen durchgeführt werden.

* Am Ende der Hauptschleife nach Abarbeitung aller Ausgaben. Wenn hier die Variable flag_1ms schon wieder aktiv ist, dauerte die Abarbeitung länger als 1ms. Wenn man ein sehr strenges Timing sicherstellen möchte, ist das ein Fehler, der erkannt und signalisiert werden kann.
* In der ISR. Wenn hier die Variable immer noch aktiv ist, wurde sie von der Hauptschleife noch nicht erkannt und zurück gesetzt. Das ist definitiv ein Fehler, denn jetzt würde ohne Fehlererkennung ein Timerdurchlauf von der Hauptschleife verschluckt werden. Diese Prüfung ist etwas nachgiebiger, weil zwischenzeitlich ein Durchlauf der Hauptschleife mehr als 1ms, jedoch nicht länger als 2ms dauern darf. Siehe auch den Abschnitt [[Interrupt#Zeitverhalten_eines_Timerinterrupts]]. Sinnvollerweise nutzt man nur eine der beiden Prüfungen, nicht beide zusammen.

<syntaxhighlight lang="c">
/*

Multitasking Demo, dritter Versuch

ATmega32 @ 3,6468 MHz

LED + 1KOhm Vorwiderstand an PB0 und PB1
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"
#include "avr/interrupt.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++;
}

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;
}
}

volatile uint8_t flag_1ms;

int main(void) {
int8_t taste;

// IOs initialisieren

PORTA = 1; // Pull Up für PA0
DDRB = 3; // PB0/1 sind Ausgang

// UART initialisieren

UBRRH = UBRR_VAL >> 8;
UBRRL = UBRR_VAL & 0xFF;
UCSRB = (1<<RXEN) | (1<<TXEN);

// Timer 0 initialisieren, CTC, Presacler 64

TCCR0 = (1<<WGM01) | (1<<CS01) | (1<<CS00);
OCR0 = 56; // 1ms
TIMSK |= (1<<OCIE0);

// Interrupts global freigeben

sei();

// Endlose Hauptschleife

while (1) {
if (flag_1ms) {
flag_1ms=0;
taste = taste_lesen();
led_blinken(taste);
uart_lesen();
if (flag_1ms) {
// Laufzeit der Tasks >1ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
}

}
}

// Interruptserviceroutine für Timer 0
// hier 1ms

ISR(TIMER0_COMP_vect) {
if (flag_1ms) {
// Laufzeit der Tasks >2ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
flag_1ms = 1;
}

</syntaxhighlight>

==== 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.

===== 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.

===== 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"

===== 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.

===== 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:

<syntaxhighlight lang="c">
#include "ACF.h"

int main(int argc, char** argv)
{
ACF_init();
ACF_loop();
return 0; // we will never arrive here
}
</syntaxhighlight>

===== 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.
[http://www.mikrocontroller.net/attachment/74409/ablauf.png Sequenzdiagramm]

== 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" einen Semaphor für "Speicher reservieren". Dieser Semaphor wird erst wieder aufgehoben, sobald Prozess A den Speicher für sich reserviert hat. Wenn der Prozess B zwischendurch gestartet wird und ebenfalls versucht den Semaphor zu setzen, wird er solange warten müssen, bis Prozess A den Semaphor 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 eines Semaphors 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 Semaphore etc.
* nicht streng deterministisch, somit kann kein festes Timing garantiert werden
* nicht explizit debug- und prüfbar, da die Prozesse nicht fest gekoppelt sind

== 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.

== Umsetzung auf Prozessoren ==
Unabhängig davon, ob Multitasking oder -threading auf einem Prozessor konkret unterstützt wird, lässt es sich immer in Form von Software realisieren. Dies wird in modernen Systemen durch das OS geleistet, das standardisierte Funktionen und Strukturen zur Verfügung stellt. Besonders C++ bietet ein stark abstrahiertes Programmiermodell und Methoden-Set an, um effektiv untereinander kompatible Programmmodule erstellen zu können. Nutzt man diese nicht, wie z.B. bei der Programmierung in C, müssen Strukturen manuell erzeugt und gehandhabt werden, was aufwändiger ist, aber auch geringeren overhead bewirkt. Das Programm ist dann fast immer erheblich kleiner, in den meisten Fällen strukturell einfacher, bezüglich komplizierter Änderungen jedoch auch unflexibler und träger.

Bei Mikrocontrollern findet man je nach Komplexität und Struktur der Appliation praktisch alle denkbaren Kombinationen:

=== System mit real-time OS und Entwicklung in C++ ===
* Programmentwicklung stark an abstrakte Interfaces und Standards gebunden
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb gleicher OS-Landschaft gut portierbar
* Sehr geringe Abhängigkeit vom Prozessortyp
* Multitasking muss über OS-Schicht ausprogrammiert werden
* Multithreading muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist niedrig durch relativ hohen Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist niedrig durch sehr viel Arbeit an Formalismen
* Planungsaufwand ist noch überschaubar
* Planungseffizienz ist relaiv hoch durch viele Standards
* Erweiterung um komplexe Module einfach möglich, Timing regelt sich selber

=== System mit real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und weniger an Standards
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb aber auch ausserhalb gleicher OS-Landschaft gut portierbar
* Geringe Abhängig von dem Prozessortyp
* Multitasking muss über OS-Schicht und eigene Strukturen programmiert werden
* Multithreading muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist höher durch geringeren Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist höher durch weniger Arbeit mit Formalien
* Planungsaufwand ist etwas höher, je nach Applikation
* Planungseffizienz ist relaiv niedriger durch weniger Standards
* Erweiterung mit akzeptablem Aufwand möglich, Timing muss beachtet werden

=== System ohne real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und kaum an Standards gebunden
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur ausserhalb von OS-Landschaft portierbar, dafür prinziepiell sehr gut
* Stärkere Abhängig von dem Prozessortyp, kann die Portierbarkeit einschränken
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithreading muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz kann sehr hoch sein, ist aber stark von der Progr. abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark Applikations abhängig, gfs sehr viel grösser
* Planungseffizienz ist gering, da RT Konzept selber optmiert werden muss
* Erweiterung nur möglich, wenn Timing weitestgehend überarbeitet wird

=== System ohne real-time OS und Entwicklung in ASM ===
* Programmentw. nur an physische Interfaces gebunden und frei von Standards
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur innerhalb der Prozessorlandschaft gut portierbar
* Volle Abhängig vom Prozessortyp, Portierbarkeit auf andere aufwändig
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithredding muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz sehr hoch, jedoch stark von Programmierung abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark applikationsabhängig, ggfs. sehr viel grösser
* Planungseffizienz sehr gering, RT Konzept nur für einfache System machbar
* Erweiterung nur möglich, wenn Timing komplett überarbeitet wird

== Weblinks ==

* [http://de.wikipedia.org/wiki/Pr%E4emptives_Multitasking Präemptives Multitasking] bei [http://de.wikipedia.org Wikipedia]
* [http://www.femtoos.org/ Femto OS], ein ultrakompaktes Mulitaskingbetriebssystem für kleine Mikrocontroller
*[http://www.freertos.org/ FreeRTOS], ein freies Echtzeitbetriebssystem für Mikrocontroller
* [http://w3.ualg.pt/~rmarcel/Get%20by%20Without%20an%20RTOS.pdf Get by Without an RTOS] Ein schönes Beispiel wie man ohne ein RTOS auch Multitasking hinbekommt.
* [[TNKernel]], freier Multitasking-Kernel.
* [http://embeddedgurus.com/state-space/2010/04/i-hate-rtoses/ i-hate-rtoses] Blog zum Thema RTOS

[[Kategorie:Betriebssysteme]]

Multitasking

2014-10-27T13:02:00Z

134.169.116.105: /* System mit real-time OS und Entwicklung in C */ Typo

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

== 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äemptiv.

== 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 [http://de.wikipedia.org/wiki/Kooperation 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.

=== 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

<syntaxhighlight lang="c">
while(1) {
PORTD ^= (1<<PD0);
_delay_ms(500);
}
</syntaxhighlight>

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.

==== 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.

<syntaxhighlight lang="c">
/*

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();
}
}
</syntaxhighlight>

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

* 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.

==== 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!

<syntaxhighlight lang="c">
/*

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++;
}

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();
_delay_ms(1); // 1 ms warten
}
}
</syntaxhighlight>

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. Das erreicht man meist am besten mit einer [[statemachine |State machine]].
*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

==== Verbesserter Ansatz mit Timer ====

Zum Abschluss noch einmal die verbesserte Version mit Timer. Diese hat mehrere Vorteile.

* Das Zeitraster der Hauptschleife ist exakt, unabhängig von der Laufzeit der Aufgaben, weil der Timer unabhängig eine feste Interruptfrequenz generiert. Im vorherigen Beispiel war das Zeitraster die Summe aus Laufzeit aller Funktionen/Tasks und dem _delay_ms(1).
* CPU-Rechenleistung wird zu 100% in der Abarbeitung der Task verwendet und nicht für nutzlose Warteschleifen verschwendet.
* Es kann leicht im realen System geprüft werden, ob die Laufzeit der Tasks klein genug ist, um den Anforderungen des Timers zu genügen.

Diese Überprüfung kann an zwei Stellen durchgeführt werden.

* Am Ende der Hauptschleife nach Abarbeitung aller Ausgaben. Wenn hier die Variable flag_1ms schon wieder aktiv ist, dauerte die Abarbeitung länger als 1ms. Wenn man ein sehr strenges Timing sicherstellen möchte, ist das ein Fehler, der erkannt und signalisiert werden kann.
* In der ISR. Wenn hier die Variable immer noch aktiv ist, wurde sie von der Hauptschleife noch nicht erkannt und zurück gesetzt. Das ist definitiv ein Fehler, denn jetzt würde ohne Fehlererkennung ein Timerdurchlauf von der Hauptschleife verschluckt werden. Diese Prüfung ist etwas nachgiebiger, weil zwischenzeitlich ein Durchlauf der Hauptschleife mehr als 1ms, jedoch nicht länger als 2ms dauern darf. Siehe auch den Abschnitt [[Interrupt#Zeitverhalten_eines_Timerinterrupts]]. Sinnvollerweise nutzt man nur eine der beiden Prüfungen, nicht beide zusammen.

<syntaxhighlight lang="c">
/*

Multitasking Demo, dritter Versuch

ATmega32 @ 3,6468 MHz

LED + 1KOhm Vorwiderstand an PB0 und PB1
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"
#include "avr/interrupt.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++;
}

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;
}
}

volatile uint8_t flag_1ms;

int main(void) {
int8_t taste;

// IOs initialisieren

PORTA = 1; // Pull Up für PA0
DDRB = 3; // PB0/1 sind Ausgang

// UART initialisieren

UBRRH = UBRR_VAL >> 8;
UBRRL = UBRR_VAL & 0xFF;
UCSRB = (1<<RXEN) | (1<<TXEN);

// Timer 0 initialisieren, CTC, Presacler 64

TCCR0 = (1<<WGM01) | (1<<CS01) | (1<<CS00);
OCR0 = 56; // 1ms
TIMSK |= (1<<OCIE0);

// Interrupts global freigeben

sei();

// Endlose Hauptschleife

while (1) {
if (flag_1ms) {
flag_1ms=0;
taste = taste_lesen();
led_blinken(taste);
uart_lesen();
if (flag_1ms) {
// Laufzeit der Tasks >1ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
}

}
}

// Interruptserviceroutine für Timer 0
// hier 1ms

ISR(TIMER0_COMP_vect) {
if (flag_1ms) {
// Laufzeit der Tasks >2ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
flag_1ms = 1;
}

</syntaxhighlight>

==== 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.

===== 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.

===== 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"

===== 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.

===== 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:

<syntaxhighlight lang="c">
#include "ACF.h"

int main(int argc, char** argv)
{
ACF_init();
ACF_loop();
return 0; // we will never arrive here
}
</syntaxhighlight>

===== 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.
[http://www.mikrocontroller.net/attachment/74409/ablauf.png Sequenzdiagramm]

== 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" einen Semaphor für "Speicher reservieren". Dieser Semaphor wird erst wieder aufgehoben, sobald Prozess A den Speicher für sich reserviert hat. Wenn der Prozess B zwischendurch gestartet wird und ebenfalls versucht den Semaphor zu setzen, wird er solange warten müssen, bis Prozess A den Semaphor 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 eines Semaphors 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 Semaphore etc.
* nicht streng deterministisch, somit kann kein festes Timing garantiert werden
* nicht explizit debug- und prüfbar, da die Prozesse nicht fest gekoppelt sind

== 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.

== Umsetzung auf Prozessoren ==
Unabhängig davon, ob Multitasking oder -threading auf einem Prozessor konkret unterstützt wird, lässt es sich immer in Form von Software realisieren. Dies wird in modernen Systemen durch das OS geleistet, das standardisierte Funktionen und Strukturen zur Verfügung stellt. Besonders C++ bietet ein stark abstrahiertes Programmiermodell und Methoden-Set an, um effektiv untereinander kompatible Programmmodule erstellen zu können. Nutzt man diese nicht, wie z.B. bei der Programmierung in C, müssen Strukturen manuell erzeugt und gehandhabt werden, was aufwändiger ist, aber auch geringeren overhead bewirkt. Das Programm ist dann fast immer erheblich kleiner, in den meisten Fällen strukturell einfacher, bezüglich komplizierter Änderungen jedoch auch unflexibler und träger.

Bei Mikrocontrollern findet man je nach Komplexität und Struktur der Appliation praktisch alle denkbaren Kombinationen:

=== System mit real-time OS und Entwicklung in C++ ===
* Programmentwicklung stark an abstrakte Interfaces und Standards gebunden
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb gleicher OS-Landschaft gut portierbar
* Sehr geringe Abhängigkeit vom Prozessortyp
* Multitasking muss über OS-Schicht ausprogrammiert werden
* Multithreading muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist niedrig durch relativ hohen Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist niedrig durch sehr viel Arbeit an Formalismen
* Planungsaufwand ist noch überschaubar
* Planungseffizienz ist relaiv hoch durch viele Standards
* Erweiterung um komplexe Module einfach möglich, Timing regelt sich selber

=== System mit real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und weniger an Standards
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb aber auch ausserhalb gleicher OS-Landschaft gut portierbar
* Geringe Abhängig von dem Prozessortyp
* Multitasking muss über OS-Schicht und eigene Strukturen programmiert werden
* Multithreading muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist höher durch geringeren Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist höher durch weniger Arbeit mit Formalien
* Planungsaufwand ist etwas höher, je nach Applikation
* Planungseffizienz ist relaiv niedriger durch weniger Standards
* Erweiterung mit akzeptablem Aufwand möglich, Timing muss beachtet werden

=== System ohne real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und kaum an Standards gebunden
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur ausserhalb von OS-Landschaft portierbar, dafür prinziepiell sehr gut
* Stärkere Abhängig von dem Prozessortyp, kann die Portierbarkeit einschränken
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithredding muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz kann sehr hoch sein, ist aber stark von der Progr. abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark Applikations abhängig, gfs sehr viel grösser
* Planungseffizienz ist gering, da RT Konzept selber optmiert werden muss
* Erweiterung nur möglich, wenn Timing weitestgehend überarbeitet wird

=== System ohne real-time OS und Entwicklung in ASM ===
* Programmentw. nur an physische Interfaces gebunden und frei von Standards
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur innerhalb der Prozessorlandschaft gut portierbar
* Volle Abhängig vom Prozessortyp, Portierbarkeit auf andere aufwändig
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithredding muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz sehr hoch, jedoch stark von Programmierung abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark applikationsabhängig, ggfs. sehr viel grösser
* Planungseffizienz sehr gering, RT Konzept nur für einfache System machbar
* Erweiterung nur möglich, wenn Timing komplett überarbeitet wird

== Weblinks ==

* [http://de.wikipedia.org/wiki/Pr%E4emptives_Multitasking Präemptives Multitasking] bei [http://de.wikipedia.org Wikipedia]
* [http://www.femtoos.org/ Femto OS], ein ultrakompaktes Mulitaskingbetriebssystem für kleine Mikrocontroller
*[http://www.freertos.org/ FreeRTOS], ein freies Echtzeitbetriebssystem für Mikrocontroller
* [http://w3.ualg.pt/~rmarcel/Get%20by%20Without%20an%20RTOS.pdf Get by Without an RTOS] Ein schönes Beispiel wie man ohne ein RTOS auch Multitasking hinbekommt.
* [[TNKernel]], freier Multitasking-Kernel.
* [http://embeddedgurus.com/state-space/2010/04/i-hate-rtoses/ i-hate-rtoses] Blog zum Thema RTOS

[[Kategorie:Betriebssysteme]]

Multitasking

2014-10-27T13:01:21Z

134.169.116.105: /* System mit real-time OS und Entwicklung in C++ */ Typo

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

== 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äemptiv.

== 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 [http://de.wikipedia.org/wiki/Kooperation 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.

=== 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

<syntaxhighlight lang="c">
while(1) {
PORTD ^= (1<<PD0);
_delay_ms(500);
}
</syntaxhighlight>

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.

==== 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.

<syntaxhighlight lang="c">
/*

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();
}
}
</syntaxhighlight>

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

* 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.

==== 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!

<syntaxhighlight lang="c">
/*

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++;
}

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();
_delay_ms(1); // 1 ms warten
}
}
</syntaxhighlight>

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. Das erreicht man meist am besten mit einer [[statemachine |State machine]].
*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

==== Verbesserter Ansatz mit Timer ====

Zum Abschluss noch einmal die verbesserte Version mit Timer. Diese hat mehrere Vorteile.

* Das Zeitraster der Hauptschleife ist exakt, unabhängig von der Laufzeit der Aufgaben, weil der Timer unabhängig eine feste Interruptfrequenz generiert. Im vorherigen Beispiel war das Zeitraster die Summe aus Laufzeit aller Funktionen/Tasks und dem _delay_ms(1).
* CPU-Rechenleistung wird zu 100% in der Abarbeitung der Task verwendet und nicht für nutzlose Warteschleifen verschwendet.
* Es kann leicht im realen System geprüft werden, ob die Laufzeit der Tasks klein genug ist, um den Anforderungen des Timers zu genügen.

Diese Überprüfung kann an zwei Stellen durchgeführt werden.

* Am Ende der Hauptschleife nach Abarbeitung aller Ausgaben. Wenn hier die Variable flag_1ms schon wieder aktiv ist, dauerte die Abarbeitung länger als 1ms. Wenn man ein sehr strenges Timing sicherstellen möchte, ist das ein Fehler, der erkannt und signalisiert werden kann.
* In der ISR. Wenn hier die Variable immer noch aktiv ist, wurde sie von der Hauptschleife noch nicht erkannt und zurück gesetzt. Das ist definitiv ein Fehler, denn jetzt würde ohne Fehlererkennung ein Timerdurchlauf von der Hauptschleife verschluckt werden. Diese Prüfung ist etwas nachgiebiger, weil zwischenzeitlich ein Durchlauf der Hauptschleife mehr als 1ms, jedoch nicht länger als 2ms dauern darf. Siehe auch den Abschnitt [[Interrupt#Zeitverhalten_eines_Timerinterrupts]]. Sinnvollerweise nutzt man nur eine der beiden Prüfungen, nicht beide zusammen.

<syntaxhighlight lang="c">
/*

Multitasking Demo, dritter Versuch

ATmega32 @ 3,6468 MHz

LED + 1KOhm Vorwiderstand an PB0 und PB1
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"
#include "avr/interrupt.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++;
}

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;
}
}

volatile uint8_t flag_1ms;

int main(void) {
int8_t taste;

// IOs initialisieren

PORTA = 1; // Pull Up für PA0
DDRB = 3; // PB0/1 sind Ausgang

// UART initialisieren

UBRRH = UBRR_VAL >> 8;
UBRRL = UBRR_VAL & 0xFF;
UCSRB = (1<<RXEN) | (1<<TXEN);

// Timer 0 initialisieren, CTC, Presacler 64

TCCR0 = (1<<WGM01) | (1<<CS01) | (1<<CS00);
OCR0 = 56; // 1ms
TIMSK |= (1<<OCIE0);

// Interrupts global freigeben

sei();

// Endlose Hauptschleife

while (1) {
if (flag_1ms) {
flag_1ms=0;
taste = taste_lesen();
led_blinken(taste);
uart_lesen();
if (flag_1ms) {
// Laufzeit der Tasks >1ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
}

}
}

// Interruptserviceroutine für Timer 0
// hier 1ms

ISR(TIMER0_COMP_vect) {
if (flag_1ms) {
// Laufzeit der Tasks >2ms, Fehlersignalisierung
// PB1 auf HIGH, Programm stoppen
PORTB |= (1<<PB1);
while(1);
}
flag_1ms = 1;
}

</syntaxhighlight>

==== 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.

===== 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.

===== 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"

===== 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.

===== 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:

<syntaxhighlight lang="c">
#include "ACF.h"

int main(int argc, char** argv)
{
ACF_init();
ACF_loop();
return 0; // we will never arrive here
}
</syntaxhighlight>

===== 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.
[http://www.mikrocontroller.net/attachment/74409/ablauf.png Sequenzdiagramm]

== 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" einen Semaphor für "Speicher reservieren". Dieser Semaphor wird erst wieder aufgehoben, sobald Prozess A den Speicher für sich reserviert hat. Wenn der Prozess B zwischendurch gestartet wird und ebenfalls versucht den Semaphor zu setzen, wird er solange warten müssen, bis Prozess A den Semaphor 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 eines Semaphors 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 Semaphore etc.
* nicht streng deterministisch, somit kann kein festes Timing garantiert werden
* nicht explizit debug- und prüfbar, da die Prozesse nicht fest gekoppelt sind

== 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.

== Umsetzung auf Prozessoren ==
Unabhängig davon, ob Multitasking oder -threading auf einem Prozessor konkret unterstützt wird, lässt es sich immer in Form von Software realisieren. Dies wird in modernen Systemen durch das OS geleistet, das standardisierte Funktionen und Strukturen zur Verfügung stellt. Besonders C++ bietet ein stark abstrahiertes Programmiermodell und Methoden-Set an, um effektiv untereinander kompatible Programmmodule erstellen zu können. Nutzt man diese nicht, wie z.B. bei der Programmierung in C, müssen Strukturen manuell erzeugt und gehandhabt werden, was aufwändiger ist, aber auch geringeren overhead bewirkt. Das Programm ist dann fast immer erheblich kleiner, in den meisten Fällen strukturell einfacher, bezüglich komplizierter Änderungen jedoch auch unflexibler und träger.

Bei Mikrocontrollern findet man je nach Komplexität und Struktur der Appliation praktisch alle denkbaren Kombinationen:

=== System mit real-time OS und Entwicklung in C++ ===
* Programmentwicklung stark an abstrakte Interfaces und Standards gebunden
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb gleicher OS-Landschaft gut portierbar
* Sehr geringe Abhängigkeit vom Prozessortyp
* Multitasking muss über OS-Schicht ausprogrammiert werden
* Multithreading muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist niedrig durch relativ hohen Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist niedrig durch sehr viel Arbeit an Formalismen
* Planungsaufwand ist noch überschaubar
* Planungseffizienz ist relaiv hoch durch viele Standards
* Erweiterung um komplexe Module einfach möglich, Timing regelt sich selber

=== System mit real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und weniger an Standards
* Starke Abängigkeit an das OS im Bezug auf RT-Funktionalität
* Innerhalb aber auch ausserhalb gleicher OS-Landschaft gut portierbar
* Geringe Abhängig von dem Prozessortyp
* Multitasking muss über OS-Schicht und eigene Strukturen programmiert werden
* Multithredding muss/kann durch Programmierleistung optimiert werden
* Laufzeiteffizienz ist höher durch geringeren Anteil des OS-Bedarfs
* Datendurchsatz regelt sich selbst und ist gleichmässig am relativen Maximum
* Programmiereffizienz ist höher durch weniger Arbeit mit Formalien
* Planungsaufwand ist etwas höher, je nach Applikation
* Planungseffizienz ist relaiv niedriger durch weniger Standards
* Erweiterung mit akzeptablem Aufwand möglich, Timing muss beachtet werden

=== System ohne real-time OS und Entwicklung in C ===
* Programmentwicklung stark an Interfaces und kaum an Standards gebunden
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur ausserhalb von OS-Landschaft portierbar, dafür prinziepiell sehr gut
* Stärkere Abhängig von dem Prozessortyp, kann die Portierbarkeit einschränken
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithredding muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz kann sehr hoch sein, ist aber stark von der Progr. abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark Applikations abhängig, gfs sehr viel grösser
* Planungseffizienz ist gering, da RT Konzept selber optmiert werden muss
* Erweiterung nur möglich, wenn Timing weitestgehend überarbeitet wird

=== System ohne real-time OS und Entwicklung in ASM ===
* Programmentw. nur an physische Interfaces gebunden und frei von Standards
* Ausprägung und Gestaltung der RT-Funktionalität absolut frei
* nur innerhalb der Prozessorlandschaft gut portierbar
* Volle Abhängig vom Prozessortyp, Portierbarkeit auf andere aufwändig
* Multitasking muss auschlieslich durch eigene Strukturen programmiert werden
* Multithredding muss durch umständliche Programmierung ermöglicht werden werden
* Laufzeiteffizienz sehr hoch, jedoch stark von Programmierung abhängig
* Datendurchsatz muss selbst ins Maximum gesteuert werden, das aber höher liegt
* Programmiereffizienz ist hoch, dank Wegfall von Konventionen
* Planungsaufwand ist stark applikationsabhängig, ggfs. sehr viel grösser
* Planungseffizienz sehr gering, RT Konzept nur für einfache System machbar
* Erweiterung nur möglich, wenn Timing komplett überarbeitet wird

== Weblinks ==

* [http://de.wikipedia.org/wiki/Pr%E4emptives_Multitasking Präemptives Multitasking] bei [http://de.wikipedia.org Wikipedia]
* [http://www.femtoos.org/ Femto OS], ein ultrakompaktes Mulitaskingbetriebssystem für kleine Mikrocontroller
*[http://www.freertos.org/ FreeRTOS], ein freies Echtzeitbetriebssystem für Mikrocontroller
* [http://w3.ualg.pt/~rmarcel/Get%20by%20Without%20an%20RTOS.pdf Get by Without an RTOS] Ein schönes Beispiel wie man ohne ein RTOS auch Multitasking hinbekommt.
* [[TNKernel]], freier Multitasking-Kernel.
* [http://embeddedgurus.com/state-space/2010/04/i-hate-rtoses/ i-hate-rtoses] Blog zum Thema RTOS

[[Kategorie:Betriebssysteme]]