Scheduling unter Echtzeitbedingungen - Lock-Based und Lock-Free Verfahren

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 Peri- oden 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

1 Einleitung

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 Resourcen zugreifen, ohne daß das System seine Konsistenz verliert und trotzdem alle Aufgaben rechtzeitig erledigt werden? Zwei wesentliche Lösungsansätze die sich ergeben haben, sind die LockBased und die Lock-Free Verfahren. Bei ersteren wird seitens des Betriebssystems darauf geachtet, daß möglichst alle Jobs ihre Deadline² erreichen, bei den anderen wird diese Aufgabe von den Prozessen selbst erledigt.

Im folgenden werden kurz auf 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ögli- cherweise kaum als Konkurrenz zu den bisherigen Verfahren angesehen werden könnten, da sie ohne Kontrolle seitens des Betriebssystems auf gemeinsame Re- sourcen zugreifen, sollen deshalb genauer analysiert werden. Dazu wird neben einigen Voraussetzungen erst einmal gezeigt, daß das Verhalten dieser Lock-Free Prozesse keinesfalls chaotisch und zeitlich durchaus begrenzt ist. Anschließend werden die Bedingungen verfeinert und auf verschiedene Schedulingalgorithmen angepaßt. Dadurch wird ein formaler Vergleich zwischen Lock-Free und Lock- Based Verfahren möglich, der abschließend auch in einem experimentellen Ver- gleich bestätigt wird.

2 Lock-Based Verfahren

Das Prinzip dieser Verfahren beruht darauf, daß ein Job, der auf eine gemeinsa- me Resource³ zugreift, z.B. eine Datei oder eine globale Variable, diese zunächst vor Zugriffen anderer Job schützen muß. Dies geschieht im allgemeinen über sogenannte Semaphore, die sofern sie gesetzt sind, keine weiteren Zugriffe auf eine Resource erlauben. Um nun zu gewährleisten, daß wichtige Aufgaben rechtzeitig erledigt werden, werden Prioritäten vergeben. In bestimmten Fällen kann es aber trotzdem vorkommen, daß ein Job mit niedriger Priorität einen anderen mit hoher Priorität blockiert. Die folgenden Methoden sollen bezüglich dieser Prioritätsinversion abhilfe schaffen.

2.1 Das Priority Ceiling Protocol

Das grundlegende Prinzip bei diesem Verfahren ist es, Deadlocks und Prioritätsin- version zum einen durch Vererbung von Prioritäten, zum anderen durch festlegen bestimmter Schranken, die den Zugriff auf die Semaphore regeln, zu verhindern.

Dazu soll zunächst die Prioritätsvererbung erklärt werden. Angenommen es gäbe drei Jobs J1, J2, J3, wobei ein kleinerer Index eine höhere Priorität bedeutet. J3 tritt nun in seine kritische Phase, daß heißt, J3 möchte auf eine gemeinsame Resource zugreifen und sperrt diese über das Semaphor S. Bevor diese Phase abgeschlossen ist, wird J3 von J1 unterbrochen, wobei J1 ebenfalls auf die von S überwachte zugreifen möchte. In genau diesem Moment wird J1 von S blockiert. Ohne Prioritätsvererbung könnte ebenfalls in diesem Moment ein Job J2 starten, J3 wiederum unterbrechen und somit den Job J1, welcher die höchste Priorität hat, aber auf die Freigabe von S wartet, blockieren (Abb. 1(links)). Durch die Vererbung erhält J3 aber für die Dauer der kritischen Phase die Priorität des höchsten blockierten Jobs, in diesem Fall J1 und die Prioritätsinversion wird verhindert, denn J3 kann nun von J2 nicht mehr unterbrochen werden, bis die gesperrte Resource von J3 wieder freigegeben wird (Abb. 1(rechts)).

In der Grafik beschreibt eine obere Linie einen aktiven Job, eine untere Linie bedeutet, daß der Job gerade von einem anderen unterbrochen wird und keine Linie heißt, der Job wurde noch nicht gestartet oder ist bereits beendet.

Um Deadlocks zu verhindern, die auftreten können, sobald verschachtelte Zu- griffe auf gemeinsame Resourcen stattfinden, wird das Verfahren der Vererbung noch erweitert. Jedem Semaphor wird eine obere Schranke zugewiesen. Diese Schranke ergibt sich aus der höchsten Priorität aller Jobs, die auf das jeweilige Semaphor zugreifen werden. Ein Job, welcher eine neue kritische Phase beginnen möchte, kann dieses nur tun, sofern seine Priorität höher ist, als alle Schranken

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Prioritätsinversion und Prioritätsvererbung

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Ablaufbeispiel unter PCP

Die drei Jobs greifen in folgender Reihenfolge auf die Resourcen zu: J1 Sperrung von S3, Freigabe von S3

J2 Sperrung von S1, Sperrung von S2,Freigabe von S2Freigabe von S1 J3 Sperrung von S2, Sperrung von S1,Freigabe von S1Freigabe von S2 Was geschieht während der einzelnen Zeitintervalle?

[t1, t2) J3 startet und sperrt das Semaphor S2. 3

[t2, t3) J2 startet und unterbricht J3.

[t3, t4) J2 versucht S1 zu sperren. Da die Priorität von J2 aber nicht höher ist, als die oberste Schranke bereits gesperrter Semaphore, wird J2 vom System ausgesetzt, J3 erbt die Priorität von J2 und setzt mit seiner Abarbeitung fort.

[t4, t5) Der Job J1 startet, unterbricht dabei J3, welcher immer noch in seiner kritischen Phase ist und versucht S3 zu sperren. Dies gelingt, da die Priorität von J1 größer ist, als die oberste Schranke bereits gesperrter Semaphore. Anschließend wird S3 wieder freigegeben.

[t5, t6) J1 beendet seine Aufgabe, J3 nimmt seine Arbeit wieder auf und sperrt S1. [t6, t7) J3 gibt S1 wieder frei.

[t7, t8) Nachdem J3 S2 freigibt und somit die kritische Phase verläßt, erhält er seine alte Priorität zurück und wird sogleich von J2 unterbrochen. Für den Rest des Intervalls beansprucht J2 die Rechenzeit.

[t8, t9] Sobald J2 fertig ist, nimmt J3 die Arbeit wieder auf und endet dann eben- falls.

3 Lock-Free Verfahren

Bei den Lock-Based Verfahren können entweder Prioritätsinversionen auftreten oder es wird, wie bei den oben aufgeführten Algorithmen, relativ viel Rechenzeit dafür benötigt, dies zu verhindern. Hier setzen nun die Lock-Free Verfahren[1] an. Durch die Verwendung von Wiederholungsschleifen (retry loops), ergeben sich zwei wesentliche Vorteile. Zum einen ist keine Kenntnis darüber notwendig, wel- che Task auf welches Objekt zugreift. Dadurch ist ein dynamisches hinzufügen neuer Tasks in das System möglich, ohne das gewisse Systemtabellen, z.B. beim PCP-Verfahren, neu berechnet werden müssen. Zum anderen ist das Durchlaufen der retry loops meist mit weniger Rechenaufwand verbunden, als das Sperren und Freigeben von Objekten.

In Abbildung 3 ist eine nach dem Lock-Free Verfahren implementierte Enqueue- Operation zu sehen. Die CAS2-Operation (compare and swap)⁴ ist dabei atomar und setzt den T ail-Zeiger entweder auf den Wert des Head-Zeigers oder auf den Wert des next-Zeigers, abhängig davon, ob die Reihe leer ist oder nicht.

Aus Sicht der Echtzeitsysteme sind Implementationen mit Lock-Free Objekten insofern interessant, da sie Prioritätsinversionen und Deadlocks verhindern, ohne dabei auf die Hilfe eines Betriebssystems angewiesen zu sein. Die Frage, die sich stellt ist, können durch stetige Unterbrechungen die Ausführungen einiger Operationen beliebig lang werden?

Im folgenden soll gezeigt werden, das auf einem Einprozessor-System die Rechenzeit für die retry loops durchaus begrenzt ist. Dazu zunächst einige Definitionen. Ein retry loop wurde erfolgreich aktualisiert, falls er erfolgreich beendet wurde. In allen anderen Fällen wurde er nicht erfolgreich aktualisiert. Eine einzelne Lock-Free Operation besteht also aus beliebig vielen erfolglosen Aktualisierungen gefolgt von einer erfolgreichen.

Bei der Betrachtung zweier Tasks Ti und Tj die gemeinsam auf ein Lock- Free Objekt B zugreifen, erfährt Tj genau dann eine erfolglose Aktualisierung, wenn sie von Ti unterbrochen wird und diese eine erfolgreiche Aktualisierung auf B durchführt. Dies zeigt, daß es einen Zusammenhang zwischen Unterbre- chungen und erfolglosen Aktualisierungen gibt. Die maximale Anzahl von Un- terbrechungen innerhalb eines Intervals kann deshalb durch den Zeitbedarf der Tasks bestimmt werden. Bei der Analyse werden folgende Scheduling-Verfahren berücksichtigt:

Deadline Monotonic (DM) Ein statisches Verfahren, bei dem ein Task mit kürzerer relativer Deadline eine höhere Priorität hat.

Rate Monotonic (RM) Ein statisches Verfahren, bei dem ein Task mit kürze- rer Periode eine höhere Priorität hat.

Earliest Deadline First (EDF) Ein dynamisches Verfahren, bei dem zu je- dem beliebigen Zeitpunkt der Task mit der nahesten Deadline die höchste Priorität hat.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Lock-free Enqueue Implementation

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 ge- nau den schedulierbar, wenn keine der Tasks die jeweilige Deadline überschreitet. Weiterhin gilt für folgende Symbole:

Abbildung in dieser Leseprobe nicht enthalten

[...]

¹ Zeitplanung

² Der Zeitpunkt, zu dem ein Job sp¨atestens erledigt sein muß.

³ Auch als Objekte bezeichnet

⁴ Die beiden ersten Parameter sind gemeinsame Variablen, die mit den zwei folgendenWerten verglichen werden. Ist der Vergleich erfolgreich, wird den Variablen jeweils der Wert der letzten beiden Parameter zugewiesen.