Betriebssystemtheorie/ Scheduling/ Ressourcen und Ressourcenverwaltung

Einleitung

Ressourcen sind die Betriebsmittel, die ein Job vom System anfordert. Dazu zählen unter anderem der oder die Prozessoren, das Dateisystem, das Netzwerk und Hardware-Geräte. Man unterscheidet zwischen aktiven und passiven Ressourcen.

Aktive Ressource: Aktive Ressourcen benötigen Zeit für ihre Benutzung. Hierunter fallen Prozessor, Dateisystem und Netzwerk.

Passive Ressource: Passive Ressourcen benötigen keine Zeit. Obwohl die Benutzung nicht unbedingt ohne Zeitverbrauch ablaufen muss, wird der Zugriff auf die Ressource implizit durch eine andere modelliert. Beispiele sind Arbeitsspeicher und Bussysteme.

Manche Ressourcen erlauben mehr als einen konkurrenten Zugriff pro Zeiteinheit. Dies wird modelliert, indem man für jeden Zugriff eine einzelne Ressource erstellt, welche nur einen Zugriff pro Zeiteinheit erlaubt.

Eine weitere wichtige Eigenschaft ist die Preemptierbarkeit.

Preemptierbarkeit: Eine Ressource ist preemptierbar, falls sie zu jedem beliebigen Zeitpunkt einem Job entzogen werden kann, der sie benutzt.

Bekommt ein Job eine Ressource zugesprochen, ist es oft vorteilhaft, sie ihm zu einem beliebigen Zeitpunkt wieder zu entziehen und einem höher-prioren Jobs zuzuweisen. Dieses Verhalten ist für die Optimalität einiger Scheduling-Algorithmen erforderlich. Ein Beispiel findet sich im Kapitel über EDF.

Die Ressourcenverwaltung im Betriebssystem ist ein besonders sensibler Bereich, da es bei einer fehlerhaften Umsetzung zu Verklemmungen kommen kann.

Verklemmungen (dead locks <engl.>) sind Zustände, wobei mehrere Jobs aufgrund bestimmter Bedingungen nicht mehr weiterarbeiten können, da sie sich gegenseitig blockieren oder sogar das Betriebssystem anhalten.

Diese Bedingungen werden zum Beispiel erfüllt, wenn ein Job eine exklusive Ressource belegt, dann ein anderer Job, der eine andere Ressource belegt, ausgeführt wird und beide jeweils die Ressource des Anderen anfordern. Da jetzt beide warten, kann keiner mehr seine Ressource freigeben. So bleiben beide Jobs für immer blockiert.

Im Folgenden werden Strategien erläutert, die ein korrektes Verhalten sicherstellen und Verklemmungen verhindern.

Timeslice donation

Timeslice donation beschreibt einen Vorgang, bei dem hoch-prioritäre Jobs ihre Zeitscheibe an nieder-prioritäre Jobs geben, um ihnen bei ihrer Arbeit zu helfen.

Betrachtet wird folgendes Beispiel: Im System befinden sich die Jobs J_h mit hoher Priorität sowie J_n mit niedriger Priorität. Weiterhin existiert eine Ressource R.

J_n wird zuerst bereit und ausgeführt. J_n greift die Ressource R.
J_h wird bereit. Da er die höchste Priorität hat, wird J_n verdrängt und J_h ausgeführt.
J_h greift R.

Das System befindet sich nun in einem Zustand der Verklemmung. Der Job J_h kann nicht ausgeführt werden, da die benötigte Ressource von J_n gehalten wird. J_n kann allerdings auch nicht ausgeführt werden, da ein anderer Job höherer Priorität vorhanden ist. Die Lösung besteht darin, dass der hoch-prioritäre Job J_h dem nieder-prioritären Job J_n seine Zeitscheibe zur Verfügung stellt, bis dieser R freigeben hat.

Priority inheritance

Bei einfachen Scheduler-Implementierungen kann es dazu kommen, dass Jobs ihre Prioritäten tauschen, dem sogenannten Priority inversion.

Folgendes Beispiel soll das Problem illustrieren. Im System befinden sich wieder ein Job J_h mit hoher Priorität, ein Job J_n mit niedriger Priortät und eine Ressource R. Weiterhin existiert ein Job J_m mit mittlerer Priorität.

Zuerst wird J_n bereit und ausgeführt. J_n greift die Ressource R.
Nach einiger Zeit wird J_h bereit. Da J_h eine hohe Priorität hat, wird J_n verdrängt und statt dessen J_h ausgeführt.
J_h greift die Ressource R. R wird allerdings noch von J_n gehalten. Deshalb gibt J_h seine Rechenzeit an J_n.
Während J_n arbeitet, taucht J_m auf. Da J_m eine höhere Priorität hat, als J_n, wird J_n erneut verdrängt und J_m wird ausgeführt.

An dieser Stelle haben J_h und J_m die Prioritäten getauscht. Da J_n im Auftrag von J_h handelt, sollte J_n nicht verdrängt werden, sondern ausgeführt werden, bis er R freigibt. Anschließend sollte J_h ausgeführt werden.

Priority inheritance verhindert die oben geschilderte Situation. Es bedeutet, dass nieder-prioritäre Jobs die Priorität von höher-prioritären Jobs erben, falls sie in dessen Auftrag handeln.

In dem Moment, in dem J_h seine Zeitscheibe an J_n gibt, erhält J_n gleichzeitig die Priorität von J_h. Wenn J_m auftaucht, wird J_n folglich nicht verdrängt, da er mit der Priorität von J_h läuft. Gibt J_n nun die Ressource R frei, verliert er gleichzeitig die Priorität von J_h. Als Konsequenz wird er von J_h verdrängt.

Priority ceiling

Mit Timeslice donation und Priority inheritance werden noch nicht alle Probleme gelöst, da es immer noch zu Verklemmungen kommen kann.

Das Beispiel besteht wieder aus den Jobs J_h und J_n. Weiterhin befinden sich nun zwei Ressourcen R₁ und R₂ im System.

Der Job J_n beginnt wieder und greift die Ressource R₁.
J_h verdrängt J_n und greift erst die Ressource R₂ und dann die Ressource R₁. Wenn R₁ gegriffen wird, geht die Zeitscheibe von J_h auf J_n über.
J_n greift R₂ bevor er R₁ freigibt.

Wieder tritt eine Verklemmung auf. Keiner der beiden Jobs kann gerechnet werden, da sie jeweils eine Ressource halten, die vom anderen benötigt wird. Man sagt, sie hängen zyklisch von einander ab.

Durch die Implementierung von Priority ceiling können solche zyklischen Abhängigkeiten verhindert werden. Hierzu werden Timeslice donation und Priority inheritance um einige Eigenschaften erweitert.

Zunächst ist es nötig zu wissen, welche Jobs eine Ressource benutzen. Jeder Ressource wird die Priorität des höchst-prioren Jobs zugeordnet, der sie benutzt. Außerdem wird eine System-Ressource eingeführt, über deren Priorität der Zugriff auf andere Ressourcen gesteuert wird. Ein Job kann dabei nur eine Ressource greifen, falls seine Priorität höher ist, als die Priorität der System-Ressource oder er die Ressource hält, welche die Priorität der System-Ressource bestimmt. Diese hat zu Beginn die niedrigste Priorität Ω, so dass prinzipiell jeder Job eine Ressource bekommen kann. Greift ein Job eine Ressource, steigt die Priorität der System-Ressource auf die Priorität der gegriffenen Ressource.

Das obige Beispiel läuft mit Priority ceiling folgendermaßen ab:

Der Job J_n beginnt und greift die Ressource R₁. Das ist möglich, da die System-Ressource die Priorität Ω hat. Der Job mit der höchsten Priorität, welcher jemals R₁ anfordern wird, ist J_h. Die System-Ressource erhält somit dessen Priorität.
J_h verdrängt J_n und greift die Ressource R₂. Dies scheitert, da die Priorität von J_h nicht größer ist, als die Priorität der System-Ressource. (Sie ist genau gleich hoch.) Da Timeslice donation implementiert wird, geht die Zeitscheibe von J_h auf J_n über.
J_n greift R₂ bevor er R₁ freigibt. Da Priority inheritance implementiert wird und J_n im Auftrag von J_h handelt, entspricht die Priorität von J_n der von J_h. Obwohl sie also nicht größer ist, als die Priorität der System-Ressource, erhält J_n die Ressource R₂, da er der Job ist, der die Ressource hält, welche die Priorität der System-Ressource bestimmt.
J_n gibt R₁ ab. Die Priorität der System-Ressource wird nun ausschließlich durch R₂ bestimmt. J_h kann folglich auch noch nicht ausgeführt werden.
J_n gibt R₂ frei. Die Priorität der System-Ressource fällt auf Ω zurück. J_h verdrängt J_n und erhält R₂. Dadurch steigt die Prioriät der System-Ressource wieder; nun auf die Priorität von R₂.
Im weiteren Verlauf kann J_h auch R₁ bekommen, da er nun der Job ist, welcher die Ressource hält, welche die Priorität der System-Ressource bestimmt.
Hat J_h beide Ressourcen freigegeben, fällt die Priorität der System-Ressource wieder auf Ω.

Die Jobs J_h und J_n können jederzeit von einem Job J_x mit extrem hoher Priorität verdrängt werden. Durch die Funktionsweise des Priority ceiling ist sichergestellt, dass dieser Job weder R₁ noch R₂ benutzen wird. Währe dem so, hätte die jeweilige Ressource die Priorität von J_x.

Datenstrukturen für gegenseitigen Ausschluß

Um die dargestellten Konzepte umzusetzen, stellen Betriebssysteme den Anwendungen verschiedene Mechanismen zur Verfügung. Je nach dem, welchen Zweck man verfolgt, bieten sich verschiedene Möglichkeiten an. Allen ist gemein, dass sie die Zugriff auf Ressourcen steuern.

Den Bereich im Quelltext von Programmen, welcher während eines Ressourcenzugriffs nicht unterbrochen werden darf, nennt man kritischen Abschnitt.

Atomare Instruktionen

Bei Atomare Instruktionen handelt es sich um einfache Anweisungen, deren Ausführung garantiert nicht unterbrochen wird. Die Garantie wird von der Hardware gegeben und durchgesetzt.

Beispielsweise soll ein Wert x aus dem Arbeitsspeicher ausgelesen werden, mit einem Referenzwert verglichen werden und bei positivem Vergleich neu gesetzt werden. Der Wert im Arbeitsspeicher enthält die Nummer des Threads, der sich aktuell im kritischen Abschnitt befindet. Ist dieser Wert 0, ist der kritische Abschnitt frei. Die Ausführung des kritischen Abschnitts läuft nun etwa so ab.

Thread 1 ließt x.
Ist x ungleich 0, ist der kritische Abschnitt belegt. Thread 1 muss zurück zum Anfang.
Der Wert x ist 0, also ist der kritische Abschnitt frei. Thread 1 schreibt die 1 in x, um anderen Threads zu signaliseren, dass sie warten müssen.
Thread 1 arbeitet sich durch den kritischen Anschnitt.
Am Ende des Zugriffs wird x auf 0 gesetzt, um anderen Threads den Zugriff zu ermöglichen.

Das Problem an diesem Beispiel wird schnell deutlich, wenn man sich überlegt, was passiert, falls ein Thread zwischen den Punkten 2 oder 3 unterbrochen wird. Der Thread hat 0 gelesen und will den kritischen Abschnitt betreten. Nun wird ein anderer Thread ausgeführt, liest 0 und will ebenfalls den kritischen Abschnitt betreten. Da sich zwei Threads im kritischen Abschnitt befinden, kann es zu inkorrekten Ergebnissen kommen.

Die Lösung des Problems besteht in der Zusammenfassung der Punkte 1 bis 3 zu einer automaren Instruktion, dem sogenannten test_and_set. Die Instruktion liest einen Wert aus, vergleicht ihn mit einem Referenzwert und schreibt bei positivem Vergleich einen neuen Wert an die selbe Stelle. Bei negativem Vergleich wird der alte Wert beibehalten.

Der Vorteil atomarer Instruktionen besteht in ihrer vollständigen Implementierung in der Hardware. Dadurch spart man sich einen Kernein- und -austritt. Speziell für sehr kurze kritische Abschnitte erhält man eine hohe Geschwindigkeit.

Je länger kritische Abschnitte werden, desto wahrscheinlicher wird es, dass der nutzende Thread verdrängt wird. Nun werden unter Umständen andere, wartende Threads ausgeführt, welche nicht in den kritischen Abschnitt können. Da das Betriebssystem keine Informationen darüber hat, welcher Thread im kritischen Abschnitt ist, kann hier kein Timeslice donation eingesetzt werden.

Atomare Instruktionen benötigen außerdem exklusiven Zugriff auf die Prozessoren im System, sowie auf das Speicherbussystem. Weiterhin müssen die Caches der Prozessoren abgeglichen werden. Dies führt zu einigem Aufwand im Speicherkontroller, welcher komplexe Protokolle zur Syncronisierung implementieren muss. Geänderte Register müssen ständig in den Arbeitsspeicher zurückgeschrieben werden, damit die anderen Prozessoren die Änderung sehen. Das Problem ist so weitreichend, dass es sogar ein spezielles Schlüsselwort volatile in C gibt, welches den Compiler anweist, den Wert einer Variable nicht in Registern zu cachen.

Mutexe und Semaphoren

Die rasche Abarbeitung längerer kritischer Abschnitte kann durch die Verwendung von Mutexen und Semaphoren gesteuert werden.

Semaphore sind Zähler, welche blockieren, wenn sie auf 0 stehen. Ein Semaphor bietet einer Maximalzahl an Threads Zugriff auf einen kritischen Abschnitt. Mit jedem Thread, welcher den kritischen Abschnitt betritt, verringert sich der Wert im Semaphor. Mit jedem Thread, der den kritischen Abschnitt wieder verläßt, erhöht sich der Wert wieder. Während der Semaphor 0 zeigt, werden ankommende Threads blockiert.

Ein Mutex ist entweder offen oder geschlossen. Er kann also als Spezialfall eines Semaphor mit dem Maximalwert 1 angesehen werden.

Die Implementierung erfolgt meist über das Betriebssystem. Dabei wird der Semaphor vom System zur Verfügung gestellt. Der Versuch, den kritischen Abschnitt zu Betreten, führt zu einem Kerneintritt. Ist der kritische Abschnitt frei, kann der Thread fortgesetzt werden. Ist der kritische Abschnitt voll, wird der Thread beiseite gelegt und zu einem Thread im kritischen Abschnitt geschaltet. Auf diese Weise läßt sich Timeslice donation implementieren. Verläßt ein Thread den kritischen Abschnitt, erfolgt ebenfalls ein Kerneintritt. Gibt es Threads, die am Semaphor warten, wird einer geweckt, welcher nun in den kritischen Abschnitt darf.

Monitore

Ein Monitor abstrahiert eine Ressource vollständig. Er bietet ein Programmier-Interface, welches sämtliche Funktionen der Ressource bereitstellt. Möchte ein Thread auf die Ressource zugreifen, benutzt er das Interface. Die kritischen Abschnitte werden also von der Anwendung in den Monitor verschoben. Die Synchronisierung zwischen mehreren Threads erfolgt automatisch im Monitor.

Monitore sind häufig eigenständige Threads, die per IPC benutzt werden oder Funktionen im Kern, welche durch Syscalls angesprochen werden. Die verbreitesten Monitore sind Gerätetreiber. Nutzerprogramme greifen in heutigen Systemen nicht direkt auf Geräte zu, sondern instruieren die Treiber des Betriebssystems, welche die Funktionen von der konkreten Hardware abstrahieren.