Das Scheduling von Prozessen und deren Jobs in Realzeitsystemen ist zu einem wichtigen Bereich der Forschung geworden. Die Frage dabei ist, wie können verschiedene Prozesse gemeinsam auf externe Ressourcen zugreifen, ohne dass das System seine Konsistenz verliert und trotzdem alle Aufgaben rechtzeitig erledigt werden? Zwei wesentliche Lösungsansätze die sich ergeben haben, sind 'Lock-Based' und 'Lock-Free' Verfahren. Bei ersteren wird seitens des Betriebssystems darauf geachtet, dass möglichst alle Jobs ihre Deadline erreichen, bei den anderen wird diese Aufgabe von den Prozessen
selbst erledigt.
Im folgenden werden kurz die Schwierigkeiten bei der Verwendung von 'Lock-Based' Verfahren dargestellt und es wird eine Lösung dieser Schwierigkeiten mittels des 'Priority Ceiling Protocol' (PCP) von Rajkumar et al. [2] angeboten. Dieses Protokoll wird später auch für den Vergleich mit den 'Lock-Free' Verfahren herangezogen.
Die 'Lock-Free' Verfahren, die zunächst recht unberechenbar scheinen und möglicherweise kaum als Konkurrenz zu den bisherigen Verfahren angesehen werden könnten, da sie ohne Kontrolle seitens des Betriebssystems auf gemeinsame Ressourcen zugreifen, sollen deshalb genauer analysiert werden. Dazu wird neben einigen Voraussetzungen gezeigt, dass das Verhalten dieser 'Lock-Free' Prozesse keinesfalls chaotisch und zeitlich begrenzt ist. Anschließend werden die Bedingungen verfeinert und auf verschiedene Schedulingalgorithmen angepasst. Dadurch wird ein formaler Vergleich zwischen 'Lock-Free' und 'Lock-Based' Verfahren möglich, der abschließend auch in einem experimentellen Vergleich bestätigt wird.
Inhaltsverzeichnis
1 Einleitung
2 Lock-Based Verfahren
2.1 Das Priority Ceiling Protocol
3 Lock-Free Verfahren
3.1 Definitionen und Voraussetzungen
3.1.1 Lemma
3.1.2 Lemma
3.1.3 Lemma
3.1.4 Lemma
3.2 Scheduling unter statischen Bedingungen
3.2.1 Satz (Notwendig unter RM)
3.2.2 Satz (Hinreichend unter RM)
3.2.3 Satz (Hinreichend unter DM)
3.3 Scheduling unter dynamischen Bedingungen
3.3.1 Satz (Notwendig unter EDF)
3.3.2 Satz (Hinreichend unter EDF)
3.3.3 Satz (Hinreichend unter EDF, wenn Deadlines und Perioden nicht übereinstimmen)
4 Lock-Based und Lock-Free im Vergleich
4.1 Scheduling mit statischen Prioritäten
4.2 Scheduling mit dynamischen Prioritäten
5 Experimenteller Vergleich
5.1 Aufbau des Experiments
5.2 Scheduling mit statischen Prioritäten
6 Zusammenfassung und Auswertung
Zielsetzung & Themen
Die Arbeit untersucht das Scheduling von Prozessen in Realzeitsystemen unter Verwendung von Lock-Based- und Lock-Free-Verfahren, um zu klären, wie Prozesse gemeinsam auf externe Ressourcen zugreifen können, ohne die Systemkonsistenz zu gefährden oder Zeitanforderungen zu verletzen.
- Vergleichende Analyse von Lock-Based (PCP) und Lock-Free-Verfahren.
- Untersuchung der Schedulierbarkeit unter verschiedenen Bedingungen (RM, DM, EDF).
- Formale Herleitung von Bedingungen für den Zeitbedarf von Lock-Free-Operationen.
- Experimentelle Evaluierung anhand eines Videokonferenzsystems.
- Bewertung von Vorteilen wie dynamischer Task-Hinzufügung bei Lock-Free-Verfahren.
Auszug aus dem Buch
3.1 Definitionen und Voraussetzungen
Bevor mit den Aufwandsabschätzungen begonnen werden kann, müssen zunächst die geltenden Parameter festgelegt werden. Eine Task ist dabei ein sequentielles Programm, welches wiederholt ausgeführt wird. Jede einzelne Ausführung wird dabei als Job bezeichnet, wobei der jeweilige Beginn des Jobs als Startzeitpunkt bezeichnet wird. Ist dabei die Zeit zwischen den Startzeitpunkten konstant, ist die Task periodisch. Durchläuft ein Job einen retry loop, der nicht erfolgreich abgeschlossen wurde, so erfuhr dieser eine Interferenz. Ein Satz von Tasks ist genau den schedulierbar, wenn keine der Tasks die jeweilige Deadline überschreitet. Weiterhin gilt für folgende Symbole:
N : Die Anzahl der Tasks in einem System. Die Verwendeten Indizes i und j gehen, sofern nicht anders erwähnt, über das Feld {1,...,N}.
Ti : Die ite Task im System.
pi : Die Periode von Task Ti. Tasks sind in nichtabnehmender Reihenfolge sortiert, d.h. pi < pj => i < j.
ri(k): Die Zeit, in der der kte Job von Ti startet. Es gilt ri(k) = ri(1) + (k - 1) * pi, mit k >= 1.
Ji,k : Der kte Job der Task Ti.
ci : Der ungünstigste Fall bezüglich der Rechenzeit, wenn Ti die einzige Task auf dem Prozessor wäre.
Zusammenfassung der Kapitel
1 Einleitung: Die Einleitung motiviert das Scheduling-Problem in Realzeitsystemen und stellt Lock-Based- sowie Lock-Free-Ansätze als wesentliche Lösungsstrategien vor.
2 Lock-Based Verfahren: Dieses Kapitel erläutert das Priority Ceiling Protocol (PCP) zur Vermeidung von Deadlocks und Prioritätsinversionen bei ressourcenkonkurrierenden Prozessen.
3 Lock-Free Verfahren: Hier werden Lock-Free-Verfahren definiert, ihr Zeitverhalten auf Einprozessor-Systemen analysiert und Bedingungen für die Schedulierbarkeit unter verschiedenen Algorithmen (RM, DM, EDF) hergeleitet.
4 Lock-Based und Lock-Free im Vergleich: Dieses Kapitel vergleicht den Overhead der beiden Verfahren unter verschiedenen Scheduling-Prioritäten, wobei Lock-Free-Ansätze formal gegen das PCP-Verfahren abgewogen werden.
5 Experimenteller Vergleich: Anhand der Implementierung in einem Echtzeit-Videokonferenzsystem wird die theoretische Schedulierbarkeit beider Ansätze experimentell überprüft und validiert.
6 Zusammenfassung und Auswertung: Das abschließende Kapitel resümiert, dass Lock-Free-Verfahren hinsichtlich Effizienz und Flexibilität konkurrenzfähig sind, nennt jedoch die Notwendigkeit spezieller Implementierung und Einschränkungen bei verschachtelten Zugriffen.
Schlüsselwörter
Scheduling, Realzeitsysteme, Lock-Based, Lock-Free, Priority Ceiling Protocol, Schedulierbarkeit, RM-Verfahren, DM-Verfahren, EDF-Verfahren, Interferenz, Retry Loops, Prozesskommunikation, Videokonferenzsystem.
Häufig gestellte Fragen
Worum geht es in der Arbeit grundlegend?
Es geht um die Untersuchung und den Vergleich von Lock-Based- und Lock-Free-Verfahren für den Zugriff auf gemeinsame Ressourcen in Echtzeitsystemen.
Was sind die zentralen Themenfelder?
Die Arbeit fokussiert sich auf Scheduling-Algorithmen, die Vermeidung von Prioritätsinversionen, die Analyse der Schedulierbarkeit und den Vergleich der Performance dieser Ansätze.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist es, nachzuweisen, dass Lock-Free-Verfahren in Echtzeitsystemen eine effiziente Alternative zu Lock-Based-Methoden darstellen, und dies formal sowie experimentell zu untermauern.
Welche wissenschaftlichen Methoden werden verwendet?
Die Arbeit nutzt mathematische Modellierung und formale Herleitungen für Schedulierbarkeitsbedingungen sowie eine praktische experimentelle Evaluierung an einem realen Videokonferenzsystem.
Was wird im Hauptteil behandelt?
Der Hauptteil behandelt die theoretischen Grundlagen des PCP, die Analyse von Lock-Free-Operationen mittels Wiederholungsschleifen (retry loops) und den Vergleich der Verfahren unter statischen und dynamischen Prioritäten.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die wichtigsten Begriffe sind Scheduling, Realzeitsysteme, Lock-Based, Lock-Free, Prioritätsinversion und Schedulierbarkeit.
Wie unterscheidet sich das Lock-Free-Verfahren in Bezug auf die Systemtabellen-Berechnung?
Im Gegensatz zum PCP-Verfahren ist bei Lock-Free-Objekten keine Kenntnis darüber erforderlich, welche Task auf welches Objekt zugreift, was eine dynamische Hinzufügung von Tasks ohne Neuberechnung von Systemtabellen ermöglicht.
Was zeigt das Experiment mit dem Videokonferenzsystem?
Das Experiment zeigt, dass Lock-Free-Verfahren in der Praxis dem PCP-Verfahren in nichts nachstehen, meist sogar effizienter sind, und dass die theoretischen Abschätzungen oft sehr pessimistisch ausfallen.
- Arbeit zitieren
- Rüdiger Busch (Autor:in), 1998, Scheduling unter Echtzeitbedingungen - Lock-Based und Lock-Free Verfahren, München, GRIN Verlag, https://www.grin.com/document/37452
