\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{am 1. Juni 2018 bis 12 Uhr in die
Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Nichtsequentielle und Verteilte Programmierung}\hfill SoSe 
2018 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katinka Wolter

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Semaphore}{10 Punkte}

\begin{enumerate}
\item Betrachten Sie das folgende Programm:
\begin{verbatim}
==========================================
global Semaphore S = (1, {}), T = (0, {})

a1: S.P()       | b1: T.P()
a2: write("p")  | b2: write("q")
a3: T.V()       | b3: S.V()
\end{verbatim}
Was sind die m\"oglichen Ausgaben? Was passiert, wenn wir
die Anweisung \texttt{a1} entfernen? Was passiert, wenn wir die Anweisung
\texttt{b1} entfernen? Begr\"unden Sie Ihre Antworten.
\item
Der folgende Algorithmus soll mit Hilfe von \emph{bin\"aren} Semaphoren 
$n$ Threads synchronisieren,
so dass sich h\"ochstens $k$ Threads gleichzeitig im kritischen 
Abschnitt befinden. Alle $n$ Threads f\"uhren den folgenden Quelltext aus:
\begin{verbatim}
================================================
global binary Semaphore S = (1, {}), D = (0, {})
       int count = k

local int temp
a1:  U
a2:  S.P()
a3:  count <- count - 1
a4:  temp  <- count
a5:  S.V() 
a6:  if temp <= -1 then
a7:    D.P()
a8:  K
a9:  S.P()
a10: count <- count + 1
a11: if count <= 0 then
a12:   D.V()
a13: S.V()
\end{verbatim}

Finden Sie f\"ur $n = 4$ und $k = 2$ ein Szenario, bei dem 
$\texttt{D.k} = 2$ wird, obwohl doch \texttt{S} und \texttt{D} 
bin\"are Semaphore sein sollten.

\end{enumerate}

\AUFGABE{Erzeuger-Verbraucher mit einem Ringpuffer}{10 Punkte}

Betrachten Sie die folgende L\"osung des
Erzeuger-Verbraucher Problems mit einem Ringpuffer:
\begin{verbatim}
===========================================================
global buffer[N]; int head = 0, tail = 0; 
       Semaphore notEmpty = (0, {}), notFull = (N, {})

p1: d <- produce             | c1: notEmpty.P()
p2: notFull.P()              | c2: d <- buffer[tail]
p3: buffer[head] <- d        | c3: tail <- (tail + 1) mod N  
p4: head <- (head + 1) mod N | c4: notFull.V()
p5: notEmpty.V()             | c5: consume(d) 
\end{verbatim}
Die Elemente von \texttt{buffer} werden von $0$ bis $N-1$ indiziert.
Es gibt nur einen Erzeuger und nur einen Verbraucher.
\begin{enumerate}
  \item Verdeutliche Sie die Arbeitsweise des Algorithmus
    anhand eines einfachen Beispiels. Was ist die Rolle der
    Variablen \texttt{head} und \texttt{tail}?
  \item Beweisen Sie, dass der Algorithmus korrekt ist.
  \item Implementieren Sie den Algorithmus in Java und f\"uhren Sie
    geeignete Testl\"aufe durch.
\end{enumerate}

\AUFGABE{Speisende Philosophen}{10 Punkte}

Beim Problem der speisenden Philosophinnen und Philosophen 
sitzen drei Philosophinnen und zwei Philosophen an
einem runden Tisch. Der Tisch enth\"alt f\"unf Gabeln, jeweils eine
Gabel zwischen zwei Philosophierenden. In der Mitte des 
Tisches befindet sich ein gro\ss{}er Topf mit Essen.

Die meiste Zeit denken die Philosophierenden nach. Ab und zu wird 
jemand hungrig. Um etwas zu essen, muss die Person 
zu\"achst die beiden Gabeln
an ihrem Platz aufnehmen. Hat die Person genug gegessen, so legt
sie beide Gabeln wieder ab. Das Aufheben und Ablegen der Gabel wird
durch ein schwaches bin\"ares Semaphor implementiert.

\begin{enumerate}
  \item Betrachten Sie die einfache L\"osung, bei der alle Essenden
    erst die linke Gabel und dann die rechte Gabel aufheben.
    Beschreiben Sie eine Situation, die zu einer Verklemmung f\"uhrt.
  \item Nehmen Sie an, dass jeder Philosophierende seinen Namen kennt. 
    Beschreiben
    Sie eine Strategie, welche Verklemmungen vermeidet und  trotzdem
    sicherstellt, dass niemand hungern muss.

    Begr\"unden Sie, warum Ihre L\"osung den individuellen Fortschritt
    sicherstellt.
  \item
    Implementieren Sie Ihre L\"osung mit Hilfe von Java Semaphoren.
\end{enumerate}

\newpage
\AUFGABE{Kritische Abschnitte mit Semaphoren}{freiwillig, 5 Zusatzpunkte}

Betrachten Sie den Quelltext zur Implementierung eines kritischen
Abschnitts mit schwachen Semaphoren:
\begin{verbatim}
=============================
global Semaphore S = (1, {})

a1: U         | b1: U
a2: S.P()     | b2: S.P()
a3: K         | b3: K
a4: S.V()     | b4: S.V()
\end{verbatim}

In der Vorlesung haben Sie die Semaphor-Invariante 
kennen gelernt. F\"ur jede m\"ogliche Zustandsfolge gilt:
\[
 \Box (\texttt{S.k} \geq 0) \wedge \Box \big(\texttt{S.k} =
   k_0 + \# V(S) - \# P(S)\big),
\]
wobei $k_0$ den urspr\"unglichen Wert von \texttt{S.k} 
und  $\# V(S)$ und $\# P(S)$ die Anzahl der erfolgreichen
\texttt{S.V()} und \texttt{S.P()} Operationen bezeichnet.

Beweisen Sie mit Hilfe der Semaphor-Invariante, dass der individuelle
Fortschritt gesichert ist.

\emph{Hinweis}: Aus der Semaphor-Invariante folgt, dass
$\Box (\# K = 1 - \texttt{S.k})$ gilt, wobei $\#K$ die Anzahl der
\emph{aktiven} Prozesse im kritischen Abschnitt bezeichnet.
Nehmen Sie an, dass Prozess \texttt{a} blockiert. Was k\"onnen Sie
dann \"uber $\#K$ folgern?
\end{description}
\end{document}
