\documentclass{article}

%\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, Spring 2012, 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}
\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...
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-s12-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-s12-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
  four processes and
%%%%%%%%%%%%%%%%%%%%%%%% DON'T FORGET TO FIX ME
  seven 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{7}{c}{Resource Declarations} \\
\cline{1-1} \cline{3-3} \cline{5-5} \cline{7-7}
Process A && Process B && Process C && Process D \\
\cline{1-1} \cline{3-3} \cline{5-5} \cline{7-7}
5 tape drives && 5 tape drives && 3 tape drives && 2 tape drives \\
\cline{1-1} \cline{3-3} \cline{5-5} \cline{7-7}
\end{tabular}

\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.

\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      & 5 & 1 & 4 \\ \hline
B      & 5 & 2 & 3 \\ \hline
C      & 3 & 1 & 2 \\ \hline
D      & 2 & 1 & 1 \\ \hline
System & 7 & 2 & - \\ \hline
\end{tabular}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Bakery Algorithm}{6}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In class we discussed the ``Bakery Algorithm'' for n-way mutual
exclusion, but did not consider how to deal with integer overflow.
Below is a version of the algorithm updated to deal with this problem.
Note that ``for some reason'' ticket numbers are fairly small integers
(\texttt{unsigned~short}).

\begin{verbatim}
// convention 0: arrays are global, scalars are local
// convention 1: for each thread, "i" is that thread's array slot
boolean choosing[MAX_THREADS] = { false, ... };
unsigned short number[MAX_THREADS] = { 0, ... } ;
\end{verbatim}

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

\clearpage

\begin{verbatim}
while (1) {

  int slot;

  // BEGIN ENTRY PROTOCOL
  // phase 1: pick a number (when we can)
  do {
    unsigned short max = 0;

    choosing[i] = true;

    for (slot = 0; slot < MAX_THREADS; ++slot) {
      if (number[slot] > max) {
        max = number[slot];
      }
    }

    if (max + 1 > 0) // no overflow
      number[i] = max + 1;

    choosing[i] = false;
  } while (number[i] < 1);

  // phase 2: wait while/until we prove our number is best

  for (slot = 0; slot < MAX_THREADS; ++slot) {
    while (choosing[slot]) {
      continue;
    }
    // note: in this language, tuples can be compared with ">"
    while ((number[slot] != 0) && ((number[i], i) > (number[slot], slot))) {
      continue;
    }
  }
  // END ENTRY PROTOCOL

  // BEGIN CRITICAL SECTION
  ...critical section...
  // END CRITICAL SECTION

  // BEGIN EXIT PROTOCOL
  number[i] = 0;
  // END EXIT PROTOCOL

  // BEGIN REMAINDER SECTION
  ...remainder section...
  // END REMAINDER SECTION
}
\end{verbatim}

Sadly, this version of the Bakery Algorithm fails to satisfy one
(or perhaps more!) of the three critical-section-protocol
requirements.

\clearpage

\subsection{2 pts}
Briefly identify a requirement which is not met and informally
suggest why it is not met.

\subsection{4 pts}
Now your objective is to demonstrate the validity of the
claim you made, using the tabular trace format
found in the lecture slides.

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.

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

\end{document}
