Abarbeiten aufeinanderfolgender Tasks

Hallo,

ich würde gerne einem Arduino serielle Befehlen senden. Diese Befehle sollen in beliebiger Reihenfolge und Geschwindigkeit an ihn gesendet werden.

Der empfangende Arduino soll diese Befehle dann in entsprechende “Aktionen” umsetzen, wobei es hierbei u.U. vorkommen kann, dass die Dauer einer “Aktion” länger andauert, so dass bereits ein neuer Befehl eingetroffen sein könnte. Des weiteren soll es Befehle geben, die gleiche Priorität haben.

Ein Beispiel:

Ich sende den “Befehl X”. → Die “Aktion X” wird ausgeführt.

Noch während die “Aktion X” läuft sende ich “Befehl 1” gefolgt von “Befehl 2”. → Die Aktion “2” wird dem Ende von “Aktion X” ausgeführt, da “Befehl 1” und “Befehl 2” dieselbe Priorität haben.

Mein Problem ist nun, dass ich nicht weiss nach was ich im Netz suchen soll. Ich suche praktisch nach einer Art Prioritätenmanager mit Speicherfunktion, da die eintreffenden Befehle ja je nach Priorität und Zeitpunkt in einer bestimmten Art und Reihenfolge abgearbeitet werden sollen. Es geht mir als lediglich darum, wie die eintreffenden Befehle verwaltet werden, bis sie dann (z.B. an div. Funktionen) “weitergeleitet” werden.

Vielleicht habt ihr mir ja ein paar Schlagworte nach denen ich suchen kann.

Gruß Chris

Ich fürchte, wenn du was findest, passt das nicht zum Arduino oder nicht zu deiner Vorstellung.

Mit so Konzepten wie "beliebig" viele, "mehrere" Prioritäten, die gerne mit dynamischem Speicher gelöst werden, ist ein Controller mit kleinem RAM leicht überfordert, so dass was eigenes, auf deine tatsächliche Aufgabe zugeschnittenes, ( und dann natürlich handgestrickt ) der einfachere Ansatz ist.

( Noch ein paar Tips was du wirklich willst, und jurs bastelt evtl. eine Demo, die nicht mehr optimiert werden kann und muss ) ;)

Was meinst Du mit

beliebiger ... und Geschwindigkeit an ihn gesendet werden.

Die Baudrate der seriellen Schnittstelle muß zwischen Sender und Empfänger übereinstimmen. Grüße Uwe

Chris72622: Vielleicht habt ihr mir ja ein paar Schlagworte nach denen ich suchen kann.

  • Scheduler
  • Round Robin Scheduling
  • EVA-Prinzip bzw. IPO principle
  • Kooperatives Multitasking

Daaankeee! :wink:

Gruß Chris

Chris72622: Daaankeee! :wink:

Gruß Chris

Ich weiß jetzt nicht genau, um was es Dir geht.

Wenn es Dir nur um ein Pseudo-Multitasking geht, dass also "verschiedene Programme" zur gleichen Zeit quasi "parallel" ausgeführt werden, und jedes Programm für sich unabhängig gestartet und beendet werden kann, schaue Dir mal das hier gepostete Programmgrundgerüst an!

Vom Konzept her ist das Grundgerüst bereits auf Pseudo-Multitasking ausgelegt, ich habe es nur aufgrund der Vorgabe des Thread-Starters "nur ein Programm zur selben Zeit" auf Single-Tasking beschränkt. Das könnte ich auch als leicht geändertes Grundgerüst posten für - Eingabe über "Serial" statt über Tastschalter - Pseudo-Multitasking mehrer aktiver Programme statt Single-Tasking

Schwieriger würde es eigentlich nur dann werden, wenn Du sowohl ein Pseudo-Multitasking benötigst als auch ein Warteschlangenkonzept. Das wäre zum Beispiel der Fall, wenn nicht alle Programme zur selben Zeit laufen können und Du Befehle "auf Vorrat" in eine Warteschlange senden möchtest. Und das Programm soll dann selbst entscheiden, welche Programme parallel laufen können und bei welchen erst auf den Abschluss eines anderen Programms gewartet werden muss.

Mal angenommen, Du hast die Programme A, B, C und D, wovon A mit B zusammen laufen kann, und C mit D, und jedes Programm würde 10 Sekunden laufen. Nun sendest Du mit je 5 Sekunden Abstand die Befehle A, B, C, D und der Ablauf wäre wie folgt: Befehl A bei 0s ==> Programm A startet bei 0s, endet bei 10s Befehl B bei 5s ==> Programm B startet bei 5s, endet bei 15s Befehl C bei 10s ==> Programm C startet bei 15s, endet bei 25s (Befehl C wartet auf das Ende von B, weil es nicht zusammen mit B laufen kann) Befehl D bei 15s ==> Programm D startet bei 15s, endet bei 25s

Wenn nicht alle Programme gleichzeitig laufen können, mußt Du sowohl Datenstrukturen darüber anlegen, welche Programme mit welchen anderen parallel laufen können (oder welche nicht mit anderen können), und Du mußt eine Warteschlange anlegen, die ggf. erst auf das Ende von nicht-kompatiblen Programmen warten, bevor ein neues Programm gestartet werden kann.

Aber der Aufwand ist für ein normales Pseudo-Multitasking, bei der alle Programme gleichzeitig laufen können, nicht notwendig. Sondern für ein flüssiges Pseudo-Multitasking ist nur notwendig, dass jedes Programm unabhängig von anderen zu jedem Zeitpunkt ein/aus geschaltet werden kann, und dass bei der Verarbeitung von Programmschritten keine blockierenden Befehle wie delay(), pulseIn(), Serial.findUntil() oder ähnlicher Quatsch verwendet wird, der den Programmablauf blockieren würde.

Wenn du Befehlen wirklich eine unterschiedliche Priorität unabhängig von der Reihenfolge zuweisen willst, kannst du dir auch mal das ansehen: Priority Queue

Im Grunde ist erst mal eine normale Warteschlange. Hier würde eine einfach verkettete Liste reichen (ein Heap lohnt sich erst wenn es wirklich umfangreich wird). Aber jedes Element hat zusätzlich noch eine Priorität.

Wie man dann vorgeht kann variieren. Am einfachsten ist es man sortiert die Elemente beim Eintreffen nach der Priorität ein. Dann muss man danach nicht mehr aufwendig suchen. Die Priorität kann auch die Laufzeit der Aktion sein. Man kann z.B. kurze Aktionen immer zuerst machen.

Um die Aktion auszuführen kann dann jedes Element gleich einen Zeiger auf die entsprechende Funktion haben.

Bei der Implementierung wie gesagt erst mal mit einer ganzen normalen Queue/Warteschlange anfangen

Wenn Befehle nur nach der Reihenfolge des Eintreffens verwaltet werden müssen reicht ein Stack (LIFO) oder irgendeine FIFO Implementierung (z.B. ein Ringpuffer aus Funktionszeigern)

Ihr habt Euch solche Mühe gemacht- recht herzlichen Dank für Eure Antworten zunächst einmal.

Momentan bin ich noch dabei jurs' Schlagwortsammlung zu durchleuchten um hilfreiche Tipps/Links zu meinem Problem zu finden.

Des weiteren werde ich versuchen meine Anforderung noch etwas zu konkretisieren. Manchmal beginnen die Schwierigkeiten für mich einfach bereits im formulieren einer entsprechenden Frage, sorry.

Gruß Chris

jurs: - Scheduler - Round Robin Scheduling - EVA-Prinzip bzw. IPO principle - Kooperatives Multitasking

Hierzu stieß ich auf Links, die sich in erster Linie mit parallelen laufenden Prozessen beschäftigen. Dies löst leider offensichtlich noch nicht mein Warteschlangen-Problem. Der im Bezug auf mein Problem vielversprechendste Link scheint momentan der hier zu sein. Momentan bin ich da noch am durchgucken, da doch (für mich als Laien) etwas umfangreich.

jurs: Schwieriger würde es eigentlich nur dann werden, wenn Du sowohl ein Pseudo-Multitasking benötigst als auch ein Warteschlangenkonzept.

Ja, genau das ist der Fall. Dein Beispiel mit "A, B, C und D" entspricht genau meinem Problem.

jurs: Wenn nicht alle Programme gleichzeitig laufen können, mußt Du sowohl Datenstrukturen darüber anlegen, welche Programme mit welchen anderen parallel laufen können (oder welche nicht mit anderen können), und Du mußt eine Warteschlange anlegen, die ggf. erst auf das Ende von nicht-kompatiblen Programmen warten, bevor ein neues Programm gestartet werden kann.

Genau hierfür suche ich eine Lösung (am Besten auf "arduinoischer" Basis was die Sprache angeht).

Serenifly: Wenn du Befehlen wirklich eine unterschiedliche Priorität unabhängig von der Reihenfolge zuweisen willst, kannst du dir auch mal das ansehen:

Priority Queue

Danach suche ich momentan noch.. leider bin ich noch nicht wirklich fündig geworden.

Ihr seid mir eine große Hilfe. :)

Gruß Chris

Chris72622:
Ja, genau das ist der Fall. Dein Beispiel mit “A, B, C und D” entspricht genau meinem Problem.

Genau hierfür suche ich eine Lösung (am Besten auf “arduinoischer” Basis was die Sprache angeht).

Und die zu startenden Programme A B C und D sind strikt zeitgesteuerte Programme, die nach einer gewissen Zeit von selbst enden, nachdem sie gestartet wurden? Also ohne dass Du Abbruchbefehle zum Beenden der Programme sendest?

Oder möchtest Du nicht nur Startbefehle für die Programme senden
A ==> Starte ProgA wenn möglich
B ==> Starte ProgB wenn möglich
C ==> Starte ProgC wenn möglich
D ==> Starte ProgD wenn möglich
Wenn Start nicht möglich, Startanforderung in eine Warteschlange einstellen

Sondern auch die Stopp-Befehle sollen von Dir gesendet werden:
a ==> Stoppe ein laufendes ProgA
b ==> Stoppe ein laufendes ProgB
c ==> Stoppe ein laufendes ProgC
d ==> Stoppe ein laufendes ProgD
Wenn Stopp nicht möglich (weil das Programm nicht läuft), entferne alle Startanforderungen für das entsprechende Programm aus der Warteschlange

Als erstes müßtest Du die Programmlogik fehlerfrei formulieren können, wie die Abläufe erfolgen sollen.

Und wenn es so ist, dass Du bei vorhandener Warteschlange auch noch Befehle empfangen möchtest, deren Ausführung vorgezogen werden soll, z.B. Abbruchbefehle für laufende Programme, bzw. Cancel-Anforderungen für Startbefehle in der Warteschlange, brauchst Du nicht nur eine Warteschlange sondern auch ein Prioritätenkonzept, um unterscheiden zu können welche Befehle “in die Warteschlange” gehen sollen und welche Befehle “sofort ausgeführt” werden sollen.

Entscheidende Fragen stellst Du. Ich werde mal versuchen ein entsprechendes Flussdiagramm zu zeichnen.

Gruß Chris

So,

ich habe nun mal versucht das Ganze etwas zu strukturieren.

void loop()
{
  cmd_input();  // Nimmt zuerst eingehende Befehle entgegen (gelber Ablauf)
  prg_check();  // Löst anschließend die einzelnen Programme aus (cyaner Ablauf)
}

Die einzelnen, durch die eintreffenden Befehle zu startenden Programme werden nicht über weitere eingehende Befehle beendet, sondern beenden sich von alleine.

Gruß Chris

hi,

deshalb ist es so wichtig bei diesen dingen, sich vorher genau zu überlegen, was man erreichen will, und auch die bezeichnungen dafür einzuhalten.

auf den ersten blick hat “priorität” bei dir nichts mit priorität zu tun, sondern legt fest, welche programme einander ausschließen. also wenn zum beispiel A durch B ersetzt wird.

damit ist noch nicht gesagt, was passiert, wenn A nicht in der liste ist und B eintrifft. soll B dann vor den anderen gereiht werden?

weiters: kann es auch befehle geben, die gleiche priorität in der reihenfolge haben, aber einander nicht ausschließen? also einfach in der reihenfolge ihres eintreffens ausgeführt werden sollen (sobald alle höher priorisierten befehle abgearbeitet wurden)?

weiters: Du löscht A, wenn B eintrifft. könnte es auch den fall geben, daß ein eintreffendes B nicht ausgeführt werden soll, wenn A schon in der liste ist?

das ganze ist garnicht so trivial, wenn man es klug und übersichtlich machen will.

gruß stefan

Eisebaer: damit ist noch nicht gesagt, was passiert, wenn A nicht in der liste ist und B eintrifft. soll B dann vor den anderen gereiht werden?

Ja.

Eisebaer: weiters: kann es auch befehle geben, die gleiche priorität in der reihenfolge haben, aber einander nicht ausschließen?

Nein.

Eisebaer: weiters: Du löscht A, wenn B eintrifft. könnte es auch den fall geben, daß ein eintreffendes B nicht ausgeführt werden soll, wenn A schon in der liste ist?

Nein. "B" sollte in diesem Fall "A" ersetzen, da beide dieselbe Priorität haben.

Gruß Chris

Bzgl. Priority Queue fand ich nun lediglich das hier.

Eine Warteschlange mit Prioritätenmanagement ist letzten Endes das, was ich benötige.

Ob ich mir aufgrund einer Warteschlange ein solches OS-Monster (s.o.)ins Boot holen soll, wage ich jedoch schwer zu bezweifeln.

Bin auf der Suche nach einer weniger schwergewichtigen Lösung.

Gruß Chris

Ob ich mir aufgrund einer Warteschlange ein solches OS-Monster (s.o.)ins Boot holen soll, wage ich jedoch schwer zu bezweifeln. Bin auf der Suche nach einer weniger schwergewichtigen Lösung.

Ist zwar toll, dass man so viel Zeug findet. Ist aber auch gut, dass man alles relativ leicht selber machen kann.

Fremden Code komplett verstehen ist auch nicht wesentlich einfacher als genau das was man braucht neu zu machen. Bleibe bei meiner Antwort #1

Was anderes ist natürlich, sich fertige Sachen anzusehen und zu überlegen, ob die Vorstellungen über die eigenen Bedürfnisse nicht doch so angepasst werden können, dass es schon passt. Hast du dir mal das ArdOS angeschaut? Wie gross ist z.B. der Flash Bedarf für das BigExample im Tutorial?

Eine Warteschlange mit Prioritätenmanagement ist letzten Endes das, was ich benötige.

Das sehe ich nicht in deinen Texten.

auf den ersten blick hat "priorität" bei dir nichts mit priorität zu tun, sondern legt fest, welche programme einander ausschließen.

Das sehe ich allerdings.

Du solltest über die Verwendung des Wortes "Priorität" nochmal nachdenken.

Ich glaube, du suchst die Verriegelung von Ressourcen mit Semaphoren.

Schau dir mal die Protothreads an. Da gibts dann auch sofort Semaphoren dazu. Und das ist recht leichtgewichtig.

Man kann das auch mit einer verketteten Liste selbst programmieren. Das ist nicht sooo schwer. Ich habe hier mal ein Grundgerüst einer Liste programmiert:

class LinkedList
{
public:
  LinkedList();
  ~LinkedList();
  void add(int element);
  void removeFirst();
  void printList();

private:
  class Node
 {
  public:
    Node(int data);
    int data;
    Node* next;
  private:
  };

  Node* head;
};
#include "Arduino.h"

LinkedList::LinkedList()
{
  this->head = NULL;
}

LinkedList::~LinkedList()
{
  if (head != NULL)
  {
    Node* current = this->head;
    Node* del;

    do
    {
      del = current;
      current = current->next;
      delete del;
    }
    while (current != NULL);
  }
}

void LinkedList::add(int element)
{
  Node* newNode = new Node(element);

  if (head == NULL)
    head = newNode;
  else
  {
    Node* current = this->head;
    while (current->next != NULL)
      current = current->next;

    current->next = newNode;
  }
}

void LinkedList::removeFirst()
{
  if (head != NULL)
  {
    Node* del = head;
    head = head->next;
    delete del;
  }
}

void LinkedList::printList()
{
  Node* current = this->head;
  while (current != NULL)
  {
    Serial.println(current->data);
    current = current->next;
  }
}

LinkedList::Node::Node(int data)
{
  this->data = data;
  this->next = NULL;
}

Das muss man natürlich anpassen und erweitern. Ist wirklich nur rudimentär! Die etwas komplizierteren Fälle habe ich weggelassen. Vor allem das Einfügen und Löschen von Elementen in der Mitte.

Im Moment wird ein neues Element einfach hinten eingefügt und man kann nur das erste Löschen. Die Liste ist also unsortiert. Hier müsste man nun einen neues Element zwischen anderen Elementen einfügen (oder ganz vorne am Anfang der Liste).

Man kann das auch effizienter machen, aber das ist hier nicht so wichtig.

Tip: Erst mal in Visual C++ testen ob alles geht (da kann man auch nach Memory Leaks) testen und erst dann auf den Arduino portieren.

Beim Portieren nicht vergessen, dass es auf dem Arduino keine Exceptions und kaum RAM gibt. ( new ) ;)

Bezüglich Mutex oder Semaphore (Mutex ist hier vielleicht etwas korrekter, da eine Semaphore x Tasks auf eine Resource zugreifen lässt):

Es stimmt zwar das das wesentlich einfacher ist und vielleicht die bessere Lösung, aber auch da braucht man irgendeinen Puffer für eintreffende Tasks während die aktuelle bearbeitet wird. Im einfachsten Fall ist das ein FIFO Puffer, was ein triviales Problem ist und über ein Array lösbar ist.

Da ist dann die Frage ob die eingehenden Tasks wirklich sortiert werden müssen oder nach FIFO abgearbeitet werden können. Nur für den ersten Fall braucht man wirklich eine Liste. Einen FIFO kann man auch simpel als Ringpuffer anlegen.