Knowledge & Learning

home *** CD-ROM | disk | FTP | other *** search

/ Knowledge & Learning / WISS_LERN.iso / doslern / computer / educard / bs___4.sti < prev next >

Wrap

Text File | 1992-02-13 | 26.7 KB | 677 lines

YCPAA #!!# - Deadlocks - @CEInhalt @CPDas Thema von BS___4 sind Deadlocks. Start mit ⌐Betriebsmittel II@BS___4¬ AHBAA #!!# Betriebsmittel II @HEWas sind Betriebsmittel ? @HB⌐Betriebsmittel@BS1¬ sind die in einem Datenverarbeitungssystem zur Erledigung eines Prozesses einsetzbaren technischen Einrichtungen (Hardware) und Dienstleistungen (Software). Beispiele technischer Einrichtungen: - Drucker, - Bandgeräte, - Speicher, - CPU, - Terminal, - Kanalwerk, ... Beispiele Dienstleistungen (im weiteren Sinne): - Programme, - Dateien, - Daten, - Prozesse, - Routinen, ... @HEVerwendung von Betriebsmitteln: @HBDie Verwendung von Betriebsmitteln wird unterschieden in: a) @HPwiederverwendbare@HB (reusable) Sie können nach ihrer Freigabe einem neuen ⌐Prozeß@BS1¬ zugewiesen werden. Beispiele: - CPU, - Speicher, - Dateien, ... b) @HPnicht wiederverwendbare@HB (consumable) Sie können nach ihrer Freigabe nicht wieder verplant werden, da sie aufgebraucht sind. Beispiele: - Nachrichten, - ⌐Rechenzeit@BS2¬, ... @HEZuteilung von Betriebsmitteln: @HBDie Zuteilung von Betriebsmitteln wird unterschieden in: a) @HPentziebare@HB (preemptible) Sie können dem Prozeß jederzeit ohne Schaden entzogen werden. Beispiele: - CPU, - Arbeitsspeicher, ... b) @HPnicht entziehbare@HB (non preemptible) Sie müssen dem Prozeß so lange zugewiesen bleiben, bis dieser sie von sich aus zurückgibt. Beispiele: - Drucker, - Bandgeräte, ... @HEZugriff auf Betriebsmittel: @HBDer Zugriff auf Betriebsmittel wird unterschieden in: a) @HPexklusiv benutzbar@HB (exclusive controllable) Sie können zu einem Zeitpunkt nur von einem einzigen Prozeß belegt werden. Beispiele: - Drucker, - Bandgeräte, - Schreibzugriff auf Dateien, ... b) @HPgemeinsam benutzbar@HB (common controllable) Sie können zu einem Zeitpunkt von mehreren Prozessen belegt werden. Beispiele: - Lesezugriff auf Dateien, - Code von Programmen, - Compiler in reentrant geschrieben, ... @HB weiter mit ⌐Deadlock II@BS___4¬ AHBAA #!!# Deadlock II @HEWas ist ein Deadlock ? @HBEin Prozeßsystem mehrerer paralleler Prozesse Pi @HAPARBEGIN P1, P2, ..., Pn PAREND; @HBist ein ⌐Deadlock@BS1¬, wenn der Prozeßfortschritt unendlich lange blockiert ist, weil zwei oder mehr Prozesse sich gegenseitig blockieren, indem sie selbst bereits exklusive, nicht-entziehbare ⌐Betriebsmittel@BS1¬ belegen, die ein anderer ⌐Prozeß@BS1¬ zur Fortsetzung seiner Arbeit benötigt. siehe auch: ⌐Betriebsmittel II@BS___4¬ @HE1. Beispiel: @HB @DP @HB @DP │ │ @HB @DP │ @DB╔═╗@DP │ @HB Deadlock-gefährdet @DP │ @DB╠═╣@DP │ @HB @DP │ @DA╚═╝@DP │ @HB Noch leicht auflösbar, @DP ─────────┘ @DM| /|\@DP └───────── @HB wenn ein Fahrer auf @DP @DM/___|______|___@DA╔@DB══╦══╗ @HB Vorfahrt verzichtet. @DP @DM\ | | @DA╚@DB══╩══╝ @HB @DP @DB╔══╦══@DA╗@DM___|______|___\ @HB @DP @DB╚══╩══@DA╝@DM | | / @HB @DP ─────────┐ @DM\|/ | @DP┌───────── @HB @DP │ @DA╔═╗@DP │ @HB @DP │ @DB╠═╣@DP │ @HB @DP │ @DB╚═╝@DP │ @HB @DP │ │ @HB @DP @HB @HE2. Beispiel: @HB @DP @HB @DP │ │ @HB @DP │ │ @HB Deadlock eingetreten @DP │ │ @HB @DP │ │ @HB Zur Auflösung müßte @DP ─────────┘ @DB╔═╗@DP └───────── @HB mindestens ein Fahrer @DP @DB╠═╣ @DA╔@DB══╦══╗ @HB zurückgesetzt werden. @DP @DA╚═╝ ╚@DB══╩══╝ @HB @DP @DB╔══╦══@DA╗ ╔═╗ @HB Das entspricht dem @DP @DB╚══╩══@DA╝ @DB╠═╣ @HB Abbruch eines Prozesses. @DP ─────────┐ @DB╚═╝@DP ┌───────── @HB ==> Schaden @DP │ │ @HB @DP │ │ @HB @DP │ │ @HB @DP │ │ @HB @DP @HB @HE3. Beispiel: @HAt @HBZwei Prozesse bewerben sich @HAP2 @HP/│\ @HBum ein exklusiv benutzbares @HP│ @HBBetriebsmittel. @HAt2e @HP│@HA_________ @HP│ @HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBDas rote Rechteck ist nicht @HP│ @HM▓▓nicht betretbar▓▓ @HBbetretbar, da das Betriebs- @HP│ @HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBmittel nur exklusiv verwend- @HAt2a @HP│@HA_________@HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBbar ist. Es muß also umgangen @HP│ @HA| | @HBwerden. @HP│ @HA| | @HP│ @HA| | @HP└─────────────────────────────────────────────> @HAt @HAt1a t1e P1 @HBIm dargestellten Prozeßverlauf wird P2 zwar behindert, aber es kommt zu keiner gegenseitigen Blockade. ??? @HE4. Beispiel: @HC▒ @HBunsicherer Bereich @HAt @HM▓ @HBnicht betretbar, da exklusives Betriebsmittel (BM) @HAP2 @HP/│\ @HP│ @HBP1 fordert zuerst BM b und @HG____@HP│@HG______ @HBwährend er noch b belegt, a an. @HG│ @HP│ @HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBP2 fordert zuerst BM a und @HAb@HG│ @HG_@HP│@HG______@HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBwährend er noch a belegt, b an. @HG│ │ @HP│ @HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBDer rote Bereich muß wieder @HG│__│_@HP│@HG______@HM▓▓▓▓x▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBumgangen werden. @HAa@HG│ @HP│ @HC▒▒▒▒@HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBGelangt ein Prozeß in den un- @HG│_@HP│@HG______@HC▒▒▒▒@HM▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HBsicheren Bereich, dann errei- @HP│ @HG| | | | @HBchen beide Prozesse den Punkt x. @HP└──────@HG|@HP───@HG|@HP─────────────@HG|@HP───@HG|@HP────────────────> @HAt @HG└───|────@HAb@HG────────┘ | @HAP1 @HG└────────@HAa@HG────────┘ @HBVom Punkt x an sind beide Prozesse im Deadlock. Hätten die Prozesse die BM in gleicher Reihenfolge angefordert, hätte es keinen Deadlock gegeben. @HENotwendige Bedingungen für das Entstehen eines Deadlocks: @HB4 Bedingungen sind für das Entstehen eines Deadlocks notwendig: 1. Bedingung des @HPgegenseitigen Ausschlusses@HB (mutual exclusion) Die angeforderten und vergebenen Betriebsmittel (also alle BM) sind exklusiv verwendbar. 2. Bedingung der @HPNicht-Unterbrechbarkeit@HB (non preemption) Die Betriebsmittel können einem Prozeß nicht entzogen werden. Der Prozeß muß sie von sich aus freigeben. 3. Bedingung des @HPWartens auf weitere Betriebsmittel@HB (resource waiting) Die Prozesse belegen die bereits erhaltenen exklusiven Betriebsmittel, während sie auf die Zuteilung noch weiterer Betriebsmittel warten. 4. Bedingung der @HPgeschlossenen Kette@HB (chains of tasks) Die Prozesse warten aufeinander, das heißt jeder Prozeß der Kette belegt bereits Betriebsmittel, die von einem anderen Prozeß der Kette benötigt werden. @HE3 prinzipielle Verfahren zur Behandlung von Deadlocks: @HB 1. @HPVerhindern@HB von Deadlocks (prevention) Das Betriebssystem ist so entworfen, daß Deadlocks unmöglich sind. Eine oder mehrere der notwendigen Bedingungen zur Entstehung eines Deadlocks werden ausgeschlossen. 2. @HPVermeiden@HB von Deadlocks (avoidance) Das Betriebssystem muß in der Lage sein, während des Prozeßablaufes dynamisch Maßnahmen zu starten, um es nicht zu einem Deadlock kommen zu lassen. Es muß vor dem Start eines Prozesses wissen, wieviel Betriebsmittel dieser von welchem Typ braucht (Maximalanforderung des Prozesses). Das Betriebssystem kontrolliert die Zuteilung von Betriebsmitteln mit Hilfe dieser Informationen so, daß nicht alle der notwendigen Bedingungen für das Entstehen eines Deadlocks gleich- zeitig erfüllt sind. 3. @HPErkennen und Beheben@HB von Deadlocks (detection and recovery) Das Betriebssystem testet von Zeit zu Zeit das Prozeßsystem, ob ein Deadlock vorliegt. Erkennt es einen Deadlock, so muß es diesen mit minimaler Schadensentstehung beseitigen. @HEVerhindern von Deadlocks (prevention) @HBDeadlocks kann man durch folgende Methoden verhindern: 1. Streng sequentieller Ablauf der Prozesse. - unrealistisch, da gerade Parallelität gewünscht ist. 2. Jeder Prozeß muß zu Beginn sämtliche Betriebsmittel, die er gebrauchen will, anfordern und zugeteilt bekommen. - unökonomisch, da ein Prozeß Betriebsmittel, die er nur zu Beginn oder am Ende benötigt, die restliche Zeit unnötig belegt. 3. Prozesse, die Betriebsmittel nachfordern, müssen zunächst alle Betriebsmittel, die sie bereits besitzen, freigeben. - Realisierung nur in speziellen Fällen möglich. Beispiel: Ein Prozeß fordert ein Bandgerät nach. Er muß dann zu- nächst alle Bandgeräte, die er schon besitzt, freigeben. Sie werden ihm praktisch entzogen. Magnetbandgeräte sind aber typische nicht-entziehbare Betriebsmittel. @HB 4. Betriebsmittel werden hierarchisch angeordnet. Ein Prozeß darf sie nur in dieser hierarchischen Reihenfolge anfordern, das heißt, er stellt zunächst Anforderungen an Betriebsmittel vom Typ Ti, die er braucht. Erst dann darf er Anforderungen an Ti+j (j ≥ 1) stellen. Betriebsmittel vom Typ Ti kann er dann nicht mehr bekommen. Beweisidee: 1. Fall: @HPEs gibt einen Prozeß mit Anforderung an höchste Ti. @HBForderungen nach Typen > Ti liegen noch nicht vor. Er braucht also auf keinen Prozeß zu warten und wird garantiert fertig. 2. Fall: @HPEs gibt 2 oder mehr Anforderungen an höchste Ti. @HBMindestens einer kann weiter, der dann auf keinen anderen Prozeß warten muß. Dies wird rekursiv fortgesetzt bis man zum 1. Fall gelangt. @HEBeispiel: Deadlockfreiheit beim ⌐5 Philosophen@BS___3¬-Problem durch hierarchische Rangfolge der Betriebsmittel (= Gabeln): @HM┌────┐@HB @HM│ 0 │@HB @HJ└┼┘@HB @HM└────┘@HB @HJ└┼┘@HB @HJ │@HB1 @HJ│@HB0 @HM┌────┐@HB @HM┌────┐@HB @HM│ 1 │@HB @HPSPAGHETTI@HB @HM│ 4 │@HB @HM└────┘@HB @HO≈≈≈≈≈≈≈≈≈ @HM└────┘@HB @HJ└┼┘@HB @HJ└┼┘@HB @HJ│@HB2 @HJ│@HB4 @HM┌────┐@HB @HJ└┼┘@HB @HM┌────┐@HB @HM│ 2 │@HB @HJ│@HB3 @HM│ 3 │@HB @HM└────┘@HB @HM└────┘@HB @HBPrioritäten: Gabel_0 < Gabel_1 < Gabel_2 < Gabel_3 < Gabel_4 @HBJeder Prozeß (= Philosoph) muß nun eine bestimmte Reihenfolge der P-Operationen entsprechend der Rangfolge der Betriebsmittel einhalten: @HAProzeß_i: CYCLE BEGIN Denken; P (Gabel geringerer Priorität); P (Gabel höherer Priorität); Essen; V (Gabel geringerer Priorität); V (Gabel höherer Priorität); END; @HBAngenommen alle 5 Philosophen wollen jetzt gleichzeitig essen. Dann wird den Philosophen 0 bis 3 ihre erste Gabel zugewiesen. Philosoph 4 möchte als erstes Gabel_0, die hat aber schon Philosoph 0. Nur der 3. Philosoph bekommt auch noch seine 2. Gabel (Gabel_4) und kann essen. ==> Schlechte Auslastung der Betriebsmittel, da nur einer ißt, obwohl zwei könnten. weiter mit ⌐Deadlock-Vermeidung@BS___4¬ AHBAA #!!# Deadlock-Vermeidung @HEVermeiden von Deadlocks (avoidance) @HBBeim Vermeiden von ⌐Deadlock@BS1¬s muß jeder ⌐Prozeß@BS1¬ vor dem Start seine Maximalanforderungen der einzelnen ⌐Betriebsmittel@BS1¬-Typen bekannt geben. Es muß vom System garantiert werden, daß die Prozesse ihre Maximalforderungen auch in Anspruch nehmen können. Im Gegensatz zum Verhindern von Deadlocks (siehe ⌐Deadlock II@BS___4¬) wird auf Grund der Informationen der Prozesse über ihre Betriebsmittel- Anforderungen und -Belegungen erst bei Neuanforderung von Betriebsmitteln überprüft, ob diese Neuanforderung zulässig ist oder nicht. Zulässig heißt hier, daß nicht alle für das Entstehen eines Deadlocks notwendigen Bedingungen erfüllt sind. Exklusiven Zugriff kann man aus logischen und physikalischen Gründen nicht verbieten. Nicht-Entziehbarkeit ist wegen der sonst entstehenden Schäden ebenfalls nicht zu verbieten. @HEGrößenabkürzungen: @HB - System P besteht aus n Prozessen @HPP = {P1, ..., Pn}@HB - Anzahl der Betriebsmittel-Typen : @HPT@HB - Anzahl der vorhandenen Betriebsmittel : m @HPm = (m1, ..., mT)@HB - Anzahl der vorhandenen Betriebsmittel : FREE @HPFREE = (free1, ..., freeT)@HB - Maximalwerte der Betriebsmittel für Prozeß Pi : MAXi @HPMAXi = (max1, ..., maxT), 1 ≤ i ≤ n@HB - aktuell angeforderte Betriebsmittel : REQ @HPREQ = (req1, ..., reqT)@HB - Anzahl der zugewiesenen Betriebmittel für Prozeß Pi : DEVi @HPDEVi = (dev1, ..., devT), 1 ≤ i ≤ n@HB - Anzahl der noch benötigten Betriebsmittel für Pi : NEEDi @HPNEEDi = (need1, ..., needT), 1 ≤ i ≤ n@HB @HBOffensichtlich muß gelten: 1. Die Anzahl der noch freien Betriebsmittel ist gleich der Anzahl der vorhandenen minus der Summe der zugewiesenen Betriebsmittel aller Prozesse@HP n FREE = m - (für alle j: Σ dev ij), 1 ≤ j ≤ T i=1 @HB 2. Die Anzahl der Betriebsmittel, die ein Prozeß noch benötigt, ist gleich der Maximalanforderung des Prozesses minus der ihm bereits zugewiesenen Betriebsmittel@HP NEEDi = MAXi - DEVi @HEKriterien für die Realisierbarkeit eines Zustandes @HBEs gibt drei Forderungen damit ein Zustand realisierbar ist: 1. Kein Prozeß kann mehr Betriebsmittel anfordern, als im System überhaupt vorhanden sind. @HPMAXi ≤ m @HB 2. Kein Prozeß darf mehr Betriebsmittel zugewiesen bekommen, als er an Maximalanforderung zu Prozeßbeginn angegeben hat. @HPDEVi ≤ MAXi @HB 3. Kein Prozeß kann mehr Betriebsmittel eines Typs anfordern, als noch frei sind. @HPREQ ≤ FREE @HBDie Realisierbarkeit eines Zustandes ist notwendig, aber nicht hinreichend, um Deadlockfreiheit zu garantieren. @HEBeispiel: @HAm = (4) @HAMAX = (4, 4, 2) @HBDer dargestellte Zustand ist zwar @HADEV = (1, 1, 1) @HBrealisierbar, aber er ist nicht sicher. @HBEin unsicherer Zustand gilt bereits @HAAnzahl BM @HBals Deadlock. @HP/│\ @HA4@HP┤ @HP┤ @HP┤ @HA1@HP┤@HJ░░░░░░ ▒▒▒▒▒▒ ▓▓▓▓▓▓ @HP└──────┬──────┬──────┬──> @HAProzesse @HAP1 P2 P3 @HEFall 1 @HBP1 (oder auch P2) fordert noch freies Betriebsmittel an. @HAm = (4) MAX = (4, 4, 2) DEV = (1, 1, 1) @HAAnzahl BM @HP/│\ @HA4@HP┤ @HP┤ @HP┤@HJ░░░░░░ @HA1@HP┤@HJ░░░░░░ ▒▒▒▒▒▒ ▓▓▓▓▓▓ @HP└──────┬──────┬──────┬──> @HAProzesse @HAP1 P2 P3 @HB==> Deadlock, wenn Maximalanforderungen in Anspruch genommen werden. @HEFall 2 @HBP3 fordert noch freies Betriebsmittel an. @HAm = (4) @HBDeadlock, da P3 zwar fertig werden kann, @HAMAX = (4, 4, 2) @HBaber die frei gewordenen Betriebs- @HADEV = (1, 1, 1) @HBmittel nicht für einen der anderen @HBProzesse ausreichen. @HAAnzahl BM @HP/│\ @HA4@HP┤ @HP┤ @HP┤ @HJ▓▓▓▓▓▓ @HA1@HP┤@HJ░░░░░░ ▒▒▒▒▒▒ ▓▓▓▓▓▓ @HP└──────┬──────┬──────┬──> @HAProzesse @HAP1 P2 P3 @HESicherer Zustand @HBEin Prozeßsystem P ist in einem sicheren Zustand Z, wenn eine der beiden folgenden Bedingungen erfüllt ist: a) |P| ≤ 1, das heißt es gibt keinen oder nur einen Prozeß b) Es gibt einen Prozeß Pi, der beendbar ist, und der Folgezustand Z+ mi P - {Pi} und FREE+ = FREE + DEVi ist sicher. Anders gesagt: Zu jedem Zeitpunkt gibt es einen Prozeß, der seine Maximalanforderungen erfüllt bekommen kann, also beendet werden kann. weiter mit ⌐Deadlock-Algorithmen@BS___4¬ AHBAA #!!# Deadlock-Algorithmen @HEHabermann'sche Forderung @HBAusgangspunkt der Habermann'schen Forderung ist ein sicherer Zustand (siehe ⌐Deadlock-Vermeidung@BS___4¬). Nach Zuteilen einer Betriebsmittel- anforderung muß es eine Folge beendbarer Prozesse geben, in der sämtliche Prozesse enthalten sind. Genauer: Nach Zuteilen einer Betriebsmittel-Anforderung muß es mindestens einen Prozeß geben, der fertig werden kann. Dieser gibt dann seine Betriebs- mittel frei. Jetzt muß es einen Prozeß geben, der mit den jetzt vor- handenen Betriebsmitteln fertig werden kann. Usw. @HL NEEDk1 ≤ FREE NEEDk2 ≤ FREE + DEVk1 : : NEEDkj ≤ FREE + DEVk1 + DEVk2 + ... + DEVk(j-1) <==> NEEDkj ≤ FREE + S (k-1), k = 1..n @HBDa gilt @HLNEEDi = MAXi - DEVi @HBergibt sich @HLMaxk - DEVk ≤ FREE + S (k-1) MAXk ≤ FREE + DEVk + S (k-1) MAXk ≤ FREE + S (k) @HBSetzt man die Habermann'sche Forderung in einen Algorithmus um, der diese Folge von beendbaren Prozessen findet, so muß dieser unter Umständen sämtliche Permutationen der n Prozesse durchlaufen, das heißt eine als nicht sicher erkannte Folge immer wieder umstellen. Da es n Prozesse sind gibt es n! Permutationen. Der Aufwand des Algorithmus ist bei T Betriebsmittel-Typen etwa von der Ordnung: O (T * n) bis O (T * n²). @HEDeadlockalgorithmus für einen einzigen Betriebsmittel-Typ @HBVorüberlegungen: Gegeben seien m Betriebsmittel vom gleichen Typ. @HEA) Für jeden Prozeß muß dann gelten: @HB1. @HP1 ≤ MAXi ≤ m @HB Entspricht dem 1. Kriterium für die Realisierbarkeit eines Zustandes. Kein Prozeß kann mehr Betriebsmittel eines Typs anfordern als im System überhaupt vorhanden sind. 2. @HP0 ≤ DEVi ≤ MAXi @HB Entspricht dem 2. Kriterium für die Realisierbarkeit eines Zustandes. Keinem Prozeß darf mehr Betriebsmittel zugewiesen werden, als er an Maximalforderung zu Prozeßbeginn angegeben hat. @HB3. @HPn @HPS (n) = Σ DEVi ≤ m @HPi=1 @HB Es können nicht mehr Betriebsmittel eines Typs zugewiesen werden, als im System überhaupt vorhanden sind. @HEB) Abschätzen der Anzahl von Betriebsmitteln m @HB Sei G der größte zulässige Maximalwert einer Anforderung eines Prozesses. Dann kann kein Deadlock auftreten, wenn m ≥ n * G ist. Andererseits rechen bereits genau n * G Betriebsmittel aus. Als untere Grenze für die Anzahl der Betriebsmittel liegt G fest, da die Maximalanforderung erfüllt werden können muß. m muß also im Bereich von G bis N * G liegen. Dieser Bereich läßt sich aufteilen in einen Bereich, in dem Deadlocks auftreten können und in einen Deadlock freien Bereich: @HPDeadlock gefährdeter Bereich: [G .. n * (G - 1)] Deadlock freier Bereich: [n * (G - 1) + 1 .. n * G] @HBDer Bereich läßt sich noch genauer angeben durch: @HPuntere Grenze: max (MAXi), 1 ≤ i ≤ n n obere Grenze : (Σ (MAXi - 1)) + 1 i=1 @HEC) Habermann'sches Theorem @HBHabermann verwendet für das Vermeiden von Deadlocks bei nur einem Betriebsmittel-Typ eine m*n-Matrix, in der für jeden Prozeß Pi seine Maximalanforderung und die Anzahl der aktuell belegten Betriebsmittel eingetragen sind. (siehe auch nächste Seite) n ist m < (Σ (MAXi - 1)) + 1, so kann man durch Abzählen feststellen, ob i=1 ein Deadlock vorliegt oder nicht. Man wählt eine horizontale Linie y = k und zählt die schraffierten Flächen oberhalb und unterhalb dieser Linie. Die Zahl der oberhalb belegten Betriebsmittel bezeichnet man mit Uk (upper), die Zahl der unterhalb belegten Betriebsmittel mit Lk (lower). Uk plus Lk ist die Summe aller belegten Betriebsmittel: Uk + Lk = S (n) @HEVeranschaulichung der n*m-Matrix @HAAnzahl BM @HP/│\ @HA4@HP┤ @HP┤@HJ░░░░░░ @HP┤@HJ░░░░░░ @HA1@HP┤@HJ░░░░░░ ▒▒▒▒▒▒ ▓▓▓▓▓▓ @HP└──────┬──────┬──────┬──> @HAProzesse @HAP1 P2 P3 @HBIm dargestellten Systemzustand sei T = 1, n = 3, m = 7. Für k = 2 gilt dann zum Beispiel Uk = 1 und Lk = 4 Insgesamt sind Uk + Lk = 5 Betriebsmittel belegt. DEV1 = 3, DEV2 = DEV3 = 1. |FREE| ist also = 2. @HEHabermann'sches Theorem @HPEin Zustand enthält dann und nur dann einen Deadlock, wenn es ein k aus 0..m gibt, für das gilt: Uk > m - k @HBPositiv ausgedrückt: @HPEin Zustand ist dann und nur dann deadlockfrei, wenn für alle k aus 0..m gilt: Uk ≤ m - k @HBBeweisidee: I. Es muß gelten: @HPUk + Lk ≤ m @HBDas heißt es können nicht mehr Betriebsmittel vergeben werden als vorhanden sind. II. Es muß gelten: @HPLk ≥ k - FREE @HBIII. Es gilt: @HPUk + Lk = m - FREE @HBDie belegten Betriebsmittel ergeben sich, indem man von allen Betriebsmitteln die freien abzieht. @HB Die hinreichende und notwendige Bedingung für Deadlock-Freiheit @HPfür alle k aus 0..m gilt: Uk ≤ m - k @HB ergibt sich also durch II. und III.: Uk + Lk = m - FREE Lk auf die rechte Seite bringen und Ersetzen durch k - FREE. Wegen Lk >= k - FREE folgt dann die Behauptung. @HEAlgorithmus zur Deadlockuntersuchung (für einen Betriebsmittel-Typ) @HBMan führt eine Tabelle mit den Maximalanforderungen und aktuell belegten Betriebsmitteln für jeden Prozeß. Der Vektor U enthält die aktuellen Uk's der Prozesse Pi. Fordert ein Prozeß ein Betriebsmittel an, so wird erst geprüft, ob der neue Zustand realisierbar ist. Ist dies der Fall, so wird der Vektor U auf den neuen Stand gebracht. Die Deadlockuntersuchung erfolgt nach der Theorem-Ungleichung: @HPFür alle k aus 0..m muß gelten: Uk ≤ m - k @HBWird ein Deadlock entdeckt, müssen alle Änderungen rückgängig gemacht werden. Wird keiner entdeckt, so wird dem Prozeß das Betriebsmittel zugewiesen. @HEAufwand: @HB O (max (MAXi)) Der Vektor ändert sich ab dem Index MAXi - DEVi - 1 = k Der Algorithmus läßt sich noch verbessern, indem man eine neue Größe k_min einführt. k_min ist der kleinste Wert von k, für den gilt: Uk = m - k. Durch die Zuweisung eines Betriebsmittels an der Stelle j ändern sich alle Werte von U für k < j (Uk := Uk + 1). Deadlockfreiheit kann nur garantiert werden für j < k_min. Für j > k_min kann Uj > m - j gelten, d. h. Deadlockgefahr. @HEAufwand nun: @HBWird kein Deadlock entdeckt, gleiche Ordnung wie oben. Wird jedoch einer entdeckt braucht nicht mehr der ganze Vektor U durchsucht zu werden. Es reicht die Abfrage j > k_min. @HEDeadlock-Algorithmus für mehrere Betriebsmittel-Typen @HBDer Deadlock-Algorithmus für einen einzigen Betriebsmittel-Typ ist nicht anwendbar bei mehreren Betriebsmittel-Typen. Man kann Fälle konstruieren, in denen zwar für jeden einzelnen Betriebsmittel-Typ der Zustand deadlockfrei ist, der Gesamtzustand aber nicht. @HEAlgorithmus-Idee: @HAMenge aller Prozesse REPEAT Überprüfe für alle Prozesse: Kann die Anforderung von Prozeß i erfüllt werden ? Falls ja, streiche ihn aus der Menge aller Prozesse und verwende die frei gewordenen Betriebsmittel wieder. UNTIL die Anforderung keines Prozesses kann erfüllt werden. Ist am Ende der Überprüfung die Menge leer, so ist der Zustand sicher, sonst ist der Zustand unsicher. @HEAufwand des Algorithmus für mehrere Betriebsmittel-Typen T @HB a) günstiger Fall : Es kann immer der nächste Kandidat aus der Menge gestrichen werden. @HPO (n * T) @HB b) ungünstigster Fall: Es kann immer erst der letzte Kandidat der Menge gestrichen werden. @HPO (T * n²) @HEBemerkung: @HBPermutationen in der Prozeßreihenfolge (Ordnung der Menge aller Prozesse) ändern nichts an dem Zustand (sicher bzw. unsicher). Wenn x Prozesse aus der Menge gestrichen sind, so ist eine bestimmte Menge von Betriebsmitteln frei. Durch eine Permutation dieser x Prozesse ändert sich nichts an dieser Menge. Durch eine Permutation der Prozesse kann sich aber der Aufwand des Algorithmus ändern. @HEErkennen und Beseitigen von Deadlocks @HBDas Erkennen und Beseitigen von Deadlocks auf der einen und das Vermeiden von Deadlocks auf der anderen Seite unterscheiden sich nur a) durch den Zeitpunkt der Untersuchung, b) dadurch, daß man die Maximalanforderungen der Prozesse nicht mehr kennen braucht. @HEDas Erkennen von Deadlocks @HBVon Zeit zu Zeit wird der aktuelle Zustand auf Deadlockfreiheit unter- sucht. Man testet, ob Prozesse, die auf die Erfüllung ihrer Anforderungen warten, jemals die angeforderten Betriebsmittel erhalten können. Man ver- wendet dazu die selben Algorithmen wie beim Vermeiden von Deadlocks (man ersetzt lediglich "NEED" durch "REQ", restliche Anforderung durch aktuelle). @HEDas Beseitigen von Deadlocks @HBIst ein Deadlock entdeckt, so wird festgestellt, welche Prozesse daran beteiligt sind. (Z.B. sind dies die noch verbliebenen Prozesse in der Menge aller Prozesse im obigen Algorrithmus.) Es wird dann derjenige Prozeß abgebrochen, bei dem der entstandene Schaden am geringsten ist. @HEBemerkung @HBDas Erkennen und Beseitigen von Deadlocks wird dem Vermeiden von Deadlocks in einigen Systemen vorgezogen, weil der Aufwand geringer als bei den anderen Lösungen ist. Es ist allerdings zu bezweifeln, daß der Zeitgewinn den entstandenen Schaden beim Beseitigen eines Deadlocks aufwiegt. weiter mit ⌐Scheduling II@BS___5¬