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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{am 8. 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{Semaphoren-Reduktionen}{10 Punkte}

\begin{enumerate}
\item
Betrachten Sie die folgende Implementierung eines
allgemeinen Semaphors mit bin\"aren Semaphoren.

\begin{verbatim}
  binary Semaphores kA <- (1, {}), tor <- (0, {})
  int k <- 0

  =====
  S.P():
  p1: kA.P()
  p2: k <- k - 1
  p3: if k < 0 then
  p4:   kA.V()
  p5:   tor.P()
  p6: else
  p7:   ka.V()
  =====
  S.V():
  v1: kA.P()
  v2: k <- k + 1
  v3: if k <= 0 then
  v4:   tor.V()
  v5: ka.V()
\end{verbatim}
Beweisen Sie, dass diese Implementierung korrekt ist,
oder geben Sie ein Gegenbeispiel.

\item
Beschreiben Sie, wie man Monitore mit Hilfe von Semaphoren 
umsetzen kann. Gehen Sie dabei insbesondere auf die Implementierung 
von Bedingungsvariablen ein. Erkl\"aren Sie, welche Garantien Ihre
Implementierung f\"ur die verschiedenen Wartebereiche des Monitors
liefert.
\end{enumerate}

\AUFGABE{Across the Bridge}{20 Punkte}
\begin{enumerate}
\item Importieren Sie das Framework ``\emph{Across the Bridge}'' in 
einer IDE Ihrer Wahl. Die Frameworks und die dazugeh\"origen 
Anleitungen finden Sie auf der Veranstaltungsseite.
\item Entwickeln Sie zwei \texttt{BridgeControl} Klassen, 
die lediglich jeweils ein Auto gleichzeitig auf die
Br\"ucke lassen. Bedienen Sie sich dazu 
einmal eines Semaphors, einmal der Klasse
\texttt{ReentrantLock} und einmal des Monitorkonzepts in Java.
\item Entwickeln Sie eine \texttt{BridgeControl}-Klasse, die abwechselnd je 
f\"unf Fahrzeuge aus Westen und Osten \"uber die Br\"ucke passieren 
l\"asst. Vermeiden Sie gesch\"aftiges Warten (busy waiting).
\item Entwickeln Sie eine faire \texttt{BridgeControl}-Klasse, die unter 
Verwendung der Standardeinstellung
(FPS darf erh\"oht werden) nach 15.000 Frames die Scores 
$\text{Efficiency} \geq  12.000$ und 
$\text{Fairness} \geq  6.500$ erreicht.
Vermeiden Sie gesch\"aftiges Warten. Begr\"unden Sie, 
dass Ihre L\"osung fair ist.
\item Erweitern Sie Ihre \texttt{BridgeControl}-Klasse aus Aufgabe (d), 
so dass sich keine \emph{Lowrider} auf der Br\"ucke begegnen k\"onnen. 
Mehrere \emph{Lowrider }
aus derselben Richtung sollen die Br\"ucke
zeitgleich passieren k\"onnen. Leichte Einbu\ss{}en bei der 
Fairness-Score sind erlaubt.
\end{enumerate}

(\emph{Diese Aufgabe basiert auf der Bachelorarbeit von Thierry 
  Meurers, betreut von Prof.~Dr.~Margarita Esponda.})
\end{description}
\end{document}
