Hallo,
ich suche eine Strategie oder einen Algorithmus der mir hilft folgendes
umzusetzen:
Ich habe eine Liste an Events. Diese sollen jeweils mit einer bestimmten
Zykluszeit "ausgeführt" werden. Jedes Event ist dabei gleich
priorisiert.
Außerdem kann nur dann ein Event ausgelöst werden wenn gerade kein
weiteres aktiv ist. D.h. das vorherige Event sollte fertig abgearbeitet
worden sein bevor ein neues gestartet wird. Unter Umständen verzögert
sich also ein Event leicht.
Dazu folgendes Beispiel:
1
ev_15ms
2
ev_230ms
3
ev_3100ms
Hier sind die Zykluszeiten großzügig gewählt. Es sollte also wenig
Probleme geben. ev_2 und ev_3 werden natürlich nicht genau zum Zeitpunkt
t=30ms oder t=100ms ausgeführt weil das schnelle ev_1 dort auch jeweils
aktiv ist. Wie gesagt, dieses leichte Delay ist in Ordnung. Gehen wir
davon aus, die Eventliste wird jede Millisekunde geprüft, so findet ev_2
bei t=31ms und ev_3 bei t=101ms statt. Passt.
Ok, nun folgendes (problematisches) Beispiel:
1
ev_15ms
2
ev_210ms
3
ev_310ms
4
ev_45ms
5
ev_55ms
6
ev_65ms
Hier wird schon durch die bloße Anzahl der Events erreicht, das die
Zykluszeit nicht mehr eingehalten werden kann. Zwar unschön, aber nun
gut.
Allerdings: die Verzögerungen werden sich aufaddieren, und irgendwann
wird dann ein Event "verschluckt", d.h. geht verloren.
Das ist zwar noch weniger schön, aber immer noch akzeptabel.
Was aber nicht sein darf ist, dass ein Event was relativ spät in der
Liste auftaucht (z.B. ev_6) gar nicht mehr ausgeführt wird.
Ich muss sicherstellen, dass jedes Event selbst bei hoher "Eventlast"
irgendwann drankommt.
Gibt es da eine günstige Strategie/Algorithmus?
Mein Ansatz wäre: ich merke mir die Position in der Liste des zuletzt
ausgeführten Events.
Ich teste meine Liste jede Millisekunde auf anstehende Events. Dabei
arbeite ich die Liste nicht von [0] bis [n-1] durch sondern starte
jeweils bei der gemerkten Position. So wird früher oder später das Ende
der Liste erreicht.
Leider fehlen mir die mathematischen Grundlagen um diesen Ansatz
bewerten/mit anderen vergleichen zu können.
Wär meine Lösung praktikabel oder gibt es da bessere Ansätze?
Ein Betriebssystem-Scheduler hat wohl ähnliche Probleme zu lösen (wenn
auch ungleich komplexer). Von daher denke ich dass es da schon Ansätze
gibt.
Viele Grüße
Man nimmt dazu eine timerschlange, also eine doppelt verkettete Liste,
da ist erster parameter des gelinkten elementes die dauer vom voeriger
her gespeichert. Nach abgearbeiteten Timer event wird der HW-timer auf
die zu wartende Zeit gestellt. Der Timer arbeitet dann das jeweils
anstehende Element ab. Einfuegen bedeutet nun sich von vorne hach hinten
hangeln, und dann in die liste einfuegen.
etwa so ?
Statt einer Liste wär evtl. eine "priority queue" besser geeignet.
Die lässt sich einfach in ein Array mappen, also keine dynamische
Speicherverwaltung nötig.
Abarbeiten/"pop" und Hinzufügen/"push" eines Jobs geht in O(log n), bzw.
bei Array-Implementierung mit konstanter Länge: in O(1) ;)
Und schon ist sichergestellt, dass immer der dringenste Job an
Array-Position 0 steht.
https://de.wikipedia.org/wiki/Vorrangwarteschlange
Meiner Ansicht nach, gehst Du bei der Analyse nicht gründlich genug vor.
Du musst drei Aspekte berücksichtigen:
1. Die Zykluszeit in der die Ereignisse tatsächlich auftreten.
2. Die reine Verarbeitungszeit der Ereignisse.
3. Die jeweilige maximal zulässige Reaktionszeit auf die Ereignisse.
Kennzeichne in Deinen Skizzen den Zeitablauf. Es wird nicht klar ob die
in der ersten Skizze gezeigte Zeit die selbe ist, wie in der zweiten.
(Ich kann mir zwar was dabei denken, aber es geht ja um ein tieferes
Verständnis bei Dir).
Ein weiterer Aspekt ist die Frage der Unterscheidung zwischen Abläufen
und Bedingungen, die aus irgendwelchen ausserhalb Deiner
Einflussmöglichkeit liegenden Gründen so sind wie sie sind, oder weil
sie so sein sollen, oder weil es wünschenswert ist, das sie so sind. Je
nachdem ergeben sich weitere Überlegungen, die recht vielfältig sind.
Nicht umsonst gibt es ganze Bücher über das Thema.
Bitflüsterer schrieb:> Nicht umsonst gibt es ganze Bücher über das Thema.
Das ist mir bewusst.
Nicht umsonst treffe ich Annahmen, die das Problem vereinfachen:
- wenn die Zykluszeit nicht eingehalten kann stört dies nicht
- es sollen im laufenden Betrieb keine neuen Events eingereiht werden
- hauptsache, ein Event wird irgendwann erreicht
- die Bearbeitungszeit eines Events ist vernachlässigbar
Das hier ist ein Nebenkriegsschauplatz. Kein RTOS Scheduler dessen
Verhalten streng deterministiech sein muss. Ich bitte das zu beachten.
Gibts dazu Ideen, die besser geeignet sind als meine Ursprüngliche?
Du musst dir schlicht merken, wann ein Event in "absoluter" Zeit dran
ist. Dann prüfst du von mir aus jede ms, ob denn jetzt einer dran ist.
Wenn ja, arbeitest du den ab, und merkst dir, wenn der wieder dran ist.
Danach solltest du noch prüfen, ob noch mehr Events "jetzt" dran sind,
und die auch abarbeiten. Wenn alle aktuellen durch sind, geht es von
vorne los.
Oliver
Haro schrieb:> Bitflüsterer schrieb:>> Nicht umsonst gibt es ganze Bücher über das Thema.>> Das ist mir bewusst.> Nicht umsonst treffe ich Annahmen, die das Problem vereinfachen:
Aus meiner Sicht machen sie es nicht einfacher. Man könnte sie klarer
und strenger formulieren. Aber gut. Wenn es Dir reicht, soll es mir
recht sein.
> Das hier ist ein Nebenkriegsschauplatz. Kein RTOS Scheduler dessen> Verhalten streng deterministiech sein muss. Ich bitte das zu beachten.
Davon habe ich nichts geschrieben. Aus meiner Sicht schien es mir
angebracht, erst einmal Grundlagen klarzustellen. Aber gut. Wenn Dir
alles klar ist, soll es mir recht sein.
> Gibts dazu Ideen, die besser geeignet sind als meine Ursprüngliche?
Sicherlich. Ich hätte angenommen, das Du, um sie zu entwickeln und zu
verstehen, ein paar Grundlagen anschauen solltest. Aber gut. Dir ist
schon alles klar. Fehlt nur noch die Idee. :-)
Wie ich darauf gekommen bin, dass Du Grundlagen benötigst?
> Leider fehlen mir die mathematischen Grundlagen um diesen Ansatz> bewerten/mit anderen vergleichen zu können.
Ok, schaun wir uns die Punkte an.
Bitflüsterer schrieb:> Du musst drei Aspekte berücksichtigen:> 1. Die Zykluszeit in der die Ereignisse tatsächlich auftreten.> 2. Die reine Verarbeitungszeit der Ereignisse.> 3. Die jeweilige maximal zulässige Reaktionszeit auf die Ereignisse.
1. Ich zeichne auf einer Zeitachse Punkte für die auftretenden Events.
Dabei sehe ich, dass unter Umständen mehrere Eventtimer gleichzeitig
abgelaufen sind. Abhängig von den einzelnen Zykluszeiten und der Anzahl
Events. Erhöhe ich die Zykluszeiten so entspannt sich die Situation, bis
irgendwann wieder alles i.O. ist. Habe ich mehr Events, verschärft sich
die Situation.
2. Da ein Event nun keinen kurzen Impuls mehr darstellt sondern Zeit
braucht verschärft sich die Situation. Das Bild aus 1. ändert sich nicht
großartig, allerdings ist es jetzt schwerer, wieder in den grünen
Bereich zu kommen.
3. Es gibt keinen "Timeout". Solange jedes Event irgendwann kommt passt
alles. Ich vermute, wenn ich meinen Ansatz aus dem Eröffnungspost
umsetze habe ich irgendwann folgendes Verhalten:
Mit jedem Zyklus verschlechtert sich die Situation. Die Delays summieren
sich auf. Irgendwann sind alle Eventtimer gleichzeitig abgelaufen. Dann
wird die Liste einfach der Reihe nach abgearbeitet, Zykluszeiten spielen
keine Rolle mehr. Das System bleibt in diesem Zustand.
Sind meine Betrachtungen soweit richtig?
Ich sehe da wenig Optimierungspotential, aber ich könnte wohl mit der
Lösung leben, außer es gibt noch Vorschläge ;-)
Haro schrieb:> Irgendwann sind alle Eventtimer gleichzeitig abgelaufen. Dann> wird die Liste einfach der Reihe nach abgearbeitet, Zykluszeiten spielen> keine Rolle mehr.
Wenn das in Ordnun für dich ist, schlage ich vor, du versetzt das System
gleich in den Zeitpunkt "Irgendwann", und arbeitest einfach alle Events,
die dann gar keine mehr sind, hintereinander ab, ganz ohne
Eventscheduler.
Oliver
Jo mei, natürlich wär eine gewisse Ordnung schöner. Momentan hab ich die
halt nur bei günstigen Parametern, abhängig von Eventzahl und deren
Zykluszeiten.
Da ich aber auf keine optimalere Lösung komme (siehe mein
Gedankenexperiment im letzten Beitrag) und hier auch nix kommt werd ich
das wohl so beibehalten. Nebenkriegsschauplatz eben.
Haro schrieb:> Da ich aber auf keine optimalere Lösung komme (siehe mein> Gedankenexperiment im letzten Beitrag) und hier auch nix kommt
Na ja, zum ganz große Töne spucken fehlt dir dann doch etwas die
Substanz. Aber egal, wenn es sowieso egal ist, wann und warum da irgend
etwas ausgeführt wird, mach einfach. Ist dein Programm.
Oliver
Thread beobachten
Seitenaufteilung abschalten