\documentclass{article}

% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname

\usepackage{fancyvrb} % SaveVerbatim for F'22 HW1
\usepackage{tabularx} % mini pages for F'22 HW1

%\setlength{\oddsidemargin}{0.0 in}
%\setlength{\evensidemargin}{0.0 in}
%\setlength{\textwidth}{7.0 in}

\oddsidemargin 0cm
\topmargin -2.5cm
\textwidth 16.5cm
\textheight 24.0cm

\def\titledquestion#1#2{\section{ {#1} ({#2} pts.)}}

% 17.9 Copyright Interests---Joint Authors (17 U.S.C. SS 101, 201(a))
% https://www.ce9.uscourts.gov/jury-instructions/node/265

\begin{document}
\begin{center}       {\large 15-410, Fall~2024, Homework Assignment 1.} \\
%              {\tiny Copyright \copyright~2023, David~A.~Eckhardt, David~O'Hallaron, Carnegie Mellon University \\}
%\Large{Due Wednesday, February 24, 20:59:59 p.m.}
%\Large{Due Monday, October 6, 20:59:59 p.m.}
%\Large{Due Tuesday, October 5, 20:59:59 p.m.}
%\Large{Due Tuesday, February 22, 20:59:59}
%\Large{Due Tuesday, October 11, 20:59:59}
%\Large{Due Tuesday, February 28, 20:59:59}
%\Large{Due Wednesday, October 13, 20:59:59}
%\Large{Due Tuesday, March 1, 20:59:59}
%\Large{Due Wednesday, October 12, 20:59:59}
%\Large{Due Wednesday, March 1, 20:59:59}
%\Large{Due Monday, October 9, 20:59:59}
%\Large{Due Tuesday, February 27, 20:59:59 p.m.}
\Large{Due Tuesday, October 8, 20:59:59}
\end{center}

% \begin{center}
% \fbox{{\Large You need} {\large complete only} Question~3 and one other question.}
% \end{center}

{\small Please} {\LARGE observe} the {\small non-standard} {\LARGE submission} time,
\textbf{which is not midnight}.
As we intend to make solutions available on the web site promptly
thereafter for exam-study purposes, please turn your solutions
in on time.

Homework must be submitted in either PostScript or PDF format (not:
Microsoft Word, Word Perfect, Apple Works, LaTeX, XyWrite, WordStar,
etc.).  Submit your answers by placing them in the appropriate
hand-in directory, e.g.,
{\tt /afs/cs.cmu.edu/academic/class/15410-f24-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-f24-users/\$USER/hw1/\$USER.pdf}.
A plain text file (.text or .txt) is also acceptable, though it must conform to Unix
expectations,
meaning lines of no more than 120 characters separated by newline characters
(note that this is {\em not} the Windows convention or the MacOS convention).
Please avoid creative filenames such as {\tt hw1/my\_15-410\_homework.PdF}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Tape drives}{4}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Consider a system with
%%%%%%%%%%%%%%%%%%%%%%%% DON'T FORGET TO FIX ME
  three processes and
%%%%%%%%%%%%%%%%%%%%%%%% DON'T FORGET TO FIX ME
  three tape drives.
%%%%%%%%%%%%%%%%%%%%%%%% DON'T FORGET TO FIX ME
The maximal needs of each process are declared below:

\begin{tabular}[b]{|l|c|l|c|l|c|l|}
\multicolumn{5}{c}{Resource Declarations} \\
\cline{1-1} \cline{3-3} \cline{5-5}
Process A && Process B && Process C \\
\cline{1-1} \cline{3-3} \cline{5-5}
3 tape drives && 3 tape drives && 3 tape drives \\
\cline{1-1} \cline{3-3} \cline{5-5}
\end{tabular}

\vspace{0.25in}

Imagine the system is in the state depicted
below.
Because a process may request any number of tape drives
until it has acquired its maximum declared quantity,
any given request might be for multiple tape drives,
or for just one.
List one request \textit{for a single tape drive}
which the system should grant right
away,
and one request \textit{for a single tape drive}
which the system should react to by
blocking the process making the request.  Briefly justify
each of your answers.
% Can ask for single process XOR ask for "just one tape drive"...
% If you can, arrange for both of your answers to involve the same process.

\vspace{0.25in}

\begin{tabular}[b]{|l|r|r|r|}
\multicolumn{1}{c}{Who} &
 \multicolumn{1}{c}{Max} &
 \multicolumn{1}{c}{Has} &
 \multicolumn{1}{c}{Room} \\
\hline
A      & 3 & 0 & 3 \\ \hline
B      & 3 & 1 & 2 \\ \hline
C      & 3 & 0 & 3 \\ \hline
System & 3 & 2 & - \\ \hline
\end{tabular}

\vspace{2in}
\begin{center}
{\textbf{(Continued on next page)}}
\end{center}

\clearpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{``Son of Peterson's Solution''}{6}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Consider the following critical-section protocol,
which is a minor variation of Peterson's (1981) classical
solution to the two-process synchronization problem.
This protocol is designed for use by two threads.
It is presented in ``standard form,'' i.e.,
when thread 0 is running this code, $i == 0$ and $j == 1$;
when thread 1 is running this code, $i == 1$ and $j == 0$,
so $i$ means ``me'' and $j$ means ``the other thread.''

\begin{verbatim}
       volatile int turn = -1;        // initially, it's nobody's turn
       volatile int want[2] = {0, };  // per-thread flags (initially all zero)

 1.    void lock(void) {
 2.        want[i] = 1;
 3.        turn = i;
 4.        while (want[j] && turn == j)
 5.            continue;
 6.    }
 7.
 8.    void unlock(void) {
 9.        want[i] = 0;
10.    }
\end{verbatim}

There is a problem with this critical-section protocol.
Identify a required property which this protocol does not have
and then present a trace which supports your claim.
You may use more or fewer
columns or
lines in your trace.
%
If you wish, you may abbreviate
  \texttt{want[]} as~\texttt{w[]}

\vspace{.25in}

{\Large
\begin{tabular}[b]{|r|c|c|}
\multicolumn{3}{c}{Execution Trace} \\
\hline
time & Thread~0 & Thread~1 \\
\hline
 0 & \hspace{1in} & \hspace{1in} \\
\hline
 1 & w[0]=1 & \\
\hline
 2 & & \\
\hline
\end{tabular}
}

\end{document}
