\documentclass{article}

% 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 2013, 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}
\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}...
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-f13-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-f13-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}

Robin, Sam, and Tracy 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 numbers they need are shown in the following table.

\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
Robin   & 7 & 1 & 1 \\ \hline
Sam     & 5 & 2 & 2 \\ \hline
Tracy   & 4 & 6 & 2 \\ \hline
\end{tabular}
}

\subsection{2 pts}  Is the following state safe?  Why or why not?

\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
Robin      & 4 & 0 & 0 \\ \hline
Sam        & 0 & 2 & 2 \\ \hline
Tracy      & 3 & 6 & 0 \\ \hline
Available  & 4   & 1   & 0 \\ \hline
\end{tabular}
}

\subsection{2 pts}  Is the following state safe?  Why or why not?

\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
Robin      & 6 & 0 & 0 \\ \hline
Sam        & 0 & 2 & 2 \\ \hline
Tracy      & 3 & 3 & 0 \\ \hline
Available  & 2 & 3 & 1 \\ \hline
\end{tabular}
}

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

\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Alerting threads}{6}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Consider the ``Sim Ciy disaster daemon'' as depicted in code found
on slides 17--19 of the ``Synchronization~\#3'' lecture.

What if somebody accidentally replaced one (or more) of the
\texttt{cond\_broadcast()} calls with \texttt{cond\_signal()}?
%
Obviously ``some thread could be awakened late.''  But the situation
is more troublesome than that!  It is possible that some thread
might \textit{essentially never} complete its ``wait for triumph''
loop (as coded on slide~17).

\subsection{5 pts}

Use the tabular trace format found in the lecture slides
to show what could go wrong.  If you can, change just one
of the \texttt{cond\_broadcast()} calls to \texttt{cond\_signal()}
(make sure it is clear which one you are breaking) and show
the ``essentially never'' case rather than the ``late'' case.

Please be sure that your trace is clear and conclusive
(otherwise your answer will not receive full credit).
You may use more or fewer lines
or columns
than are provided
in this sample table.
You may change the column headings if you wish.
%Also, you may wish to invent and display specific code
%for the body of the critical section.

{%\Large
\begin{tabular}[b]{|r|c|c|c|c|c|c|c|c|}
\multicolumn{8}{c}{Execution Trace} \\
\hline
time & Thr~0 & Thr~1 & Thr~2 & Thr~3 & Thr~4 & Thr~5 & Thr~6 & Thr~7 \\
\hline
 0 & \hspace{.65in} & \hspace{.65in} & \hspace{.65in} & \hspace{.65in} & \hspace{.65in} & \hspace{.65in} & \hspace{.65in} & \hspace{.65in} \\
\hline
 1 & & & & & & & & \\
\hline
 2 & & & & & & & & \\
\hline
 3 & & & & & & & & \\
\hline
 4 & & & & & & & & \\
\hline
 5 & & & & & & & & \\
\hline
 6 & & & & & & & & \\
\hline
 7 & & & & & & & & \\
\hline
 8 & & & & & & & & \\
\hline
 9 & & & & & & & & \\
\hline
10 & & & & & & & & \\
\hline
\end{tabular}
}

\subsection{1 pt}

The bug described above suggests that perhaps programmers should
\textit{always} use 
\texttt{cond\_broadcast()} instead of \texttt{cond\_signal()}.
Is this true?  Explain.

\end{document}
