\documentclass{article}

\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[OT4]{fontenc}
\usepackage{graphicx,color}
\usepackage{listings}
\usepackage{multirow}
\usepackage[a4paper,left=3cm,right=3cm,top=3cm,bottom=3cm,headsep=1.2cm]{geometry}
\selectlanguage{polish}

\title{\textbf{Laboratorium Podstawy Przetwarzania Rozproszonego \\ SPRAWOZDANIE z zadania 8 \\ Maniakalni Bokserzy}}
%\author{Jakub Szwachła \\ 101473 \and  Paweł Lampe \\ 99277}
\author{}
\date{}

\lstset{numbers=left}

\begin{document}

\maketitle

\begin{center}
    \begin{tabular}{| l | l | l |}
    \hline
    \textbf{Nazwisko i Imię} & \textbf{album} & \textbf{Termin zajęć} \\ \hline
    Szwachła Jakub & 101473 & \multirow{2}{*}{środa 11:45 tydzień nieparzysty} \\
    Lampe Paweł & 99277 & \\
    \hline
    \end{tabular}
\end{center}

\section{Algorytm rozwiązania}
\subsection{Definicja problemu}
\emph{Bokserzy rozgoryczeni korupcją panoszącą się w istniejących federacjach boksu zawodowego, założyli własną, w której każda walka odbywa się tak długo, aż obaj zawodnicy padną na matę. Sala turniejowa mieści R ringów. Bokserzy wybierają ring i staczają walkę. Walka wymaga zarezerwowania sędziego. Po zakończeniu walki, bokser jest wynoszony i wraca do cyklu walk dopiero po zakończeniu rekonwalescencji. Walka i rekonwalescencja trwają przez czas o zmiennej długości. Dodatkowo osobni pracownicy co pewien czas zajmują ring, żeby zmyć krew i pozbierać zęby (i w tym czasie nie może się odbywać walka). Ringi (R) i sędziowie (S \textless R) to zasoby. Bokserzy (B \textgreater 2R) oraz pracownicy (P \textless R) to procesy.}

\subsection{Założenia przyjętego modelu komunikacji}
\begin{itemize}
\item asynchroniczny system z wymianą komunikatów
\item topologia połączeń: \emph{każdy z każdym}
\item wymagana pojemność kanału:  \emph{wiadomości w jednym kierunku / nieskończona}
\item inne wymagane własności sieci komunikacyjnej: \emph{kanały typu FIFO, transmisja rozgłoszeniowa}
\end{itemize}

\subsection{Algorytm wzajemnego wykluczania}

\underline{Pętla boksera:}
\begin{itemize}
    \item Rezerwacja ringu
    \item Walka
    \item Zwolnienie ringu (bokser o większym id z pary), jeśli
    przeciwnik jeszcze nie zakończył to czekaj
    \item Rekonwalescencja
\end{itemize}

\underline{Pętla sprzątacza:}
\begin{itemize}
    \item Odpoczynek
    \item Rezerwacja ringu
    \item Sprzątanie
    \item Zwolnienie ringu
\end{itemize}

\underline{Bokser -- Rezerwacja ringu:}
\begin{itemize}
    \item Zwiększ zegar lamporta
    \item Dodaj żądanie do własnej kolejki
    \item Wyślij żądanie do pozostałych procesów \verb|MSG_REQUEST|
    \item Czekaj aż będą spełnione warunki: otrzymano odpowiedź od
    wszystkich procesów, jest dostępny co najmniej jeden ring i jeden
    sędzia, jesteś pierwszy w kolejce a drugi proces w kolejce jest
    bokserem
    \item Sekcja krytyczna:
    \begin{itemize}
        \item Znajdź pierwszy wolny ring i zajmij go (zaznacz w tablicy)
        \item Zmniejsz lokalną liczbę dostępnych sędziów
    \end{itemize}
    \item Powiadom drugiego boksera (przeciwnika) \verb|MSG_OPPONENT|
    \item Usuń swoje żądanie oraz żądanie przeciwnika z lokalnej kolejki
    \item Powiadom wszystkie pozostałe procesy o zajętym ringu i o tym,
    że mogą usunąć żądania dwóch bokserów z kolejki \verb|MSG_NOTIFY|
\end{itemize}

\underline{Sprzątacz -- Rezerwacja ringu:}
\begin{itemize}
    \item Zwiększ zegar lamporta
    \item Dodaj żądanie do własnej kolejki
    \item Wyślij żądanie do pozostałych procesów \verb|MSG_REQUEST|
    \item Czekaj aż będą spełnione warunki: otrzymano odpowiedź od
    wszystkich procesów, jest dostępny co najmniej jeden ring, jesteś
    pierwszy lub drugi w kolejce
    \item Sekcja krytyczna:
    \begin{itemize}
        \item Znajdź pierwszy wolny ring i zajmij go (zaznacz w tablicy)
    \end{itemize}
    \item Usuń swoje żądanie z lokalnej kolejki
    \item Powiadom wszystkie pozostałe procesy o zajętym ringu i o tym,
    że mogą usunąć żądanie sprzątacza z kolejki \verb|MSG_NOTIFY|
\end{itemize}

\underline{Zwolnienie ringu (w przypadku bokserów wykonuje bokser o większym id):}
\begin{itemize}
    \item Zwolnij ring (odznacz w tablicy)
    \item Zwiększ lokalną liczbę dostępnych sędziów
    \item Zwiększ zegar lamporta
    \item Powiadom wszystkie pozostałe procesy o zwolnieniu \verb|MSG_RELEASE|
\end{itemize}

\underline{Odebranie wiadomości:}
\begin{itemize}
    \item Zaktualizuj zegar lamporta
    \item Jeśli odebrano \verb|MSG_REQUEST|: dodaj żądanie do lokalnej
    kolejki i  wyślij odpowiedź (z wartością zegara lamporta) \verb|MSG_REPLY|
    \item Jeśli otrzymano \verb|MSG_REPLY|: zanotuj fakt otrzymania
    odpowiedzi
    \item Jeśli otrzymano \verb|MSG_RELEASE|: zanotuj fakt zwolnienia
    ringu (odznacz w tablicy), jeśli to wiadomość od boksera zwiększ
    lokalną liczbę dostępnych sędziów
    \item Jeśli otrzymano \verb|MSG_OPPONENT|: zanotuj numer ringu oraz
    id przeciwnika, zanotuj fakt zajęcia ringu i sędziego, usuń własne
    żądanie oraz żądanie przeciwnika z kolejki
    \item Jeśli otrzymano \verb|MSG_NOTIFY|: zanotuj fakt zajęcia ringu,
    jeśli to wiadomość od boksera zmniejsz lokalną liczbę dostępnych
    sędziów, usuń odpowiednie żądania z kolejki (jeśli bokser: usuń
    boksera wraz z przeciwnikiem, jeśli sprzątacz: usuń tylko jedno
    żądanie)
    \item Jeśli otrzymano \verb|MSG_DONE|: zanotuj, że przeciwnik
    zakończył walkę
\end{itemize}

Aby zapobiec anomaliom związanym z otrzymywaniem wiadomości
\verb|MSG_NOTIFY| oraz \verb|MSG_RELEASE| w złej kolejności, po
otrzymaniu \verb|MSG_NOTIFY| proces zapamiętuje znacznik czasowy tej
wiadomości i zaznacza zwolnienie ringu po otrzymaniu wiadomości \verb|MSG_RELEASE|
tylko jeśli znacznik czasowy jest większy. Chroni to przed sytuacją
typu:
\begin{itemize}
    \item \verb|MSG_NOTIFY| od procesu 1: zajęcie ringu 2
    \item \verb|MSG_NOTIFY| od procesu 2: zajęcie ringu 2 (proces 2 w
    międzyczasie otrzymał wiadomość o zwolnieniu ringu 2 przez proces 1)
    \item \verb|MSG_RELEASE| od procesu 1: zwolnienie ringu 2
    \item W tym momencie ring 2 powinien być nadal zaznaczony jako
    zajęty
\end{itemize}



\subsection{Analiza złożoności komunikacyjnej algorytmu}

Przed przystąpieniem do szczegółowej analizy, zaznaczyć należy, iż $N$ --
to ilość wszystkich procesów. Złożoności ponadto rozpatrywane są z punktu
widzenia pojedynczego procesu.

\subsubsection{Złożoność komunikacyjna pakietowa (wyrażona w liczbie komunikatów)}

\begin{itemize}
\item \textbf{Bokser--inicjator}
  \begin{itemize}
  \item rozsyłanie żądań: $N - 1$
  \item oczekiwanie na odpowiedzi: $N - 1$
  \item powiadomienie przeciwnika: $1$
  \item powiadomienie pozostałych o zajętym ringu: $N - 2$
  \item powiadomienie o zwolnieniu ringu: $N - 1$
  \item \textbf{Złożoność:} $4(N - 1)$
  \end{itemize}
\item \textbf{Bokser--przeciwnik}
  \begin{itemize}
  \item rozsyłanie żądań: $N - 1$
  \item oczekiwanie na odpowiedzi: $N - 1$
  \item \textbf{Złożoność:} $2(N - 1)$
  \end{itemize}
\item \textbf{Sprzątacz}
  \begin{itemize}
  \item rozsyłanie żądań: $N - 1$
  \item oczekiwanie na odpowiedzi: $N - 1$
  \item rozsyłanie powiadomienia o zajętym ringu: $N - 1$
  \item powiadomienie o zwolnieniu ringu: $N - 1$
  \item \textbf{Złożoność:} $4(N - 1)$
  \end{itemize}
\end{itemize}

\subsubsection{Złożoność czasowa (przy założeniu jednostkowego czasu przesłania pojedynczego komunikatu w kanale)}
\begin{itemize}
\item \textbf{Bokser--inicjator}
  \begin{itemize}
  \item rozsyłanie żądań: $1$
  \item oczekiwanie na odpowiedzi: $1$
  \item powiadomienie przeciwnika: $1$
  \item powiadomienie pozostałych o zajętym ringu: $1$
  \item powiadomienie o zwolnieniu ringu: $1$
  \item \textbf{Złożoność:} $5$
  \end{itemize}
\item \textbf{Bokser--przeciwnik}
  \begin{itemize}
  \item rozsyłanie żądań: $1$
  \item oczekiwanie na odpowiedzi: $1$
  \item \textbf{Złożoność:} $2$
  \end{itemize}
\item \textbf{Sprzątacz}
  \begin{itemize}
  \item rozsyłanie żądań: $1$
  \item oczekiwanie na odpowiedzi: $1$
  \item rozsyłanie powiadomienia o zajętym ringu: $1$
  \item powiadomienie o zwolnieniu ringu: $1$
  \item \textbf{Złożoność:} $4$
  \end{itemize}
\end{itemize}

%% \section{Implementacja rozwiązania}
%% lamport.h
%% \hrule
%% \lstinputlisting[language=C++]{../lamport.h}
%% \hrule
%% lamport.cpp
%% \hrule
%% \lstinputlisting[language=C++]{../lamport.cpp}
%% \hrule
%% boxer.h
%% \hrule
%% \lstinputlisting[language=C++]{../boxer.h}
%% \hrule
%% boxer.cpp
%% \hrule
%% \lstinputlisting[language=C++]{../boxer.cpp}
%% \hrule

\end{document}
