\documentclass[12pt,oneside]{article}

\usepackage{amsmath}
\usepackage{booktabs}
%\usepackage[onlytext]{MinionPro}
\usepackage[letterpaper, margin=1in]{geometry}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{fancyvrb}

%% \setlength{\topmargin}{-0.75in}
%% \addtolength{\textheight}{2.00in}
%% \setlength{\parindent}{0in}
\pagestyle{empty}

\begin{document}

\begin{center}
  {\Large Homework 02}\hfill\emph{COSC 273: Parallel and Distributed Computing}, Spring 2023\\
  \hrule
\end{center}

\vspace{0.5em}

\noindent\textbf{Due:} Friday, 03/03/2023 at 11:59 pm

\vspace{0.5em}

\noindent\emph{Instructions:} You may work on this assignment in groups of up to 3 and submit a single solution for your group. All group members are responsible for understanding all submitted solutions.

\vspace{2em}

\noindent\textbf{Exercise 1.} Consider the following modified \texttt{lock()} method for the Peterson lock (cf. Section 2.3.3 in \emph{The Art of Multiprocessor Programming}):

\begin{Verbatim}[numbers=left]
public void lock() {
    int i = ThreadID.get();
    int j = 1 - i;
    victim = i;
    flag[i] = true;
    while (flag[j] && victim == i) {} // wait
}
\end{Verbatim}

The only difference with the original method is that the statements \texttt{victim = i} and \texttt{flag[i] = true} are reversed in the modified version. Does the modified Peterson satisfy mutual exclusion? Why or why not? If so, you should argue that mutual exclusion is satisfied. If not, describe an execution for which mutual exclusion fails.

% \begin{enumerate}[label={(\alph*)}]
% \item 
% \end{enumerate}

\vspace{1em}

\noindent\textbf{Exercise 2.} So far in our discussion of locks, we have assumed that the only atomic operations to shared memory locations are \texttt{read} and \texttt{write}. Most modern computer hardware, however, supports other atomic operations as well. One such operation is the \texttt{getAndIncrement} operation which is implemented in Java for the \texttt{AtomicInteger} class. An \texttt{AtomicInteger} stores an integer, whose value can be accessed by the \texttt{get()} method. The \texttt{getAndIncrement} method (1) returns the current value of an \texttt{AtomicInteger}, and (2) increments the stored value as a single atomic operation. For example, if \texttt{AtomicInteger ai} stores a value \texttt{7}, and two threads (say, thread1 and thread2) concurrently call \texttt{ai.getAndIncrement()}, then exactly one thread will get the value \texttt{7}, and the other will get the value \texttt{8}. After both operations, the stored value will be \texttt{9}.

Using \texttt{AtomicInteger}s that support the \texttt{getAndIncrement} operation, devise a \emph{simple} lock that works for any number of threads. Argue that your lock satifies mutual exclusion and starvation freedom.

\emph{Hint: consider Lamport's original idea of a ticket counter in a bakery.}

\clearpage

\noindent\textbf{Exercise 3.} Consider the following \texttt{Bouncer} object:

\begin{Verbatim}[numbers=left]
class Bouncer {
    public static final int DOWN = 0;
    public static final int RIGHT = 1;
    public static final int STOP = 2;
    private boolean goRight = false;
    private int last = -1;
    int visit () {
        int i = ThreadID.get();
        last = i;
        if (goRight)
             return RIGHT;
        goRight = true;
        if (last == i)
            return STOP;
        else
            return DOWN;
    }
}
\end{Verbatim}

Suppose $n$ threads call the \texttt{visit()} method. Argue that the following hold:

\begin{enumerate}
\item At most one thread gets the value \texttt{STOP}.
\item At most $n - 1$ threads get the value \texttt{DOWN}.
\item At most $n - 1$ threads get the value \texttt{RIGHT}.
\end{enumerate}

\noindent\textbf{Exercise 4.} So far in this course, we have assumed that all threads have IDs that are reasonably small numbers. In Java, however, thread IDs can be arbitrary \texttt{long} values. In this exercise, we will see how to use \texttt{Bouncer} objects as above to create unique IDs that are reasonably small compared to the number of threads.

Consider a 2D triangular array of `Bouncer` objects arranged as follows:

\begin{center}
  \includegraphics[width=0.5\textwidth]{bouncer.png}
\end{center}

Suppose each thread performs the following procedure: All threads start by calling \texttt{visit()} on \texttt{Bouncer 0}. Whenever a thread visits a \texttt{Bouncer}, if the \texttt{Bouncer} returns \texttt{STOP}, the thread adopts the number of the \texttt{Bouncer} as its ID. If \texttt{DOWN} is returned, the thread then visits the \texttt{Bouncer} below; if \texttt{RIGHT} is returned, the thread visits the \texttt{Bouncer} to the right.

\begin{enumerate}[label={(\alph*)}]
\item If there are 2 threads, argue that all threads adopt unique IDs in the range $0$ to $2$.
\item If there are 3 threads, argue that all threads adopt unique IDs in the range $0$ to $5$.
\item More generally, argue that if there are $n$ threads and sufficiently many \texttt{Bouncer} objects, then all threads adopt unique IDs. How many such \texttt{Bouncer}s are sufficient in this case?
\end{enumerate}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
