Betriebssysteme:Aufgaben T

Aus Tudwiki
Wechseln zu: Navigation, Suche

T1

"Erläutern Sie zwei Methoden, mit denen ein Prozeß seinen kritischen Abschnitt schützen kann! Geben Sie jeweils eine Implementationsmöglichkeit (in Pseudocode) an, und bewerten Sie die gewählten Methoden!"

Methode 1: Semaphore

Pseudocode: 

s = new Semaphor(1);
s.P();
//kritischer Abschnitt
s.V();

Vorteile:

  • kein busy Waiting
  • einfach
  • leichtes Implementieren

Nachteile:

  • V Operation kann schnell vergessen werden
  • vergessene V Operationen bringen keinen CompilerFehler
  • Verklemmungen möglich (über Kreuz anfordern)

Methode 2: atomare Operationen

Pseudocode: 

1=belegt, 0=frei
int xchg(int value, int *mutex);
...
while(1==xchg(1,&mutex)) {} //lock
//KA
mutex=0;  //unlock

Vorteile:

  • einfach
  • leichtes Implementieren

Nachteile:

  • busy Waiting

T2

Prozess = Thread + Adressraum (in Worten: Ein Prozess ist eine Einheit aus Adressraum und mindestens einem Thread) Warum wird er eingeführt?

  • getrennte Adressräume (Sicherheit)
  • ermöglicht "Parallelverarbeitung" auf 1-Prozessor-Systemen

ein Prozess kann sich in folgenden Zuständen befinden:

  1. aktiv: rechnend auf CPU (hat alle Betriebsmittel)
  2. blockiert: CPU + mindestens ein weiteres BM fehlen
  3. bereit: Prozess hat alle BM außer CPU
  4. ausgelagert: es fehlen die BM Hauptspeicher und CPU
  5. nicht existent: vor dem Erzeugen bzw. nach dem Beenden

(in den Übungen wurde dazu ja ein hübsches Diagramm mit den jeweiligen Zustandsübergängen gemalt)

T3

Geben Sie einen Überblick über die Mittel, die in Betriebssystemen zur Realisierung kritischer Abschnitte bereitgestellt werden können, und bewerten Sie sie!

Zur Realisierung des wechselseitigen Ausschlusses gibt es verschiedene Möglichkeiten.

  • Protokoll 
  1. entersection() 
   - kritischer Abschnitt frei?
    „Ja“, den kA als belegt markieren
    „Nein“, warten
  2. leavesection() 
   - falls ein Prozess auf den Eintritt in den kA wartet, diesen freisetzen
   - falls kein Prozess wartet, den kA als frei markieren
  • Hardware unterstützt
    • Interrupts
    • unteilbare Befehle (test_and_set)
  • Betriebssystem unterstützt
    • Semaphore
    • sprachunterstützt (Java, ADA)


Bewertung:

Interrupts

  • Vorteile
    • einfach
  • Nachteile
    • nur im Kern ausführbar
    • MultiCPU --> nutzlos
    • nur auf 1CPU Systeme nutzbar

Semaphore

  • Vorteile
    • einfach
    • Busy Waitung vermieden
    • leichte Implementierung
  • Nachteile
    • V Operation schnell mal vergessen
    • Verklemmungen möglich
    • keine Compilerpürfung auf vergessene V Operationen machbar

sprachunterstützt (Java, ADA)

  • Vorteile
    • universell
    • nicht an bestimmte HW gebunden
    • geringe Voraussetzungen
  • Nachteile
    • Fehler könnten reinprogrammiert werden
    • höherer Implementierungsaufwand

unteilbare Befehle (test_and_set)

  • Vorteile
    • einfach und sicher
    • auch auf UserEbene nutzbar
  • Nachteile
    • müssen vorhanden sein
    • busy waiting

T4

Erläutern Sie das Problem „Race Condition“ an folgendem Beispiel! 

VAR kontostand: INTEGER;
PROCEDURE abbuchen (betrag: INTEGER);
   BEGIN kontostand := kontostand - betrag;
END;
kontostand := 100;
Prozeß 0: abbuchen(10);       Prozeß 1: abbuchen(80);

Race Condition - Wettlaufsituation:

mehrere Prozesse aus P bewerben sich unabhängig voneinander um die zeitweise exklusive Nutzung derselben Betriebsmittel aus P. (P = ein System paralleler Prozesse)

an diesem Beispiel:

  • der Kontostand beträgt 100
  • Prozeß 0 erhällt CPU Zeit/Zugriff
  • ruft somit abbuchen(10); auf
  • geht in die Funktion
  • berechnet (NICHT ATOMAR) "kontostand - betrag" = 100-10 speichert das Ergebnis irgendwie zwischen....Erg=90

JETZT wird aber zufällig umgeschalten --> Prozeß 1 CPU Zeit/Zugriff

  • ruft somit abbuchen(80); auf
  • geht in die Funktion
  • berechnet (NICHT ATOMAR) "kontostand - betrag" = 100- 80 speichert das Ergebnis irgendwie zwischen....Erg=20
  • schreibt das Erg=20 auf die Variable "kontostand"
  • und ist fertig

JETZT wird aber zufällig umgeschalten --> Prozeß 0 CPU Zeit/Zugriff

  • setzt wieder an der "alten" Stelle ein und..
  • schreibt das Erg=90 auf die Variable "kontostand"
  • und ist fertig

==> kontostand beträgt nun 90, obwohl insgesamt 90 von 100 abgebucht wurden -> Fehler!!

Weitere mögliche Kontostände wären 20 (analog dem oben) und 10 (wenn beide Befehle "kontostand = kontostand - betrag" hintereinander ausgeführt werden).

T5

"Der Prozeß A fülle zyklisch einen zweielementigen Puffer P1. P1 wird (gemäß FIFO) durch einen Prozeß B geleert, der ein gelesenes Element unmittelbar in einen Puffer P2 schreibt; dieser Puffer wird durch einen Prozeß C geleert. Erläutern und lösen Sie das genannte Problem!"

Problem: Erzeuger Verbraucher Problem

Erläuterung des Problems

  • Der Produzent versucht einen Zugriff auf den gemeinsamen Speicher, wenn dieser bereits vollständig belegt ist.
  • Der Konsument versucht einen Zugriff auf den gemeinsamen Speicher, wenn dieser nicht belegt ist.

Lösung: wechselseitiger Ausschluss

  • zwei binäre Semaphore, welche jeweils gekreuzt die beiden kritischen Abschnitte Eintragen und Auslesen absichern. 
sem_t S1 = new_sem(2),
s2 = new_sem(0),
s3 = new_sem(1),
s4 = new_sem(0);

int n = 0, m = 0;
int = P1[] = 2; // Puffer der Größe 2
int = P2[] = 1; // Puffer der Größe 1

Prozess A 
P(S1); 
fuelle(P1[n]); // falls Prozess A 2 mal parallel ausgeführt wird muss hier noch
n = (n++)%2;   // ein binärer Semaphore herum
V(S2);



Prozess B
P(S2);
entnehme(P1[m]); // falls Prozess B 2 mal parallel ausgeführt wird muss 
m = (m++)%2;     // hier noch ein binärer Semaphore herum
V(S1);
P(S3);
fuelle(P2[1]);
V(S4);



Prozess C
P(S4);
entnehme(P2[1]);
V(S3);



alternativer Lösungsvorschlag für Prozess B:
P(S2);
P(S3);
entnehme(P1[m]); // falls Prozess B 2 mal parallel ausgeführt wird muss 
m = (m++)%2;    
fuelle(P2[1]);   // hier noch ein binärer Semaphore herum
V(S4);
V(S1);

T6

Lösen Sie das folgende Erzeuger-Verbraucher-Problem mittels Semaphoren! Ein Prozeß E fülle einen linearen Puffer unbegrenzter Kapazität mit Datenelementen. Diese Datenelemente werden durch einen Prozeß V aus dem Puffer gemäß der Strategie LIFO entnommen. Bewerten Sie Ihre Lösung! Welche Modifikationen sind erforderlich, wenn der Puffer durch mehrere Prozesse gefüllt wird? 

Erzeuger:

sem_t S1=new_sem(1);int n=0; Puffer[] = unendlich ; n=0
//schreiben = true solange Erzeuger schreiben will
//lesen = true solange Verbraucher lesen will
P(S1)
while(schreiben) { 
schreibe(Puffer[n]) ;
n++ ;
}
V(S1)

Verbraucher:

P(S1)
while((n>0)&&(lesen)) {
lese(Puffer[n-1]);
n-- ;
}
V(S1)

Dies löst das Problem, dass:


  • Der Konsument versucht einen Zugriff auf den gemeinsamen Speicher, wenn dieser nicht belegt ist und verhindert gleichzeitigen Zugriff

Welche Modifikationen sind erforderlich, wenn der Puffer durch mehrere Prozesse gefüllt wird?

Diese dürfen sich nicht gegenseitig beeinflussen. In den KA darf immer nur ein Schreiber rein, da ja sonst Mist rauskommt bzw. Sachen verloren gehen. Also bleibt es bei einem binären Semaphor. Man könnte eine Art Warteschlange für die Schreiber einführen, dies würde die Situation lösen. 

alternative Lösung:
Unschön bei der obigen Lösung ist das busy-waiting, dass man mit einem zusätzlichen Semaphor S2 beheben könnte:

sem_t S1=new_sem(1);
sem_t S2=new_sem(0);
int n=0; 
Puffer[] = unendlich ; 
n=0
//schreiben = true solange Erzeuger schreiben will
//lesen = true solange Verbraucher lesen will

Erzeuger:

P(S1)
while(schreiben){ 
schreibe(Puffer[n]) ;
n++ ;
}
V(S1)
V(S2)

Verbraucher:

P(S2)
P(S1)
while(lesen)
lese(Puffer[n-1]);
n-- ;
}
V(S1)

T7

Drei parallele Prozesse nutzen einen Puffer der Größe 1 KByte zum byteweisen Senden von Daten (unterschiedlichen Umfangs) an einen Drucker; dabei soll das Senden durch einen Prozeß jeweils erst abgeschlossen sein, bevor der nächste Prozeß den Puffer benutzen darf. Ein weiterer Prozeß liest die Daten byteweise aus dem Puffer und übergibt sie an den Drucker. Entwerfen Sie in Pseudocode unter Verwendung von Semaphoren eine Lösung des Problems! 

sem_t belegt(0);
sem_t frei(1024);    // 1KB Puffergroesse
sem_t schreiben(1);
puffer p(1024);

P1 - P3:
  daten d;
  while(1){
      schreiben.P();
      while(!daten.leer()){          // laeuft so lange, bis 
                                     // alle Daten gesendet sind
          frei.P();
          hinzufuegen(p, d.next());
          belegt.V();
      }
      schreiben.V();
  }

Verbraucher:
  while(1){
      belegt.P();
      entnehmen(p);
      frei.V();
  }

T8

In einem System paralleler Prozesse existiere ein Druckerspooler, der aus einem 4 KByte großen Puffer Daten liest und byteweise zum Drucker sendet. Andere Prozesse übergeben ihre zu druckenden Daten (unterschiedlichen Umfangs), indem sie diese byteweise in den Puffer schreiben; dabei sollen sich die Daten eines Prozesses mit denen eines anderen nicht vermischen. Beschreiben Sie in Pseudocode unter Verwendung von Semaphoren die Struktur des Druckerspoolers und der sendenden Prozesse, so daß eine maximale Parallelität möglich ist! (Beachten Sie die genaue Beschreibung der verwendeten Semaphore und deren Initialisierung!) 

sem_t *schreiben = new_sem(1);
sem_t *leer = new_sem(4096);
sem_t *voll = new_sem(0);

// schreiber: 

P(schreiben);
While(Datei nicht komplett gesendet) do
{
 P(leer);
 schreibe ein Byte;
 V(voll);
}
V(schreiben);

// leser: 

while (true) {
 P(voll);
 nehme Byte und schicke an Drucker;
 V(leer);
}

// bist du sicher ? ---> " dabei sollen sich die Daten eines Prozesses mit denen eines anderen nicht vermischen. "

// und dabei E/V klassisches Problem ---> gleichzeitige lese/schreib Zugriff

T9

Beschreiben Sie unter Verwendung von Semaphoren die Implementation eines Wechselpuffers folgender Struktur und Strategie. Der Puffer bestehe aus den beiden Teilen linkeHälfte und rechteHälfte (und kann damit als zweielementig betrachtet werden). Er werde durch den Prozeß A gefüllt und durch den Prozeß B geleert; beide Prozesse arbeiten zyklisch. Ist der gesamte Puffer leer, so füllt A stets zuerst linkeHälfte, genauso leert B bei vollem Puffer zuerst linkeHälfte. Beide Prozesse sollen weitestgehend parallel arbeiten können. Zur Beschreibung des Pufferzustands ist neben den ggf. erforderlichen Semaphorvariablen maximal eine weitere Variable zustand zu verwenden. (Hinweis: Ermitteln Sie zunächst die möglichen Pufferzustände und deren Änderungen!). Demonstrieren Sie die Korrektheit Ihrer Lösung! Angenommen, die Daten besitzen eine Gültigkeitsdauer. Welches Problem birgt dann die Strategie des Füllens und Leerens in sich?

Mögliche Übergänge der Pufferzustände sind:

->beide leer ->nur rechts voll ->beide voll ->nur links voll
beide leer-> X
nur rechts voll-> X X
nur links voll-> X X
beide voll-> X

T10

a) z kann folgende Werte annehmen:

  • -1,0,1

welches ist das Endergebnis?:

  • -1 oder 0 oder 1 ...kann man nicht genau sagen

Welches Problem tritt auf?

  • kritischer Abschnitt bzw. Wettlaufsituation. Beide Prozesse wollen die Variable z ändern würden diese gern exklusiv nutzen. Das tun sie aber nicht! (z++ und z-- sind keine atomaren Operationen, können also jederzeit unterbrochen werden -> Überschreiben der gegenseitigen Ergebnise möglich)

b) Welche Werte kann z nun annehmen? 

s=1

Somit kann nur P1 anfangen, es dekrementiert z (z=-1) und setzt s=0. Nun könnte P0 drankommen, es inkrement. z womit z=0 ist. Sollte P1 nie aufgerufen werden, bleibt z=0 bestehen. // in der Aufgabe ist nicht angegeben was nun wie aufgerufen wird. Ich geh mal davon aus dass da sowas wie: 

P1;
P0;

stehen sollte. Unter dieser Vor. wird z am Ende IMMER 0 sein

Was wird durch die Verwendung der Variablen s bewirkt?

Es wird verhindert, beide Prozesses gleichzeitig an z "arbeiten" entweder P1 oder P2, nicht beide gleichzeitig.

c)

Semaphor s(1); // ein binärer 

P0: 
    s.P();
    z++;
    s.V();

P1: 
    s.P();
    z--;
    s.V();

negative Eigenschaft von b)

  • Fernwirkung
    • Ein Thread übt immer eine Fernwirkung auf den anderen aus. Die Bedingung Lebendigkeit ist nicht erfüllt. (Wenn P1 nicht aufgerufen wird, läuft P0 nie!)
  • kein busy waiting

T11

Ein Prozeß A will mit read(x) einmalig eine Nachricht in Form einer Integer-Variablen x lesen, die ihm von einem anderen Prozeß B durch write(x) in einem gemeinsam genutzten Speicher übergeben werden soll. a) Welches Problem tritt dabei auf? Lösen Sie das Problem mittels Semaphoren! b) Kann das Problem auch ohne Semaphore und ohne spezielle Hardware-Unterstützung, also nur mit einfachen Lese-, Schreib- und Testoperationen auf einer Variablen gelöst werden? Wenn ja, geben Sie eine möglichst einfache Lösung an und begründen Sie deren Korrektheit, wenn nein, beweisen Sie es! c) Angenommen, die Nachricht wird nicht als Integer-Wert übergeben, sondern als Zeichenkette, die byteweise in einem Puffer der Größe 10 Byte abgelegt wird; sie kann auch byteweise entnommen werden. Dabei sollen beide Prozesse möglichst parallel arbeiten. Die Länge der Nachricht ist nicht von vornherein bekannt. Beschreiben Sie die Struktur der Lösung in den Fällen a) und b) (mit bzw. ohne Semaphore), sofern dies möglich ist!

a)

Falls A nicht genau dann liest, wenn B schreibt muss die Nachricht gepuffert werden. => Erzeuger-/Verbraucherproblem mit einelementigem Puffer 

sem_t voll(0);

A                    B
/* ... */            /* ... */
while(noMsg){       write(x);
    voll.P();        voll.V();
    read(x);         /* ... */
}
/* ... */

Da B nur einmalig eine Nachricht schreibt, besteht keine Gefahr, dass der Puffer überschrieben wird. Deshalb reicht ein Semaphor.

// Die While-Schleife ist doch überflüssig bei A. Oder nicht? //-> ja ich hab auch keine!

b)

Eine Mögliche Lösung: 

int s = 0;

A
/* ... */
while(s == 0); /* busy waiting bis s=1 ist */
read(x);
/* ... */

B
/* ... */
write(x);
s = 1;
/* ... */

Nachteil: busy waiting

c)

SemaphoreT empty(10), full(0), mutex(1);
  
QueueT queue; //wegen FIFO
     
void writer()
   
{
 int i;
 char dummy;
 DataT data();
 data = get_data() + '\0'; //0 terminierte Message
  
 for (i = 0; i < data.length(); i++)
 {
   dummy = data.get(i);
   empty.P();
   mutex.P();
   queue.add(dummy);
   mutex.V();
   full.V();
 }
}
 
void reader()
{
 char dummy;
 MessageT msg = "";
 do
 {
   full.P();
   mutex.P();
   dummy = queue.get();
   mutex.V();
   empty.V();
   msg += dummy;
 } 
  while (dummy != '\0');
  
 //handle msg

}

T12

Betrachtet werde folgendes Problem. Für ein System paralleler Prozesse existiere ein gemeinsam genutzter Puffer (der als Ganzes betrachtet wird). Dieser Puffer wird von einem Prozeß S beschrieben und von prinzipiell beliebig vielen Prozessen L gelesen, allerdings ist ein gleichT3 zeitiges Lesen nur durch maximal fünf Prozesse zugelassen; außerdem ist kein gleichzeitiges Lesen und Schreiben möglich. Dazu sei folgender Lösungsversuch gegeben: 

int z = 0;
sem_t *S = new_sem(1);
sem_t *L = new_sem(5);
Leserprozeß: while(1) {          Schreiberprozeß: while (1) {
    z = z+1;                         P(S);
    if (z == 1)                      schreiben();
        P(S);                        V(S);
    P(L);                        }
    lesen();
    V(L);
    z = z-1;
    if (z == 0)
        V(S);
}

a) Welchem Zweck dienen die drei Variablen z, *S und *L? b) Die Lösung ist nicht korrekt. Worin liegt die Ursache? c) Geben Sie eine korrekte Lösung an, indem Sie die vorliegende Lösung geeignet modifizieren!

a)

  • z - soll die Leserprozesse zählen
    • Das soll sicher stellen, dass nur der erste Leserprozess P(S) ausführt. Sonst würden alle nachfolgenden Leserprozesse schlafen gelegt werden. Es könnte immer nur ein Prozess lesen.
    • Das selbe gilt für den letzten Leserprozess und V(S).
  • *S - zählt die Schreiber - Wenn ein Prozess schreibt kann kein anderer Prozess auf den Puffer zugreifen.
  • *L - zählt die Leser - Es kann maximal 5 Leser geben.

b)

Der Zähler z für die Leserprozesse funktioniert nicht. Beispiel:

  1. erster Leserprozess beginnt
    1. liest z (z=0)
  2. Prozesswechsel
  3. zweiter Leserprozess beginnt
    1. wertet z = z + 1 aus (z=1)
    2. führt P(S) aus
  4. Prozesswechsel
  5. erster Leserprozess setzt fort
    1. wertet z = z + 1 aus (z=1)
    2. führt P(S) aus

=> Da der Mutex S bereits 0 ist wird der erste Leser schlafen gelegt. => Passiert das mit allen Leserprozessen gleichzeitig, dann kann nur der lesen, der P(S) zuerst ausführt.


/* z ist eine globale Variable, wird nach z=z+1 gewechselt, so merkt das auch der nächste Prozess. Deswegen ist die Begründung meiner Meinung nach falsch! Der eigentliche Fehler: wenn nach z+1 prozesswechsel, dann kommt der nächste Thread, und führt ebenfalls z+1 aus, dann ist z=2... somit führt KEINER P(S) aus. das führt zum gleichzeitigen lesen und schreiben, oder sogar zum doppelten schreiben, wenn man ich das genau ansieht würde das auch gehen. die lösung in c) ist dennoch korrekt*/

/* nein, das ist schon richtig so, wie es da steht, denn wenn z=0, dann ließt das ein prozess und rechnet z+1, weißt es aber noch nicht zu (sprich speichert noch nicht) und dann kann es auch der nächste prozess noch nicht wissen und ließt wieder z=0, da ist es egal, wie global z ist */

/* Aber immerhin wird bei z == 1 die globale Variable z abgefragt... es wird zu keinem Zeitpunkt eine lokale Variable erzeugt, also würde ich zustimmen, dass P(S) nie gemacht werden würde */

c)

int z = 0;
sem_t *S = new_sem(1);
sem_t *L = new_sem(5);
sem_t *mutex = new_sem(1);
Leserprozeß: while(1) {          Schreiberprozeß: while (1) {
    P(mutex);
    z = z+1;                         P(S);
    if (z == 1)                      schreiben();
        P(S);                        V(S);
    V(mutex);
    P(L);                        }
    lesen();
    V(L);
    P(mutex);
    z = z-1;
    if (z == 0)
        V(S);
    V(mutex);
}

T13

a) Warum hat nach Beendigung von A und B die Variable z nicht notwendig den Wert 9?

  • Wettlaufsituation
  • kritischer Abschnitt
  • beide Prozesse laufen ->A liest Wert aus z aus, Addiert dann 1, speichert zwischen
  • nun wird zufällig umgeschalten -> B ist dran
  • B liest Wert aus z aus, Addiert dann 1, speichert zwischen und schreibt zurück
  • somit ist z nun 8
  • jetzt kommt wieder A dran
  • schreibt auch seinen Wert zurück
  • z=8 am Ende

Welche Werte kann sie haben?

  • 8 oder 9

b) Modifizieren Sie das Programm so, daß der Endwert 9 garantiert ist! (Die Anweisung z = 9 ist dabei ausgeschlossen.) 

Semaphor s(1); // ein binärer

Programm:
{
  s.P();
  z = z+1;
  s.V();
}


c)

Es wird 11 ausgegeben, denn beide Prozesse haben den gleichen file descriptor und schreiben beide jeweils eine 1.

Begründung: Da Eltern wie Kind BEIDE die if-Bedingung erfüllen (fork>=0, Kind hat 0, Eltern >0), werden auch BEIDE i=i+1; ausführen. Das Kind erbt aber den Code und Speicher, Stack,b.. von Eltern zu dem Zeitpunkt. Also steht bei BEIDEN i=0 also rechnen BEIDE 1 auf 0 drauf und schreiben BEIDE eine 1 zurück.

d) 

i=1
i=1
i=1

Begründung? 

#include <stdio.h>
#include <unistd.h>
int main(void)
{
 int i, j;
 i=0;
 for(j=0; j<2; j++) {
  if (fork() == 0) {
   i = i+1;
   printf(i = %d\n, i);
   exit(0);
  }
 }
i = i+1;
printf(i = %d\n, i);
return 0;
}
  • Kind erbt Speicher bzw. Stack und arbeitet danach mit seinem eigenen weiter
  • Prozess beginnt und geht in die for Schleife rein
  • fork()
  • WENN es das Kind ist, geht es in IF rein
  • Kind hat auch i=0, erhöht es (1) und schreibt es in die Datei + Zeilenumbruch und geht raus (exit)
  • der Eltern läuft einfach drüber und macht das ganze nochmal
  • nächstes Kind hat auch i=0, erhöht es (1) und schreibt es in die Datei + Zeilenumbruch und geht raus (exit)
  • Eltern läuft wieder drüber
  • Eltern hat immer noch i=0 erhöht dieses und schreibt auch wieder SEIN i + Zeilenumbruch in die Datei
  • es spielt keine Rolle in welcher Reihenfolge das geschieht.
    • die 2 Kinder werden erzeugt
    • jedes schreibt einmal sein Zeug rein
    • Eltern am Ende auch
    • es wäre auch möglich das erst der Eltern durchläuft und dann die Kinder drankommen
    • für die Ausgabe macht das aber keinen Unterschied
    • letztendlich laufen 3 Prozesse (1 Eltern und der macht 2x fork -> 2 Kinder)
    • jeder hat sein i auf 0 stehen
    • somit kommt es nicht zu 2 3 oder sonstwas in der Datei (als Wert für i)

T14

a) 

Sem_T S = new_sem(1);
Sem_T L = new_sem(5);
int Warteschlange = 0;
 
Leser:
  
Warteschlange ++;
if (Warteschlange > 0){
   S.P();
}
L.P();
 /* lese */
L.V();
z--;
if (Warteschlange == 0){
S.V();
} 
  
Schreiber:
  
while(1){
S.P();
/* write */
S.V();
}

Angaben ohne Gewähr....also muss nicht stimmen..überprüft das mal jemand der da sicherer ist als ich?

stimmt nicht es kann immer nur ein Leser lesen, da jeder leser auf die binäre Semaphore S trifft.

Wie schauts mit folgendem aus: 

sem_t s0 = new sem(5)
sem_t s1 = new sem(1)
sem_t s2 = new sem(1)
 
int leser = 0
 
 -------------------
Leser:
 
while(1){
 s0.P()
 s1.P()
  
if(leser == 0) 
     s2.P()
leser++

s1.V() 
 
//lese
 
s1.P()

leser--
 
if(leser==0)
  
    s2.V()
 
s1.V()
  
s0.V()}
  
-------------------
Schreiber:
  
while(1){
   
s2.P()
   
//schreibe
   
s2.V()}

/* Hier könnte es passieren, dass die Leser unterbrochen werden, da zwischenzeitlich das Semaphor Schreiber zurückgesetzt wird und der Schreiber sich schnell zwischenschalten könnte(zwar nicht schlimm, aber in der Aufgabenstellung steht, falls noch Leser anstehen, sollen sie nicht unterbrochen werden) */ 

-----------------------------------------------------------

//Ich (--Brogazo 17:11, 21. Feb 2007 (CET)) würde es so machen: 

int z = 0;
sem_t *S = new_sem(1);
sem_t *L = new_sem(5);
sem_t mutex = new_sem(1);
Leserprozeß: while(1) {          Schreiberprozeß: while (z>5){}
                                   while(1) {
    P(mutex);
    z = z+1;                         P(S);
    if (z == 1)                      schreiben();
        P(S);                        V(S);
    V(mutex);
      P(L);                        }
      lesen();
      V(L);
    P(mutex);
    z = z-1;
    if (z == 0)
        V(S);
    V(mutex);
}

/* diese lösung ist korrekt, da die aufgabe analog T12 c ist ;) */


b) Problem: Busy Waiting, Lösung: gleichzeitiges Lesen und Schreiben ermöglichen


c) Man müsste festlegen, ob nur 1 Prozess oder mehrere Prozesse gleichzeitig schreiben dürfen und gegebenenfalls eine Unterscheidung der geschriebenen Daten/Prozess ermöglichen

T15

Ob die Variable true oder false ist lässt sich aus der Aufgabenstellung so nicht sagen. Kommt ganz darauf an, wie das System implementiert ist...sie könnte sowohl true als auch false sein.


naja......Detaillierter:

es tritt eine Race Condition auf, Variable wird true, wenn zB:

P1 liest true -> negiert -> schreibt false ->P2 liest false -> negiert -> schreibt true

und false, wenn zB:

P1 liest true -> wird angehalten -> P2 liest true -> negiert -> schreibt false -> P1 wird aktiviert -> hat noch true eingelesen, negiert -> schreibt false

T16

a) 

sem_t s0 = new_sem(1), s1 = new_sem(0), s2 = new_sem(2),
s3 = new_sem(0);
int turn1 = 0, turn2 = 0;
    
 Prozess A      Prozess B            Prozess C
 P(so);         P(s1);               P(s3)
 fuellen(R);    leeren(R);           If(turn2 == 0){
 V(s1);         V(s0);               leere(S[0]);
                P(s2);               V(s2);
                if(turn1 == 0){      turn2 = 1;}
                fuellen(s[0]);       else{
                V(s3);               leere(s[1]);
                turn1 = 1;}          V(s2);
                else {               turn2 = 0;}
                fuellen(s[1]);
                V(s3);
                turn1 = 0;}

b) C weiß nicht ob B die Daten schon hatte, bzw. A weiß nicht ob B die Daten gerade entnommen hat oder C sie schon hat. Außerdem weiß B nicht, ob die Daten, die in R sind, schon modifiziert wurden. ---> System wird sehr langsam weil es so aufgebaut werden muss, dass erst A arbeit, dann B und dann erst C.

Ist nur noch ein Pufferspeicher vorhanden, so muss eine Information mitgeführt werden, welcher Thread als nächstes mit der Abarbeitung dran ist. Dies führt dazu, das ein Thread stets nach einen Bearbeitungsgang unterbrochen wird und ein Threadwechsel stattfinden muss. Dies bewirkt einen großen Verlust der Pseudoparallelität und die Threads verhalten sich wie in einer seqmentiellen Abarbeitung (mit geringerer Performance).

T17

Drei Threads P, Q und R eines Prozesses laufen parallel auf mehreren Prozessoren eines Multiprozessor- Systems mit gemeinsamem Speicher. Jeder der Threads inkrementiert die globale Variable count um 1 (Anfangswert: 17). a) Warum kann count verschiedene Endwerte haben, welche sind das? b) Inwieweit ändert sich die Situation, wenn die Inkrement-Operation auf den einzelnen Prozessoren nicht unterbrechbar ist? c) Inwieweit spielt die Verteilung der Prozesse auf die Prozessoren eine Rolle?

d) Geben Sie eine Lösung an, die zu einem deterministischen Ergebnis führt, bei der kein busy waiting auftritt!

a)

Es kann verschiedene Endwerte haben, da alle drei Threads - es sind ja Aktivitätsträger EINES Prozesses - auf den gleichen Adressraum zugreifen. Dem des Prozesses. SOmit steht in diesem Adressraum irgendwo die Variable count=17. Es kann nun bei der Ausführung passieren, dass alle 3 gleichzeitig die Variable lesen auswerten erhöhen und zurückschreiben, somit wird nicht 3x inkrementiert sondern am Ende nur einmal.

  • count könnte also 18,19 oder 20 sein. Je nachdem wann welche CPU welche Operation ausführt. Es wäre eben auch möglich das alle drei fein hintereinander laufen, dann wird count natürlich auch 3x inkrementiert und ist am Ende 20. Bzw Teilmengen von diesen Ereignissen

b)

  • auf SingleCPU Systeme kämte das einer atomaren Operation gleich. D.h. es käme IMMER 20 raus.
  • Da es aber mehrere Prozessoren sind sind die Operationen zwar nicht teilbar aber die CPU könnten ja zum genau gleichen Zeitpunkt jeweils das inkrement machen und somit wäre das Endergebnis wieder offen

//--Brogazo 18:01, 21. Feb 2007 (CET) Bin mir aber nicht sicher, ob das wirklich so ist!

Vermutung : Da die alle auf dem selben Bus arbeiten und natürlich ein Cache Kohärenzprotokoll anliegt ist das Ergebnis fest (20), dies trifft für a nur nicht zu weil die Register nicht beschützt werden (dafür sind dann Semaphore) 141.76.179.18 16:19, 22. Feb 2007 (CET)

c)

Inwieweit spielt die Verteilung der Prozesse auf die Prozessoren eine Rolle?

  • lustige Frage, oben ist noch die Rede von Threads jetzt von Prozessen???
  • siehe b)
    • wenn alle auf einem Laufen ist das Ergebnis sicher
    • laufen die Threads aber auf unterschiedlichen CPUs ist dies nicht mehr der Fall


//Frage(22.02): können Threads denn überhaupt auf verschiedenen Prozessoren laufen? Prozesse können es, ja, aber Threads werden doch nur innerhalb des Prozesses umgeschalten, oder nicht?? Daher käme bei der b) dann auch eine garantierte 20, oder?

d)

  • Semaphore? ..das Mittel gegen alles? 
sem_t *S = new_sem(1);
    
{...  
  
P(S);   
  count++; 
V(S); 
  
...}

Vermutung es stimmt nicht ganz da ja die Prozessoren immernoch Parallel laufen können.

Sem_t A(1);

Sem_t B(0);

Sem_t C(0);

Prozess A;

A.P(); count++; B.V();

Prozess B;

B.P(); count++; C.V();


Prozess C; C.P(); count++ A.V();

somit schließen sich alle aus und das ergebniss ist definitiv 20.

/* vermutlich nicht ganz richtig, da prozess B und C dann warten müssen, bis prozess a abgeschlossen ist. wenn a aber sehr lange braucht um an die stelle zu kommen, warten b und c auch serh lange. ich denke, es sollte möglich sein, dass die prozesse in beliebiger reihenfolge ablaufen. */

T18

Im Adreßraum eines Prozesses gebe es die drei wie folgt definierten globalen Variablen: 

int i;
int z = 0;
sem_t *s = new_sem(1);

In diesem Adreßraum laufen zwei Threads A und B, die beide einmalig folgenden gleichen Programmcode abarbeiten: 

for (i = 0; i < 2; i++) {
  P(s);
   z++;
  V(s);
}
  • a) Welchen Endwert hat z, wenn A erst nach Beendigung von B gestartet wird?
  • b) Ist der Endwert von z bei paralleler Abarbeitung von A und B eindeutig? (Begründung!)
  • c) Wenn der Wert eindeutig ist: welcher Wert ist dies und warum? Wenn der Wert nicht eindeutig ist: welche Werte sind möglich, wie kommen sie zustande?



a)

  • 4

b)

  • NEIN! der KA ist zwar durch Semaphore geschützt, aber nicht die Schleife! ..es könnte also z.B. das passieren:
  • A hat CPU(Zeit)
    • forSchleife setzt i=0 und macht i++;
    • sperrt den Semaphore und macht z++
  • B hat CPU(Zeit)
    • forSchleife setzt i=0 und macht i++;
  • A hat CPU(Zeit)
    • forSchleife: i ist jetzt wieder 0 !! macht i++;
    • sperrt den Semaphore und macht z++
    • noch ein Durchlauff, macht also i++;
    • sperrt den Semaphore und macht z++
    • nun kein Durchlauf mehr, ja ja i=2 ist
  • B hat CPU(Zeit)
    • sperrt den Semaphore und macht z++
    • i ist nun aber schon 2
    • somit kein weitere Durchlauf

Endergbnis ist also: z=4


  • A hat CPU(Zeit)
    • forSchleife setzt i=0 und macht i++;
  • B hat CPU(Zeit)
    • forSchleife setzt i=0 und macht i++;
  • A hat CPU(Zeit)
    • sperrt den Semaphore und macht z++
    • gibt Sem wieder frei
    • noch ein Durchlauff, macht also i++; i ist nun 2
    • sperrt den Semaphore und macht z++
    • gibt Sem wieder frei
  • B hat CPU(Zeit)
    • sperrt den Semaphore und macht z++
    • gibt Sem wieder frei
    • nun aber keiner DUrchlauf mehr! i ist ja schon nicht mehr kleiner als 2

Endergbnis ist also: z=3

/* prinzipiell richtig, reihenfolge der schleifen abarbeitung stimmt aber nicht: i wird verglichen, ob i < 2 und erst am ende der schleife incrementiert, nicht direkt nach dem vergleich. schließlich ist bei for(i=0;i<1;i++){print(i);} die ausgabe 0 und nicht 1 */

c)

  • Der Wert ist nicht eindeutig. 2,3,4,5 sind mögliche Werte.

T19

a)

  • A vor B: x=2
  • B vor A: x=4

b)

  • x kann wiederum 2 oder 4 sein, je nachdem, wann y=y+1 ausgeführt wird

c)

sem_t s = new_sem(0)
   
void A(){
   x = x+1; 
   x = x*y;
   s.V();
}
void B(){
  s.P();
  y = y+1;
}

T20

a)

  • Fall 1)
    • A beginnt (x=2) -> B blockiert -> C arbeitet (x=1) -> B kommt dran (x=2)
  • Fall 2)
    • C beginnt (x=0) -> A blockiert -> B arbeitet (x=0) -> A kommt dran (x=1)

b)

eine Art Ablaufsteuerung, B kann nicht vor C drankommen, A entweder am Anfang oder am Ende
oder einfach nur, dass nie mehrere Threads gleichzeitig auf den kA (hier x) zugreifen können...?

c)

Deadlocks existieren nicht, da jeder Thread nur maximal ein Betriebsmittel (Semaphor) belegt. Das kann laut Def. und logischen Denken nicht zu Deadlocks führen

T21

a)

  • f1: CPU wird frei oder Rechenzeit des Vorgängerprozesses abgelaufen
  • f2: Prozeß mit höherer Priorität bereit
  • f3: Prozeß benötigt Input (Ereignis) von außen
    • // bzw. Prozess braucht ein BM was er nicht bekommt --> zB einen Semaphor -> wird blockiert
  • f4: Prozeß hat benötigten Input erhalten
    • geht aber in BEREIT über, da CPU noch nicht frei bzw. er "nicht dran" ist
  • f5: Prozesserzeugung
    • zB durch einen fork...
  • f6: Thread beendet
    • z.B. kill des Prozesses

b)

Prozeß kann sich im blockierten Zustand befinden und erhält niemals den gewünschten Input, kann somit blockierten Zustand nie verlassen

Lösung: Timeout einführen und damit einen Übergang schaffen zw. blockiert und nicht existierend, unter der Bedingung Timeout

T23

a)

  1. Sicherheit (aka wechselseitiger Ausschluss):
    1. Es darf zu einem Zeitpunkt nur ein Prozess im kritischen Abschnitt sein.
  2. Lebendigkeit:
    1. Jeder Prozess, der in den kritischen Abschnitt möchte, muss das auch irgendwann dürfen.
      1. Ausschluss von Fernwirkung: Das Betreten des kA darf nicht davon abhängig sein, dass ein anderer Prozess bereits im kA war
      2. Ausschluss von Ausgrenzung: ein Prozesse darf nicht ständig gehindert werden, den kA zu betreten
      3. Ausschluß von Deadlocks: 2 oder mehr Prozesse dürfen sich nicht gegenseitig am Eintritt in ihren kA behindern

b)

zu 1.: da jeder Prozess vor Betreten des kA überprüft, ob sich der jeweils andere bereits dort befindet (Zeile 3) und wenn ja in eine Schleife geht und diese erst verlässt, wenn der andere Prozess den kA verlassen hat (Zeile 10), ist diese Bedingung erfüllt.

zu 2.: (hierbei sei vorausgesetzt, dass jeder Prozess den kA nach endlicher Zeit auch wieder verlässt)

Fall 1: Beide Prozesse in der While-Schleife "turn" kann nur 0 oder 1 sein. folglich wird flag0 oder 1 kurzzeitig auf false gesetzt, so dass ein Prozess die Schleife verlassen kann

Fall 2: Ein Prozess im kA der andere in der While-Schleife flag0 und flag1 müssen true sein, weil auf dem Weg zur Schleife Zeile 2 mindestens einmal passiert wurde. Beendet Prozess1 den kA und will danach sofort wieder hinein, ohne dass Prozess0 dort war, so ist turn=0 (Zeile 11) und deswegen wird flag1 kurzzeitig wieder auf false gesetzt (Zeile 5), so dass Prozess0 die Möglichkeit bekommt die Schleife zu verlassen und den kA zu betreten.

Fall 3: Ein Prozess inaktiv, der andere will erneut in den kA flag0 musste bereits false sein, folglich wird die While Schleife übersprungen und der Prozess kommt direkt in den kA.

T22

a) 

        Thread A                      Thread B
betrag = 20;                  betrag = 1;
if (kontostand >= betrag)     if (kontostand >= betrag)
-->                           -->
   kontostand -= betrag;         kontostand -= betrag;

Angenommen kontostand war zu beginn 20, so kann es nach dieser Konstruktion auftreten, dass Thread A und Thread B abheben, wenn sie zu einem Zeitpunkt an den mit den Pfeilen markierten Positionen sind. Die Bedingung kontostand soll größer oder gleich 0 sein kann so nicht erfüllt werden.

b) Der einzig mögliche Ablauf ist: Zuerst kann B arbeiten und danach A. Der Endwert für x ist somit 3. Das kommt daher, dass das Semaphor mit 0 initialisiert wird und A somit nicht in der Lage ist es runter zu zählen. Bevor B also fertig gelaufen ist und das Semaphor am Ende inkrementiert hat kann A demnach nicht laufen -> erst endet B, dann A (sequentiell), egal in welcher Reihenfolge die Threads gestartet werden.

c) Die Forderung kann nicht als Allgemeingültig gelten, da der Zugriff von B auf x ungeschützt stattfindet und es dennoch nur eine Möglichkeit gibt, wie die beiden Threads ausgeführt werden.

T26

Annahme: A, B und C laufen jeweils nur 1x. Sei mutex1, mutex2 = Semaphor(1) und k = Semaphor(0). Dann ist folgendes der Code für die einzelnen Threads:

A:
mutex1.P();
//working
mutex1.V();
k.V();

B:
mutex2.P();
//working
mutex2.V();
k.V();

C:
k.P();
//working

Der k-Semaphor lässt C solange schlafen, bis jeweils A und B den k-internen Counter wieder auf 1 gesetzt haben und damit C aufwecken.

/* ich denke die lösung ist falsch, da bei dieser lösung A und B gleichzeitig ausgeführt werden können, was durch die Aufgabenstellung unzulässig ist. Desweitern wird ein wartender prozess aktiviert, sobald ein semaphor freigegeben wird, somit wird C gestartet, sobald A _oder_ B fertig sind.
Meiner Meinung nach müsste die lösung so aussehen:

mutex1 = semaphor(1);
mutex2 = semaphor(0);

A:
mutex1.P(); // mutex 1 stellt sicher, dass nur A oder B laufen
//working
mutex1.V();
mutex2.V(); // anzeige für C, dass prozess fertig

B:
mutex1.P();
//working
mutex1.V();
mutex2.V();

C:
mutex2.P(); // warten auf ersten prozess
mutex2.P(); // warten auf zweuten prozess
//working // erst wenn beide fertig sind, arbeiten

/* die lösung ist auch falsch, da A zwei mal laufen kann und danach C laufen kann, obwohl B nicht abgearbeitet wurde */
mutex = sem(1);
semA = sem(0);
semB = sem(0);

A:
mutex.P();
//working
mutex.V();
SemA.V();

B:
mutex.P();
//working
mutex.V();
SemB.V();

C:
SemA.P();
SemB.P();
mutex.P();
//working
mutex.V();

T27

Betrachtet werde ein System von drei Threads, die in einem gemeinsamen Adressraum laufen und folgende globalen Variablen nutzen...(Aufgabenstellung zu lang)

a) sem_T s(1), t(0); Thread A kann nur laufen, wenn weder Thread B noch Thread C läuft. Thread B kann nur laufen, wenn weder Thread A noch C läuft. Thread C kann nur dann einmal laufen, wenn Thread B einmal gelaufen ist. Semaphore t() wird am Ende von B auf 1 gesetzt und am Anfang von C geprüft und auf 0 gesetzt. Jeder Aufruf von C ist also an einen vorherigen Aufruf von B gebunden. C kann außerdem nicht laufen, wenn A gerade läuft, da auch Semaphore s() in C genutzt wird.

b) Das Vertauschen der beiden P Operationen in C kann zu folgendem Ablauf führen. Thread B läuft, Semaphore s() wird von 0 auf 1 gesetzt am Ende von B. Es kommt zu einem Interrupt, Semaphore t() ist in diesem Moment 0. Der Interrupt startet Thread C. Dieser dekrementiert s(), kann aber t() nicht dekrementieren, da t(0). Nun sind beide Semaphore 0 und keiner kann mehr starten. --> Deadlock

/* aber sobald b wieder dran ist, gibt dieser t frei und c kann weiterlaufen, also kein deadlock.
der deadlock tritt auf, wenn C sich s holt und dann auf t wartet. t kann nur am ende von B freigegeben werden. B kann aber nicht laufen, da er dazu s braucht, welches von C blockiert wird. */

Kurios im P-B-Graphen ist, dass auf den ersten Blick kein Zyklus zu sehen ist. Stellt man sich jedoch vor, dass Thread B als einziger das Recht hat, t.V(); auszuführen, und damit eigentlich das Betriebsmittel t "besitzt", führt dies zu einer neuen Kante im Graphen. Trägt man diese Kante im Graphen ein, sieht man einen Zyklus.

Von „https://tudwiki.hicknhack.org/index.php?title=Betriebssysteme:Aufgaben_T&oldid=6909“