Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 10th, 2012  |  syntax: None  |  size: 12.52 KB  |  hits: 25  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. Betriebssysteme WiSe 2010 / Übungsblatt 10
  2. -------------------------------------------
  3.  
  4. 37)
  5.   (a)
  6.     Mit Hilfe von Semaphoren kann der Zugriff von mehreren Prozessen
  7.     auf einen kritischen Bereich geregelt werden.
  8.     Ein Semaphor S ist eine Integervariable, die nur durch 3 atomare
  9.     Operationen verändert werden kann
  10.     - init(S, Anfangswert) setzt S auf den Anfangswert (Initialisierung)
  11.     - wait(S) oder auch P(S) versucht S zu verringern  (Dekrementierung)
  12.     - signal(S) oder auch V(S) erhöht S                (Inkrementierung)
  13.     Man muss also in seinem Programm z.B. folgendermaßen vorgehen:
  14.     init(S, 1);
  15.     ...
  16.     wait(S)
  17.     <kritischer Bereich>
  18.     signal(S)
  19.     ...
  20.            
  21.   (b)
  22.     Der Anfangswert gibt an, wie viele Prozesse gleichzeitig auf den
  23.     kritischen Bereich zugreifen dürfen.
  24.    
  25.   (c)
  26.     Bei Vertauschung der Zeilen 3 und 4 in Prozess P1 kann es zu einem
  27.     Deadlock kommen.
  28.  
  29. 38)
  30.   (a)
  31.     Es kann beispielsweise passieren, dass ein Druckauftrag in der War-
  32.     teschlange verloren wird, weil er durch eine Racecondition von einem
  33.     anderem überschrieben wird. Gleichzeitig entsteht dadurch auch leere
  34.     Plätze in der Warteschlange.
  35.    
  36.     Aktiver Prozess | ausgeführte Codezeile | Inhalt von W        | Inhalt von next | Kommentar
  37.     ----------------|-----------------------|---------------------|-----------------|-----------
  38.      P1             | W[next] = ptr_file1;  | [filexy, ptr_file1] | 1               | Eintrag des Jobs des ersten Proezsses in die Queue
  39.     ----------------|-----------------------|---------------------|-----------------|-----------
  40.      P2             | W[next] = ptr_file2;  | [filexy, ptr_file2] | 1               | Eintrag des Jobs des zweiten Proezsses in die Queue (Bereits vorhandener Job an dieser Position wird übeschrieben!)
  41.     ----------------|-----------------------|---------------------|-----------------|-----------      
  42.      P2             | next = next + 1;      | [filexy, ptr_file2] | 2               | Erhöhung des Index-Zählers            
  43.     ----------------|-----------------------|---------------------|-----------------|-----------    
  44.      P1             | next = next + 1;      | [filexy, ptr_file2] | 3               | Erhöhung des Index-Zählers                  
  45.     ----------------|-----------------------|---------------------|-----------------|-----------    
  46.  
  47.     Jetzt ist der ptr_file2-Druckjob verloren gegangen und an Index 2
  48.     in der Warteschlange ein "Loch" entstanden.
  49.    
  50.   (b)
  51.     Prozess P1:
  52.       ...
  53.       flag[0] = true;
  54.       turn = 1;
  55.       while(flag[0] && turn == 1) {
  56.         /* do nothing */
  57.       }
  58.       W[next] = ptr_file1;
  59.       next = next + 1;
  60.       flag[0] = false;
  61.       ...
  62.        
  63.     Prozess P2:
  64.       ...
  65.       flag[1] = true;
  66.       turn = 0;
  67.       while(flag[0] && turn == 0) {
  68.         /* do nothing */
  69.       }
  70.       W[next] = ptr_file2;
  71.       next = next + 1;
  72.       flag[1] = false;
  73.       ...    
  74.      
  75.   (c)
  76.     Der Nachteil dieses Ansatzes ist, dass wartende Prozesse
  77.     den Prozessor nicht abgeben sondern ihn durch "Busy Wait"
  78.     weiter beanspruchen
  79.  
  80. 39)
  81.   (a)
  82.     Aktiver Prozess | ausgeführte Codezeile | Inhalt von k | Inhalt von b | Kommentar
  83.     ----------------|-----------------------|--------------|--------------|-----------
  84.      Ehemann        | b = k;                |  200         | 200          | Prozess fragt Kontostand ab
  85.     ----------------|-----------------------|--------------|--------------|-----------
  86.      Ehefrau        | b = k;                |  200         | 200          | Prozess fragt Kontostand ab
  87.     ----------------|-----------------------|--------------|--------------|-----------
  88.      Ehefrau        | b = b - 100;          |  200         | 100          | Prozess berechnet intern neuen Kontostand
  89.     ----------------|-----------------------|--------------|--------------|-----------
  90.      Ehefrau        | k = b;                |  100         | 100          | Prozess weisst neuen Kontostand zu
  91.     ----------------|-----------------------|--------------|--------------|-----------
  92.      Ehemann        | b = b + 400;          |  100         | 600          | Prozess berechnet intern neuen Kontostand
  93.     ----------------|-----------------------|--------------|--------------|-----------
  94.      Ehemann        | k = b;                |  600         | 600          | Prozess weisst neuen Kontostand zu (RACECONDITION!)
  95.     ----------------|-----------------------|--------------|--------------|-----------
  96.    
  97.     Der Kontostand beträgt wegen der Racecondition jetzt 600 Euro statt
  98.     500 Euro.
  99.    
  100.   (b)
  101.     Zur Verhinderung von Raceconditions müssen folgende Bedingungen
  102.     erfüllt sein:
  103.     - Mutual exclusion:
  104.         Zu jedem Zeitpunkt darf sich höchstens ein Prozess im kriti-
  105.         schen Bereich befinden                    
  106.     - Progress:
  107.         Befindet sich kein Prozess im kritischen Bereich, aber es gibt
  108.         einen Kandidaten für diesen Bereich, so hängt die Entscheidung,
  109.         welcher Prozess ihn betreten darf, nur von diesem Kandidaten ab
  110.         und fällt in endlicher Zeit. Der Fall, dass ein Prozess im kri-
  111.         tischen Bereich terminiert darf keinen Einfluss haben.
  112.     - Bounded Waiting:
  113.         Zwischen der Anforderung eines Prozesses, in den kritischen Be-
  114.         reich einzutreten und dem tatsächlichen Eintreten in den kriti-
  115.         schen Bereich kann eine gewisse Zeitdauer liegen. Allerdings muss
  116.         es für die Wartezeit einen angebbare, maximalen Wert geben.    
  117.     - Vermeidung von "Circular Wait":
  118.         Es soll vermieden werden, dass eine geschlossene Kette von Pro-
  119.         zessen entsteht, sodass jeder Prozess mind. enie Ressource hält,
  120.         die von einem anderem Prozess benötigt wird.
  121.    
  122.   (c)
  123.     (i)
  124.       Aktiver Prozess | ausgeführte Codezeile | Inhalt von k | Inhalt von b | Inhalt von x | Inhalt von y | Kommentar
  125.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  126.        Ehemann        | x = false;            | 200          | 0            | false        | false        |
  127.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  128.        Ehefrau        | y = false;            | 200          | 0            | false        | false        |
  129.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  130.        Ehemann        | while(y) {...}        | 200          | 0            | false        | false        | Überspringung der while-Schleife (d.h. es folgt Eintritt in den kritischen Bereich)
  131.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  132.        Ehefrau        | while(x) {...}        | 200          | 0            | false        | false        | Überspringung der while-Schleife (d.h. es folgt Eintritt in den kritischen Bereich)
  133.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  134.        Ehefrau        | y = true;             | 200          | 0            | false        | true         |
  135.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  136.        Ehefrau        | b = k;                | 200          | 200          | false        | true         | Abfrage des Kontostandes
  137.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  138.        Ehemann        | x = true;             | 200          | 0            | true         | true         |
  139.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  140.        Ehemann        | b = k;                | 200          | 200          | true         | true         | Abfrage des Kontostandes
  141.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  142.        Ehefrau        | b = b + 400;          | 200          | 600          | true         | true         | Interne Berechnung des neuen Kontostands
  143.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  144.        Ehefrau        | k = b;                | 600          | 600          | true         | true         | Zuweisung des neuen Kontostands
  145.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  146.        Ehefrau        | y = false;            | 600          | 600          | true         | false        |
  147.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  148.        Ehemann        | b = b - 100;          | 100          | 600          | true         | false        | Interne Berechnung des neuen Kontostands
  149.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  150.        Ehemann        | k = b;                | 100          | 100          | true         | false        | Zuweisung des neuen Kontostands
  151.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  152.        Ehemann        | x = false;            | 100          | 100          | false        | false        |
  153.       ----------------|-----------------------|--------------|--------------|--------------|--------------|-----------
  154.  
  155.       Die Bedingung "Mutual exclusion" wird verletzt, d.h. es befinden
  156.       sich beide Prozesse gleichzeitig im kritischen Bereich.
  157.       Dadurch kommt am Ende der Kontostand von 100 statt 500 Eur zustande.
  158.      
  159.     (ii)
  160.       Aktiver Prozess | ausgeführte Codezeile | Inhalt von k | Inhalt von b | Inhalt von x | Inhalt von y | Inhalt von z | Kommentar
  161.       ----------------|-----------------------|--------------|--------------|--------------|--------------|--------------|-----------
  162.        Ehemann        | x = true;             | 100          | 0            | true         | false        |  0           |
  163.       ----------------|-----------------------|--------------|--------------|--------------|--------------|--------------|-----------
  164.        Ehefrau        | y = true;             | 100          | 0            | true         | true         |  0           |
  165.       ----------------|-----------------------|--------------|--------------|--------------|--------------|--------------|-----------
  166.        Ehefrau        | z = 1;                | 100          | 0            | true         | true         |  1           |
  167.       ----------------|-----------------------|--------------|--------------|--------------|--------------|--------------|-----------
  168.        Ehemann        | z = 0;                | 100          | 0            | true         | true         |  0           |
  169.       ----------------|-----------------------|--------------|--------------|--------------|--------------|--------------|-----------
  170.        Ehemann        | while(z==1 || y){...} | 100          | 0            | true         | true         |  0           | Prozess muss solange Warten, bis Variablen entsprechend geändert werden
  171.       ----------------|-----------------------|--------------|--------------|--------------|--------------|--------------|-----------
  172.        Ehefrau        | while(z==0 || x){...} | 100          | 0            | true         | true         |  0           | Prozess muss solange Warten, bis Variablen entsprechend geändert werden
  173.       ----------------|-----------------------|--------------|--------------|--------------|--------------|--------------|-----------
  174.      
  175.       Die letzten beiden Schritte wiederholen sich jetzt unendlich oft
  176.       in beliebiger Reihenfolge, da wegen einer Racecondition ein Dead-
  177.       lock eingetreten ist.
  178.       Da beide Prozesse gegenseitig Variablenänderungen anfordern, die
  179.       vom jeweils anderen Prozess durchgeführt werden müssen, ist
  180.       "Circular Wait" eingetreten, also die letzte Bedingung verletzt.
  181.      
  182.   (d)
  183.     Prozess Eheman:
  184.       ...
  185.       flag[0] = true;
  186.       turn = 1;
  187.       while(flag[0] && turn == 1) {
  188.         /* do nothing */
  189.       }
  190.       b = k;
  191.       b = b - 100;
  192.       k = b;
  193.       flag[0] = false;
  194.       ...
  195.        
  196.     Prozess Ehefrau:
  197.       ...
  198.       flag[1] = true;
  199.       turn = 0;
  200.       while(flag[0] && turn == 0) {
  201.         /* do nothing */
  202.       }
  203.       b = k;
  204.       b = b - 100;
  205.       k = b;
  206.       flag[1] = false;
  207.       ...
create a new version of this paste RAW Paste Data