Implementierung eines statischen Ablaufplaners ("Schedulers") innerhalb eines Übersetzers einer Sprache mit blockierenden Threads

BearbeiterIn:Felix Sauer
Titel:Implementierung eines statischen Ablaufplaners ("Schedulers") innerhalb eines Übersetzers einer Sprache mit blockierenden Threads
Typ:masters thesis
Betreuer:Veldema, R.; Blaß, T.; Philippsen, M.
Status:abgeschlossen am 1. Oktober 2015
Vorausetzungen:
Thema:

Voraussetzungen
Systeme, welche sogenannten harten Echtzeitbedingungen unterliegen, müssen extrem zuverlässig sein. Die Berechnungen des Systems haben harte zeitliche Fristen, deren Einhaltung garantiert werden muss. Dementsprechend ist nichtdeterministisches Verhalten zur Laufzeit unerwünscht, da es die Vorhersagbarkeit des Systemverhaltens unmöglich macht.
Die Vorhersagbarkeit dieser Systeme wird in der Praxis häufig mit Hilfe von statischen Ablaufplanern zugesichert, welche die Ablaufstränge ("Threads") und die Ereignisse während der Übersetzung auf die vorhandenen Prozessoren (bzw. Kerne) fix verteilen. Zur Laufzeit wird der berechnete Ablaufplan ausgeführt und nicht mehr verändert. Für ein System mit mehreren Kernen wird dabei je eine Methode pro Kern generiert. Innerhalb dieser Methoden werden die dem Kern zugewiesenen Berechnungen in einer Endlosschleife abgearbeitet, siehe folgendes Beispiel für 2 Kerne:

//Methode für den ersten Kern
void kern0() {
while(1) {
//Anweisungen des ersten Kerns
}
}

//Methode für den zweiten Kern
void kern1() {
while(1) {
//Anweisungen des zweiten Kerns
}
}
Die konkrete Aufteilung der Anweisungen eines Programms erfolgt schrittweise. Gegeben sei ein Arbeitspaket "foo", welcher periodisch alle 3 Millisekunden (= "periodOfFoo") ausgeführt werden soll. Für dieses Paket wird ein freier Kern gesucht und in dessen while-Schleife wird es eingefügt, z.B. bei kern0. Ein weiteres Arbeitspaket "bar" mit Periode "periodOfBar" 1 Millisekunde kann auf dem zweiten Kern platziert werden, sofern die einzelnen Laufzeiten der Pakete sowie deren Summe stets unter 1 Millisekunde liegt. Es ergibt sich beispielsweise folgender Quelltext:

void kern0() {
while(1) {
foo();
wait periodOfFoo - timeOfFoo;
}
}

void kern1() {
while(1) {
bar();
wait periodOfBar - timeOfBar;
}
}

In diesem Szenario sind beide Kerne beschäftigt. Wie bei der nebenläufigen Ausführung üblich, können Sichtbarkeitsprobleme auftreten, welche im Rahmen der Arbeit gelöst werden sollen. Sei ein drittes Arbeitspaket "zoo" mit einer maximalen Ausführungszeit (Worst case execution time, WCET(zoo)) gegeben, das so häufig wie möglich ausgeführt werden soll (sofern Rechenkapazität zur Verfügung steht). Falls "zoo" und "bar" zusammen höchstens 1 Millisekunde erfordern, dann lassen sich diese beiden Pakete mit dem folgenden Quelltext zusammen auf dem zweiten Kern platzieren:
void kern1() {
while (1) {
long deadline = currentTime() + periodOfBar;
bar();
//now we can execute zoo repeatedly
while (currentTime + WCET(zoo) <= deadline) {
zoo();
}
wait deadline - currentTime();
//now the exact period of bar has passed
}
}

Das Arbeitspaket "zoo" wird bei dieser Variante in dem Zeitraum nach der Beendigung von "bar" bis zum Ablauf der Periode von "bar" ausgeführt. Dabei wird vor jeder Ausführung von "zoo" dessen maximale Ausführungszeit herangezogen, um die Frist von "bar" zu garantieren. Insgesamt entsteht eine Schleife, die verlässlich jede Millisekunde ausgeführt wird.
Obige Ablaufpläne beruhen auf der Annahme, dass die Laufzeiten nach oben begrenzt werden können. Falls diese Abschätzung zum Übersetzungszeitpunkt jedoch nicht möglich ist, dann führt dies im Umfeld der Echtzeitsysteme zu Problemen. Zum Beispiel könnte das Paket "zoo" auf eine Bedingung wartet, welche wiederum durch den periodischen Task "bar" beeinflusst wird:

void zoo() {
prepare();
wait a == 0;
action();
}

void bar() {
a++;
if (a == 10) a = 0;
}

Falls die Bedingung zu Beginn der Ausführung von "zoo" nicht erfüllt ist, dann blockiert die Ausführung des Pakets und somit auch der zugehörige Kern. Dadurch werden alle dem Kern zugeordneten Pakets blockiert, wodurch ggf. periodische Pakete ihre Frist verletzen können (z.B. durch einen Deadlock, falls "bar" auf dem gleichen Kern liegt). Somit können die beiden Pakete nicht ohne Weiteres zusammen auf einem Kern platziert werden.
Zur Lösung dieses Problems bietet sich zum Beispiel eine Aufteilung von "zoo" in zwei Teile an. Dabei wird ein Bitflag "zoowaitingbit" genutzt, welches eine Ausführung des ersten Teiles anzeigt und in die Bedingung des zweiten Teiles des Tasks aufgenommen wird:

void zooAnfang() {
prepare();
zooWaitingBit = true;
}

// Vorbedingung zum Einplanung der Methodenausführung:
// a == 10 && zooAnfangBit
void zooEnde() {
action();
zooWaitingBit = false;
}

Der Übersetzer mit dem statischen Ablaufplaner muss in dem für "bar" und "foo" generierten Quelltext an jeder Stelle, bei der die Wartebedingung von "zoo" auf wahr gesetzt wird, einen Aufruf von "zooEnde" einfügen. Darüber hinaus muss auch den den Stellen ein Aufruf von "zooEnde" eingefügt werden, in denen die Bedingung bearbeitet wird, ihr Wert jedoch anschließend true oder false sein kann. In diesem Fall muss der entsprechende Aufruf von "zooEnde" zusätzlich mit einer Fallunterscheidung zur Laufzeit getestet werden muss. Neben der allgemeinen Bestimmung der relevanten Einfügestellen, ist diese Unterscheidung zwischen zwingender und möglicher Erfüllung nicht trivial.

Aufgaben
Die Arbeit baut auf eine Programmiersprache mit zugehörigem Laufzeitsystem auf, die sich in der Entwicklung befindet. Die derzeitige Implementierung ist naiv, d.h. pro Arbeitspaket wird ein Aufgabenstrang mit einer while-Schleife gestartet. Da jedoch üblicherweise weniger Kerne als Pakete zur Verfügung stehen, können die Echtzeitbedingungen in diesem Umfeld noch nicht garantiert werden. Folglich ist die Implementierung eines statischen Ablaufplaners die erste Aufgabe.
In der vorliegenden Programmiersprache kann der oben eingeführte wait-Befehl flexibel eingesetzt werden. Mögliche Einsatzgebiete sind das Warten auf Bedingungen, auf den Ablauf einer Zeitspanne, auf das Beenden eines anderen Pakets, usw. Die zweite Aufgabe ist daher eine Transformation aller blockierenden und wartenden Anweisungen eines Quelltextes auf die oben vorgestellte Weise.

Literatur
1. Yu-Kwong Kwok and Ishfaq Ahmad: "Static scheduling algorithms for allocating directed task graphs to multiprocessors", ACM Computing Surveys, Volume 31, Issue 4, pp. 406 - 471, Dec. 1999 Link:http://doi.acm.org/10.1145/344588.344618
2. Marco Sgroi, Luciano Lavagno, Yosinori Watanabe, and Alberto Sangiovanni-Vincentelli: "Synthesis of Embedded Software Using Free-Choice Petri Nets", Proceedings of the 36th Design Automation Conference Design Automation Conference (DAC 1999), pp. 805 - 810, 1999 Link: http://www-inst.cs.berkeley.edu/~ee249/fa08/discussions/PetriNets-Sgroi99synthesis.pdf
3. Lin Huang and Michael J. Oudshoorn: "Static Scheduling of Conditional Parallel Tasks", Chinese Journal of Advanced Software Research, Volume 6, Number 2, 1999, pp. 121 - 129 Link: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.3341&rep=rep1&type=pdf

Meilensteine

  • Einarbeitung in das Themengebiet der statischen Ablaufplanung und in die relevanten Techniken.
  • Einarbeiten in die am Lehrstuhl 2 entwickelte Sprache sowie den zugehörigen Übersetzer.
  • Implementierung einer einfachen statischen Ablaufplanung ohne den wait-Befehl.
  • Erweiterung des statischen Ablaufplaners um die Behandlung des wait-Befehls.
  • Transformation aller blockierenden Befehle (z.B., sleep(), joinThread(), usw.) in wait-Befehle (wie oben vorgestellt).
  • Messungen (Analyse der Laufzeiten sowie der Qualität der generierten Ablaufpläne).
  • Verfassen der Ausarbeitung.
watermark seal