\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 % 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 % 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, Spring~2026, 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} \Large{Due Monday, February 23, 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-s26-users/\$USER/hw1/\$USER.ps} or {\tt /afs/cs.cmu.edu/academic/class/15410-s26-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{Thingies}{10} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In lecture, Professor Pillai presented an example (drawn originally from ``the Dinosaur Book''), of a system with three processes with various peak needs for thingies: \vspace{\baselineskip} \begin{tabular}[b]{|c|r|} \multicolumn{1}{c}{Who} & \multicolumn{1}{c}{Max} \\ \hline P0 & 10 \\ \hline P1 & 4 \\ \hline P2 & 9 \\ \hline System & 12 \\ \hline \end{tabular} \vspace{\baselineskip} As you may recall, Professor Pillai presented evidence that this state is 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 P0 & 10 & 5 & 5 \\ \hline P1 & 4 & 2 & 2 \\ \hline P2 & 9 & 2 & 7 \\ \hline System & 12 & 3 & - \\ \hline \end{tabular} \vspace{\baselineskip} ...and also that this state, in which P2 has requested one more thingy and been granted it, 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 P0 & 10 & 5 & 5 \\ \hline P1 & 4 & 2 & 2 \\ \hline P2 & 9 & 3 & 6 \\ \hline System & 12 & 2 & - \\ \hline \end{tabular} \vspace{\baselineskip} Thus a deadlock-avoidance allocator would block P2 in its request for 1 thingy instead of granting the request, on the grounds that other processes should release thingies before it is safe for P2's request to be granted. \subsection{4 pts} Imagine that, while P2 is blocked, P1 releases the 2~thingies it is holding, resulting in this state: \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 P0 & 10 & 5 & 5 \\ \hline P1 & 4 & 0 & 4 \\ \hline P2 & 9 & 2 & 7 \\ \hline System & 12 & 5 & - \\ \hline \end{tabular} \vspace{\baselineskip} Would granting P2 its pending request for 1~thingy put the system into a safe state or an unsafe state? Explain. \subsection{4 pts} Consider again the orginal state, again with P2 being blocked because it has made a request for 1~thingy. Would it be safe to grant P2's request if P0, rather than P1, were to release 2~thingies? Explain. \subsection{2 pts} With respect to P2's request for 1~thingy, why does it matter whether it is P0 or P1 releasing 2~thingies? %% ### !!! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% ### !!! \clearpage %% ### !!! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \titledquestion{Not-Peterson's Not-Solution}{6} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Consider the following critical-section protocol, which is a minor variation of Peterson's (1981) classical solution to the two-process synchronization problem. This protocol is designed for use by two threads. It is presented in ``standard form,'' i.e., when thread 0 is running this code, $i == 0$ and $j == 1$; when thread 1 is running this code, $i == 1$ and $j == 0$, so $i$ means ``me'' and $j$ means ``the other thread.'' \vspace{\baselineskip} \begin{verbatim} volatile int turn = -1; // initially, it's nobody's turn volatile int want[2] = {0, }; // per-thread flags (initially all zero) 1. void lock(void) { 2. turn = j; 3. want[i] = 1; 4. while (want[j] && turn == j) { 5. continue; 6. } 7. } 8. 9. void unlock(void) { 10. want[i] = 0; 11. } \end{verbatim} \vspace{\baselineskip} There is a problem with this critical-section protocol. Identify a required property which this protocol does not have and then present a trace which supports your claim. Your trace may use more or fewer rows or columns than the format example below. % If you wish, you may abbreviate \texttt{want[]} as~\texttt{w[]}. \vspace{\baselineskip} {\Large \begin{tabular}[b]{|r|c|c|} \multicolumn{3}{c}{Execution Trace} \\ \hline time & Thread~0 & Thread~1 \\ \hline 0 & & \hspace{1in} \\ \hline 1 & \hspace{1in} & \\ \hline 2 & ... & ... \\ \hline \end{tabular} } \vspace{\baselineskip} \end{document}