Zum Inhalt springen

Betriebssystemtheorie/ Scheduling/ Ressourcen und Ressourcenverwaltung

Aus Wikibooks


Einleitung

[Bearbeiten]

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

[Bearbeiten]

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 Jh mit hoher Priorität sowie Jn mit niedriger Priorität. Weiterhin existiert eine Ressource R.

  1. Jn wird zuerst bereit und ausgeführt. Jn greift die Ressource R.
  2. Jh wird bereit. Da er die höchste Priorität hat, wird Jn verdrängt und Jh ausgeführt.
  3. Jh greift R.

Das System befindet sich nun in einem Zustand der Verklemmung. Der Job Jh kann nicht ausgeführt werden, da die benötigte Ressource von Jn gehalten wird. Jn 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 Jh dem nieder-prioritären Job Jn seine Zeitscheibe zur Verfügung stellt, bis dieser R freigeben hat.

Priority inheritance

[Bearbeiten]

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 Jh mit hoher Priorität, ein Job Jn mit niedriger Priortät und eine Ressource R. Weiterhin existiert ein Job Jm mit mittlerer Priorität.

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

An dieser Stelle haben Jh und Jm die Prioritäten getauscht. Da Jn im Auftrag von Jh handelt, sollte Jn nicht verdrängt werden, sondern ausgeführt werden, bis er R freigibt. Anschließend sollte Jh 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 Jh seine Zeitscheibe an Jn gibt, erhält Jn gleichzeitig die Priorität von Jh. Wenn Jm auftaucht, wird Jn folglich nicht verdrängt, da er mit der Priorität von Jh läuft. Gibt Jn nun die Ressource R frei, verliert er gleichzeitig die Priorität von Jh. Als Konsequenz wird er von Jh verdrängt.

Priority ceiling

[Bearbeiten]

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 Jh und Jn. Weiterhin befinden sich nun zwei Ressourcen R1 und R2 im System.

  1. Der Job Jn beginnt wieder und greift die Ressource R1.
  2. Jh verdrängt Jn und greift erst die Ressource R2 und dann die Ressource R1. Wenn R1 gegriffen wird, geht die Zeitscheibe von Jh auf Jn über.
  3. Jn greift R2 bevor er R1 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:

  1. Der Job Jn beginnt und greift die Ressource R1. Das ist möglich, da die System-Ressource die Priorität Ω hat. Der Job mit der höchsten Priorität, welcher jemals R1 anfordern wird, ist Jh. Die System-Ressource erhält somit dessen Priorität.
  2. Jh verdrängt Jn und greift die Ressource R2. Dies scheitert, da die Priorität von Jh 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 Jh auf Jn über.
  3. Jn greift R2 bevor er R1 freigibt. Da Priority inheritance implementiert wird und Jn im Auftrag von Jh handelt, entspricht die Priorität von Jn der von Jh. Obwohl sie also nicht größer ist, als die Priorität der System-Ressource, erhält Jn die Ressource R2, da er der Job ist, der die Ressource hält, welche die Priorität der System-Ressource bestimmt.
  4. Jn gibt R1 ab. Die Priorität der System-Ressource wird nun ausschließlich durch R2 bestimmt. Jh kann folglich auch noch nicht ausgeführt werden.
  5. Jn gibt R2 frei. Die Priorität der System-Ressource fällt auf Ω zurück. Jh verdrängt Jn und erhält R2. Dadurch steigt die Prioriät der System-Ressource wieder; nun auf die Priorität von R2.
  6. Im weiteren Verlauf kann Jh auch R1 bekommen, da er nun der Job ist, welcher die Ressource hält, welche die Priorität der System-Ressource bestimmt.
  7. Hat Jh beide Ressourcen freigegeben, fällt die Priorität der System-Ressource wieder auf Ω.

Die Jobs Jh und Jn können jederzeit von einem Job Jx mit extrem hoher Priorität verdrängt werden. Durch die Funktionsweise des Priority ceiling ist sichergestellt, dass dieser Job weder R1 noch R2 benutzen wird. Währe dem so, hätte die jeweilige Ressource die Priorität von Jx.

Datenstrukturen für gegenseitigen Ausschluß

[Bearbeiten]

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

[Bearbeiten]

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.

  1. Thread 1 ließt x.
  2. Ist x ungleich 0, ist der kritische Abschnitt belegt. Thread 1 muss zurück zum Anfang.
  3. 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.
  4. Thread 1 arbeitet sich durch den kritischen Anschnitt.
  5. 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

[Bearbeiten]

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

[Bearbeiten]

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.