\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 2022, 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 Wednesday, October 13, 20:59:59}
\Large{Due Tuesday, March 1, 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-s22-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-s22-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}{10}

Consider a system with three processes and three tape drives.
%
In \textit{typical} operation, each process needs just one
tape drive.
However, every now and then in a special circumstance
each of the processes might need a second tape drive
briefly.
In accordance with the deadlock avoidance approach,
the \textit{maximal} needs of each process are declared below:

\vspace{\baselineskip}
\begin{tabular}[b]{|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}
2 tape drives && 2 tape drives && 2 tape drives \\
\cline{1-1} \cline{3-3} \cline{5-5}
\end{tabular}

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

\vspace{\baselineskip}
\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      & 2 & 1 & 1 \\ \hline
B      & 2 & 2 & 0 \\ \hline
C      & 2 & 0 & 2 \\ \hline
System & 3 & 0 & - \\ \hline
\end{tabular}

\subsection{3 pts}  Explain why the following state is not safe.

\vspace{\baselineskip}
\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      & 2 & 1 & 1 \\ \hline
B      & 2 & 1 & 1 \\ \hline
C      & 2 & 1 & 1 \\ \hline
System & 3 & 0 & - \\ \hline
\end{tabular}

\subsection{4 pts} One day your boss says that a government
business efficiency investigator instrumented this system and
the system was never observed using more than
  two
tape drives, with
  at least one
idle at all times.
The efficiency investigator suggests transferring
  one
of the
  three
tape drives to a different business unit, leaving
  two.
Would this system work with only
  two
tape drives?
If so, how well would it work?

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Transfer trouble}{10}

Consider the following code for trasferring money from one
bank account to another.

\begin{verbatim}
int transfer(account from, account to, int amount)
{
  int available;

  /* check */
  available = from->value;
  if (available < amount)
    return (-1);

  /* commit */
  available -= amount;
  from->value = available;
  to->value += amount;
  return (0);
}
\end{verbatim}

In a mathematical sense, it should be ok to ``transfer'' money
from an account to itself, e.g., \texttt{transfer(A,~A,~500)}.

Using the tabular format presented in class,
show how concurrent invocations of the ``mathematically safe''
operation \texttt{transfer(A,~A,~500)} can double the
amount of money in account \texttt{A}.

You may use more or fewer lines or columns than are provided
in this sample table.

\vspace{\baselineskip}
{\Large
\begin{tabular}[b]{|r|c|c|c|}
\multicolumn{4}{c}{Execution Trace} \\
\hline
time & Thread~A & Thread~B & Thread~C \\
\hline
 0 & \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}
