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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 11. Mai 2018 bis 10 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{Zustandsdiagramme}{10 Punkte}

\begin{enumerate}
\item
Zeichnen Sie das vollst\"andige Zustandsdiagramm f\"ur den 
ersten Versuch aus der Vorlesung zur L\"osung des Problems des 
kritischen Abschnittes (inklusive der Zust\"ande, in denen mindestens 
einer der Prozesse h\"angen geblieben ist). 
\item
Argumentieren Sie im Detail anhand des Zustandsdiagramms, dass der 
Zustand \texttt{(a2, b2, b)} nicht zu einer Verklemmung f\"uhren 
kann (unter Annahme der schwachen Fairness).
\end{enumerate}
\emph{Zur Erinnerung}: 
Der Pseudocode f\"ur den ersten Versuch lautete folgenderma\ss{}en
(beide Prozesse befinden sich in einer Endlosschleife):
\begin{verbatim}
===================================================
                    global dran = a
a1: U                     | b1: U
a2: while dran != a do    | b2: while dran != b do
a3:     NOP               | b3:     NOP
a4: K                     | b4: K
a5: dran <- b             | b5: dran <- a
\end{verbatim}

\AUFGABE{Der Algorithmus von Peterson}{10 Punkte}

Der Algorithmus von Peterson ist eine vereinfachte Variante 
des Algorithmus von Dekker. Er lautet folgenderma\ss{}en
(beide Prozesse befinden sich in einer Endlosschleife):
\begin{verbatim}
======================================================
  global adrin = false, bdrin = false, letzter = a
a1: U                     | b1: U
a2: adrin  <- true        | b2: bdrin  <- true
a3: letzter <- a          | b3: letzter <- b
a4: while bdrin &&        | b4: while adrin && 
          letzter = a do  |           letzter = b do
a5:     NOP               | b5:     NOP
a6: K                     | b6: K
a7: adrin <- false        | b7: bdrin <- false
\end{verbatim}

\begin{enumerate}
    \item Beschreiben Sie die Idee des Algorithmus mit einfachen 
      Worten. Was ist der Unterschied zu Dekkers Algorithmus?
      Was sind die Gemeinsamkeiten?
    \item Beweisen Sie mit Hilfe eines Zustandsdiagramms, dass 
      Petersens Algorithmus den wechselseitigen Ausschluss 
      garantiert. Dabei k\"onnen Sie das Zustandsdiagramm 
      sinnvoll vereinfachen, indem Sie Anweisungen weglassen, 
      die den Zustand nicht wesentlich beeinflussen.
\end{enumerate}

\AUFGABE{CMPXCHG}{10 Punkte}

Die \texttt{CMPXCHG}-Anweisung funktioniert folgenderma\ss{}en:
\begin{verbatim}
CMPXCHG(common, old, new):
    int temp
    temp <- common
    if common = old then
        common <- new
    return temp
\end{verbatim}
Beschreiben Sie einen m\"oglichst einfachen Algorithmus 
zur Implementierung eines kritischen Abschnitts, falls eine
atomare \texttt{CMPXCHG}-Anweisung zur Verf\"ugung steht, 
und beweisen Sie seine Korrektheit.

\end{description}
\end{document}
