\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

\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, Spring~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.}
\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-s24-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-s24-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.
The maximal needs of each process are declared below:

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

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

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

\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} Show a safe state in which three tape drives
are allocated.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 \textit{increase}
the amount of money in account \texttt{A}.
For fun, see if you can get \texttt{transfer(A,~A,~500)}
to \textit{double} the amount of money in the account.

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

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