Hallo Leute, ich habe mir gerade diesen Artikel über Multitasking durchgelesen: http://www.mikrocontroller.net/articles/Multitasking#Ein_einfaches_Beispiel_f.C3.BCr_den_AVR Dabei habe ich mir die Frage gestellt, wie es möglich ist, ein präemtives Multitasking System mit nur einem Hardwaretimer/Interrupt zu implementieren? Damit dies Möglich ist, müsste sich doch der Interrupt selbst unterbrechen können? Gibt es ev. irgend einen Artikel der auf dieses Problem eingeht? Bzw. vl. kann mir einer von euch erklären wie so etwas gelöst wird (vl. auch mit einem kleinen Pseudo-Code Beispiel :) )? Vielen Dank für eure Hilfe!
Der Timer ISR wäre dann doch der Scheduler, der die Tasks dann nach einem verfahren (zB Round Robin) switcht. Also Register sichern/wiederherstellen und Stack.
Eine Messagequeue, in der alles was auf den Timer wartet eingetragen ist. EinTimer genuegt.
Peter S. schrieb: > Damit dies Möglich ist, müsste sich doch der Interrupt selbst > unterbrechen können? Nope. Der Trick bestehtz darin, dass die Interruptroutine selber im Grunde der Scheduler (also der OS-Kern) ist. Ein Benutzerprozess wird durch den Interrupt unterbrochen, dadurch kriegt der Scheduler die Kontrolle und manipuliert jetzt den Stack so, dass beim Return vom Interrupt mit einem anderen (vorher unterbrochenen) Prozess weitergemacht wird. Für den Prozess (für jeden Prozess im System) sieht die Sache so aus, dass er durch einen Interrupt unterbrochen wird und irgendwann diese Interruptbehandlung fertig ist und er wieder weitermachen kann. Das in der Zwischenzeit Zeit vergangen ist und andere Prozesse (die das gleiche durchmachen) gelaufen sind, kriegt der so gar nicht mit.
Pseudo-Code des Schedulers:
1 | 0. Irgendein Task läuft |
2 | |
3 | 1. Scheduler durch Timerinterrupt aufrufen |
4 | Die Rücksprungadresse befindet sich jetzt auf dem Stack |
5 | |
6 | 2. Rücksprungadresse des laufenden Tasks vom Stack holen und |
7 | in eine Liste schreiben |
8 | |
9 | 3. Rücksprungadresse eines anderen Tasks von der Liste holen und |
10 | in den Stack parken |
11 | |
12 | 4. Interrupt-Return (zur Rücksprungadresse, die wir in den Stack |
13 | geparkt haben) |
14 | |
15 | 5. Jetzt läuft der nächste Task |
Ist es dir jetzt klarer? Gruß Jonathan
Hätte dazu nochn paar Uni Folien, wer will -> mail an mich.
Vielen Dank für die Antworten! Ok, das mit dem Stack manipulieren macht natürlich Sinn. So weit habe ich nicht gedacht. D.h. im einfachsten Fall muss nur der Programcounter der im Stack beim Sprung in die Interruptroutine gesichert wurde auf eine andere Programmspeicheradresse geändert werden (also auf die Adresse, wo eine andere Task zuletzt unterbrochen wurde). Dadurch kann auf eine andere Task gewechselt werden. Gibt es dazu irgendwelche Beispiele, denn Fehler in der Implementierung sind hier ziemlich fatal (falsche Änderungen im Stack würden zu unvorhersehbaren Dinge führen...). Deshalb würde ich irgend eine Beschreibung benötigen, um zu wissen worauf ich aufpassen muss.
Bzw. ist es mit der Änderung der Rücksprungadresse bereits getan oder müssen noch andere Stack Daten verändert werden (Parameter von Funktionen werden doch auch im Stack gespeichert oder irre ich mich da)?
Peter S. schrieb: > Gibt es dazu irgendwelche Beispiele, denn Fehler in der Implementierung > sind hier ziemlich fatal (falsche Änderungen im Stack würden zu > unvorhersehbaren Dinge führen...). Deshalb würde ich irgend eine > Beschreibung benötigen, um zu wissen worauf ich aufpassen muss. Das war nur die Kurzform. Selbstverständlich muss auch die restliche Umgebung des Prozesses wiederhergestellt werden. D.h. alle CPU Register inklusive Status Register. Der eigentliche Knackpunkt an der ganzen Sache ist aber ein anderer: Wie teilst du den vorhandenen Speicher so auf, dass sich die Prozesse nicht gegenseitig ins Gehege kommen.
Karl Heinz Buchegger schrieb: > Das war nur die Kurzform. Selbstverständlich muss auch die restliche > Umgebung des Prozesses wiederhergestellt werden. D.h. alle CPU Register > inklusive Status Register. Der eigentliche Knackpunkt an der ganzen > Sache ist aber ein anderer: Wie teilst du den vorhandenen Speicher so > auf, dass sich die Prozesse nicht gegenseitig ins Gehege kommen. Mit Semaphore, das sollte nicht das Problem sein. Da habe ich bereits eine gute lauffähige Implementierung. Momentan verwende ich allerdings für jede Task einen eigenen Timerinterrupt --> Die Anzahl der Tasks ist durch die Hardware limitiert. Dies möchte ich nun umgehen, indem ich nur noch einen Timerinterrupt verwende. Folgendes müsste doch theoretisch funktionieren: 1) Start des Hauptprogramms 1)a) Timer für Scheduler wird eingestellt 1)b) Hauptprogramm geht in eine Endlosschleife (while(1);) 2) Scheduler Interrupt wird aufgerufen 2)a) Scheduler merkt anhand eines Merkerbits, dass er das erste mal aufgerufen wird --> Er überschreibt den Stack mit der Adresse des Unterprogramms der höchstpriorsten Task 2)b) Sprung in die Task 3) Die Task arbeitet und verändert diverse Register, springt in unterprogramme, etc. 4) Scheduler Interrupt wird aufgerufen, dabei werden alle wichtigen Daten automatisch im Stack gespeichert (IST DIESE ANNAHME RICHTIG???) 4)a) Scheduler Speichert den gesamten Stack 4)b) Scheduler überschreibt den gesamten Stack mit der Sprungadresse zu einer anderen Task ODER schreibt den gesicherten Stack einer Task hinein Versteht ihr was ich meine? Alle wichtigen Daten müssen ja eigentlich automatisch im Stack abgelegt werden (sonst würde ja die herkömmliche Verwendung eines Interrupts nie funktionieren). Also sichere ich einfach den gesamten Stack. Demnach hat jede Task wie Martin Wende schrieb "seinen eigenen Stack". Sollte doch klappen oder?
Peter S. schrieb: > Karl Heinz Buchegger schrieb: >> Das war nur die Kurzform. Selbstverständlich muss auch die restliche >> Umgebung des Prozesses wiederhergestellt werden. D.h. alle CPU Register >> inklusive Status Register. Der eigentliche Knackpunkt an der ganzen >> Sache ist aber ein anderer: Wie teilst du den vorhandenen Speicher so >> auf, dass sich die Prozesse nicht gegenseitig ins Gehege kommen. > > Mit Semaphore, das sollte nicht das Problem sein. Da habe ich bereits > eine gute lauffähige Implementierung. Ähm. Das hilft dir nichts. 2 Prozesse brauchen Speicher. Du teilst dem einen Prozess 300 Bytes zu und du teilst dem anderen Prozess 300 Bytes später seinen eigenen Stackframe zu. Jetzt braucht aber der 2.te Prozess viel Speicher, weil er viele Funktionen aufruft. Sein Stack wird größer als der für diesen Prozess zur Verfügung stehende Speicher. Er wächst in den Stack des anderen Prozesses hinein. -> Kaboom Prämptives Multitasking ohne MMU ist wie Spielen im Lotto. Man weiß nie so genau wann es krachen wird.
Peter S. schrieb: > Also sichere ich einfach > den gesamten Stack. Demnach hat jede Task wie Martin Wende schrieb > "seinen eigenen Stack". > > Sollte doch klappen oder? Sollte klappen, Du musst halt alle Register usw. vor der Stack-Sicherung in den Stack sichern. Und dann brauchst Du nichtmal mehr die Rücksprungadresse zu manipulieren, da die ja im gesicherten Stack schon drin ist. Auf die Idee bin ich auch noch nicht gekommen ;) Ach ja, wie Karl Heinz Buchegger eben geschrieben hat, musst Du natürlich auch aufpassen, dass die einzelnen Stacks nicht zu groß werden. Gruß Jonathan
Peter S. schrieb: > 4) Scheduler Interrupt wird aufgerufen, dabei werden alle wichtigen > Daten automatisch im Stack gespeichert (IST DIESE ANNAHME RICHTIG???) Na ja, es gibt da noch Variable im Speicher und so ein Zeugs ;)
Karl Heinz Buchegger schrieb: > Prämptives Multitasking ohne MMU ist wie Spielen im Lotto. Man weiß nie > so genau wann es krachen wird. Das hat mit prämptivem Multitasking recht wenig zu tun. Umso mehr mit grosszügigem Umgang mit Pointern. Das Problem von Realtime-Kernels ist eher eine gewisse Neigung zu unreproduzierbaren Verklemmungen (deadlocks) und unbedachter ungeschützter Zugriff auf gemeinsame Resourcen. Solange sich das Multitasking auf der Ebene von Realtime-Kernels bewegt ist eine MMU zwar nett aber unnötig. Erst wenn sich die Bezeichnung "Betriebssystem" allmählich zu lohnen anfängt wird die MMU wesentlich.
Peter S. schrieb: > Momentan verwende ich allerdings für jede Task einen eigenen > Timerinterrupt --> Die Anzahl der Tasks ist durch die Hardware > limitiert. Das ist sowieso ganz unnötig. Ich verwende z.B. einen Time-Interrupt, der sich zuerst um das Multiplexing der Anzeige kümmert, dann um die Tastatur und dann darum, ob an 3 seriellen Schnittstellen was zu empfangen oder zu senden ist. Solange man sicher ist, dass die Interrupt-Routine nicht zu lange läuft, ist das absolut zuverlässig und auch übersichtlich. Das Hauptprogramm erfährt z.B. über eine globale Variable, ob ein Tastendruck erfolgt ist, und schreibt in einen Buffer, was auf der Anzeige erscheinen soll - Warteschleifen in der Interruptroutine gibt es nicht und darf es nicht geben. In einfachen Fällen besteht das System aus einer Hauptschleife (die natürlich mehrere Aufgaben nacheinander bearbeitet) und einer Timerroutine, die alle Real-Time-Aufgaben übernimmt. Für die ganz schnellen Sachen kann man dann noch eigene Interrupts vorsehen. Aber ein System mit Interrupts für jeden Zweck ist immer unübersichtlicher, besonders zur Laufzeit, als eines, bei dem alles in festen Zeitabständen passiert. Gruss Reinhard
Dynamischen Speicher sollte man vermeiden. Das ist zwar nett fuer die C++ Programmierer auf dem PC, hat aber auf einem Controller wenig verloren. Denn dynamischer Speicher ist auch eine Resource und daher muss jedes new() und free() mit einer Semaphore abgesichert werden. Dann geht die Performance in die Knie.
@Peter S. Du kannst dir mal die Dokumentation von FreeRTOS anschauen, dort ist für den AVR der Ablauf sehr anschaulich erklärt, den die zum Taskwechsel verwenden.
Reinhard Kern schrieb: > Das ist sowieso ganz unnötig. Kommt auf alle Fälle auf die Anwendung darauf an und darüber will ich jetzt gar nicht diskutieren. Ich will einfach so ein System implementieren und sehen wie einfach/komplex die Sache ist und in welche Projekte ich sie ev. einsetzen kann und wo nicht. In meinem Projekt gibt es sehr viele Aufgaben die unter sehr zeitkritischen Umständen bewältigt werden. Das vergeben von Prioritäten der Tasks ist in dieser Anwendung sehr wichtig. Darum die aktuelle Lösung mit den verschienden Timer-Interrupts, die eben verschiedene Prioritäten haben. Zurück zum eigentlichen Thema. Angenommen ich benutze kein Echtzeitbetriebssystem. Ich verwende also völlig normale Interrupts. Weiters nehmen wir an, das Hauptprogramm (eines 8-bit Controllers) führt gerade eine komplexe Berechnung mit 4 Byte großen Datentypen durch. Der C-Compiler wird wahrscheinlich den Code so aufbrechen, dass diverse Register für die Berechnung verwendet werden. Nun passiert aber eben während dieser Berechnung ein Interrupt. Damit nach dem Rücksprung aus dem Interrupt wieder alles weiter läuft, muss der Compiler doch zwangsweise die Register in den Stack gespeichert haben? Oder irre ich mich da? D.h. wenn ich in meinem Betriebssystem den gesamten Stack speichere, sollte das absolut kein Problem sein, oder? A. K. schrieb: > Das Problem von Realtime-Kernels ist > eher eine gewisse Neigung zu unreproduzierbaren Verklemmungen > (deadlocks) und unbedachter ungeschützter Zugriff auf gemeinsame > Resourcen. Das Problem mit der Resourcenverwaltung ist wieder ganz ein anderes Thema. Aber mit einer geschickten Implementierung von Semaphoren durchaus zu bewältigen wie ich finde. Deadlocks könnte man z.B. verhindern, indem eine höher priore Task, eine niederpriore Task aus der Critical Region kicken kann. Karl Heinz Buchegger schrieb: > Er wächst in den Stack des > anderen Prozesses hinein. -> Kaboom Das Problem mit der Stackgröße kann ich durchaus prüfen, indem ich die Position des Stackpointers des tatsächlichen (physikalischen) Stacks vor dem Sichern Abfrage. Ist er zu groß (bzw. zu wenig reservierter Speicher verfügbar), dann werden alle Tasks beendet und ein Fehlercode ausgegeben.
Bonzo schrieb: > Dynamischen Speicher sollte man vermeiden. Das ist zwar nett fuer die > C++ Programmierer auf dem PC, hat aber auf einem Controller wenig > verloren. Denn dynamischer Speicher ist auch eine Resource und daher > muss jedes new() und free() mit einer Semaphore abgesichert werden. Dann > geht die Performance in die Knie. Ja sowieso, den Speicherbereich in dem der Stack gesichert wird würde ich einfach über eine Konstante fix reservieren. Auch meine geteilten Variablen, die sich in der Critical Region befinden, würden fixe Speicherbereiche erhalten.
Narfie schrieb: > Du kannst dir mal die Dokumentation von FreeRTOS anschauen, dort ist für > den AVR der Ablauf sehr anschaulich erklärt, den die zum Taskwechsel > verwenden. Vielen Dank für den Tipp. Hab zwar noch nie mit einem AVR gearbeitet, aber die Dokumentation wird sicher hilfreich sein!
>dann werden alle Tasks beendet und ein Fehlercode ausgegeben.
Das ist eben nicht machbar, ausser vielleicht in einer Debugumgebung. In
einem realen System geht das nicht. Das waere dann eine Seilbahn oder
so. Die kann nicht einfach stehenbleiben.
Peter S. schrieb: > Das Problem mit der Stackgröße kann ich durchaus prüfen, indem ich die > Position des Stackpointers des tatsächlichen (physikalischen) Stacks vor > dem Sichern Abfrage. Ist er zu groß (bzw. zu wenig reservierter Speicher > verfügbar), dann werden alle Tasks beendet und ein Fehlercode > ausgegeben. Du kannst ja dann ein blaues Display anschalten und einen BSOD ausgeben... g Nein, im Ernst: Ich würde da nur den Task, der zu viel RAM verbraucht, abmurksen und das dann halt melden. Oder Du beendest den unwichtigsten Task, dann kann weniger passieren. Gruß Jonathan
Und wie soll es moeglich sein, dass dies nur einmal in 10 Jahren passiert und nicht jede Sekunde, oder Minute ?
Karl Heinz Buchegger schrieb: > Prämptives Multitasking ohne MMU ist wie Spielen im Lotto. Man weiß nie > so genau wann es krachen wird. Mit Verlaub: Der Commodore Amiga hatte auch prämptives Multitasking ohne MMU, und der lief (bei korrekter Programmierung) ziemlich stabil.
>... und der lief (bei korrekter Programmierung) ziemlich stabil.
Ziemlich stabil mag ja fuer eine Arbeitsmaschine genuegend sein. Fuer
eine Steuerungsanwendung ist das etwas mager. Da gibt es eigentlich nur
eins : 24x7 und das jahrelang, ohne Neustart.
Beim kooperativen Multitasking hat man noch eine Kontrolle drueber, wann
der Task gewechselt wird, beim Preemptiven eben nicht mehr.
Präemptives Multitasking ist meiner Meinung nach für fast alle MC Anwendungen overkill. Ein nettes Experiment, allerdings selten wirklich sinnvoll. Üblicherweise weiß man exakt welche Routinen laufen werden und selten hat der User die Möglichkeit, zusätzliche Routinen einzubinden. Entsprechend stellt sich mir die Sinnfrage. Ich kann einige gute Gründe für kooperatives MT finden, aber präemptives? Kann mir jemand ein Beispiel nennen wo dieser Overhead wirklich gerechtfertigt wäre?
@Heinz L. (ducttape) >Präemptives Multitasking ist meiner Meinung nach für fast alle MC >Anwendungen overkill. Naja, der Begriff MC ist je sehr breitbandig. Vom kleinen 8-Pin AVR bis 300Pin BGA ARM9 ist da alles drin. >sinnvoll. Üblicherweise weiß man exakt welche Routinen laufen werden und >selten hat der User die Möglichkeit, zusätzliche Routinen einzubinden. ARM9 mit embedded Linux? >Ich kann einige gute Gründe für kooperatives MT finden, aber >präemptives? Kann mir jemand ein Beispiel nennen wo dieser Overhead >wirklich gerechtfertigt wäre? Gute Frage.
>Kann mir jemand ein Beispiel nennen wo dieser Overhead wirklich gerechtfertigt
wäre?
Kooperative Multitasking bedeutet Kooperation. Das bedeutet jeder Task
muss die Rechenzeit nach einer sinnvollen Zeit wieder freigeben. Ich hab
schon gesehen wie jede Ziffere einer BCD Umwandlung einen Durchgang
bedeutete, um schnelle Zykluszeiten zu erreichen. Das ist vielleicht
etwas extrem, und bedeutet totale Kontrolle ueber den Code. Andereseits
hat man vielleicht weniger Kontrolle, setzt vielleicht eine FFT ein,
ohne begriffen zu haben was sie macht, dann kann man sie auch nicht
zerscheibeln, und die Rechenzeit zwischendurch freigeben. Wenn man also
sporadische Rechnungen(zB Matritzen mit Float) macht die laenger sind
wie die Antwortzeit des Systems sein sollte, dann kann man preemptives
multitasking einsetzen. Die ist dann faehig diese Berechnungen zu
unterbrechen.
Wie Nilp etwas unklar ausfuehrte, ist die Antwortzeit von kooperativem Multitasking bestimmt durch den langsamsten Task. Bei preemptivem Multitasking benoetigt das System in jedem Fall N Zeitscheiben fuer eine Antwort. Echtzeit bedeutet ja eine definierte Antwortzeit, wobei dann noch zwischen weich und hart unterschieden wird.
Beim Multitasking muß man für jede Ressource erstmal einen Treiber schreiben. Keine Task kann mehr direkt drauf zugreifen. Z.B. in einer Mainloop hat man mehrere Tasks hintereinander laufen. Eine schreibt die Uhrzeit aufs LCD, eine andere die Temperatur und wieder eine andere ist gerade beim Weckzeit einstellen. Jede setzt dazu den Kursor auf ihre Position und schreibt den Text hin. Das geht super, keiner kommt dem anderen in die Quere. Beim Multitasking würden sie aber alle bunt durcheinander schreiben. Es muß daher einen LCD-Treiber geben, der das LCD verwaltet und sich für jede Task die aktuelle Kursorposition merkt. Peter
Bonzo schrieb: > Das ist eben nicht machbar, ausser vielleicht in einer Debugumgebung. In > einem realen System geht das nicht. Das waere dann eine Seilbahn oder > so. Die kann nicht einfach stehenbleiben. Ist wieder was Anwendungsspezifisches, das wollte ich jetzt eig. erstmal außen vor lassen. Aber natürlich dürfte man nicht das ganze Programm anhalten, sondern einfach in einen sicheren Zustand wechseln und ev. neu starten. Bzw. kann man sich ja ansehen, wann der Stack am größten ist und den Wert mit Sicherheitsreserven verwenden. Der grund warum ich ein präemtives Multitaskin System benötige ist oben bereits gut erklärt! Genau das ist auch in meiner Anwendung der Fall.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.