\documentclass{article}

\usepackage{yfonts}

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

%\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.)}}

\begin{document}
\begin{center}{\large 15-410, Fall 2017, Homework Assignment 1.} \\
%\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 Tuesday, October 9, 20:59:59}
%\Large{Due Tuesday, February 26, 20:59:59}
%\Large{Due Tuesday, October 8, 20:59:59}
%\Large{Due Sunday, February 23, 20:59:59}
%\Large{Due Tuesday, October 7, 20:59:59 p.m.}
%\Large{Due Wednesday, February 25, 20:59:59 p.m.}
%\Large{Due Monday, October 12, 20:59:59 p.m.}
%\Large{Due Tuesday, February 23, 20:59:59 p.m.}
%\Large{Due Monday, October 17, 20:59:59 p.m.}
%\Large{Due Tuesday, February 28, 20:59:59 p.m.}
\Large{Due Wednesday, October 11, 20:59:59 p.m.}
\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} {\small time}...
% Sorry, purists!
\textfrak{{\small Pleas:e} {\LARGE obs:erve} the {\small non-s:tandard} {\LARGE s:ubmis:s:ion} {\small time}...}
As we intend to make solutions available on the web site immediately
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-f17-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-f17-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{Chefs}{4}

Jamie, Kelly, and Morgan
are chefs in a single kitchen. They cook with 
knives, bowls, and woks.
%_% Each has special dishes and cooking methods, and hence each
%_% needs different numbers of these items in the worst case.
The maximum number of each item needed by each chef is shown in the following table.

\vspace{\baselineskip}
\centerline{
\begin{tabular}[h]{|l|r|r|r|}
\multicolumn{1}{c}{Chef} &
 \multicolumn{1}{c}{Knives} &
 \multicolumn{1}{c}{Bowls} &
 \multicolumn{1}{c}{Woks} \\ \hline
Jamie   & 1 & 2 & 3 \\ \hline
Kelly   & 3 & 2 & 1 \\ \hline
Morgan  & 2 & 2 & 2 \\ \hline
\end{tabular}
}
\vspace{\baselineskip}

Imagine that the kitchen contains 4 knives, 4 bowls, and 4 woks.

\vspace{0.25in}

Imagine the system is in the state depicted
below.  List one request which the system should grant right
away, and one request which the system should react to by
blocking the process making the request.  Briefly justify
each of your answers.  If you can, arrange for both of your
answers to involve the same
%  process.
  resource request, but made by two different processes.

\vspace{0.25in}

\vspace{\baselineskip}
\centerline{
\begin{tabular}[h]{|l|r|r|r|}
\multicolumn{1}{c}{Chef} &
 \multicolumn{1}{c}{Knives} &
 \multicolumn{1}{c}{Bowls} &
 \multicolumn{1}{c}{Woks} \\ \hline
Jamie      & 1 & 2 & 1 \\ \hline
Kelly      & 1 & 0 & 1 \\ \hline
Morgan     & 1 & 2 & 1 \\ \hline
Available  & 1 & 0 & 1 \\ \hline
\end{tabular}
}
\vspace{\baselineskip}

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{``Nemo's Algorithm''}{5}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Consider the following critical-section protocol.
This protocol is designed for use by multiple threads.
In
each thread,~\texttt{i}~is the thread number, ranging from
zero through~\texttt{N}, the number of threads in the system.
For the purposes of this question we can assume
that~\texttt{N} is a compile-time constant.

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

 1.    int n_entering(void) {
 2.        int n_entering = 0;
 3.        for (int t = 0; t < N; t++)
 4.            n_entering += entering[t];
 5.        assert(n_entering > 0);
 6.        return (n_entering);
 7.    }
 8.
 9.    void lock(void) {
10.        do {
11.            do {
12.                entering[i] = 0;
13.                if (turn == -1)
14.                    turn = i;
15.            } while (turn != i);
16.            entering[i] = 1;
17.        } while (n_entering() != 1);
18.    }
19.
20.    void unlock(void) {
21.        turn = -1;
22.        entering[i] = 0;
23.    }
\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.
%_%_%_
%_%_%_ (This protocol is presented in ``standard form,'' i.e.,
%_%_%_ if thread~1 is running this code, $i == 1$ and $j == 0$.)
%_%_%_
%
If you wish, you may abbreviate
  \texttt{entering[]} as~\texttt{e[]}
and
  \texttt{n\_entering()} as~\texttt{n\_e()}.

\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 & & \\
\hline
 2 & & \\
\hline
\end{tabular}
}

\end{document}
