Knowledge & Learning

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

/ Knowledge & Learning / WISS_LERN.iso / doslern / computer / educard / bs___3.edu < prev next >

Wrap

Text File | 1992-03-19 | 37.3 KB | 1,421 lines

61 BS___3 Diplomprüfung Informatik (Teil 3 von 7) Teilprüfung Betriebssysteme Thema: Synchronisation paralleler Prozesse zusammengestellt von Andreas Smoor Wichtiger Hinweis: Nach der Beantwortung einer Frage besteht die Möglichkeit, sich durch Drücken der Taste "i" den thematischen Kontext anzusehen. März 1992 Was versteht man unter Unter Parallelität im engeren Sinn versteht man Parallelität das gleichzeitige Ablaufen mehrerer Prozesse. im engeren Sinn ? 2 Parallelität 1 1 Parallelität - 1 31100186 Was versteht man unter Unter Parallelität im weiteren Sinn versteht man, Parallelität daß Prozesse in beliebiger, nicht festlegbarer Reihen- im weiteren Sinn ? folge, die im Grenzfall sequentiell sein kann, ablaufen dürfen. 2 Parallelität 0 1 Parallelität - 2 31200187 Nennen Sie drei Möglichkeiten Parallele Prozesse lassen sich darstellen durch: parallele Prozesse - Schreibweisse einer Programmiersprache darzustellen. - Präzedenzgraphen - Ordnungsrelationen 2 Parallelität 0 1 Parallelität - 3 31300188 Definieren Sie den Begriff Unter Synchronisation versteht man die gegenseitige zeitliche Abstimmung Synchronisation. paralleler Prozesse beim Zugriff auf gemeinsame exklusiv benutzbare Betriebsmittel. 2 Synchronisation 0 1 Synchronisation - 1 32200189 Synchronisation, also die Synchronisation kann man gegenseitige zeitliche erreichen, indem man Abstimmung, kann man Befehlsfolgen zu einer erreichen, indem man unteilbaren Operation Befehlsfolgen ... zusammenfaßt, so daß die Befehle der Folge nur Ergänzen Sie den Satz. sequentiell ablaufen können. 2 Synchronisation 0 1 Synchronisation - 2 32200190 Eine Möglichkeit zur Ein kritisches Gebiet ist Synchronisation wird durch dadurch gekennzeichnet, daß Einführen kritischer Gebiete Operationen in ihnen nur von gegeben. einem einzigen Prozeß ausge- führt werden dürfen. Dies Was versteht man unter einem wird erst durch die Synchro- kritischen Gebiet ? nisationsmethoden erreicht. 2 Synchronisation 0 1 kritisches Gebiet 32300191 Wie erfolgen Prozeßwechsel Bei Rechenanlagen mit nur bei Rechenanlagen mit nur einer CPU erfolgen einer CPU ? Prozeßwechsel auf Grund von Interrupts. 2 Interrupts sperren 0 1 Prozeßwechsel 33100192 Befehle höherer Programmier- Eine Synchronisationsmethode sprachen bestehen aus besteht darin, Befehle mehreren Elementar- höherer Programmiersprachen operationen. Dies kann man unteilbar zu machen. Es kann zur Synchronisation nutzen. also nicht innerhalb eines solchen Befehls zu einem Wie ? Prozeßwechsel kommen. 2 Interrupts sperren 0 1 Elementaroperation 33100193 Wie kann man bei Systemen Um bei einem System mit nur einer CPU einen Befehl mit nur einer CPU einen unteilbar zu machen, muß man während der Abarbeitung Befehl unteilbar machen ? dieses Befehls die Interrupts sperren, die einen Prozeß- wechsel auslösen könnten. 2 Interrupts sperren 0 1 unteilbarer Befehl 33100194 Was sind die Nachteile bei - Nur privilegierte Benutzer (Supervisor) können der Synchronisation durch Interrupts sperren - Es können Interrupts das Sperren von Interrupts ? verloren gehen - Nur für Einprozessor- Systeme möglich. 2 Interrupts sperren 0 1 Interrupts sperren 33100195 LOCK und UNLOCK Befehle sind LOCK (x): unteilbare Befehle, über die {IF x = 0 THEN x := 1 insbesondere Mehrprozessor- ELSE GoTo LOCK (x)} Anlagen verfügen. UNLOCK (x): {x := 0} Wie sind LOCK und UNLOCK Befehl definiert ? {...} bedeutet hier unteilbar 2 LOCK und UNLOCK 0 1 LOCK und UNLOCK - 1 33200195 Wie sieht der Zugriff auf Ein Prozeß, der X benutzen ein Betriebsmittel X aus, möchte, sieht solange in falls dieser mit LOCK (x) und LOCK (x) nach, bis x=0 gilt. UNLOCK (x) Befehlen zur Dann setzt er x auf 1 und Synchronisation geschützt betritt das kritische Gebiet. wird ? Wenn er dieses verläßt, setzt er x wieder auf 0. 2 LOCK und UNLOCK 1 1 LOCK und UNLOCK - 2 33200196 Erklären Sie das Phänomen des Die Prozesse belasten den Prozessor mit ihren ständigen "pollings" Abfragen, ob das Betriebs- mittel endlich frei ist. auch "busy waiting" genannt. 2 LOCK und UNLOCK 0 1 Polling - 1 33200197 Wie könnte das Problem des Ein Prozeß, der auf ein gesperrtes Betriebsmittel X Pollings zugreifen möchte, sollte schon beim ersten Versuch gelöst werden ? auf Eis gelegt werden und erst wieder aktiviert werden, wenn X frei gegeben wurde. 2 LOCK und UNLOCK 0 1 Polling - 2 33200198 Falls sich in einem System Wenn B sich im kritischen ein Prozeß A mit hoher und Gebiet befindet und das Be- ein Prozeß B mit niedriger triebsmittel X freigeben will Priorität befindet, kann es kann es sein, daß er das bei der LOCK / UNLOCK Methode niemals kann, weil A den zu Deadlocks kommen. Prozessor blockiert, indem A Erklären Sie warum. dauernd nach X fragt. 2 LOCK und UNLOCK 0 1 LOCK und UNLOCK - 3 33200199 Wie kann man Deadlocks Durch Verwendung dynamischer vermeiden, obwohl man die Prioritäten, die für einen LOCK / UNLOCK Methode Prozeß, der sich im Wartezu- benutzen und Prioritäten stand auf ein Betriebsmittel für die Prozesse vergeben befindet, in festen Zeitab- möchte ? ständen erniedrigt werden. 2 LOCK und UNLOCK 0 1 LOCK und UNLOCK - 4 33200200 Der Dekker-Algorithmus zur Ein Prozeß A zeigt durch sA=0 Synchronisation von zwei Pro- an, daß er in G möchte. Falls zessen verwendet 2 Boolsche sB auch = 0 und turn = B, Variablen s für die Bewerbung d. h. B ist in G, dann sA=1 und turn für die Belegung und warten bis turn = A. Dann des kritischen Gebiets G. Wie wieder sA=0, und hinein in G. läuft das prinzipiell ? Nach G sA=1 und turn = B. 2 Dekker 0 1 Dekker-Algorithmus 33300201 Der Algorithmus von Dijkstra Der Algorithmus paßt nicht bietet eine Synchronisations- auf diese Karte. Deshalb lösung für N Prozesse. nach der Kontrolle die Wie sieht er aus ? Taste "i" für mehr Information drücken. 2 Dijkstra 1 1 Dijkstra - Algorithmus - 1 33300202 Bei Verwendung des Es ist möglich, daß beim Dijkstra-Algorithmus zur Dijkstra-Algorithmus Prozesse Synchronisation von verhungern, weil nicht fest- N parallelen Prozessen kann gelegt ist, wie der es zum "Verhungern" von "Auserwählte" bestimmt wird, Prozessen kommen. der das kritische Gebiet be- Was ist damit gemeint ? treten darf, wenn er möchte. 2 Dijkstra 1 1 Dijkstra - Algorithmus - 2 33300203 Um die Möglichkeit des Ein Prozeß muß auf höchstens Verhungerns beim Dijkstra- f (N) Besuche des kritischen Algorithmus auszuschließen, Gebiets durch andere Prozesse haben einige kluge Leute warten. Verbesserungsvorschläge Für f (N) gibt es dann von gemacht. Worauf laufen diese den einzelnen Leuten im Grunde genommen hinaus ? verschiedene Vorschläge. 2 Dijkstra 1 1 Dijkstra - Algorithmus - 3 33300204 Um die Synchronisation Dijkstra hat einen Datentyp paralleler Prozesse eleganter Semaphor eingeführt, mit dem zu lösen und um ein man wartende Prozesse "busy-waiting" zu vermeiden, schlafen legen kann und beim hat Dijkstra Semaphore Eintreten des Ereignisses, eingeführt. Was muß man sich auf das sie warten, wieder darunter vorstellen ? wecken kann. 2 Semaphore 1 1 Semaphor - 1 33400205 Im allgemeinen sind auf Semaphor-Operationen: Semaphoren drei Operationen - Initialisierung definiert. - P-Operation Welche ? - V-Operation 2 Semaphore 1 1 Semaphor - 2 33400206 Wie ist die P (s) = { s := s - 1; IF s < 0 THEN Warte (s); } P-Operation P (s) ist unteilbar. für Semaphore definiert ? 2 Semaphore 0 1 Semaphor - 3 33400207 Was geschieht bei Der Prozeß wird schlafen Synchronisation durch gelegt (angehalten). In Semaphore mit einem Prozeß, seiner Zustandsbschreibung der wird notiert, daß er auf eine "Warte (s)" V-Operation auf das Semaphor s wartet. ausführt ? 2 Semaphore 0 1 Semaphor - 4 33400208 Wie ist die V (s) = { s := s + 1; IF s ≤ 0 THEN Wecke (s); } V-Operation V (s) ist unteilbar. auf Semaphore definiert ? 2 Semaphore 0 1 Semaphor - 5 33400209 Was geschieht bei der Bei Wecke (s) wird einer der Synchronisation mit Hilfe von Prozesse, die auf s warten Semaphoren, wenn geweckt und kann weiter- rechnen. Die Auswahl des "Wecke (s)" Prozesses kann zufällig oder nach dem FIFO-Prinzip ausgeführt wird ? geschehen. 2 Semaphore 0 1 Semaphor - 6 33400210 Warum ist es von Vorteil, Falls auch negative Werte für Semaphore zugelassen sind für Semaphore auch negative kann das Betriebssystem erkennen, ob und auch wie- Werte zuzulassen ? viele Prozesse auf ein V (s) warten. 2 Semaphore 0 1 Semaphor - 7 33400211 Semaphore dienen in erster Schutz durch Semaphore: Linie dem Schutz kritischer Gebiete. : P (s) Wie sieht der Schutz dabei kritisches Gebiet immer prinzipiell aus ? V (s) : 2 Semaphore 1 1 Semaphor - 8 33420212 Welcher Vorgang ist als Ein Produzent von Nachrichten möchte einem Verbraucher Erzeuger - Verbraucher Nachrichten zukommen lassen. Dazu legt er diese in einen Problem bekannt ? Puffer, einen Speicher variabler Länge, ab. Von dort holt sie der Verbraucher. 2 Erzeuger-Verbraucher 0 1 Erzeuger-Verbraucher - 1 33420213 Welche Forderungen werden an - Prozesse sollen sich beim Zugriff auf den Puffer eine Lösung des Erzeuger- nicht stören - nichts in vollen Puffer Verbraucher-Problems legen - nichts aus leerem Puffer gestellt ? holen 2 Erzeuger-Verbraucher 0 1 Erzeuger-Verbraucher - 2 33420214 Eine Forderung an eine Lösung Die Arbeitsgeschwindigkeit für das Erzeuger-Verbraucher Problem hängt mit der von Erzeugern und Arbeitsgeschwindigkeit von Erzeugern und Verbrauchern Verbrauchern soll unabhängig zusammen. Welche ? voneinander sein. 2 Erzeuger-Verbraucher 0 1 Erzeuger-Verbraucher - 3 33420215 Wie sieht eine triviale Man erzwingt eine sequentielle Reihenfolge Lösung des Erzeuger- für das Beschreiben und Leeren des Puffers. Verbraucher- Problems aus ? Mehr Information durch die Taste "i". 2 Erzeuger-Verbraucher 0 1 Erzeuger-Verbraucher - 4 33420216 Was passiert, wenn man die Es kommt zum "Stottern" des triviale Lösung des Druckers. Er liest und druckt Erzeuger-Verbraucher-Problems Pufferinhalt, muß dann aber beispielsweise auf eine warten bis der Puffer wieder Druckerausgabe anwendet ? beschrieben wurde, da dieser während des Lesens ja nicht gefüllt werden durfte. 2 Erzeuger-Verbraucher 1 1 Erzeuger-Verbraucher - 5 33420217 Wenn man zur Lösung des Stottern läßt sich vermeiden, Erzeuger-Verbraucher-Problems indem man zwei oder mehr den Puffer nur entweder Lesen (Kreispuffer) einführt. oder beschreiben darf, kommt Während der eine Puffer ge- es zum "Stottern". Wie läßt lesen wird, kann der nächste sich dieses Problem bereits beschrieben werden. beheben ? 2 Erzeuger-Verbraucher 1 1 Erzeuger-Verbraucher - 6 33420218 Eine Lösung des Erzeuger- Die Antwort ist zu umfang- Verbraucher-Problems läßt reich für diese Karte. sich durch Verwendung eines Kreispuffers erreichen. Drücken Sie deshalb nach der Skizzieren Sie die Lösung Kontrolle die Taste "i", unter Verwendung von falls Sie die Lösung sehen Semaphoren. möchten. 2 Erzeuger-Verbraucher 1 1 Kreispuffer 33420219 Beim Leser-Schreiber-Problem - Es dürfen mehrere L gleich- gibt es zwei Arten von zeitig aktiv sein. Prozessen, Leser L und - Es darf immer nur ein S Schreiber S, die auf ein aktiv sein. gemeinsames Betriebsmittel - Falls ein S aktiv ist, dann zugreifen. darf kein L aktiv sein. Welche Regeln gelten dabei ? - Bevorzugung von L oder S 2 Leser-Schreiber 1 1 Leser-Schreiber - 1 33430220 Geben Sie eine Lösung des Die Antwort paßt nicht auf Leser-Schreiber-Problems mit diese Karte. Hilfe von Semaphoren an, bei der die Leser gegenüber den Den Algorithmus erhalten Sie Schreibern bevorzugt nach der Kontrolle durch die behandelt werden. Taste "i". 2 Leser-Schreiber 1 1 Leser-Schreiber - 2 33430221 Geben Sie eine Lösung des Die Antwort paßt nicht auf Leser-Schreiber-Problems mit diese Karte. Hilfe von Semaphoren an, bei der ein Schreiber gegenüber Den Algorithmus erhalten Sie den Lesern bevorzugt wird. nach der Kontrolle durch die Taste "i". 2 Leser-Schreiber 1 1 Leser-Schreiber - 3 33430222 Beim 5 Philosophen-Problem Um zu essen braucht jeder der sitzen 5 derselben an einem Philosophen seine linke UND kreisförmigen Tisch. Zwischen seine rechte Gabel. Die je 2 von ihnen liegt eine Gabeln stellen ein exklusives Gabel. Betriebsmittel dar, auf das der Zugriff synchronisiert Wo liegt ihr Problem ? werden muß. 2 5 Philosophen 0 1 5 Philosophen - 1 33440223 Lösung für 5 Philosophen: Wenn alle Philosophen gleich- "denken" zeitig auf ihre linke Gabel P (g [i]); P (g [i+1]); zugreifen (g [i]) ist noch "essen" alles ok. Dann wollen aber V (g [i]); V (g [i+1]); alle ihre rechte (g [i+1]) Die Lösung ist deadlock- und alle warten darauf, daß gefährdet. Wieso ? ihr Nachbar sie freigibt. Ko. 2 5 Philosophen 0 1 5 Philosophen - 2 33440224 Wie kann man beim Zugriff in kritisches Gebiet: 5 Philosophen-Problem vermei- : den, daß alle gleichzeitig P (mutex); auf ihre linke Gabel zugrei- P (gabel [i]); fen um danch alle auf die P (gabel [i+1]); Freigabe ihrer rechten Gabel V (mutex); zu warten ? : 2 5 Philosophen 1 1 5 Philosophen - 3 33440225 Falls man beim 5 Philosopen- Es kann vorkommen, daß ein Problem die Zugriffe auf Philosoph warten muß, obwohl rechte und linke Gabel zusam- seine beiden Gabeln frei men in ein kritisches Gebiet wären, weil ein anderer das legt, erhält man eine kritische Gebiet durch schlechte Auslastung der Be- Warten auf eine Gabel triebsmittel Gabeln. Warum ? versperrt. 2 5 Philosophen 0 1 5 Philosophen - 4 33440226 Wie wird das 5 Philosophen- Indem man Zustandsvariablen für jeden Philosophen ein- Problem am besten gelöst ? führt (denken, hungrig sein, essen), erreicht man, daß ein Philosoph immer essen kann, wenn seine beiden Gabeln frei sind. 2 5 Philosophen 0 1 5 Philosophen - 5 33440227 Semaphore sind ein mächtiges - undurchsichtig Instrument zur Synchroni- - schwer zu konstruieren sation. Der Prozessor wird - keine Plausibilitätsprüfung nicht durch "busy-waiting" durch Compiler möglich belastet. - welche P- und V-Operationen Nennen Sie Nachteile der Syn- gehören zusammen ? chronisation durch Semaphore. - schwierige Beweismethoden 2 5 Philosophen 0 1 Semaphor - 9 33440228 In einem Ansatz für "Beweise nv [s] : bisher ausgeführte von Semaphor-Operationen" V-Operationen auf s führt man Buch über bestimmte np [s] : begonnene und auch Operationen auf ein vollendete P-Operationen Semaphor s. na [s] : alle jemals Welche Operationen werden begonnenen P-Operationen dabei gezählt ? auf s 2 5 Philosophen 1 1 Habermann - 1 33440229 Wie ist die P-Operation P (s): definiert, wenn man zur { na [s] := na [s] + 1; Beweisführung nv [s], s := s - 1; np [s] und na [s] einführt ? IF s < 0 THEN warte (s); np [s] := np [s] + 1; } 2 5 Philosophen 1 1 Habermann - 2 33440230 Bei der Verwendung von Invariante bei Semaphoren: Semaphoren muß immer eine Invariante für np [s] also np [s] = Minimum (na [s], die Zahl der begonnenen und ini [s] + nv [s]) auch abgeschlossenen P-Operationen auf s gelten. mit ini [s] = Initialwert [s] Welche ? 2 5 Philosophen 1 1 Habermann - 3 33440231 Zur Definition eines Ein bedingtes kritisches bedingten kritischen Gebietes Gebiet wird definiert durch: kann man region-Anweisungen verwenden. REGION V WHEN B DO Si END; Wie sieht eine region-Anweisung im Prinzip aus ? 2 Region 1 1 Region - 1 33510232 Was bedeuten V, B und Si V : Menge gemeinsam benutz- in einer region-Anweisung barer Betriebsmittel B : boolscher Ausdruck REGION V WHEN B DO Si END; ? Si: Anweisungen, die ausge- führt werden, wenn ein Prozeß im Besitz von V und B true ist. 2 Region 1 1 Region - 2 33510233 Darf in einer Nein, Si selbst darf keine region-Anweisung innerhalb region-Anweisung enthalten, von Si wieder eine region- da sonst Deadlocks entstehen Anweisung enthalten sein ? können. 2 Region 1 1 Region - 3 33510234 Was läßt sich über die Die in B vorkommenden Änderung der in B vorkommen- Variablen können nur in den Variablen einer kritischen Gebieten geändert region-Anweisung werden. REGION V WHEN B DO Si END; aussagen ? 2 Region 1 1 Region - 4 33510235 Darf bei der Verwendung einer Nein, während der Bearbeitung region-Anweisungen während der Si kann V nicht an einen der Bearbeitung der anderen Prozeß vergeben Si-Anweisungen V an einen werden. anderen Prozeß vergeben werden ? 2 Region 1 1 Region - 5 33510236 Geben Sie eine prinzipielle VAR g : SHARED ARRAY [0..4] OF T; Lösung des 5-Philosophen- Ph_i: CYCLE "denken" Problems unter Verwendung von REGION (g [i], g [i+1]) DO "essen" END; REGION-Anweisungen an. END; 2 Region 1 1 Region - 6 33540237 Wie sieht der prinzipielle <Monitorname> : MONITOR; BEGIN Aufbau eines Monitors als <Deklaration lokaler Daten> <Folge lokaler Prozeduren> Mittel zur Synchronisation <Initialisierung lokaler Daten> aus ? END; 2 Monitore II 1 1 Monitor - 1 33610238 Es sei q eine Variable vom Falls q eine Variable vom Typ condition (bei Verwendung Typ condition ist, so ist von Monitoren). definiert: Welche drei Prozeduren bzw. Funktionen sind für q - q.wait definiert ? - q.signal - q.queue 2 Monitore II 1 1 Monitor - 2 33610239 Welche der folgenden drei Semaphore, Regions und Synchronisationsmethoden für parallele Prozesse ist am Monitore sind gleich mächtigsten ? a) Semaphore mächtig. b) Regions c) Monitore 2 Monitore II 1 1 Synchronisationsmethoden - 1 33700240 Nennen Sie zu jeder der drei Semaphore sind Synchronisationsmethoden Datenstrukturen. Semaphore, Regions und Regions sind Monitore ein Schlagwort, das Programmieranweisungen. die jeweilige Methode Monitore sind annähernd charakterisiert. Objekte bestehend aus Daten und Prozeduren. 2 - Synchronisation - 1 1 Synchronisationsmethoden - 2 33700241 Welche Synchronisations- Weitere methodische Ansätze methoden außer Sperren von zur Synchronisation sind: Interrupts, LOCK und UNLOCK, Semaphore, Regions und - Guarded Commands Monitore kennen Sie ? - Path-Expressions - Petri-Netze 2 Monitor - Beispiele 1 1 Synchronisationsmethoden - 3 33700242 Die Beweismethode von WHILE-Statement: Owicki / Gries verwendet die Hoare Notation. {P AND B} S {P} Geben Sie als Beispiel für ─────────────────────────── diese Notation ein {P} WHILE B DO S {P AND \B} WHILE-Statement an. 2 Owicki / Gries 1 1 Owicki / Gries 34200243 Zum Korrektheitsbeweis für Beweisregeln für Monitore: Monitore nach Hoare wurden 4 Beweisregeln aufgestellt. 1. {true} Init. {J AND E} 2. {J AND E} Proz. {J AND E} Nennen Sie diese Regeln ! 3. {J AND E} wait {J AND B} 4. {J AND B} signal {J AND E} 2 Monitore - Beweis 1 1 Monitore - Beweise 34300244 Bei der Beweismethode für A: alle Infos, die jemals Monitore nach Hoare werden im Puffer waren Invarianten verwendet. R: alle Infos, die jemals den Puffer verlassen haben Wie lautet die Invariante S: alle Infos im Puffer für das Erzeuger-Verbraucher Problem ? Invariante: A = R konkat S 2 Monitore - Beweis 1 1 Monitore - Invarianten 34300245