2.2 Berechnungsmodelle
41
Abb. 2.3 Task-Graph mit
Ein/Ausgabeknoten und
-kanten
τ
τ
τ
τ
τ 1
5
2
4
3
3. Exklusiver Zugriff auf Ressourcen: Berechnungen können einen exklusiven Zugriff auf eine Ressource anfordern, etwa auf ein Ein/Ausgabegerät oder auf einen
Speicherbereich zur Kommunikation. Informationen über eventuell notwendige
exklusive Zugriffe sollten beim Scheduling berücksichtigt werden. Durch die
Verwendung dieser Information kann man z.B. das Problem der Prioritätsumkehr vermeiden (siehe Seite 233). Solche Informationen über exklusiven Zugriff
können auch in Task-Graphen dargestellt werden.
4. Periodische Abläufe: Viele Berechnungen, insbesondere im Bereich der digitalen Signalverarbeitung, sind periodisch. Man muss also genauer zwischen einer
Task und ihrer Ausführung unterscheiden – letztere wird häufig als Job bezeichnet [349]5. Task-Graphen für solche Schedules sind unendlich groß. Abb. 2.4
zeigt einen Task-Graphen mit den Jobs J n−1 bis J n+1 einer periodischen Task.
Abb. 2.4 Task-Graph mit
Jobs (Ausführungen) einer
periodischen Task
1
-1
n+
J
n
J
J
...
....
n
5. Hierarchische Knoten: Die Komplexität der Berechnungen, die in einem Knoten ausgeführt werden, kann sehr unterschiedlich sein. Einerseits können die
beschriebenen Programme sehr groß sein und Tausende von Codezeilen enthalten. Andererseits kann man Programme in kleine Programmteile aufteilen, sodass
im Extremfall jeder Knoten nur genau einer Operation entspricht. Die Komplexität von Knoten im Graphen heißt Granularität. Die Frage, welche Granularität
man verwenden sollte, lässt sich nicht allgemeingültig beantworten. Für einige
Zwecke sollte die Granularität so grob wie möglich sein, etwa wenn die Knoten
Prozesse eines Echtzeitbetriebssystems darstellen. In diesem Fall sollten die Knoten große Programmteile enthalten, um die Anzahl der Kontextwechsel zwischen
den Prozessen gering zu halten. Für andere Anwendungen kann es sinnvoll sein,
wenn jeder Knoten nur eine Operation enthält, etwa wenn die Knoten entweder
als Hardware oder als Software realisiert werden sollen. Wenn eine bestimmte Operation (z.B. die häufig vorkommende Diskrete Cosinus-Transformation
(DCT)) auf eine Spezialhardware abgebildet werden kann, dann sollte sie nicht
in einem großen Knoten mit vielen anderen Operationen versteckt sein. Vielmehr
5 Präzisierungen erfolgen in den Definitionen 4.4 und 6.1.
41
Abb. 2.3 Task-Graph mit
Ein/Ausgabeknoten und
-kanten
τ
τ
τ
τ
τ 1
5
2
4
3
3. Exklusiver Zugriff auf Ressourcen: Berechnungen können einen exklusiven Zugriff auf eine Ressource anfordern, etwa auf ein Ein/Ausgabegerät oder auf einen
Speicherbereich zur Kommunikation. Informationen über eventuell notwendige
exklusive Zugriffe sollten beim Scheduling berücksichtigt werden. Durch die
Verwendung dieser Information kann man z.B. das Problem der Prioritätsumkehr vermeiden (siehe Seite 233). Solche Informationen über exklusiven Zugriff
können auch in Task-Graphen dargestellt werden.
4. Periodische Abläufe: Viele Berechnungen, insbesondere im Bereich der digitalen Signalverarbeitung, sind periodisch. Man muss also genauer zwischen einer
Task und ihrer Ausführung unterscheiden – letztere wird häufig als Job bezeichnet [349]5. Task-Graphen für solche Schedules sind unendlich groß. Abb. 2.4
zeigt einen Task-Graphen mit den Jobs J n−1 bis J n+1 einer periodischen Task.
Abb. 2.4 Task-Graph mit
Jobs (Ausführungen) einer
periodischen Task
1
-1
n+
J
n
J
J
...
....
n
5. Hierarchische Knoten: Die Komplexität der Berechnungen, die in einem Knoten ausgeführt werden, kann sehr unterschiedlich sein. Einerseits können die
beschriebenen Programme sehr groß sein und Tausende von Codezeilen enthalten. Andererseits kann man Programme in kleine Programmteile aufteilen, sodass
im Extremfall jeder Knoten nur genau einer Operation entspricht. Die Komplexität von Knoten im Graphen heißt Granularität. Die Frage, welche Granularität
man verwenden sollte, lässt sich nicht allgemeingültig beantworten. Für einige
Zwecke sollte die Granularität so grob wie möglich sein, etwa wenn die Knoten
Prozesse eines Echtzeitbetriebssystems darstellen. In diesem Fall sollten die Knoten große Programmteile enthalten, um die Anzahl der Kontextwechsel zwischen
den Prozessen gering zu halten. Für andere Anwendungen kann es sinnvoll sein,
wenn jeder Knoten nur eine Operation enthält, etwa wenn die Knoten entweder
als Hardware oder als Software realisiert werden sollen. Wenn eine bestimmte Operation (z.B. die häufig vorkommende Diskrete Cosinus-Transformation
(DCT)) auf eine Spezialhardware abgebildet werden kann, dann sollte sie nicht
in einem großen Knoten mit vielen anderen Operationen versteckt sein. Vielmehr
5 Präzisierungen erfolgen in den Definitionen 4.4 und 6.1.