\documentclass{article}

% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission pathname
% Edit: Semester name; due date; submission 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, Fall~2025, 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.}
%\Large{Due Tuesday, October 8, 20:59:59}
%\Large{Due Monday, February 24, 20:59:59}
\Large{Due Monday, October 6, 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-f25-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-f25-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).
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{Choice Problem}{6}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In class we discussed Lamport's 1974 Bakery Algorithm,
which provides mutual exclusion, progress, and bounded waiting.
We also discussed ways in which ``modern memory'' (technically,
a memory consistency model other than ``sequential consistency'')
might break the ``choosing'' synchronization in the Bakery Algorithm.

Consider a variant of the Bakery Algorithm that doesn't have
the ``chosing'' synchronization.
Recall that
we are using thread identifiers as tie-breakers when
comparing ticket numbers.
Also, \texttt{j} and \texttt{max} are local to each thread;
\texttt{i} is local to each thread and is the thread's identifier.
The \texttt{number[]} array is shared across threads, and
\texttt{n} is the number of threads, which is shared across the threads.

\begin{verbatim}
01    max = 0;
02    for (j = 0; j < n; j++)
03        if (max < number[j]) 
04            max = number[j];
05    number[i] = max + 1;
06    
07    for (j = 0; j < n; ++j) {
08        while ((number[j] != 0) &&
09              ((number[i], i) > (number[j], j)))
10            continue;
11    }
12    ...critical section...
13    number[i] = 0;
\end{verbatim}

Unfortunately, that code does not ensure mutual exclusion.
Present a tabular execution trace demonstrating a mutual-exclusion
failure.
Your trace may use more or fewer rows or columns than the
format example below.

\vspace{.25in}

{\Large
\begin{tabular}[b]{|r|c|c|}
\multicolumn{3}{c}{Execution Trace} \\
\hline
time & Thread~0 & Thread~1 \\
\hline
 0 & max=0        & \hspace{1in} \\
\hline
 1 & \hspace{1in} & max=0 \\
\hline
 2 & ... & ... \\
\hline
\end{tabular}
}

\end{document}
