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
- Einleitung
- Lock-Based Verfahren
- Das Priority Ceiling Protocol
- Lock-Free Verfahren
- Definitionen und Voraussetzungen
- Lemma.
- Lemma.
- Lemma.
- Lemma.
- Scheduling unter statischen Bedingungen
- Satz (Notwendig unter RM)
- Satz (Hinreichend unter RM)
- Satz (Hinreichend unter DM)
- Scheduling unter dynamischen Bedingungen
- Satz (Notwendig unter EDF). .
- Satz (Hinreichend unter EDF).
- Satz (Hinreichend unter EDF, wenn Deadlines und Peri- oden nicht übereinstimmen)
- Definitionen und Voraussetzungen
- Lock-Based und Lock-Free im Vergleich
- Scheduling mit statischen Prioritäten
- Scheduling mit dynamischen Prioritäten
- Experimenteller Vergleich
- Aufbau des Experiments
- Scheduling mit statischen Prioritäten
- Zusammenfassung und Auswertung
Zielsetzung und Themenschwerpunkte
Diese Arbeit beschäftigt sich mit dem Scheduling von Prozessen und Jobs in Realzeitsystemen, insbesondere im Hinblick auf den effizienten und konsistenten Zugriff auf gemeinsame Ressourcen. Es werden zwei grundlegende Ansätze, Lock-Based und Lock-Free Verfahren, verglichen und analysiert.
- Die Herausforderungen bei der Verwendung von Lock-Based Verfahren.
- Das Priority Ceiling Protocol (PCP) als Lösung für Deadlocks und Prioritätsinversionen.
- Die Funktionsweise von Lock-Free Verfahren, insbesondere die Verwendung von Wiederholungsschleifen (retry loops).
- Die Bedingungen für das ordnungsgemäße Funktionieren von Lock-Free Verfahren in verschiedenen Scheduling-Szenarien.
- Ein formaler und experimenteller Vergleich zwischen Lock-Based und Lock-Free Verfahren.
Zusammenfassung der Kapitel
- Einleitung: Dieses Kapitel führt in die Thematik des Schedulings in Realzeitsystemen ein und stellt die Herausforderungen dar, die sich aus dem gemeinsamen Zugriff auf Ressourcen ergeben. Die Lock-Based und Lock-Free Verfahren werden als zwei wichtige Ansätze vorgestellt.
- Lock-Based Verfahren: Dieses Kapitel beschreibt das Prinzip von Lock-Based Verfahren und die Problematik der Prioritätsinversion. Das Priority Ceiling Protocol (PCP) wird als Lösung zur Vermeidung von Deadlocks und Prioritätsinversionen vorgestellt.
- Lock-Free Verfahren: Dieses Kapitel definiert Lock-Free Verfahren und erläutert ihre Funktionsweise mithilfe von Wiederholungsschleifen (retry loops). Es werden grundlegende Voraussetzungen und Lemmata für das korrekte Verhalten von Lock-Free Verfahren aufgestellt.
- Scheduling unter statischen Bedingungen: Dieses Kapitel analysiert das Verhalten von Lock-Free Verfahren unter statischen Bedingungen. Es werden Sätze formuliert, die die Bedingungen für die korrekte Funktionsweise von Lock-Free Verfahren unter verschiedenen Scheduling-Algorithmen (RM, DM) beschreiben.
- Scheduling unter dynamischen Bedingungen: Dieses Kapitel erweitert die Analyse auf dynamische Scheduling-Szenarien und formuliert Sätze für die korrekte Funktionsweise von Lock-Free Verfahren unter dem EDF-Algorithmus.
- Lock-Based und Lock-Free im Vergleich: Dieses Kapitel vergleicht Lock-Based und Lock-Free Verfahren hinsichtlich ihrer Leistungsfähigkeit unter statischen und dynamischen Scheduling-Bedingungen.
- Experimenteller Vergleich: Dieses Kapitel beschreibt die Durchführung eines experimentellen Vergleichs zwischen Lock-Based und Lock-Free Verfahren. Die Ergebnisse des Experiments werden analysiert und interpretiert.
Schlüsselwörter
Realzeitsysteme, Scheduling, Lock-Based Verfahren, Lock-Free Verfahren, Priority Ceiling Protocol (PCP), Prioritätsinversion, Deadlock, Wiederholungsschleifen (retry loops), statische Scheduling-Bedingungen, dynamische Scheduling-Bedingungen, Scheduling-Algorithmen (RM, DM, EDF).
- 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
