Betriebssysteme:Aufgaben V

• Aufgaben
• Zurück zur Auswahl

V1

Aufgabenstellung

Untersuchen Sie das folgende Prozesssystem auf das Auftreten von Deadlocks (s1, s2, s3: binäre Semaphore, mit true initialisiert):

 Prozess 1                 Prozess 2                 Prozess 3

  P(s1);                    P(s2);                    P(s3);
  P(s3);                    /*working*/               P(s2);
  /*working*/               V(s2);                    P(s1);
  V(s3);                                              /*working*/
  V(s1);                                              V(s3);
                                                      V(s2);
                                                      V(s1);

Antwort

Deadlock bezeichnet in der Informatik einen Zustand, bei dem mindestens zwei Prozesse auf Betriebsmittel (BM) warten die einem anderen beteiligten Prozess zugeteilt sind.

Das vorliegende Prozesssystem tritt bei ungünstiger Prozessumschaltung in ein Deadlock ein.

Konstruktion eines solchen Beispiels: Prozess 1 tritt in das binäre Semaphore s1 ein, danach kommt es zu einer Prozessumschaltung zu Prozess 2. Dieser tritt in das binäre Semaphore s2 ein und arbeitet. Während des Arbeitsprozesses findet eine Umschaltung zu Prozess 3 statt, dieser tritt in das binäre Semaphor s3 ein, kann aber nun nicht weiterrechnen, da das Semaphore s2 schon belegt ist. Es tritt eine Prozessumschaltung zu Prozess 2 auf. Dieser rechnet zuende und verlässt nach erfolgreichem Arbeiten das binäre Semaphore s2. Danach findet eine Prozessumschaltung zu Prozess 1 statt, dieser kann jedoch nicht weiterechnen, da er in das binäre Semaphore s3 eintreten will, sich jedoch Prozess 3 schon dieses BM für sich behält. Es tritt eine Prozessumschlatung zu Prozess 3 in Kraft, dieser tritt in das Semaphore s2 ein und will nun in das Semaphore s1 eintreten. Dies gelingt jedoch nicht, da Prozess 1 dieses BM schon einbehält.

Anmerkung: Prozess 2 ist völlig unbedeutend. Es reicht, wenn sich P1 s1 schnappt und P3 s3 und s2. Selbst die Reihenfolge, in der sie den jeweiligen Semaphore belegen ist egal. Fertig ist das Deadlock.

Grafisch:

 Prozess 1                 Prozess 2                 Prozess 3

  P(s1);
                ->
                            P(s2);
                            /*working1*/    
                                             ->       
                                                      P(s3);
                                             <-
                            /*working2*/ 
                            V(s2);
                                             ->
                                                      P(s2);

 Prozess 1: braucht s3
            hat s1
 Prozess 2: braucht s2
 Prozess 3: braucht s1
            hat s3
            hat s2

Dieser erreichte Zustand aller Prozesse nennt man Deadlock, da kein Prozess in der Lage ist ein Betriebsmittel wieder freizugeben und kein Prozess zu Ende arbeiten kann.

V2

Aufgabenstellung

Gegeben sei folgender Prozeß-Betriebsmittel-Graph:

[siehe Aufgabenstellung]

Gibt es in diesem Fall eine Menge von Prozessen, die sich im Deadlock befinden können? Wenn ja, wie lautet diese Menge, und unter welchen weiteren Voraussetzungen tritt ein Deadlock tatsächlich auf? Erläutern Sie eine Möglichkeit, Deadlocks entgegenzuwirken!

Am konkreten Beispiel

Im Deadlock befinden sich die Prozesse P3 und P4. Prozess P3 fordert das Betriebsmittel 9 (im Folgenden BMi) an. Dieses Betriebsmittel wird jedoch von P4 einbehalten. P4 braucht BM6 um fertig zu rechnen, dieses BM wird jedoch von P3 einbehalten. Im Prozess-Betriebsmittel-Graphen sieht man schon den Zyklus, der in diesem Diagramm entsteht. Beide Prozesse blockieren sich also gegenseitig, da jeder Prozess ein Betriebsmittel braucht, was der andere einbehält.

Die Menge der Prozesse die sich im Deadlock befinden können ist also: $ \{ P_3, P_4 \} $

//Anm. Ist nich P2 auch mit in den Deadlock einbezogen, da P3 alle seine Betriebsmittel hält aber P2 ja noch BM4 verlangt?

AW: rein formal nicht, weil P2 nicht zur eigentlichen Verklemmung beiträgt (Information von unserem Tutor in der Übung)

Vorraussetzungen für ein Deadlock

• 1-Exemplar Betriebsmittel
• exklusive Nutzung von Betriebsmitteln (Bsp. Semaphorsemantik)
• Nachfordern von Betriebsmitteln
• Nicht-Entziehbarkeit von Betriebsmitteln
• BM-Graph enthält Zyklus

Alle diese Bedingungen sind hinreichende Bedingungen dafür, dass Verklemmungen auftreten können. Jede einzelne für sich genommen ist notwendig.

Deadlocks entgegen wirken

Deadlocks erkennt man zum Beispiel an Timeouts oder bei der Analyse mittels eines Betriebsmittelgraphen. Diese kann man beseitigen durch zurücksetzen des Systems (reset).

Verhindern kann man Deadlocks zum Beispiel durch:

• anfordern aller Betriebsmittel am Anfang
• hierarchische Vergabe von Betriebsmitteln
• Freigabe aller Betriebsmittel bei Neuanforderung
• Entzug von Betriebsmitteln

Vermeidung von Deadlocks zum Beispiel durch intelligente Vergabe von Betriebsmitteln zum Beispiel durch den Bankieralgorithmus

V3

Aufgabenstellung

Kann sich ein System in einem Zustand befinden, der weder ein Deadlock-Zustand noch ein sicherer Zustand ist? Wenn ja, geben Sie ein Beispiel an; wenn nein, bewiesen Sie dies!

Antwort mit Beispiel

Es gibt 2 Prozesse, die jeweils von ein und dem selben Betriebsmittel 2 Einheiten brauchen um zu Ende zu rechnen.

 Prozess       |       maximal gefordert      |       belegt
 --------------+------------------------------+-------------
    A          |               4              |          2
 --------------+------------------------------+-------------
    B          |               5              |          3
 --------------+------------------------------+-------------
   frei        |                              |          1

Das System befindet sich offenbar in keinem Deadlock, weil jeder Prozess noch ein freies Betriebsmittel nehmen kann, noch in einem sicheren Zustand. Da nachdem sich ein Prozess das verbleibende Betriebmittel genommen hat sich das System in einem Deadlock-Zustand befindet. Also befindet es sich momentan in einem unsicheren Zustand.

V4

Aufgabenstellung

Konstruieren Sie (in Pseudocode) unter Verwendung von Semaphoren ein Prozeßsystem, in dem es zum Auftreten eines Deadlocks kommen kann, aber nicht muß! Begründen Sie Ihre Lösung! Erläutern Sie anhand Ihres Beispiels die Bedingungen, die für das Auftreten von Deadlocks erfüllt sein müssen!

Beispiel

Es stehen 2 binäre Semaphoren zur Verfügung.

 Prozess 1                    Prozess 2
   P(s1)                        P(s2)
   P(s2)                        P(s1)
   /*working*/                  /*working*/
   V(s2)                        V(s1)
   V(s1)                        V(s2)

Begründung

Angenommen in dem Prozesssystem findet keine Umschaltung statt, somit kommt es zu keiner Verklemmung. Findet jedoch, nachdem sich Prozess 1 schon in dem Semaphor s1 befindet, eine Prozessumschaltung zu Prozess 2 statt, kommt es zu einem Deadlock, nachdem Prozess 2 in das Semaphor s2 eingetreten ist. Keiner der beiden Prozesse kann weiterrechnen, da jeder Prozess das Betriebsmittel benötigt, was der andere hält.

Bedingungen

Die Bedingungen die für ein Auftreten eines Deadlocks sind:

Exklusivität der Betriebsmittel-Nutzung: In dem Bespiel kann sich nur ein Prozess in jedem Semaphor befinden, da es sich um binäre Semaphoren handelt.

Nichtentziehbarkeit von Betriebsmitteln: Die Prozesse können sich nicht gegenseitig aus den Semaphoren eliminieren.

Nachfordern von Betriebsmitteln: Beide Prozesse fordern jeweils ein Betriebsmittel nach, was jedoch der andere Prozess hält.

Zyklusbedingung: In einem Prozess-Betriebsmittel-Graphen halten beide Prozesse das Betriebsmittel, was der andere Benötigt.

 +---------+                ----                   +---------+
 |PROZESS 1|<----belegt----( s1 )<----fordert------|PROZESS 2|
 +---------+                ----                   +---------+
      |                                                ^
      |                         ----                   |
      +----------fordert------>( s2 )--------belegt----+
                                ----

<!--Achtung, um die Prozesse kommen Kreise, die Betriebsmittel haben eckige Kästchen!-->

V5

Aufgabenstellung

Was versteht man im Zusammenhang mit Verklemmungen unter einem sicheren Zustand? Geben Sie ein Beispiel mit maximal drei (möglichst nur zwei) Prozessen dafür an, daß sich ein System in einem Zustand befinden kann, der weder ein Verklemmungszustand noch ein sicherer Zustand ist! Wie kann man vorgehen, um dieser Situation vorzubeugen, d.h. nur sichere Zustände zuzulassen? Worin bestehen die Nachteile dieses Vorgehens?

Lösung

siehe Lösungen

V6

Aufgabenstellung

a) Unter welchen Bedingungen kommt es in einem System paralleler Prozesse allgemein zu einer Verklemmung (Deadlock)?

b) Gegeben sei folgendes System paralleler Prozesse (s1, s2, s3: binäre Semaphore, mit 1 bzw. true initialisiert):

 (Prozeß 1)       (Prozeß 2)       (Prozeß 3)
   P(s2);           P(s1);           P(s3);
   P(s3);           P(s2);           P(s2);
   {working}        {working}        {working}
   V(s3);           V(s2);           V(s2);
   V(s2);           V(s1);           V(s3);

Zeigen Sie, daß in diesem Beispiel eine Verklemmung eintreten kann, aber nicht muß! Verwenden Sie zur Begründung auch einen Prozeß-Betriebsmittel-Graphen!

a) Bedingungen für Verklemmungen

Die Bedingungen die für ein Auftreten eines Deadlocks sind:

• Exklusivität der Betriebsmittel-Nutzung
• Nichtentziehbarkeit von Betriebsmitteln
• Nachfordern von Betriebsmitteln
• Zyklusbedingung im Prozess-Betriebsmittel-Graphen

b) evtl. Verklemmung

mit Verklemmung: Wenn jeder Prozess jeweils seine erste P-Operation ausführt kommt es zu einer Verklemmung, da dann jeder Prozess jeweils ein Semaphore zur Verfügung hat, jedoch nicht in das zweite Semaphor eintreten kann, weil es ein anderer Prozess hält.

ohne Verklemmung: Prozess 2 sichert sich durch seine erste P-Operation das Semaphore s1. Es tritt eine Prozessumschaltung auf zu Prozess 3, dieser führt seine ersten beiden P-Operationen aus und sichert sich somit Semaphore s3 und s2. Nach der 2. Prozessumschaltung zu Prozess 1 sind keine Änderungen an der Verteilung der Betriebsmittel festzustellen, da sich Prozess 3 schon in dem Semaphore s2 befindet. Die 3. Prozessumschaltung zu Prozess 3 stellt sicher, dass Prozess 3 bis zum Ende rechnen kann und somit die beiden Semaphoren s2 und s3 wieder freigibt. Danach sichert sich Prozess 2 Semaphore s2 und rechnet bis zum Ende. Nun kann auch Prozess 1 sich beide Semaphoren sichern und bis zu seinem Ende rechnen. Es tritt in diesem Beispiel keine Verklemmung auf.

//nur so als tipp: man kannst auch einfach alle 3 Prozesse nacheinander ausführen. Dann gibt es auch keine verklemmung und das ist nicht verboten. --77.132.133.134 10:40, 23. Feb 2008 (CET) mäh

V7

Aufgabenstellung

Die Software eines Bankhauses stelle einen Dienst

 umbuchen (int betrag, int kto_A, int kto_B)

bereit, der das Umbuchen eines Betrags von einem Konto A auf ein Konto B dieses Bankhauses gestattet (als Kontobezeichnungen werden nur natürliche Zahlen verwendet) und der von verschiedenen parallelen Prozessen gleichzeitig genutzt werden kann. Die Implementation habe folgende Struktur (sem_A, sem_B: dem jeweiligen Konto zugeordnete binäre Semaphore):

 P(sem_A);
 P(sem_B);
 /*Aktualisieren der beiden Kontostände*/
 V(sem_B);
 V(sem_A);

a) Welches Problem wird durch die Verwendung der Semaphore gelöst? (Es werde angenommen, daß eine Umbuchung stets ausgeführt werden kann.)

b) Welches andere Problem kann durch die Verwendung der Semaphore in der angegebenen Weise auftreten? Wie lauten die Bedingungen, unter denen es eintritt, und inwieweit sind diese Bedingungen erfüllt bzw. erfüllbar?

c) Geben Sie – unter Beibehaltung der Verwendung von Semaphoren – eine Implementation des Dienstes an, die dieses Problem löst! Begründen Sie kurz Ihre Lösung!

a) Problem dieser Implementation

Durch die Verwendung der Semaphoren wird das Problem gelöst, dass zum Beispiel zwei unterschiedliche Prozesse nicht zur selben Zeit auf die gleiche Variable zugreifen und diese ändern. Denn so könnte sich die Berechnung des Betrags auf beiden Konten ändern.

b) weiteres Problem

Das Problem was hier auftreten kann ist eine Verklemmung (Deadlock), da wenn sich 2 Prozesse auf die gleichen Konten beziehen und bei dem ersten Prozess die P-Operation mit sem_A ausgeführt wird, danach eine Prozessumschaltung stattfindet zu dem zweiten Prozess, dieser seine erste P-Operation ausführt sem_B befindet sich das System in einem Deadlock, weil jeder Prozess das Betriebsmittel hält, was der andere Prozess fordert.

c) Lösung unter Beibehaltung von Semaphoren

3 binäre Semaphoren:

• sem_A (für Konto A)
• sem_B (für Konto B)
• sem_Test (globale Semaphore)

 P(sem_Test);
 if (kto_A > kto_B) {
    hilfskto = kto_B;
    kto_B = kto_A;
    kto_A = hilfskto;
 } 
 // Anm.: if{} nicht nötig meiner Meinung, BM sind durch
 // sem_Test schon geschützt, ein zweiter Prozess würde warten,
 // ein 3. würde nicht in sem_Test reinkommen.
 // man sollte vllt noch angeben, dass die beiden Semaphoren mit 1 
    initialisiert sind und dann würde vor P(sem_A) noch das P(sem_Test) fehlen.
 P(sem_A);
 P(sem_B);
 V(sem_Test);
 /*Aktualisieren der beiden Kontostände*/
 V(sem_B);
 V(sem_A);

Somit wird sichergestellt, dass das Konto mit der kleinsten Kontonummer immer mit der ersten P-Operation geschützt wird. Und dann erst das Konto mit der höheren Kontonummer.

V8

Aufgabenstellung

In einem System paralleler Prozesse gebe es vier Prozesse P1,...,P4, die vier Dateien A,...,D in folgender Weise benutzen:

 P1 liest von A und B und schreibt in C
 P2 liest von A und schreibt in D
 P3 liest von C und schreibt in D
 P4 liest von C und schreibt in B und D.

Die Prozesse müssen die von ihnen benötigten Dateien einzeln öffnen, wobei zuerst die zu lesenden Dateien geöffnet werden. Versucht ein Prozeß eine bereits geöffnete Datei zu öffnen, so wird er blockiert. Ein Prozeß schließt alle von ihm benutzten Dateien erst, nachdem er seine gesamte Schreibaktivität beendet hat.

a) Zu welchem Problem kann die angegebene Prozeßstruktur führen? Verwenden Sie zur Begründung auch einen Prozeß-Betriebsmittel-Graphen!

b) Welche Konsequenzen hat es, wenn P4 von C liest, aber nur in D schreibt?

c) Welches Problem ergibt sich, wenn eine Datei von mehreren Prozessen gleichzeitig geöffnet werden kann?

a) Problem der Prozessstruktur

In diesem System könnte es zu Verklemmungen kommen, weil beispielsweise der Prozess-Betriebsmittel-Graph einen Zyklus zeigt bei P1, C, P4 und B. Prozess 1 hält Betriebsmittel B und fordert C, jedoch hat P4 C und fordert B.

b) Konsequenz

Wenn P4 nur von C liest und nur in D schreibt wäre, dass das System nicht verklemmen würde, da aus D von keinem Prozess gelesen wird. Die Folge davon wäre, dass alle Prozesse nacheinander fertig arbeiten könnten.

c) gleichzeitiges öffnen von Dateien

Wenn dies der Fall wäre, würde man nicht sicherstellen, dass alle Betriebsmittel eine exklusive Nutzung haben. Es könnte zu inkonsistenten Dateien kommen und evtl. erfolgreiche Schreibvorgänge könnten durch andere Prozesse, die die selbe Datei geöffnet haben, überschrieben werden.

V9

Aufgabenstellung

Ein Prozeßsystem bestehe aus vier Prozessen P1,..., P4 und vier Betriebsmitteln A, B, C, D. Dabei gebe es von A, B und D je ein Exemplar und von C mehrere Exemplare. Das Betriebssystem teilt ein freies Betriebsmittel-Exemplar nur einem Prozeß zu. Außerdem erfolgt die Zuteilung eines Exemplars nur, nachdem es ein Prozeß freigegeben hat (abgesehen vom Anfangszustand). Ein Prozeß gibt erst dann seine Betriebsmittel-Exemplare frei, wenn er alle angeforderten Exemplare auch erhalten hat; sofern möglich, erhält er alle angeforderten Exemplare auf einmal, sonst gar keine. Betrachtet werde folgender Zustand:

• P1 besitzt nichts
• P2 besitzt 1 Exemplar von C
• P3 besitzt je 1 Exemplar von A und B
• P4 besitzt je 1 Exemplar von C und D.

Jeder der Prozesse P1, P2 und P4 fordert nun je ein Exemplar von A und C an (in einer gemeinsamen Anforderung), P3 stellt keine weiteren Forderungen. Welches ist die Mindestanzahl n von Exemplaren des Betriebsmittels C, so daß keine Verklemmung auftritt? Begründen Sie, daß es bei n – 1 Exemplaren zwangsläufig zu einer Verklemmung kommt; verwenden Sie dazu auch einen Prozeß-Betriebsmittel-Graphen!

Lösung 1

  Prozess   |     besitzt    |  fordert
 -----------+----------------+-----------
    P1      |      keine     | 1xA, 1xC
 -----------+----------------+-----------
    P2      |       1xC      | 1xA, 1xC
 -----------+----------------+-----------
    P3      |    1xA, 1xB    |
 -----------+----------------+-----------
    P4      |    1xC, 1xD    | 1xA, 1xC
 -----------+----------------+-----------

Die Forderungen passieren in einer gemeinsamen Anforderung der Betriebsmittel.

Prozess 3 kann fertig rechnen, da es keine weiteren Forderungen stellt. Somit stehen im System einmal A und einmal B zur Verfügung. Will jetzt jedoch ein Prozess weiter rechnen benötigt er mindestens ein C. Daraus folgt, dass die Anzahl der C's um eins erhöht werden muss. Daher sind es nun im System 3 C's $ (n=3) $. Jetzt kann ein weiterer Prozess zu Ende rechen, da jetzt 3 Betriebsmittel zur Verfügung stehen: 1mal A, 1mal B und 1mal C. Jeder Prozess kann nun weiterrechnen. Und da er fertig rechnet werden die Betriebsmittel wieder frei.

Bei $ n-1 $ entsteht im Prozess-Betriebsmittel-Graphen ein Zyklus.

Lösung 2

n=3

Grund:

"sofern möglich, erhält er alle angeforderten Exemplare auf einmal, sonst gar keine."

Ausgangszustand ist so:

P1 hat nichts P2 hat C P3 hat A B P4 hat C D

somit gibt es schon mal 2 C´s.

und die Anforderungen sehen so aus:

P1 will A C P2 will A C P3 will ...nix P4 will A C

Damit überhaupt etwas losgehen kann, muss P3 seine BM freigeben, sonst gäbe es ja kein A. Gibt P3 seine BM frei, sind A und B verfügbar.

Jetzt braucht man also schon mal ein C damit etwas los gehen kann - Somit gibt es jetzt an freien BM: A,B und C Da aber gilt "sofern möglich, erhält er alle angeforderten Exemplare auf einmal, sonst gar keine." bekommt jetzt P1,2 oder 4 GLEICHZEITIG A und C oder eben nix. SOmit braucht man insgesamt 3 C´s, damit es nicht zur Verklemmung kommt. Hat man n-1 C´s, also 2 kommt es zwangsläufig zur Verklemmung, da nach der Freigabe von A,B nichts mehr geht.

Da aber nur "alles oder nichts gilt"

V10

Aufgabenstellung

Drei Philosophen sitzen an einem runden Tisch, jeder vor einem Teller mit Spaghetti. Zwischen den Tellern liegt jeweils eine Gabel (insgesamt also drei Gabeln). Zum Essen benötigt ein Philosoph die linke und die rechte Gabel. Werden die Gabeln durch binäre Semaphore gabel[i] und die Philosophen durch Prozesse philosoph(int i) (i = 0,1,2) modelliert, so läßt sich das Verhalten der Philosophen folgendermaßen beschreiben:

 philosoph(int i) {
     denken();
     down(gabel[i]);
     down(gabel[(i+1)%3];
     essen();
     up(gabel[(i+1)%3];
     up(gabel[i]);
 }

(gabel[i] ist dabei die rechte Gabel des Philosophen i; down und up bezeichnen die entsprechenden Semaphor-Operationen P und V).

a) Welches Problem steckt in diesem Verhalten?

b) Welche Konsequenzen hat es, wenn unter den Philosphen ein oder mehrere Linkshänder sind, die also zuerst nach der linken Gabel greifen und entsprechend zuerst die rechte Gabel ablegen?

c) Welche (positiven und negativen) Konsequenzen hat es, wenn in der Mitte des Tisches eine vierte Gabel liegt, die in der Ausgangssituation (nur Rechtshänder) folgendermaßen benutzt wird: Hat ein Philosoph die rechte Gabel erhalten, so prüft er zunächst, ob die linke Gabel frei ist; wenn ja, ergreift er sie, wenn nein, verzichtet er auf die linke Gabel und bemüht sich um die in der Mitte liegende Gabel. Diese Gabel legt er auch als erste wieder ab.

d) Welche Konsequenzen hat es, wenn die nicht benutzten Gabeln nicht zwischen den Tellern liegen, sondern unsortiert in der Mitte des Tisches? Alle zu den Semaphoren gehörenden Warteschlangen werden nach FIFO geleert.

a) Problem

Philosophen-Problem

b) Konsequenz von Linkshändern

Wenn ein oder zwei Linkshänder in dem Kreis der Philosophen sind, dann kommt es nicht zur Verklemmung. Sind jedoch alle 3 Philosophen Linkshänder tritt das gleiche Problem auf wie bei nur Rechtshändern.

c) 4. Gabel in der Mitte des Tisches

Das System würde nicht zu Verklemmungen führen, zwar würde viele Philosophen warten, bis wieder die Gabel in der Mitte des Tisches liegt. Jedoch könnte jeder Philosoph essen.

//--Brogazo 09:01, 22. Feb 2007 (CET)

Ich sehe da auch noch ein Problem:

• Phil. 3 bekommt zu erst seine rechte Gabel
  • prüft ob die Linke frei ist --> JA also nimmt er diese
• Jetzt will Phil. 1 essen ->prüft ob rechte frei ist --> NEIN -> er macht gar nichts!

In dieser Situation isst also nur Phil. 3 und OBWOHL 2 Gabeln auf dem Tisch liegen, kann der Phil.1 nicht essen

// Das wär doch aber kein Deadlock weil der P3 ja essen kann und die Gabeln wieder freigibt

--Brogazo 14:56, 22. Feb 2007 (CET) Nein! Klar ist das keine DL (hab ich ja auch nicht behauptet ;) ), aber schon ein Nachteil, findest du nicht? Ja ich geb zu ein KLEINER denn bei dem anderen Phil. würde das nicht passieren

d) Gabeln in der Mitte des Tisches

Wenn sich alle Gabeln in der Mitte des Tisches befinden würden, könnte trotzdem der Fall auftreten, dass sich jeder Philosoph (Prozess) eine Gabel nimmt und auf seine 2. Gabel wartet.

V11

b) Kein Deadlock: P3 erhält s1, gibt am Ende s1 und s2 frei. Danach holt sich P1 s1 und s2 und gibt s1, s2 und s3 frei. Jetzt läuft P2 durch.

Deadlock: P1 oder P2 erhält s1 -> Zyklus

c) Eine vollständige Ordnung herstellen, nach der die Semaphore angefordert werden müssen:

• Nach Indizes sortieren: $ s1\rightarrow s2\rightarrow s3\rightarrow s4 $
• Oder die Reihenfolge der Anforderungen der Semaphore in Prozess 3 und der ersten beiden Semaphore in Prozess 1 vertauschen: $ s4\rightarrow s1\rightarrow s3\rightarrow s2 $

V12

Wesentlichen drei Fälle: 1) Der Linkshänder hat beide Gabeln. 2) Der Linkshänder hat die linke Gabel. 3) Der Linkshänder hat keine Gabel.

Im Fall 1) ist das System nicht verklemmt, da der Linkshänder selbst essen kann.

Im Fall 2) kann er entweder die rechte Gabel nehmen und wir landen bei Fall 1). Oder er muss auf die rechte Gabel warten, weil sie sein rechter Sitznachbar aufgenommen hat. Da der aber Rechtshänder und dies seine linke Gabel ist, nimmt er sie nur auf, wenn er schon seine rechte genommen hat, er hat dann also beide Gabeln. Das System ist nicht verklemmt, da der rechte Sitznachbar des Linkshänders essen kann.

Im Fall 3) kann der Linkshänder entweder die linke Gabel aufnehmen und wir landen bei Fall 2). Oder er wartet auf die linke Gabel, weil die von seinem linken Sitznachbar blockiert wird. Der kann entweder auch die andere Gabel (seine linke) besitzen und somit essen können (das System ist dann nicht verklemmt), oder sein linker Sitznachbar besitzt diese. Wir können jetzt immer weiter nach links rutschen und entweder feststellen, dass der gerade ausgewählte Philosoph essen kann (das System also nicht verklemmt ist), oder seinen linken Nachbarn betrachten. Spätestens der rechte Sitznachbar des Linkshänders kann neben der rechten auch die linke Gabel besitzen, weil der Linkshänder keine Gabel besitzt. Das System ist somit auch in diesem Fall nicht verklemmt. Man sieht ziemlich gut, dass das nicht nur für 5 sondern für n Philosophen funktioniert. Auf die Sitzordnung kommt es dann auch nicht an.

Oder hab ich irgendwas wichtiges unberücksichtigt gelassen?
hab ich auch so, ein Linkshänder reicht
aber maximal n-1

--Brogazo 09:29, 22. Feb 2007 (CET) Ich glaub, ich hätte das anders beantwortet... also erst mal:

• bei n-1 Linkshändern ist das System verklemmungsfrei
  • wenn nur 1 Linkshänder am Tisch sitzt, ist die Reihenfolge egal -> er ist IMMER umgeben von Rechtshändern
  • wenn 2 und diese nebeneinander sitzen, können diese beiden nicht gleichzeitig essen, sonst ja
  • wenn 3 ... na ja irgendwie würde ich jetzt versuchen die Anzahl der maximalen Esser anzugeben...die Frage ist halt sehr schwammig diesbezüglich
  • wenn 4

--Anmerkung 12. Feb 2008 (CET) Ich würde noch dazu schreiben, wenn im Fall n= 2 die beiden nicht neben einander sitzen, dann erfolgt der gesamte Ablauf aller "Essens-Prozesse" schneller als wenn sie nebeneinander sitzen.

Ein weitere Gedanke von mir ist, dass man für den Fall n=3 und n=4 einfach schreiben könnte, dass es genauso ist wie bei n=1 und n=2 , bloß umgekehrt in der Argumentation bzgl. dem Aufnehmen und Ablegen der Gabeln.

V13

a)

Was ist der Grund für diese letzte Bedingung? (Der Scheduler beginnt erst dann einen Prozeß, wenn drei Bandlaufwerke verfügbar sind, und teilt diese drei Laufwerke dem Prozeß während seiner gesamten Laufzeit fest zu.)?

• naja, die wollens halt deadlockfrei haben, möglichst einfach?

--Brogazo 09:42, 22. Feb 2007 (CET)

• Würde der Scheduler eine Prozess beginnen lassen, auch wenn nur 2 Bandlaufwerke verfügbar sind, könnte der Prozess durchaus starten
• Problem: irgendwann braucht dann aber JEDER der Prozesse das dritte Bandlaufwerk -> es sind aber keiner mehr frei -> Deadlock
• Grund also: Ausschließen von Deadlocks

Welchen erheblichen Nachteil hat sie?

• Es bleiben Ressourcen ungenutzt.
• es können maximal 2. Prozesse laufen, und während dieser Zeit bleiben 2 Bandlaufwerkte ungenutzt -> Verschwendung
• insbesondere die Tatsache, das "und gegen Ende für eine kurze Zeit zusätzlich ein drittes Laufwerk." lässt das Verfahren ineffizient werden
  • alle Prozesse brauchen ein drittes Laufwerk nur GANZ AM ENDE und auch NUR KURZ
  • dabei reicht ja 1 Bandlaufwerk um Verklemmungsfrei zu bleiben, es ist also nicht notwendig 2 als Reserve zu haben

b)

maximal 2 prozesse (gibt nur 8 laufwerke, jeweils 3 an zwei prozesse vergeben) - minimale=(?maximale?) anzahl im leerlauf=8-2*3 = 2

Ergänzung bzw. Korrektur: Ich würde sagen minimale Anzahl der Bänder im Leerlauf = 0 -> wenn nämlich jeder der beiden Prozesse (welche jeweils 3 Bänder belegt haben) gerade in ihrer letzten Phase sind (in der sie auch das dritte Band brauchen), dann sind keine im Leerlauf

doch!

2 Stück! denn es laufen ja nur 2 Prozesse und es gibt 8 Bänder
- man könnte das mit dem Leerlauf auch so sehen, dass sich jedes Band im Leerlauf befindet, welches nicht gerade benutzt wird (also auch die Bänder, die gerade keinem Prozess zugewiesen sind)...in diesem Fall wäre die Antwort: max. = 4 min = 2

das ist meiner Meinung nach die korrekte Antwort

--Brogazo 09:46, 22. Feb 2007 (CET) Da stimme ich zu:

• min. Anzahl der Laufwerke im Leerlauf: 2
  • Prozess 1 und 2 haben sich je 3 reserviert und sind in ihrer "Endphase" brauchen also auch ALLE 3 ->2 sind ungenutzt
• max. Anzahl der Laufwerke im Leerlauf: 4
  • Prozess 1 und 2 haben sich je 3 reserviert und sind NICHT in ihrer "Endphase" brauchen also nur je 2 ->4 sind ungenutzt

PS.: das ist im übrigen eine schwammige Frage bzw. der Kandidat mit der Lösung "0 Bänder im Leerlauf" KÖNNTE mit Begrüngung auch recht haben: die 2 aktiven Prozesse BENUTZEN ja je 3 Bänder, also schmeißen diese VERMUTLICH auch schon an usw. aber die anderen 2 Bänder KÖNNTEN (!!) als völlig INAKTIV/DEAKTIVIERT betrachtet werden womit sie nicht im Leerlauf sind. IMHO war das aber nicht die Intention des Leerstuhls, sondern die min=2,max=4 Lösung...sonst wäre es eher eine Aufgabe zu Bandlaufwerken geworden als zu Deadlocks

c)

eine bessere Strategie wäre es doch, wenn die Prozesse erst nur 2 BM bekommen und das 3. nach bedarf anfordern. ein neuer prozess dürfte dann bei 3 freien BM gestartet werden.. müsste eigentlich deadlockfrei sein und die auslastung ist höher: es können 3 prozesse parallel arbeiten. Bank Algorithmus

/* dabei sind dann zwar zwei bänder frei für die endphase, aber wenn angenommen P1 band 1 und 2 hat, P2 Band 3 und 4 und P3 Band 5 und 6 und Band 1 geht seinem Ende zu, braucht dann Band 5 und P3 braucht Band 1 am Ende, hast du wieder einen Deadlock
Wobei diese Tatsache nicht explizit in der Aufgabenstellung gegeben ist, man könnte die Formulierung auch so auslegen, dass die Prozesse nicht sagen können, welches Band sie haben wollen, sondern irgendein freies zugeteilt bekommen. */

d)

 globale Variable:
   
sem_t sem_a(1);
sem_t sem_frei(2); //es können max 2 Prozesse gleichzeitig arbeiten
  
int a = 0; // gibt an, ob die ersten vier Bänder benutzt werden
   
void prozess_zuteilung(prozess p)
{
  int band = 0; // lokale Zwischenspeicherung der zu nutzenden Bandhälfte
   
  down(sem_frei);
 
  down(sem_a); 
   // prüfe die Bandhälfte, da sem_frei passiert ist, ist min. eine frei
  
   if (a==0)
      a = 1;
   else band = 4; //bedeutet soviel wie ab Bahn 4
    
  up(sem_a);
   
  work_with(p, 1+band, 2+band, 3+band);
   
  if (band == 0)
  {
   down(sem_a);
    a = 0;
   up(sem_a);
  }
  
  up(sem_frei);
}

wieso so kompliziert? :

sem_t s(2);
           
s.P();
 besorgeBaender(3);
 work();
s.V();

garantiert, daß nur 2 Prozesse im kA sind

--Brogazo 10:04, 22. Feb 2007 (CET) Ich hätte es einfach so gemacht: -- Kommentar von Robert: naja, die Zuteilungsstrategie ist nicht "besser" im Sinne der Aufgabenstellung, da da Deadlocks haben kannst.

sem_t *S = new_sem(8);
sem_t *M = new_sem(1);
    
$ P_i $: 
 P(M);
  P(S);
  P(S);
  P(S);
 V(M);
    
  //Arbeiten
    
  V(S);
  V(S);
  V(S);

V14

Aufgabenstellung

Gegeben sei ein System paralleler Prozesse (Threads) A,...,D, die drei binäre Semaphore s1,...,s3 in folgender Weise gemeinsam benutzen:

Prozeß A	Prozeß B	Prozeß C	Prozeß D
P(s1);	P(s3);	P(s3);	P(s2);
P(s2);	P(s1);	/*working*/	P(s3);
/*working*/	/*working*/	V(s3);	/*working*/
V(s2);	V(s3);		V(s2);
V(s1);	V(s1);		V(s3);

Antwort

a)

Prozeß A	Prozeß B	Prozeß C	Prozeß D
P(s1);	P(s3);	P(s3);	P(s2);
P(s2);	P(s1);	/*working*/	P(s3);
/*working*/	/*working*/	V(s3);	/*working*/
V(s2);	V(s3);		V(s2);
V(s1);	V(s1);		V(s3);

b)

A -> S2 -> D
↑          ↓
S1 <- B <- S3 <- C

V15

Aufgabenstellung

Ein Betriebssystem habe eine einzige Betriebsmittelart zu verwalten, die in mehreren identischen Exemplaren (BME) vorliegt; dabei kann ein einzelnes Exemplar nur exklusiv genutzt werden. Anforderung, Zuteilung und Freigabe der BME geschehen nach folgenden Regeln:

-Ein Prozess muss bei seinem Start angeben, wie viele BME er im Laufe seiner Existenz maximal gleichzeitig benötigt.

-Ein Prozess kann mehrere BME gleichzeitig anfordern; er kann jederzeit beliebig viele seiner ihm zugeteilten BME freigeben.

-Überschreitet ein Prozess bei einer Anforderung mit der Summe der angeforderten und bereits zugeteilten BME den bei Programmstart vereinbarten Maximalwert, so wird er abgebrochen.

-Sind alle angeforderten BME verfügbar, so werden sie dem Prozess zugeteilt. Andernfalls erhält der Prozess momentan kein einziges BME und wird blockiert.

-Spätestens am Ende gibt ein Prozess alle BME frei; beim Abbruch werden sie ihm entzogen.

Antwort

a)

Vorteil im vergleich zum Bankers Algorithmus: bei einer unmöglicher Anforderung wird den Prozess abgebrochen und die BME freigegeben.

Nachteil: Maximalanzahl muß vorher bekannt sein, Prozeß wird auch abgebrochen, falls er seine Maximalzahl überschreitet und eigentlich genug BME vorhanden wären, um die Forderung zu erfüllen

b)

Anfangszustand

Prozess	akt. BME	max. BME
A	2	4
B	4	5
C	2	5
D	1	2

12 BME = 9 benutzt + 3 frei

A fordert 2 BME an: A bekommt die geforderten BME

B fordert 2 BME an: Maximalwert überschritten, deswegen wird B abgebrochen und die BME freigegeben.

C fordert 2 BME an: genau wie A