fragment_nebenlaeufigkeit.tex

\section{Nebenläufigkeit}

\question{Erkläre den Begriff ,,Nebenläufigkeit''. Welchen Zweck haben Petri-Netze in diesem Kontext?}
\begin{answer}
engl. concurrency

Nebenläufigkeit entsteht, wenn mehrere Ereignisse in keiner kausalen Beziehung zueinander stehen, sich also nicht beeinflussen. Aktionen können nur dann nebenläufig ausgeführt werden (sie sind parallelisierbar), wenn keine das Resultat der anderen benötigt.

Eine Modellierungssprache, die diese Abhängigkeiten wiedergibt, sind Petri-Netze.
\end{answer}

\question{Skizziere kurz einige Probleme des nebenläufigen Zugriffs auf Betriebsmittel.}
\begin{answer}
Zwei Prozesse dürfen nicht gleichzeitig auf ein Betriebsmittel zugreifen (kritischer Abschnitt). Es kann hier zu \crucial{Verklemmungen (Deadlocks), dem After-you-after-you Problem und dem Verhungern} kommen.

Bei nebenläufigem Zugriff kann es zu inkonsistenten Daten kommen, wenn der \crucial{gegenseitige Ausschluss} nicht gewährleistet ist.
\end{answer}

\question{Grenze die Begriffe \textit{Nebenläufigkeit}, \textit{Quasi-Parallelität} und \textit{Parallelität} voneinander ab. Was verstehen wir unter Nichtdeterminismus?}
\begin{answer}
\begin{description}
\item[Nebenläufigkeit] \hfill \\ ist das Abarbeiten von mehreren Prozessen mit einer CPU. 
\item[Quasi-Parallelität]  \hfill \\ ist z.B. paralleles Arbeiten auf einem Einprozessorsystem. In der CPU wird nichts parallel bearbeitet, für uns scheint es am Monitor aber so.
\item[Paralellität] \hfill \\  ist das Abarbeiten von Prozessen mit einer Mehrprozessormaschine.
\item[Nichtdeterminismus] \hfill \\  ist ein Konzept, in dem Algorithmen oder Maschinen bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand haben. 
\end{description}
\end{answer}

\begin{multilinequestion}[Welche Nebenläufigkeitseigenschaften bzw. -probleme werden durch die folgenden ,,klassischen'' Szenarien ausgedrückt:]
\begin{enumerate}
\item Kritischer Abschnitt (Critical Section)
\item Leser/Schreiber (Reader/Writer)
\item Erzeuger/Verbraucher (Producer/Consumer)
\item Speisende Philosophen (Dining Philosophers)?
\end{enumerate}
\end{multilinequestion}
\begin{answer}
\begin{description}
\item[Kritischer Abschnitt] \hfill \\
Zwei nebenläufige Vorgänge greifen auf das selbe Betriebsmittel zu (z.B. zwei Threads auf eine gemeinsame Variable). Das Ergebnis hängt von der tatsächlichen Ausführungsreihenfolge ab und es entsteht (ungewollter) nicht-Determinismus.\\
Lösung: Gegenseitiger Ausschluss oder Mehrseitige Synchronisation.
\item[Leser/Schreiber] \hfill \\
Datenbestand, auf den verschiedene Prozesse lesend bzw. schreibend zugreifen. Z.B. Datenbank (Datensätze mit mehreren Komponenten). Paralleles Lesen ist ok. Aber nicht parallel lesen und schreiben. \\
Abhilfe: z.B. Verwendung eines Locking-Verfahrens
\item[Erzeuger/Verbraucher] \hfill \\
Gemeinsames Kommunikationsobjekt (Warteschlange: Speicherbereich, Datei, Pipe,...).
Erst schreiben, dann lesen - Verbraucher muss auf den Erzeuger warten. Viele mögliche Probleme (Count-Zähler führt nicht korrekt Buch: kritischer Abschnitt; Elemente in scheinbar leerer Warteschlange, Platz in scheinbar voller Warteschlange; Lost-Wakeup, Verklemmung).
\item[Speisende Philosophen] \hfill \\
Fünf Philosophen und nur fünf Stäbchen zum Reisessen. Mehrseitige Synchronisation nötig und Gefahr von Verklemmungen, Philosophen verhungern.\\
Mögliche Lösung durch Vermeidung (Bankiers Algorithmus): Es dürfen nur vier Philosophen an den Tisch.
\end{description}
\end{answer}

\question{Was ist ein Thread (,,Faden'')? Skizziere ein sinnvolles Anwendungsbeispiel für die Verwendung mehrerer Threads innerhalb eines Prozesses.}
\begin{answer}
\begin{description}
\item[Threads] können parallel durchlaufen werden, auch wenn sie zu einem gleichen Prozess gehören. Sie ermöglichen also Parallelisierung/Nebenläufigkeit. Bringen aber damit auch bekannte Gefahren mit sich. 
\end{description}

Ein Prozess könnte eine Operation auf mehrere Datensätze ausführen, das ist sehr gut parallelisierbar.

Oder ein Prozess hat eine Grafische Benutzeroberfläche (GUI) und führt Berechnungen durch. Dann soll die GUI immer bedienbar sein, auch wenn grade eine aufwändige Berechnung läuft.
\end{answer}

\question{Was besagt Prämemption?}
\begin{answer}
Präemption ist die \crucial{zeitweise Unterbrechung} der Bearbeitung einzelner Prozesse zugunsten anderer.
\end{answer}

\question{Grenze den Thread-Begriff gegen den UNIX-Prozess ab (Adressraum, Zustandsinformationen etc.). Was haben Light-Weight-Prozesse (LWPs) damit zu tun?}
\begin{answer}
Ein Prozess hat einen eigenen Adressraum und ist somit stark abgeschottet gegenüber anderen
Prozessen. Prozesse können aus anderen Prozessen erzeugt werden und arbeiten trotzdem weiter,
wenn der Vater-Prozess terminiert ist. Prozesse sind eigenständig.
\crucial{Threads sind mehrere Kontrollfäden in einer Hülle, nämlich dem Prozess}, aus dem sie aufgerufen
wurden. Threads haben zwar einen \crucial{eigenen Ausführungszustand (PC, Stack)} dafür aber eine
\crucial{gemeinsame Umgebung} (Adressraum, offenen Dateien, gemeinsame Datenstrukturen). Hier kann 
es zu kritischen Abschnitten kommen. Eine Synchronisation ist erforderlich. Einem Thread muss
Arbeit (eine Prozedur) zugewiesen werden. Ein Thread ist beendet, wenn die Umgebung, also der Prozess,
terminiert. Ein \crucial{Thread ist also von der Umgebung abhängig}.
Ein Problem ist, dass der Betriebssystemkern nichts vom Erzeugen der Threads erfährt, es ist also
keine ,,echte Nebenläufigkeit'' gegeben.
Light-Weight-Prozesse dagegen sind dem Bestriebsystemkern bekannt. Das stellt die Grundlage
für das Scheduling dar.
\end{answer}

\question{Die Routinen \texttt{pthread\_create()}, \texttt{pthread\_join()}, \texttt{pthread\_exit()} realisieren die Erzeugung und Termination von Threads in der UNIX-Multithreading-Umgebung. Vergleiche ihre Funktionalität mit den Systemaufrufen zur Erzeugung und Termination von Prozessen (\texttt{wait()}, \texttt{fork()} und \texttt{exit()}). Warum arbeitet \texttt{pthread\_create()} deutlich anders als \texttt{fork()}?}
\begin{answer}
\begin{description}

\item[pthread\_create()] \hfill \\ 
Thread wird Prozedur zugewiesen, hat eigenen Ausführungszustand (PC,Stack)

\item[fork()] \hfill \\ 
erstellt eine Kopie des Adressraumes. Kind kann weiterarbeiten nachdem der Vater bereits terminierte.

\item[pthread\_join()] \hfill \\ 
sammelt Thread ein wenn er beendet ist. Bei Prozessende werden eventuell nichtabgeschlossene
Threads beendet.

\item[wait()] \hfill \\ 
wartet auf die Terminierung eines Prozesses. Welcher Prozess kann über die Prozess-ID abgefragt
werden.

\item[pthread\_exit()] \hfill \\ 
zum vorzeitigen Beenden von Threads

\item[exit()] \hfill \\ 
zum vorzeitigen Beenden von Prozessen
\end{description}

\texttt{pthread\_create()} erzeugt in einer gemeinsamen Umgebung einen eigenen Ausführungszustand. Dazu muss
beim Erzeugen unter anderem auch eine Stack-Info erstellt werden. Mit Threads ist es möglich,
von einem Programmfaden in mehrere überzugehen. 

\texttt{fork()} ist dagegen so ausgelegt, dass ein
eigenständiger Prozess erzeugt wird. Dieser wird auch vom Scheduler berücksichtigt, da er dem
Betriebsystemkern bekannt ist.
\end{answer}

\question{Was versteht man unter \textit{einseitiger} bzw. \textit{mehrseitiger Synchronisation}? Gib jeweils ein Anwendungsbeispiel an.}
\begin{answer}
\begin{description}

\item[Einseitige Synchronisation] Producer-Consumer-Problem mit unendlicher Pufferkapazität; benötigt eine Semaphore
\begin{verbatim}
Sem s(0);

Producer:
erzeugen();
s.V();

Consumer:
s.P();
verbrauchen();
\end{verbatim}

\item[Mehrseitige Synchronisation] Producer-Consumer-Problem mit begrenzter Pufferkapazität; benötigt zwei Semaphoren
\label{mehrseitige-synchronisation-beispiel}

\begin{verbatim}
Sem s1(0);
Sem s2(3);

Producer:
s2.P();
erzeugen();
s1.V();

Consumer:
s1.P();
verbrauchen();
s2.V();
\end{verbatim}
\end{description}
\end{answer}

\question{Was ist der Unterbrechungsauschluss?}
\begin{answer}
Beim Unterbrechungsausschluss werden alle Unterbrechungen auf Systemebene für den kritischen Abschnitt augeschaltet:

\begin{verbatim}
disable_interrupts(); (entspricht lock())
... kritischer Abschnitt ...
enable_interrupts(); (entspricht unlock())
\end{verbatim}

Damit sind keine Unterbrechungen möglich, folglich auch kein ,,Prozesswechsel''. Ebenso kann sich nur ein Prozess gleichzeitig im kritischen Abschnitt befinden.

Problem hierbei ist, dass Interrupts zeitkritisch sind und somit die Gefahr besteht, dass relevante Interrupts nie verarbeitet werden. Ebenso funktioniert der Unterbrechungsauschluss nur bei Einprozessorsystemen. Im User-Mode ist der Unterbrechungsauschluss gar nicht möglich.

In der Regel wird zuviel gesperrt; viele Aktivitäten wollen kritischen Abschnitt gar nicht betreten.
\end{answer}

\question{Was ist ein kritischer Abschnitt? Wie kann man den gegenseitigen Ausschluss gewährleisten? Warum ist ein Unterbrechungsausschluss dabei nicht immer das geeignete Mittel?}
\begin{answer}
Ein kritischer Abschnitt ist ein Teil des Programmcodes, welcher geschützt werden muss, wenn zwei Threads auf die selben Ressourcen zugreifen.

Ein kritischer Abschnitt ist ein Programmteil, in dem von mehreren Programmabläufen auf eine gemeinsame
Datenstruktur oder auf ein gemeinsames Betriebsmittel zugegriffen wird. Kritische Abschnitte müssen daher geschützt werden. Sonst würde es eventuell zu falschen Ergebnissen kommen. jeder kritische Abschnitt benötigt daher einen Schliessmechanismus, der durch eine ,,Schlossvariable'' realisiert wird. Bei Betreten eines kritischen Abschnitts wird dann diese Variable gesetzt (oft Boolean TRUE).

\paragraph*{}
Andere Programmabläufe müssen nun den Status der Schlossvariablen nachfragen,
um zu erfahren, ob der kritische Abschnitt frei ist oder nicht.
Möglichkeiten, den gegenseitigen Ausschluss zu gewährleisten:
- eigene Absicht anmelden, dann überprüfen ob anderer auch will. Jeder Programmablauf benötigt
eine eigene Schlossvariable. Sobald einmal die Absicht einzutreten erklärt wurde, ist der kritische
10
Abschnitt gesperrt. Der gegenseitige Ausschluss ist somit gewährleistet.
Problem: Wenn zwei Programmabläufe nebenläufig die Absicht anmelden, können beide Abläufe
in einer Endlosschleife hängenbleiben, weil sie darauf warten, dass der andere den kritischen Abschnitt
freigibt.
- Unterbrechungen ausschalten. Andere Programmabläufe können nun nicht mehr einen anderen
unterbrechen, wenn sich dieser im kritischen Abschnitt befindet.
- andere Prozesse blockieren>: hier werden andere programmabläufe einfach blockiert, egal ob sie
nun auf kritische Abschnitte zugreifen können oder nicht.
- wenn trotdem andere prozesse während eines kritischen Abschnitts zugelassen werden sollen,
dann müssen wie oben mechanismen gefunden werden, um den kritischen Abschnitt zu schützen.
Gegenseitiger Ausschluss durch Unterbrechungsausschltung funktioniert nur bei Einprozessorsystemen.
Wenn ein Prozess sich in einem kritisdchen Abschnitt befindet, und nicht selbst wieder
herauskommt (z.B. Endlosschleife), wäre es nicht sinnvoll, hier die Unterbrechung auszuschalten.
\end{answer}

\question{Nach welchen Kriterien wird Korrektheit bzw. Güte von \textit{Locking-Algorithmen} bewertet? Wie geht man dabei vor?}
\begin{answer}
Der Zugriff auf Schlossvariablen darf nicht selbst in einem kritischen Abschnitt liegen. Locking-Algorithmen sollten verklemmungsfrei arbeiten.
\end{answer}

\question{Warum sollte man die Bewertung von Locking-Algorithmen auf der Grundlage von \textit{unteilbaren Operationen} durchführen?}
\begin{answer}
Nur unteilbare Operationen sind nicht unterbrechbar. Unteilbare Operationenen sind Maschinen-Instruktionen, also die unterste Ebene der Programm-Ausführung.
Wenn man ein Programm auf Maschinen-Code runterbricht, kann man sehr gut erkennen, dass nach jedem Befehl eine Unterbrechung, z.B. ein Interupt zum Prozesswechsel, erfolgen kann (z.B. durch Ablauf der Zeitscheibe). Die kritischen Abschnitte lassen sich daher genau analysieren und Anfang und Ende festlegen.
\end{answer}

\question{Auf welche verschiedenen Arten kann man \textit{Verklemmungen} angehen? Wie arbeitet der \textit{Bankiersalgorithmus}?}
\begin{answer}
Ein Deadlock liegt an, wenn z.B. zwei oder mehrere Prozesse auf ein Betriebsmittel warten, das nur
von anderen freigegeben werden kann, es aber nicht mehr zu der Freigabe kommen wird.
Möglichkeiten:
\begin{itemize}
\item Deadlock ignorieren, wenn er nur selten auftreten kann, da eine Lösung unter Umständen zu
teuer ist.
\item Deadlock durch Untersuchung des Betriebsmittelgraphen entdecken und Deadlock durch Zwangsentfernen
eines Prozesses beheben.
\item Deadlock verhindern durch das erkennen der Randbedingung, die zum Deadlock führt:
\begin{itemize}
\item Exklusivität (Spooling)
\item alles auf einmal anfordern (aber: Verschwendung von Ressourcen!)
\item Zwangsentzug
\item Zyklus verhindern (Betriebsmittel nach aufsteigender Nummer anfordern und belegen), dies führt
zu einer Einschränkung der Prozesse.
\end{itemize}
\item Deadlocks vermeiden: Bankiersalgorithmus.
\end{itemize}
\begin{description}
\item[Bankiersalgorithmus] \hfill \\
Die Idee ist, dass die maximale Anforderung von Betriebsmitteln im voraus bekannt ist. Belegung
wird nur dann gewährt, wenn das System dadurch nicht in einen Zustand gelangt, der zu einem
Deadlock führen kann. Diesem Verfahren liegt das Modell eines Bankiers zugrunde, der mit Kunden
einen Kreditrahmen aushandelt, der nach und nach eingelöst werden kann, aber die Grenzen der
Leistungsfähigkeit nicht sprengt.
\end{description}
\end{answer}

\question{Wie kann man eine einseitige Synchronisation mit Hilfe von wait() und signal() vornehmen? Wie kann man diese Primitiven in etwa auf lock() und unlock() abbilden?}
\begin{answer}
TODO
\end{answer}

\question{Grenze die Begriffe \textit{aktives} und \textit{blockierendes} Warten voneinander ab.}
\begin{answer}
Beim aktiven Warten wird ständig die Schlüsselvariable eines kritischen Abschnitts überprüf, ob diese nun frei geworden ist oder nicht. Durch das ständige Abfragen wird unter Unständen unnötig CPU-Zeit in Anspruch genommen.
Beim blockierenden Warten legt sich der betreffende Prozess schlafen, falls der kritische Abschnitt nicht frei ist. Wird der kritische Abschnitt von dem anderen Prozess verlassen, so führt dieser ein wakeup() aus, um die schlafenden Prozesse zu wecken.
\end{answer}

\question{Was ist ein Spinlock?}
\begin{answer}
Ein Spinlock ist aktives Warten im Programm selber.
\end{answer}

\question{Was ist aktives Warten?}
\begin{answer}
Aktives Warten ist das Verharren in einer Schleife, bis der kritische Abschnitt wieder frei ist: Spinlocks

Nachteil: Verbrauchen unnötig Prozessorkapazität durch permanente Abfragen (bis Zeitscheibe aufgebraucht)

\begin{verbatim}
    Gemeinsam von A und B genutzte Variable: lock
    Interpretation des Werts:                0 gesperrt, ungleich 0 offen 
    Initialisierung:                         lock = 0
           
    Prozess A                    Prozess B
       ...                          ...
       solange (lock == 0) {        ...
          ;                         lock = 1;
       }                            ...
       Aktion a                     ...
\end{verbatim}
\end{answer}

\question{Was ist blockierendes Warten?}
\begin{answer}
Beim blockierenden Warten legt sich der Prozess schlafen, wenn der kritische Abschnitt gerade nicht frei ist (sleep()).

Bei Verlassen des kritischen Abschnitts werden darauf wartende Prozesse aufgeweckt (wakeup()).

Interrupthandler sind zeitkritisch und haben keinen eigenen Prozesskontext, können sich also nicht schlafenlegen und können zur mehrseitigen Synchronisation kein blockierendes Warten verwenden.
\end{answer}

\question{In einer UNIX-Multiprozessorumgebung können mehrere Prozesse nebenläufig \texttt{sleep()} aufrufen. Warum ist dies ein kritischer Abschnitt? Warum kann man ihn nicht einfach davor schützen, dass man den Aufruf von \texttt{sleep()} von einem \textit{Spinlock} umgibt? Was wird man stattdessen tun?}
\begin{answer}
Die gemeinsame Datenstruktur ist hier die Sleep-Queue. Wenn sich ein schlafender Prozess von einem Spinlock umgibt, dann kann er unter Umständen nicht wieder aufgeweckt werden, da er die Sleep-Queue nicht freigegeben hat.

Als Lösung wird eine Variante von sleep() eingeführt: sleepl().
sleepl() gibt die Sleep-Queue wieder frei (gibt den Spinlock wieder ab), bevor die CPU abgegeben wird (vorm Schlafenlegen).

Tim: Was ist mit der Prozesstabelle? Laut Tutorium ist diese ebenfalls relevant.
\end{answer}

\question{Was sind Semaphore?}
\begin{answer}
P() / V()

P(): blockieren [wait, acquire oder down]; counter-- \\
V(): entblockieren [signal, release, post oder up]; counter++

auch; ,,counting semaphore''

Zähler $>= 0$ bei Eintritt in kritischen Bereich inkrementiert, dekrementiert bei Austritt. Bei Zähler $= 0$ warten.

P()/V() ist nicht an Blockstrukturen gebunden. \\
P()/V() ist nicht immer regelmä"sig geschachtelt. 
\end{answer}

\question{Welche zusätzlichen Eigenschaften zeichnen Semaphoren gegenüber blockierenden Locks aus?}
\begin{answer}
\begin{itemize}

  \item Semaphore ist FIFO-Queue, ist also fair.

  \item Semaphore: Anzahl der Zugriffe können begrenzt werden (<-> blockierendes Warten alle).

  \item Blockierendes Warten ist unabhängig.

  \item Synchronisation der Betriebsmittelverwaltung.
\end{itemize}

Es gibt zwei zusätzliche Erweiterungen bei einer Semaphore:

\begin{itemize}

  \item Im Wartefall wird der Prozess in eine FIFO-Queue eingereiht, das hei"st, die Prozesse werden nach Ankunftsreihenfolge beim kritischen Abschnitt abgearbeitet.

  \item Semaphore-Counting, das heisst die Semaphore enthält einen Counter, durch den die Semaphore erst blockiert, wenn sich n Prozesse im kritischen Abschnitt befinden. Eine Semaphore wird mit $n$ vorinitialisiert.

\end{itemize}
\end{answer}

\question{Was sind Monitore?}
\begin{answer}
\begin{verbatim}
  public synchronized void einzahlen(int betrag) {
  .. ändere Konto ..
  }
\end{verbatim}

Schutz erfolgt nur gegenüber anderen Methoden der Klasse, die ebenfalls synchronized sind, und kritischen Abschnitten, die sich über das Objekt synchronisieren.
\end{answer}

\question{Was sind Mutexes?}
\begin{answer}
kurz für: mutual exclusion

Erlauben den gegenseitigen Ausschluss. Sie sind als mehrseitige Synchronisation (allerdings Zugriff auf die selbe Semaphor-Variable) realisiert.

\begin{verbatim}
  IrgendeineKlasse myObj = new IrgendeineKlasse();
  synchronized (myObj) {
  .. kritischer Abschnitt ..
  }
\end{verbatim}

äquivalent zu:

\begin{verbatim}
  Mutex myObj;
  myObj.lock();
  .. kritischer Abschnitt ..
  myObj.unlock();
\end{verbatim}

Mutexes lassen sich auch über Semaphore umsetzen.

Signale/Ereignisse: myObj.wait()/myObj.notify()
\end{answer}

\question{Wie wird eine einseitige bzw. mehrseitige Synchronisation durch Semaphore ausgedrückt?}
\begin{answer}
\begin{itemize}

  \item einseitige: Erzeuger-Verbraucher-Prinzip \\
    Die Semaphore muss mit 0 vorinitialisiert werden. Wenn in einem Prozess B etwas ausgeführt werden soll, was abhängig von einem anderen Prozess A ist (zum Beispiel ein Ereignis), dann muss vorher P() ausgeführt werden. In A muss, wenn das betreffende Ereignis stattgefunden hat, V() ausgeführt werden. Wurde das V() nicht ausgeführt, und versucht B jetzt P() auszuführen, so wird blockiert und gewartet bis V() kommt.

    P1: .. Daten produzieren .. (kritischer Abschnitt); S.V (Producer-Thread) \\
    P2: S.P; .. Daten verarbeiten .. (kritischer Abschnitt) (Verbraucher-Thread)

    S = Sempaphor

  \item mehrseitige Synchronisation: Funktioniert wie einseitige, jedoch mit einer oder mehren Semaphoren.
        Bei einer Semaphore S greifen alle Threads auf S zu:

      P1: S.P; kritischer Abschnitt 1; S.V \\
      P2: S.P; kritischer Abschnitt 2; S.V

        Für ein Beispiel mit mehreren Semaphoren, siehe \ref{mehrseitige-synchronisation-beispiel}.

\end{itemize}
\end{answer}

\question{Was sind die speisenden Philosophen?}
\begin{answer}
Die Philosophen sitzen am Tisch und denken über philosophische Probleme nach. Wenn einer hungrig wird, greift er zuerst die Gabel links von seinem Teller, dann die auf der rechten Seite und beginnt zu essen. Wenn er satt ist, legt er die Gabeln wieder zurück und beginnt wieder zu denken. Sollte eine Gabel nicht an ihrem Platz liegen, wenn der Philosoph sie aufnehmen möchte, so wartet er, bis die Gabel wieder verfügbar ist.

Solange nur einzelne Philosophen hungrig sind, funktioniert dieses Verfahren wunderbar. Es kann aber passieren, dass sich alle fünf Philosophen gleichzeitig entschlie"sen, zu essen. Sie ergreifen also alle gleichzeitig ihre linke Gabel und nehmen damit dem jeweils links von ihnen sitzenden Kollegen seine rechte Gabel weg. Nun warten alle fünf darauf, dass die rechte Gabel wieder auftaucht. Das passiert aber nicht, da keiner der fünf seine linke Gabel zurücklegt. Die Philosophen verhungern.
\end{answer}

\question{Wie können Semaphore zur Lösung des Problems der speisenden Philosophen eingesetzt werden? In welches Problem wird eine allzu einfache ,,Implementierung'' laufen?}
\begin{answer}
Fünf Philosophen sitzen an einem Tisch mit fünf Tellern Reis. Zwischen jedem der Teller befindet
sich ein Stäbchen, also insgesamt sind auch fünf Stäbchen vorhanden. Das Problem ist, dass jeder Philosoph zwei Stäbchen zum Essen benötigt, es können also nicht alle Philosophen gleichzeitig essen. Nur für zwei gleichzeitig speisende Philosophen sind ausreichend Stäbchen vorhanden.
Jedes Stäbchen ist ein kritischer Abschnitt. Es kommt aber zu Verklemmungen, wenn jeder Philosoph z.B. sein linkes Stäbchen nimmt, kann keiner der Philosophen essen.
Lösung: Einsatz von Semaphoren für Stäbchen und Philosophen, das hei"st immer Paare schützen.
\end{answer}

\question{Warum bietet eine einfache Semaphor-Implementierung mit den UNIX-eigenen \texttt{sleep()/wakeup()}-Routinen keine vollständige Semaphore-Semantik? Welche zusätzlichen Massnahmen müsste man ergreifen?}
\begin{answer}
Bevor sich ein Prozess schlafenlegt, wäre es sinnvoll den kritischen Abschnitt wieder freizugeben, da dieser sonst unter Umständen nicht wieder aufgeweckt werden kann. Als zusätzliche Massnahme muss der Abschnitt also wieder freigegeben werden.
\end{answer}

\question{Welche Probleme gibt es mit ,,fairen Semaphoren''? Was sind ,,Konvois'', was sind ,,donnernde Herden''?}
\begin{answer}
Duch das Einreihen der Prozesse in eine FIFO-Queue kommt es zu einer festen Reihenfolge bei der Abarbeitung. Es kann hier zu Konvois kommen. Weiterhin kann es zu unnötig vielen Prozesswechseln kommen, wenn die Prozesse aus der FIFO-Queue entnommen werden, prüfen ob sie den kritischen Abschnitt betreten können und wieder eingereiht werden.

\paragraph*{}
Zu donnernden Herden kann es kommen, wenn man das Semaphore-Counting benutzt. Alle Prozesse, die beim Eintreten in den kritischen Abschnitt schlafen gelegt wurden, warten praktisch auf eine Veränderung des Counters. Wenn nun ein anderer Prozess den kritischen Abschnitt frei gibt, indem er ein V() ausführt, werden alle wartenden Prozesse geweckt und donnern los. Es kommt aber nur einer in den kritischen Abschnitt hinein.
\end{answer}

\question{Was ist ein Monitor? Unter welchen Bedingungen wird ein Monitor betreten bzw. wieder verlassen?}
\begin{answer}
Ein Monitor ist ein ADT (Abstrakter Datentyp), also mit Daten und Operationen auf diesen Daten. Die Zugriffsoperationen sind implizit gegen nebenläufigen Zugriff geschützt. Das heisst, der Programmierer muss sich keinen Gedanken mehr um den Schutz von kritischen Abschnitten innerhalb des Programmes zu machen, da der Nenbenläufigkeitsschutz im Monitor bereits implementiert
ist.

\paragraph*{}
Vorteil dieser Lösung ist, dass eventuelles Vergessen von Schutzanweisungen nicht mehr möglich ist. Ein Monitor wird betreten, wenn von einer Prozedur des Programms eine entsprechende Monitorfunktion aufgerufen wird. Verlassen wird er, wenn er warten muss (wait()) oder wenn er fertig ist.
\end{answer}

\question{Aus welchen Komponenten besteht ein Petrinetz (mit Marken)? Was kann man damit beschreiben?}
\begin{answer}
Ein Petrinetz ist ein gerichteter Graph, der aus Zuständen (Stellen) und Zustandübergängen
(Transistionen) besteht. Mit Marken (Tokens) ist der aktuelle Ausführungszustand beschreibbar.
Mit einem Petrinetz kann man grafisch die Synchronisationszusammenhänge darstellen.
\end{answer}

\begin{multilinequestion}[Wie kann man durch ein Petrinetz typische Synchronisationsvorschriften ausdrücken:]
\begin{enumerate}
\item Sequenz
\item Beschränkte Nebenläufigkeit
\item Unabhängigkeit?
\end{enumerate}
\end{multilinequestion}
\begin{answer}
a) Sequenz
b) beschränkte Nebenläufigkeit
c) Unabhängigkeit?
Bei einer Sequenz a, b gibt es die Transistionen a und b, die jeweils eine Ein- und Ausgangsstelle
haben. Die Ausgangsstelle von a ist allerdings die Eingangsstelle von b.
Die beschränkte nebenläufigkeit kann man darstellen, indem man Token verwendet, um die Anzahl
der möglichen Prozesse/Threads anzuzeigen.
Bei Unabhängigkeit können zwei Prozesse beliebig oft und in beliebiger Reihenfolge gestartet
werden und somit unabhängig nebenläufig laufen.
\end{answer}

\question{Was kennzeichnet lebendige bzw. todesgefährdete Petrinetze?}
\begin{answer}
Bei lebendigen Petrinetzen gibt es immer Transistionen, egal welche Ausführungsreihenfolge stattgefunden
hat.
Bei todesgefährdeten Petrinetzen kann es nach einer Transistion zu einem Zustand kommen, von
dem aus keine Transistionen mehr ausgeführt werden kann.
\end{answer}

\question{Was wird durch einen Pfadausdruck beschrieben? Welche Operatoren werden dazu vorgesehen? Was ist ihre Semantik?}
\begin{answer}
Mit einem Pfadausdruck kann man Angaben über mögliche Nebenläufigkeit von Zugriffsoperationen
eines ADTs machen.
Operator : : (Beschränkte) Nebenläufigkeit
Operator + : Alternative ,,Entweder ... oder ...''
Operator ; : Sequenz ,,Erst ..., dann ...''
Operator | : Unabhängikeit von Prozessen
\end{answer}

\question{Welche Vorteile bieten Pfadausdrücke zur Steuerung von Nebenläufigkeit im Vergleich zu Semaphoren bzw. Monitore?}
\begin{answer}
Vorteil ist die korrekte Definition dessen, was erlaubt ist oder was nicht erlaubt ist.
\end{answer}

\question{Was ist der Unterschied zwischen offenen und geschlossenen Pfadausdrücken?}
\begin{answer}
Geschlossenen Pfadausdrücke: alle erlaubten Ausführungsreihenfolgen von Operationen eines synchronisierten
Datentyps (ADT mit expliziter Synchronisationsvorschrift) sind zu spezifizieren. Das
heisst alles davon abweichende ist verboten.
Offene Pfadausdrücke: alle Einschränkungen von Ausführungsreihenfolgen sind im Pfadausdruck
zu spezifizieren. Das heisst alles andere ist erlaubt.
\end{answer}

\question{Welches Problem entsteht bei Nebenläufigkeit, wenn bspw. zwei Threads die Variable i inkrementieren möchten und was verursacht dieses? Wie hei"st dieses Problem genau? Wie kann man dies Semaphoren lösen?}
\begin{answer}
Es handelt sich um das Leser-/Schreiber-Problem. Das Problem führt dazu, dass der zweite Thread u.U. mit dem alten Wert weiterarbeitet. Lesende Zugriffe stören sich nicht gegenseitig und können parallel erfolgen. Jedoch ist nebenläufiges Schreiben problematisch.

Auf Assembler-Ebene ist ersichtlich, dass Inkrementieren mehr als eine Instruktion erfordert. Deswegen ist das Definieren des kritischen Blocks notwendig.

Mit Semaphoren lassen sich beide Threads synchronisieren. Es gibt zwei Möglichkeiten: Gegenseitiger Ausschluss (Mutual Exclusion) und mehrseitige Synchronisation.

Gegenseitiger Ausschluss:

\begin{verbatim}
Sema1(1);

Thread 1:
Sema1.P()
i++
Sema1.V()

Thread 2:
Sema1.V()
i++
Sema1.P()
\end{verbatim}
\end{answer}

\question{Wie würde man das klassische Reader-/Writer-Problem als Pfadausdruck formulieren?}
\begin{answer}
Beim Reader-/Writer-Problem sollen beliebig viele Leser, aber kein Schreiber zugelassen werden,
oder ein Schreiber ohne Leser. Damit werden inkonsistente Ergebnisse verhindert.
Als Pfadausdruck: leser+writer
\end{answer}

\question{Was versteht man unter \textit{synchronem} bzw. \textit{asynchronem Nachrichtenaustausch}? Inwiefern sind diese beiden Kommunikationsformen aufeinander abbildbar?}
\begin{answer}
Bei synchronem Datenaustausch warten Sender und Empfänger aufeinander. Das heist, send()
und recieve() wirken blockierend aufeinander. Der Empfänger muss bereit sein, die Nachricht aufzunehmen.
Bei asynchronem Datenaustausch muss der Empfänger nicht unbedingt empfangsbereit sein, damit
der Sender senden kann. Die Nachricht muss dazu aber in einem Puffer innerhalb des Kommunikationskanals
festgehalten werden. Wenn dieser Puffer zu klein ist, muss der Sender blockiert
werden, da es sonst zu einem Pufferüberlauf (Bufferover
ow) kommt.
Synchrone Kommunikation kann durch asychrone Operationen vorgenommen werden, d.h. der
Sender wartet nach dem senden auf die Bestätigung des Empfängers.
Asynchrone Kommunikation kann durch sychrone Operationen vorgenommen werden. Dazu muss
ein Pufferprozess eingeführt werden.
\end{answer}

\question{Wie kann man die Sychronisationseigenschaften von synchronem bzw. asynchronem Nachrichtenaustausch mit Semaphoren modellieren?}
\begin{answer}
\begin{verbatim}
Sema1(0);
Sema2(0);

Synchron:
A       B
send(); s1.P();
s1.V(); receive();
s2.P(); s2.V();

Asynchron:
A       B
send(); s1.P();
s1.V(); receive();
\end{verbatim}
\end{answer}