Betriebsysteme (Subject) / Prozesskommunikation (Lesson)

This lesson was created by UF13.

Learn lesson

back  |  next 1 / 1

• Warum ist der wechselseitige Ausschluss (mutual exclusion) notwendig? Damit die Resultate von Abläufen konkurrenter Prozesse determiniert bleiben, müssen deren kritische Abschnitte exklusiv ausgeführt werden, d.h. ein kritischer Abschnitt zu einer Zeit. Innerhalb eines kritischen Abschnitts greift ein Prozess exklusiv auf gemeinsam benutzte Betriebsmittel zu. Das Betreten und Verlassen eines kritischen Abschnittes muss abgestimmt (synchronisiert) sein. Es muss folglich zwei Funktionen enter_critical_section und leave_critical_section geben, die das Betreten und Verlassen des kritischen Abschnittes regeln. Die Lösung dieses Problems bezeichnet man als "wechselseitigen Ausschluss". Die Notwendigkeit kritischer Abschnitte in konkurrenten Prozessen ist ein logisches Problem, das immer bei gemeinsam benutzten Daten auftritt. Das Problem lässt sich weder durch zusätzliche Hardware noch durch zusätzliche Software lösen. Nicht gemeinsam benutzbare Betriebsmittel können von konkurrenten Prozessen nur in kritischen Abschnitten belegt werden. Beispiele nicht-gemeinsan benutzbarer Betriebsmittel sind die meisten peripheren Geräte sowie veränderliche Daten. Zu den gemeinsam benutzbaren Betriebsmitteln gehören beispielweise nur lesbare Daten (read-only files). /* nicht kritischer Abschnitt */enter_critical_section;/* kritscher Abschnitt */leave_critical_section/* nicht kritischer Abschnitt */ Die Funktionen enter_critical_section und leave_critical_section regeln das Betreten und Verlassen des kritischen Abschnitts. Jeder Prozess, der versucht, in den kritischen Abschnitt einzutreten, muss zuerst enter_critical_section ausführen, und danach dann leave_critical_section, damit andere Prozesse in ihren kritischen Abschnitt eintreten können.
• Was sind Race conditions? Eine Race Condition entsteht, wenn zwei oder mehrere Prozesse im Wettbewerb einen gemeinsamen Speicher (z.B eine Variable) lesen und schreiben und das Ergebnis von der zeitlichen Reihenfolge der Operationen abhängt. Diese Race Conditions kann man von außen nicht beeinflussen, weil man nicht weiß, wann der Scheduler einen Prozess unterbricht und einem anderen Prozess den Prozessor zuteilt. Also werden Race Conditions i.A. beeinflusst durch: Prozesse laufen auf nur einer CPU Prozesse laufen auf mehreren CPUs mit unbekannten Geschwindigkeiten Parallelität von Prozessen Scheduling: wann werden welche Prozesse wieder rechnend gemacht
• Was ist ein Semaphor? Wenn sich ein Prozess in seinem kritischen Abschnitt befindet, sollte kein anderer Prozess ständig nachfragen, ob er in den kritischen Abschnitt eintreten darf (busy waiting -> unwirtschaftlich, da unproduktive Prozessorzeit benötigt wird). Vielmehr sollte es möglich sein, dass ein Prozess, der eintreten möchte, deaktiviert und wieder aufgeweckt wird, wenn der derzeitige aktive Prozess seinen kritischen Abschnitt verlässt. Dijkstra hat daher das konzept der Semaphore entwickelt. Ein Semaphor kann als eine Variable betrachtet oder als abstrakter Datentyp spezifiziert werden, die/der einen ganzzahligen Wert hat. Der Zustand von S besteht aus der Anzahl freier Betriebsmittel, gespeichert in einer Zählvariablen die einen ganzzahligen Wert hat. Mit Hilfe dieses Semaphor wird eine bestimmte kritische Ressource überwacht. Initialisiert man s mit k, so werden höchstens k gleichzeitige Zugriffe auf diese Ressource zugelassen => meistens ist k=1. Ein Semaphor ist eine Datenstruktur, die aus einer Ganzzahl und den Nutzungsoperationen „Reservieren/Probieren“ und „Freigeben“ besteht. Sie eignet sich insbesondere zur Verwaltung beschränkter (zählbarer) Ressourcen, auf die mehrere Prozesse oder Threads zugreifen sollen, wie etwa Erzeuger und Verbraucher. Im Gegensatz zu einem Lock bzw. einem Mutex brauchen die Aktivitätsträger, die „reservieren“ und „freigeben“, nicht identisch zu sein. Zur Benutzung dieser Semaphore stehen zwei Operationen down und up (Veralgemeinerung von sleep und wakeup) zur Verfügung, die als atomare Elementaroperationen betrachtet werden, d.h. vor Abschluss dieser Operationen sind diese nicht unterbrechbar. 1. Die down-Operation down(s) angewendet auf den Semaphor s bedeutet, dass der gegenwärtige Wert des Semaphors um 1 vermindert wird. Wird der resultierende Wert negativ, blockiert der Prozess, der die Operation down ausführt. 2. Die up-Operation up(s) bedeutet, dass der Wert des Semaphors s um 1 erhöht wird. Ist der resultierende Wert nicht positiv, wird ein durch eine down-Operation blockierter Prozess freigegeben, also geht dieser Prozess vom Zustand blockiert zum Zustand bereit über. Man unterscheidet zwei Typen von semaphoren. Semaphore, die mit 1 initialisiert werden, bezeichnet man als binäre Semaphore, und Semaphore, deren Werte auch größere Zahlen sein können, werden allgemeine Semaphore genannt.    
• Welche Vor- und Nachteile hat ein Semaphor? Vorteile: einfach effizient zu realisieren die Operationen benötigen nur sehr kurze Zeit die Implementierung kann mit Hilfe der TSL-Anweisung durch die Hardware unterstützt werden Nachteile: niedriges Abstraktionsniveau fehleranfälliges Programmieren (beim down-Operation -- kein wechselseitiger Ausschluss; beim up-Operation -- mögliche Verklemmung) unstrukturierte Programmierung ( down und up Operationen sind über das ganze Programm verstreut, z.B. bei bedingter Synchronisation)  
• Warum ist die Synchronisation von Prozessennotwendig? Ein Programm muss deterministisch sein, d.h. das Ergebnis darf nicht von der Ausführungsreihenfolge der Prozesse abhängen. Bei gleichzeitig vorgenommenen Zugriff wäre der resultierende Zustand der Ressource unbestimmt. Um deadlocks zu vermeiden. Eine Menge von Prozessen befindet sich in einem Deadlock, wenn jeder Prozess der Menge auf ein Ereignis wartet, das nur von einem anderen Prozess der Menge ausgelöst werden kann.
• Was ist ein kritischer Abschnitt eines Prozesses? Kritische Abschnitte sind Abschnitte, die lesend und/oder schreibend gemeinsame Daten verarbeiten, die von mehreren konkurrenten Prozessen genutzt werden, so dass eine Race Condition entstehen kann. Damit kritische Abschnitte determinierte Resultate zur Folge haben, müssen solche Abschnitte ohne Störung durch die anderen konkurrenten Prozesse in einer Sequenz ausgeführt werden. Innerhalb eines kritischen Abschnitts greift ein Prozess exklusiv auf gemeinsam benutzte Betriebsmittel zu. Nicht gemeinsam benutzbare Betriebsmittel (z.B. Drucker, diskettenlaufwerk) können von konkurrenten Prozessen nur in kritischen Abschnitten belegt werden. Kritische Abschnitte in konkurrenten Prozessen müssen eindeutig gegen die unkritischen Abschnitte abgegrenzt sein. Ein Prozess kann nacheinander mehrere verschiedene kritische Abschnitte durchlaufen, allerdings dürfen diese nicht ineinander geschachtelt sein. Die Notwendigkeit kritischer Abschnitte in konkurrrenten Prozessen ist ein logisches Problem, das immer bei gemensam benutzten Daten auftritt. Das Problem lässt sich weder durch zusätzliche Hardware noch durch zusätzliche Software lösen.
• Welche Anforderung gibt es an einen wechselseitigen Ausschluss?   Ein Prozess zu einer Zeit in seinem kritischen Abschnitt Falls mehrere Prozesse gleichzeitig versuchen, den kritischen Absc hhnitt zu betreten, gibt es in endlicher Zeit eine Entscheidung, wer zuerst darf. Ein Prozess, der eintreten möchte, darf nicht beliebig oft von anderen überholt werden, so dass er verhungert. Die Wartezeit eines Prozesses sollte fäir sein. Wegen des wechselseitigen Ausschlußes darf kein Prozess, welcher sich außerhalb eines kritischen Abschnittes befindet, einen anderen Prozess blockieren, da dieser sich eventuell gerade in einem kritischen Abschnitt befinden kann und es ihm somit nicht mehr möglich wäre, die durch ihm belegten Betriebsmittel wieder freizugeben. Wenn ein Prozess im unkritischen Abschnitt gestoppt wird, so beeinflusst dies nicht den weiteren Ablauf der anderen Prozesse. Ein Algorithmus zur Realisierung des wechselseitigen Ausschlusses darf nicht auf irgendwelchen Annahmen über die relative oder absolute Ausführungsgeschwindigkeiten der Prozesse beruhen.
• Was sind globale Synchronisationsvariablen? Globale Synchronisationsvariablen, sind Variablen mit welchen ein wechselseitiger Ausschluss gesteuert werden kann. Sie dienen also zur Synchronisation Konkurrent laufender Prozesses welche auf diese Variablen Zugriff haben. Wir definieren also eine globale Variable s, über die ein Prozess den kritischen Abschnitt für den jeweils anderen freigibt. Beispiel: Bei n Prozessen gibt der (n-1)-te Prozess den kritischen Bereich für den n-ten Prozess frei und der n-te Prozess gibt daraufhin den kritischen Bereich für den 1 Prozess frei.
• Welche Probleme entstehen bei Synchronisationsvariablen? Die kritischen Abschnitte können (bei n=2) nur abwechselnd 1,2,1,2,... ablaufen => kein Überrunden möglich. Ein Prozess kann nicht selbst zweimal hintereinander den gleichen kritischen Abschnitt aufrufen. Während sich ein Prozess in seinem kritischen Abschnitt befindet, fragt ein anderer Prozess ständig nach Erlaubnis zum Eintritt in seinen kritischen Abschnitt (aktives Warten, busy waiting). Es warten also immer n-1 Prozesse. Stürzt ein Prozess ab, bleibt das ganze Konstrukt stehen. Bei dem Verfahren mit n globalen Variablen und n Prozessen werden zwar o.g. Nachteile behoben, dafür wird aber die Gefahr zugezogen wenn voneinander abhängige Prozesse zeitgleich den kritischen Prozess betreffen, kann es zu den Systemverklemmungen (Deadlocks kommen). Keiner der Prozesse kann den kritischen Abschnitt jemals wieder verlassen.
• Welche Operationen sind auf einem Semaphor definiert? Zur Benutzung der Semaphore stehen zwei Operationen sown und up (Verallgemeinerung von sleep und wakeupe) zur Verfügung, die als atomare Elementaroperationen betrachtet werden, d.h. vor Abschluss dieser Operationen sind diese nicht unterbrechbar. Die down-Operation down(s) angewendet auf den Semaphor s bedeutet, dass der gegenwärtige Wert des Semaphors um 1 vermindert wird. Wird der resultierende Wert negativ, blockiert der Prozess, der die Operation down ausführt. Die up-Operation up(s) bedeutet, dass der Wert des Semaphors s um 1 erhöht wird. Ist der resultierende Wert nicht positiv, wird ein durch eine down-Operation blockierter Prozess freigegeben, also geht dieser Prozess vom Zustand blockiert zum Zustand bereit über.      Sei s der Semaphor eines bestimmten kritischen Abschnitts, so wird down(s) vor Beginn und up(s) nach Abschluss des kritischen Abschnitts ausgeführt.
• Advertisement
• Wie können die atomaren down- und up-Operationen realisiert werden? Zur Implementierung von Semaphoren benutzen wir eine Warteschlange, die Prozesse aufnimmt, die aufgrund des Semaphors warten. Die Prozesse in der Warteschlange können z.B. nach dem FIFO-Prinzip ausgewählt werden. Zu jedem gegebenen Zeitpunkt kann der Wert s wie folgt interpretiert werden: s>=0: s ist die Anzahl der Prozesse, die noch die Operation down ohne Blockierung ausführen können. s<0: |s| ist die Anzahl der Prozesse, die sich in der Warteschlange des Semaphors s befinden. down(s):    s:=s-1    if s<0       then begin          füge den Prozess in die Warteschlange ein;          versetze den Prozess in den blockierten Zustand;       end; up(s):    s:=s+1;    if s<=0 (* Die Warteschlange ist nicht leer gewesen *)       then begin          wähle einen Prozess aus der Warteschlange aus;          versetze ihn in den bereiten Zustand;       end;      
• Was macht ein Prozess, wenn er nicht in den kritischen Abschnitt eintreten kann? Sollte die Zählvariable der Betriebsmittel bei der Ausführung der down() Operation negativ werden, so blockiert der Prozess und wird in eine Warteschlange eingereiht. Hier muss er solange warten, bis Betriebsmittel wieder zur Verfügung stehen sodass er in den kritischen Bereich eintreten darf.
• Was ist ein Deadlock? In modernen Betriebssystemen treten zahlreiche konkurrent ablaufende Aufgaben auf, die sich in vielfältiger Weise gegenseitig beeinflussen. Beispielsweise bewerben sich zeitlich verzahnt mehrere Prozesse um verschiedene Betriebsmittel, z.B. Prozessor, Hauptspeicher, /A-Einheiten, Dateien, Übersetzungsprogramme u.s.w., die, nach der Reihenfolge der Anforderung zugeteilt, häufig zu Zuständen des Gesamtsystems führen können, so dass alle bzw. ein Teil der am System beteiligten Prozesse sich gegenseitig blockieren. Ein Prozess muss manchmal auf ein gewisses Ereignis warten. Wenn das Ereignis auftritt, kann der Prozess seinen Ablauf fortsetzen. Wenn jedoch das Ereignis nicht auftritt, ist der Prozess unter Umständen beliebig lange blockiert. Unter ungünstigen Umständen kann ein inkonsistenter Zustand erreicht werden, eine Verklemmung, die keiner der beteiligten Prozesse wieder auflösen kann. Enen solchen Zustand im System bezeichnen wir als Deadlock Eine Menge von Prozessen befindet sich in einem Deadlock, wenn jeder Prozess der Menge auf ein Ereignis wartet, das nur von einem anderen Prozess der Menge ausgelöst werden kann. Deadlocks treten nicht mur in Rechnersystemen, sondern ganz allgemein in dynamischen Systemen auf (Verkehrsstau, Buchausleihe) Es gibt Ressourcen und es gibt Prozesse, die auf ressourcen warten und dadurch blockiert sind, sie irgendwann bekommen und irgendwann wieder freigeben. Eine Verklemmung kann ohne einen radikalen Eingriff von außen nicht aufgelöst werden.
• Welche vier Deadlock-Bedingungen müssen erfüllt sein, wenn ein Deadlock vorliegt? Wechselseitiger Ausschluss: Die Prozesse fordern und erhalten exklusive Kontrolle über die benötigten Betriebsmittel. Also kann zu einem Zeitpunkt immer jeweils nur ein Prozess ein Betriebsmittel nutzen. Nichtunterbrechbarkeit (no preemption): Die Betriebsmittel können temporär nicht zurückgegeben werden, sondern bleiben dem Prozess bis zum Ende der Anforderung zugeordnet. Hold-and-wait-Bedingung: Die Prozesse belegen (exklusiv) bereits zugewiesene Betriebsmittel, während sie noch auf zusätzliche Betriebsmittel warten. Zyklische Warte-Bedingung (cirkular wait): Es besteht eine geschlossene Kette aus Prozessen und von ihnen belegten bzw. angeforderten Betriebsmitteln in der Weise, dass jeder Prozess mindestens ein Betriebsmittel belegt, das vom nächsten Prozess in der Kette benötigt werden. Sobald nur eine der Bedingungen nicht erfüllt ist, kommt es nicht zum Deadlock. Die vier Bedingungen sind notwendig, d.h. wenn ein Deadlock vorlegt, dann müssen die vier Bedingungen erfüllt sein. Wenn die vier Bedingungen erfüllt sind und keine zusätzliche externe Ressourcen angeschlossen werden dürfen, dann sind die vier Bedingungen auch hinreichend.
• Wie kann man ein Deadlock erkennen? Das Betriebssystem führt regelmäßig einen Algorithmus zur Erkennung von Deadlocks aus, der das zyklische Warten (Bedingung 4) erkennt. Zu jedem Zeitpunkt wird der aktuelle Zustand zur Belegung der Betriebsmittel von Prozessen durch die folgenden Informationen definiert.. 1. Der Betriebsmittelvektor gibt die Anzahl der Betriebsmittel an, die von jeder Klasse insgesamt verfügbar sind. 2. Der Betriebsmittelrestvektor gibt die Anzahl Betriebsmittel an, die von jeder Klasse noch frei sind. 3. Die Belegungsmatrix gibt an, wie viele Betriebsmittel aktuell von den Prozessen belegt sind. 4. Die Anforderngsmatrix gibt an, wie viele Betriebsmittel zur Zeit angefordert werden. Das Algotithmus zur Erkennung von Deadlocks sucht nach einem Prozess, dessen Anforderungen durch die momentan verfügbaren Betriebsmittel erfüllt werden können. In einer repeat-Schleife bei jedem Durchlauf werden alle Prozesse, die potentiell noch im Deadlock enthalten sind, daraufhin untersucht, ob ihre Restanforderung durch die noch vorhandenen Betriebsmittel erfüllt werden kann. Falls ein solcher Prozess gefunden wird, wird dieser als beendbar markiert, und die von ihm belegten Betriebsmittel können freigegeben werden. Die repeat-Schleife wird so lange wiederholt, wie weitere beendbare Prozesse gefunden werden. Nur wenn alle Prozesse als beendbar markiert sind, dann liegt keine verklemmung vor, ansonsten bilden die nicht beendbaren Prezesse einen Deadlock-Zyklus.
• Wie kann man einen Deadlock vermeiden? Vermeidung von Deadlocks bedeutet, dass Informationen über zukünftige Betriebsmittel-Anforderungen genutzt werden, um zu versuchen, nur solche Betriebsmittel-Anforderungen zuzulassen, bei denen nicht die Gefahr einer Verklemmung besteht. Der Bankier-Algorithmus (Dijkstra, 1965) ist eine Erweiterung des Algorithmus zur Erkennung von Deadlocks. Basiert auf dem Konzept der sicheren Zustände zur Belegung von Betriebsmitteln. Zu jedem Zeitpunkt wird der Zustand durch verfügbare Restbetriebsmittel R und die Belegungsmatrix C definiert. Außerden muss jeder Prozess seine maximalen Anforderungen an allen Betriebsmitteln vorab bekannt geben, diese sind in der maximalen Anforderungsmatrix. Ein Zustand ist sicher, wenn es mindestens eine Ausführungsreihenfolge der Prozesse gibt, die nicht zu einer Verklemmung führt, selbst wenn alle Prozesse sofort ihre maximale Anzahl an Betriebsmitteln anfordern. Das System ist in einem sicheren Zustand gestartet. Wenn ein Prozess Betriebsmittel anfordert, wird getestet, ob der Zustand durch dese Zuteilung unsicher würde. Falls ja, bleibt das System im sicheren Zustand und blockiert den Prozess so lange, bis es sicher ist, die Anforderung zu gewähren. Der Bankier-Algorithmus ist fast gleich zu dem Algorithmus zur Erkennung von Deadlocks, nur haben wir anstelle von der Anforderungsmatrix jetzt die maximale Anforderungsmatrix und anstelle des Test (Anforderung>Rest) den Test (max Anforderung-Belegung>Rest). Leider haben wir auch dadurch keine endgültige Lösung des Deadlocksproblems gefunden, denn die maximalen Anforderungen eines Prozesses sind kaum im Voraus verfügbar.  
• Wie funktioniert der Bankier-Aögorithmus? vorgeschichte: Wie einem Bankier nur eine begrenzte Anzahl an Geld zur Verfügung steht, um die Kreditwünsche seiner Kunden zu erfüllen, so steht einem Betriebssystem auch nur eine begrenzte Anzahl von Betriebsmitteln zur Verfügung. Der Bankier hält deswegen immer noch so viel Geld in seinem Tresor zurück, damit er noch von mindestens einem Kunden das komplette Kreditlimit erfüllen kann. Dieser eine Kunde (Prozess) kann dann sein Geschäft erfolgreich zum Abschluss bringen und das verwendete Geld wieder zurück auf die Bank bringen. Nun kann es ein anderer Kunde haben. Informatik: Jeder Prozess muss seine maximalen Anforderngen an allen Betriebsmitteln vorab bekannt geben, diese sind in der maximalen Anforderungsmatrix M gespeichert. Ein Zustand ist sicher, wenn es mindestens eine Ausführungsreihenfolge der Prozesse gibt, die nicht zu einer Verklemmung führt, selbst wenn alle Prozesse sofort ihre maximale Anzahl an Betriebsmitteln anfordern. Das System wird in einem sicheren Zustand gestartet. Wenn ein Prozess Betriebsmittel anfordert, wird getestet, ob der Zustand durch diese Zuteilung unsicher würde. Falls ja, bleibt das System im sicheren Zustand und blockiert den Prozess so lange, bis es sicher ist, die Anforderung zu gewähren. Das Testen auf einen sicheren Zustand, erfolgt hierbei über eine leicht abgewandelte Version des Algorithmus zum Erkennen von Deadlocks.
• Umgang mit Deadlocks Vogel-Strauß-Algorithmis Der einfachste Ansatz beim Umgang mit Deadlocks ist der Vogel-Straiß-Algorithmus, d.h. die Ignorierung des Problems. Dieser Ansatz, der für Mathematiker indiskutabel ist, wird dennoch unter Informatikert und Ingeneuren in Erwägung gezogen. Die Gründe dafür sind einfach: Die Wahrscheinlichkeit für ein Deadlock ist wesentlich geringer als die für Compiler- oder Betriebssystemfehler. Die Behandlung on Deadlocks jedoch führt zu einer nicht unbeträchtlichen Geschwindigkeitseinbuße und ist daher wesentlich störender als die meisten Deadlocks, die oft für den Benutzer unerkannt bleiben. Außerdem müssen Prozesse für die Behandlung von Deadlocks stark eingeschränkt werden. Es handelt sich also beim Umgang mit Deadlocks um die Frage dem Komfort oder der Korrektheit den Vorzug zu geben. Daher wird in den meisten Betriebssystemen der Vogelstrauß-Algorithmus angewandt.
• Was wird in der Praxis gemacht? Es ist für Betriebssysteme gar nicht leicht, Deadlocks sicher zu vermeiden oder zu verhindern bzw. wenigstens zu erkennen und sinnvoll automatisch zu behandeln. Deshalb ist in den am weitesten verbreiteten Systemen wie Windowa und Linux die so genannte Vogel-Strauß-Strategie "implementiert": Das Problem wird ignoriert. Man setzt darauf, dass die Wahrscheinlichkeit für das Eintreten eines Deadlocks extrem gering ist und dass der Benutzer im Notfall selbst eingreift und z.B. Prozesse beendet oder den Rechner neu startet. Verfahren von Silberschatz, Die Ressourcen werden nach ihrer Wichtigkeit in vier Klassen eingeteilt, und Verklemmungen zwischen einzelnen Klassen werden durch diese Ordnung, wie in Frage 11 aufgelistet, verhindert.
• Wie kann man ein Deadlock verhindern? Bei der Verhinderung von Deadlocks wird versucht, zumindest eine der vier Deadlock-Bedingungen niemals erfüllen zu lassen. - Bedingung 1 scheidet aus, da die wechselseitiger Ausschluss i.d.R. erforderlich ist . Bedingung 2 ist möglich durch Ressourcenentzug: Prozess müsste alle Betriebsmittel zurückgeben und diese wieder zusammen mit dem neuen Betriebsmittel anfordern. Das würde funktionieren, ist aber nicht immer praktikabel, da z.B. einem Prozess ein Ausgabegerät nicht entzogen werden kann, auf das er gerade etwas ausgibt. - Bedingung 3 müssten alle Prozesse in Zukunft benötigten Betriebsmittel von Anfang an anfordern (alle oder keines). Nachteil: Lösung ist nicht effizient und man kann nicht immer im Voraus sehen, wie viele Ressourcen benötigt werden. - lineare Ordnung der Betriebsmittel ("wichtiger als") -> nur weniger wichtige Betriebsmittel können nachträglich angefordert werden; funktioniert, da die weniger wichtigen Betriebsmittel nur von Prozessen blockiert werden können, die auf noch weniger wichtigeBetriebsmittel warten. Nachteil: Eine vernünftige Ordnung für alle Ressourcen kann man kaum finden.
• Eine übergreifende Strategie für den Umgang mit den Deadlocks Eine wirkliche, kombinierte Strategie, die die Vor- und Nachteile der genannten Verfahren berücksichtigt, hat Silberschatz vorgeschlagen. Die Ressourcen werden nach ihrer Wichtigkeit in vier Klassen eingeteilt, und Verklemmungen zwischen einzelnen Klassen werden durch diese Ordnung verhindert. Innerhalb jeder Klasse wird das hier am besten geeignete Verfahren angewendet. Die vier Klassen sind: 1. Interne Ressourcen wie Prozesskontrollblöcke und Ein-/Ausgabe-Kanäle: Verhinderung durch lineare Ordnung, die sich hier leicht festlegen lässt. 2. Hauptspeicher für Anwendungsprozesse: Verhinderung durch Ressourcenentzug, ein Prozess kann in den Swap-Bereich ausgelagert werden und macht dadurch Hauptspeicherressourcen für andere Prozesse frei. 3. Prozessressourcen wie Dateien, Laufwerke und andere Geräte: Die Vermeidungsstrategie ist hier sinnvoll, weil man durchaus verlangen kann, dass Prozesse im Voraus festlegen, welche Geräte sie benötigen werden. 4. Der Swap-Bereich für die Auslagerung von Prozessen: Verhinderung durch Vorausanforderung, die maximalen Speicheranforderungen sollen zum Prozessbeginn bekannt gegeben werden.
• Permanente Speicherung großer Datenmengen. Der Hauptspeicher eines Rechners ist hierzu i.d.R. aus mehreren Gründen nicht geeignet: Er ist wesentlich teuerer als Speicherplatz auf E/A-Geräten. Er ist zu klein: Normalerweise ist der maximal adressierbare Bereich des Hauptspeichers wesentlich kleiner als alle Programme und Benutzerdaten zusammen. Der Inhalt des Hauptspeichers geht bei gänginen Technologien verloren, sobald die Stromversorgung ausfällt bzw. der Rechner ausgeschaltet wird. Der Hauptspeicher wird deshalb auch Primärspeicher genannt. Er wird gewöhnlich durch einen schnelleren, kleineren Cache ergänzt. Das ist ein Zwischenspeicher von Datenbewegungen zwischen Hauptspeicher und den Prozessorregistern mit dem Ziel der Leistungssteigerung. Wenn der Prozessor ein Wort aus dem Hauptspeicher lesen will, wird es zuerst im Cache gesucht. Wenn das Wort schon im Cache vorliegt, dann wird es direkt an den Prozessor übergeben, sonst wird ein Block des Hauptspeichers, der aus einer festen Anzahl von Wörtern besteht und in dem das gesuchte Wort liegt, in den Cache kopiert und das Wort an den Prozessor transferiert. E/A- Geräte, die der permanenten Speicherung großer Datenmengen dienen, nennt man auch Sekundärspeicher. Ein Sekundärspeicher besteht normalerweise aus einem Datenträger (auch Medium genannt) und einem Laufwerk. Bei manchen Sekundärspeichern sind die Datenträger austauschbar, bei anderen sind sie fest im Laufwerk eingebaut. Laufwerke sind üblicherweise fest im Rechner eingebaut bzw. mit diesem verbunden. Beispiele für Datenträger sind: Magnetplatten, Magnetbänder (Spulen bzw. Kassetten), optische Speicher (CD, DVD usw.) und andere, siehe die Speicherhierarchie Register --> Cache --> Hauptspeicher --> Magnetplatte --> optischer Speicher --> Magnetband. Jede Stufe arbeitet als Cache für die nächstiefere Stufe. Die Kosten nehmen von oben nach unten ab, dagegen steigen die Kapazität und die Zugrifszeiten. Zur Beurteilung verschiedener Sekundärspeicher ist es hilfreich, drei verschiedene Motivationen für die permanente Speicherung von Daten zu unterscheiden: Arbeitsdaten: diese Daten werden beim täglichen Betrieb eines Rechners benutzt und müssen möglichst schnell verfügbar sein. Sicherungskopien (backup): dies sind Kopien der Arbeitsdaten; sie werden nur deshalb angefertigt, weil die Arbeitsdaten aus verschiedenen Gründen beschädigt werden könnten und nam dann wenigstens eine Sicherungskopie der Arbeitsdaten hat, auch wenn diese vielleicht veraltet ist. Auf den Sicherungskopien wird normalerweise nicht gearbeitet, sie werde nur im Bedarfsfall zurückkopiert. Deshalb braucht der Zugriff zu Sichrungskopien nicht besonders schnell zu sein. Da man u.U. von den gleichen Arbeitsdaten zu verschiedenen Zeitpunkten wiederholt Sicherungskopien anfertigt, kann der Umfang der Sicherungsdaten sehr groß werden; da diese Daten ansonsten zu nichts nütze sind, ist es hier besonders wichtig, die Kosten für die Speicherung der Daten gering zu halten. Archivierte Daten: dies sind ebenfalls Kopien von Arbeitsdaten, sie weisen aber eine Reihe von Unterschieden zu Sicherungskopien auf. Aus gesetzlichen oder anderen Gründen will man oft Daten über sehr lange Zeiträume (Jahrzehnte) verwahren. Daher kommt der Langzeitstabilität des Speichermediums hier eine größere  Bedeutung zu. Nachdem Arbeitsdaten archiviert worden sind, werden sie oft nicht mehr weiter bearbeitet und können als Arbeitsdaten gelöscht werden.  
• Welche Arten der Synchronistation kennen Sie? – Synchronisationsvariablen– Wir definieren eine globale Variable s, über die ein Prozess den kritischen Abschnitt für denjeweils anderen freigibt. – Nachteil: Die kritischen Abschnitte können nur abwechselnd 1,2,1,2,... ablaufen → keinÜberrunden möglich und ein Prozess kann nicht selbst zweimal hintereinander den gleichenkritischen Abschnitt aufrufen.– Lösungsmöglichkeit: 2 Synchronisationsvariablen verwenden → Neuer Nachteil: Gefahreines Deadlock– Peterson Algorithmus– 2 Variablen zum Anzeigen von Interesse in den kritischen Bereich einzutreten.– 1 Variable hält fest welcher Prozess dran ist– Nachteil: Aktives Warten (busy waiting)– Semaphore– Dijkstra hat daher das Konzept der Semaphore entwickelt. Eine Semaphore kann als eineVariable betrachtet werden, die einen ganzzahligen Wert hat. Mit Hilfe dieses Semaphores wirdeine bestimmte kritische Ressource überwacht.– Initialisiert man s mit k, so werden höchstens k gleichzeitige Zugriffe auf diese Ressourcezugelassen → meistens ist k=1.– Zur Benutzung der Semaphore stehen die Operationen down und up zur Verfügung.– down(s) bedeutet, dass der aktuelle Wert der Semaphore s um 1 vermindert wird. Wird derWert negativ, blockiert der Prozess, der down ausführt.– up(s) erhöht den Wert von s um 1. Ist der neue Wert nicht positiv, wird ein durch einedown-Operation blockierter Prozess freigegeben, er geht folglich vom Zustand blockiert in bereitüber.– Sei s der Semaphor eines kritischen Abschnittes, so wird down(s) vor und up(s) nach demkritischen Abschnitt ausgeführt.– Vorteil: hohe Geschwindigkeit, hardwareseitige Implementierung– Nachteil: up- und down-Operationen sind überall im Text verstreut, man verliert den Überblick– Nachrichtenaustausch– Ringpuffer– Sender-Empfänger-Prinzip– Zugriff auf Puffer muss synchronisiert werden– Unterscheidung zwischen Einweg-Kommunikation (nur von A nach B) und Zweiweg-Kommunikation (Sender A erwartet von Empfänger B eine Bestätigung).– Monitore– Vorteil: alle Funktionen nur im Monitor, nicht überall verteilt– Unter einem Monitor versteht man eine Menge von Prozeduren, Variablen undDatenstrukturen, die als Betriebsmittel betrachtet und mehreren Prozessen zugänglichgemacht sind. Die gemeinsam genutzten Betriebsmittel können geschützt werden, indem sieim Monitor platziert werden.– Ein Monitor unterstützt die Synchronisation durch Bedingungsvariablen, auf die zweiFunktionen wirken:– wait(c): Prozess wird blockiert, wenn c nicht erfüllt ist; Prozess kommt in dieWarteschlange der Bedingung c– signal(c): Wenn in einer Monitorprozedur die Bedingung c wahr wird, dann wird diesignal-Operation aufgerufen. Ein wartender Prozess wird ein aktiver.– Monitor-Konzept ist vergleichbar mit einem Raum, zu dem es nur einen einzigen bewachtenEingang gibt, so dass sich immer nur ein Prozess im Raum befinden kann. Andere Prozesse geratenin eine Warteschlange für blockierte Prozesse, die auf die Verfügbarkeit des Monitors (Änderung derBedingung c) warten. Sobald ein Prozess eingetreten ist, kann er sich selbst auf Grundlage derBedingung c blockieren, indem er wait(c) aufruft. Wenn ein Prozess, der im Monitor läuft, eineÄnderung von c bemerkt, ruft er signal(c) aus.– Monitor Hoare-Typ: Einer der wartenden Prozesse wird nun fortgesetzt, dersignalisierende Prozess wird angehalten. Dieser wird fortgesetzt, wenn der wartende Prozessden Monitor verlässt.– Monitor Mesa-Typ:Im Gegensatz zum HoarTey-p blockiert signal(c) den signalisierendenProzess nicht. Dieser wird stets fortgesetzt. signal(c) reiht stattdessen einen Prozess von derWarteschlange der Bedingungsvariablen c in die Monitor-Warteschlange um.

back  |  next 1 / 1