Betriebssystem-Scheduler

[Jürgen C. (cjr)]

Hallo,

ich bin gerade dabei die Software meines Projektes zu überarbeiten.
Es handelt sich um ein Modul, das möglichst universel, Steuer- und
Regelungsaufgaben in der Haustechnik (Heizung) übernehmen kann.
Ich möchte jetzt gerne ein "Betriebssystem" dafür schaffen, welches
die Grundfunktionen wie Anzeige, Benutzereingabe, analoge- und digitale
Ein- und Ausgabe, Daten- Speicherung und -Übertragung, Datum und
Uhrzeit und was mir sonst noch einfällt zur Verfügung stellt.

Programmierumgebung ist mikroPascl Pro for AVR,
Prozessor: ATXMEGA256A3B

Als Grundlage versuche ich einen Scheduler zu entwickeln, der etwa
wie Folgt Funktioniert:

Im Timerinterrupt wird eine Byte-Variable (scheduler_index) 
kontinuierlich
hochgezählt.
In einem Konstanten-Byte-Array (scheduler_table) mit 256 Werten wird für 
jeden
Wert der Byte-Variablen festgelegt, welcher Prozess aufgerufen werden 
soll.
Byte-Variable = 0    ->   Prozess 0
                1                 1
                2                 2
                3                 1
                4                 3
                5                 1
                6                 2
                7                 4
                .                 .
                .                 .
                252               1
                253               3
                254               2
                255               1

Es stehen 9 Prozesse zur Verfügung die gleichmäsig verteilt in
abgestuften Taktungen aufgerufen werden. Wobei Prozess 8 und 0 im 
Gleichtakt abwechselnd ausgeführt werden.
Die Ausführungsfrequenz von Prozess 7 ist doppelt so hoch wie
von Prozess 8, 6 ist 4 mal so hoch wie 8, 5 ist 8 mal, ... 1 ist 128 mal 
so hoch wie 8.

Die Prozesse werden als normal Proceduren ausgeführt und vom Scheduler 
in der entsprechenden Reihenfolge und Zeit aufgerufen. 
Stackmanipulationen will ich nicht durchführen.
Meine Frage ist, ob dies ein brauchbarer Lösungsansatz ist oder ob ich 
auf
dem Holzweg bin. Habt ihr Verbesserungsvorschläge.

Die angehängte Datei ist nich kompilierbar, da einige verbundene
Dateien fehlen.

Viele Grüße

Jürgen

[Jürgen C. (cjr)]

Hallo,
entschuldigt bitte, habe oben die falsche Datei angehängt.

[Dr. Sommer (Gast)]

Das wären dann aber keine richtigen Prozesse, denn die können mitten in 
ihrem Ablauf unterbrochen werden, um zu einem anderen Prozess zu 
wechseln. Dies ermöglicht eine schön lineare einfache Programmierung der 
Prozesse. Für solche richtigen Kontextwechsel sind die AVR's aber eher 
nicht so geeignet, das geht zB auf den Cortex-M viel besser.
Dein Ansatz ist eigentlich nur ein erweiterter Software-Timer, so wie 
"cron"... Das heißt aber nicht dass das "falsch" ist, ich würde nur 
keine 256 Bytes für das Array verschwenden sondern versuchen die Zahl 
"live" auszurechnen. Und die Begriffe "Scheduler" und "Betriebssystem" 
sind hier etwas irreführend.

[Jürgen C. (cjr)]

Hallo Dr. S.,

Danke für deine Antwort.
Mit den Begriffen hast Du sicher Recht. Mir ist nur nichts passendes
eingefallen. Es soll halt mein "System" mit den Bezeichnungen, wie sie 
bei grosen System verwendet werden, beschreiben.

Scheduler -> Software-Timer der die Prozeduren abwechselnd aufruft.
Prozess -> Prozedur / Funktion die vom Software-Timer aufgerufen wird.
Betriebssystem -> Sammlung von Prozduren und Funktionen,die im
                  Hintergrund laufen und die Grundfunktionalität der
                  Hardware zur Verwendung mit der "Software" aufbereitet
                  (Temperatur, Frequenz, Zeit, Tastatureingabe,
                  Displayausgabe, Relais, PWM, UART, SD-Card, ..).

Die 256 Byte sind kein Problem ich glaube ich bring die restlichen knap
256 KByte nicht mehr voll. Ich hab mir über die "live" Berechnung schon
Gedanken gemacht, aber ich bin noch auf nichts gekommen(Übersteigt meine
Fähigkeiten).

[Dr. Sommer (Gast)]

Jürgen C. schrieb:
> Ich hab mir über die "live" Berechnung schon
> Gedanken gemacht, aber ich bin noch auf nichts gekommen(Übersteigt meine
> Fähigkeiten).
Naja, was wann aufgerufen wird folgt ja scheinbar irgendeinem Schema, 
das sind ja keine Zufallszahlen die da im Array landen?! ... Und dieses 
Schema lässt sich bestimmt in C-Code ausdrücken...

[Olaf (Gast)]

> Meine Frage ist, ob dies ein brauchbarer Lösungsansatz ist oder ob ich
> auf dem Holzweg bin.

Grundsaetzlich steht man mit so einem Ansatz natuerlich am Anfang von 
20Jahren Entwicklung und Forschung von Multitasking Betriebssystemen. 
:-)

Aber es funktioniert, ich hab vor einiger Zeit mal genau dasselbe 
gemacht:

Beitrag "Neuer Multitasker Olix"

Ist eine interessante Aufgabe wenn mal mal seinen Controller und 
Compiler etwas besser kennenlernen will. :)

Olaf

[Svenska (Gast)]

Es handelt sich um einen statischen Offline-Scheduler, in diesem Fall 
mit einer Periode von 256 Schritten. Vorteilhaft ist, dass die 
Berechnung des nächsten Tasks nicht versehentlich schief gehen kann und 
auch keine Rechenzeit benötigt. Das spielt bei harten Echtzeitsystemen 
durchaus eine Rolle und wird teilweise so gemacht.

Die Art und Weise, wie dieses Array erzeugt wird, bestimmt dann den 
Algorithmus. Klassisch wären hier Rate Monotonic/Deadline Monotonic zu 
nennen, die sind optimal* (für statische Algorithmen), können aber 
sowohl Online als auch Offline genutzt werden.

Daneben gibt es noch dynamische Algorithmen (optimal* wäre z.B. Earliest 
Deadline First), die sind aber grundsätzlich Online.

Und schließlich gibt es noch Unmengen an Algorithmen, die nicht auf 
harte Echtzeit ausgelegt sind und andere Schwerpunkte setzen (mehrere 
CPUs, geringe Latenzen, wenig Cache-Thrashing, hoher Durchsatz im 
Mittel, ...), die man eher bei größeren Systemen findet.

*optimal unter gewissen Randbedingungen.

> Das wären dann aber keine richtigen Prozesse, denn die können
> mitten in ihrem Ablauf unterbrochen werden, um zu einem anderen
> Prozess zu wechseln.

Der Scheduler braucht nur per Timer-Interrupt aufgerufen werden. Pro 
Prozess brauchst du einen eigenen Stackframe, auf den du die Register 
sichern kannst.

> Dies ermöglicht eine schön lineare einfache Programmierung der
> Prozesse. Für solche richtigen Kontextwechsel sind die AVR's aber eher
> nicht so geeignet, das geht zB auf den Cortex-M viel besser.

Stimmt. Es gibt auf AVRs eigentlich nur einen Speicherkontext, also 
nenne die Prozesse lieber Threads und lass deinen Scheduler dann darauf 
los. :-)

Gruß,
Svenska

[c-hater (Gast)]

Jürgen C. schrieb:

> Als Grundlage versuche ich einen Scheduler zu entwickeln, der etwa
> wie Folgt Funktioniert:
>
> Im Timerinterrupt wird eine Byte-Variable (scheduler_index)
> kontinuierlich
> hochgezählt.

Das ist trivial.

> In einem Konstanten-Byte-Array (scheduler_table) mit 256 Werten wird für
> jeden
> Wert der Byte-Variablen festgelegt, welcher Prozess aufgerufen werden
> soll.

Das ist, naja, eigenartig umständlich, aber sonst weiter kein Problem.

> Die Prozesse werden als normal Proceduren ausgeführt und vom Scheduler
> in der entsprechenden Reihenfolge und Zeit aufgerufen.

Also läuft der Scheduler schienbar in der Hauptschleife des Programms 
und wird nicht von der Timer-ISR aus aufgerufen.

> Stackmanipulationen will ich nicht durchführen.

Brauchst du dann auch nicht.

Allerdings: was du da gebaut hast, ist kooperatives Multitasking. Es ist 
auf die Mitarbeit sämtlicher beteiligter "Prozesse" angewiesen. Keiner 
davon darf zu seiner Ausführung jemals länger brauchen, als eine Periode 
deines Timers dauert, sonst gehen dir unweigerlich Zählschritte in 
deinem Scheduler verloren, d.h.: die in den fehlenden Schritten 
aufzurufenden "Prozesse" werden halt nicht aufgerufen.
Und ein fehlerhafter Prozess, der z.B. durch einen Programmfehler in 
eine Endlosschleife gerät, kann das gesamte System anhalten.

> Meine Frage ist, ob dies ein brauchbarer Lösungsansatz ist oder ob ich
> auf
> dem Holzweg bin. Habt ihr Verbesserungsvorschläge.

Naja, die Alternative zu kooperativem MT ist präemptives. Das hat die 
o.g. Nachteile nicht, dafür aber andere: Programmieraufwand und 
Resourcenverbrauch sind deutlich höher. Und natürlich kommt es nicht 
ohne Stackmanipulationen aus.

[Mehmet K. (mkmk)]

Eine elegantere Lösung waere Protothreads von Adam Dunkels zu benutzen.
http://de.wikipedia.org/wiki/Protothread

[Blubber (Gast)]

Hab nun nicht alles gelesen und daher vielleicht ein dagegen sprechendes 
Argument nicht gesehen. Aber warum kein bestehendes OS benutzen? 
FreeRTOS z.B.?

[Purzel H. (hacky)]

>Aber warum kein bestehendes OS benutzen? FreeRTOS z.B.?

Weils zB auf einem Tiny2313 oder Mega8 laufen muss...

[Peter D. (peda)]

Beitrag "Wartezeiten effektiv (Scheduler)"

[(prx) A. K. (prx)]

Siebzehn mal Fuenfzehn schrieb:
>>Aber warum kein bestehendes OS benutzen? FreeRTOS z.B.?
>
> Weils zB auf einem Tiny2313 oder Mega8 laufen muss...

Oben steht: ATXMEGA256A3B. Der wär gross genug.

[Jürgen C. (cjr)]

Hallo,
Danke für die vielen Beiträge.
So wie ich das aus eueren Antworten entnehme sollte mein Lösungsansatz 
funktionieren.

Dr. Sommer: Die "live" Berechnung werde ich als Nächstes angehen und
            schauen was für meine Anwendung vorteilhafter ist;
            Speicher ist ausreichend vorhanden(XMEGA256A3B),
            Rechenzeit sollte sparsam genutzt werden.

Olaf: Ich mache das aus Spass(Selbstbestätigung, Ehrgeiz, Abwechslung,
      Hobby) und muss damit, Gott sei Dank, nicht meine Brötchen
      verdienen. Wie Du schreibst ist es auch eine Gute Übung, und die
      schadet nicht.

Svenska: Ich habe zwar im Moment noch keine Aufgabe die Harte Echtzeit
         erfordert, aber ich möchte diese Möglichkeit nicht
         ausschließen. Ich werde also in Richtung  statischer Offline-
         Scheduler weiter arbeiten, auch weil er meiner Meinung nach
         am einfachsten zu Realisieren ist.

c-hater: Meine Hauptschleife sieht zur Zeit so aus:

            while true do
            begin
            scheduler;
            end;

         in der Timer-ISR wird bestimmt welchen Thread vom scheduler als
         Nächstes aufgerufen wird.

         Im Thread der am häfigsten aufgerufen wird, wird bestimmt
         welcher Teil des Hauptprogrammes als nächstes aufgerufen wird.
         "Scheduler im Scheduler"
         In den anderen Threads werden dann "Betriebssystemfunktionen"
         wie AD-Wandlung mit Temperaturberechnung, Displayausgabe,
         Tastatureingabe usw. ausgeführt.

         Kooperatives Multitasking sollte für meine Zwecke ausreichend,
         da ich alle Threads selbst entwickle und prüfe und auf eine
         ordentliche Rückkehr aus dem Thread achten werde.

Mehmet Kendi: Danke für den Link.

Karsten S.: Ich wills "selber" machen und verstehen was ich mache.

Peter Dannegger: Ich tu mich mit C etwas schwer, aber so wie ich es
                 verstehe geht mein Ansatz auch in diese Richtung.
                 Ich werde es wohl weiter mit Pascal und meiner "Syntax"
                 machen.
                 Aber die Hinweise in deinem Link sind sehr nützlich
                 und ich werde mich noch weiter damit auseinantersetzen.

@all: Ich habe keinerlei Ausbildung in Informatik "genossen" und bin
      desshalb wohl etwas unbeholfen und unkonventionel in meiner
      Herangehens- und Ausdrucksweise.
      Ich beschäftige mich Hobbymäsig aber schon seit langer Zeit mit
      PC-Programmierung und MC- Hard- und Software.
      Ich werde noch ein kompilierbares Beispiel meiner Fortschritte
      hier einstellen. Wird aber bis nächstes Wochenende dauern.
      Vieleicht werden dann auch meine Absichten und Gedankengänge
      etwas klarer.

Eine schöne Woche und Viele Grüße

Jürgen

[Dr. Sommer (Gast)]

Jürgen C. schrieb:
> @all: Ich habe keinerlei Ausbildung in Informatik "genossen"
Dann hast du ja noch alle Chancen...

Das schöne an "richtigen" Threads/Prozessen (mit Stackmanipulation) ist 
die einfache lineare Programmierung der Thread-Funktionen, z.B. so in 
etwa (mangels Pascal-Erfahrung C-Code aber das sollte ja nix machen):

void UartInputThread () {
  while (1) { // Endlosschleife
    char command = readUart ();
    if (command == 1) {
      char param1 = readUart ();
      setPwn (param1);
    } else if (command == 2) {
      ledOff ();
    } // ... usw ...
  }
}

Während man auf Eingaben vom UART wartet würde dieser Thread gar nichts 
machen und den anderen Zeig geben. Die Funktion ist wunderbar 
"intuitiv", wenn man viele verknüpfte "warten"-Operationen hat wie 
UART-Input, SPI-Output etc. kann das große Vorteile haben. Das muss gar 
nicht mal präemptiv sein, man könnte zB immer bei den readUart() 
-Funktionen einen Kontextwechsel durchführen...

[Jürgen C. (cjr)]

Hallo,
ich habe jetzt "live" Berechnung wie folgt implementiert:

if Scheduler_index = 0 then Prozess0
 else if scheduler_index.0 = 1 then Prozess1
 else if scheduler_index.1 = 1 then Prozess2
 else if scheduler_index.2 = 1 then Prozess3
 else if scheduler_index.3 = 1 then Prozess4
 else if scheduler_index.4 = 1 then Prozess5
 else if scheduler_index.5 = 1 then Prozess6
 else if scheduler_index.6 = 1 then Prozess7
 else if scheduler_index.7 = 1 then Prozess8
end;

Das ganze Testprogramm ist im Anhang.

Als nächstes gehe ich jetzt die "Function Pointer" an, um über einen
Index den Ablauf von Funktions- und Proceduraufrufen steuern zu können.
Ich stelle mir das so vor: Der Scheduller fordert das Hauptptrogramm
auf die nächste Funktion in der Reihe auszuführen. Das Hauptprogramm
ermittelt über den Index die Funktion und führt sie aus, anschliesend
wird die Kontrolle wieder an den Scheduller übergeben.
Erste Tests schauen schon recht vielversprechend aus.

MFG Jürgen