\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 2006, Homework Assignment 1.} \\
\Large{Due Monday, October 9, 6:59:59 p.m.}
\end{center}

%{\small Please} observe the {\large non-standard} {\Large submission time}...
{\Large Please} {\large observe the} non-standard {\small 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, XyWriter, WordStar,
etc.).  Submit your answers by placing them in the appropriate
hand-in directory, e.g.,
{\tt /afs/cs.cmu.edu/academic/class/15410-f06-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-f06-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{Memory Madness}{10}

Consider a system with 600 megabytes of temporary disk space.

Processes~A and B share an execution pattern:
\begin{verbatim}
void A_or_B(void) {
  temp_allocate(100 * 1024 * 1024); /*1*/
  ...other code...
  temp_allocate(100 * 1024 * 1024); /*2*/
  ...other code...
  exit(code); /* invokes temp_free() as side effect */
}
\end{verbatim}

Process C's execution pattern looks like this:
\begin{verbatim}
void C(void) {
  temp_allocate(100 * 1024 * 1024); /*1*/
  ...other code...
  temp_allocate(100 * 1024 * 1024); /*2*/
  ...other code...
  temp_allocate(100 * 1024 * 1024); /*3*/
  ...other code...
  temp_allocate(100 * 1024 * 1024); /*4*/
  ...other code...
  temp_allocate(100 * 1024 * 1024); /*5*/
  ...other code...
  exit(code); /* invokes temp_free() as side effect */
}
\end{verbatim}

\newpage
\subsection{4 pts}  Illustrate how this system can deadlock.

Use the table below and the execution-trace format presented
in the lecture slides.
You may not need to fill in all lines of the table, and you
may use more lines than we provide if you wish.

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

\subsection{2 pts}  Sketch a process/resource graph showing the deadlock.

\subsection{4 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      & 200 & 100 & 100 \\ \hline
B      & 200 & 200 &   0 \\ \hline
C      & 500 & 300 & 200 \\ \hline
System & 600 &   0 & - \\ \hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Paradise Lost}{5}

Slide 12 of the ``Paradise Lost'' lecture contains a BSD-style
```XXX comment''' indicating that something is wrong with the
code.  Briefly state the problem and provide code which fixes
it.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \newpage
\titledquestion{IRET}{10}

Slide~27 (``IA32 Single-Task Mode Example'') of the ``Hardware''
lecture shows that a ``surprise'' (meaning a system call, hardware
interrupt, or exception) which does not
involve a stack switch pushes, in order,
{\tt \%EFLAGS}, {\tt \%CS}, and {\tt \%EIP}.
Meanwhile, slide~18 of the ``Yield'' lecture explains that
in the case of a stack switch due to a privilege-level change,
a ``surprise'' pushes, in order,
{\tt \%SS}, {\tt \%ESP}, {\tt \%EFLAGS}, {\tt \%CS}, and {\tt \%EIP}.
Consider for the purposes of this question a ``surprise''
which does not push an error code.
One instruction, {\tt IRET}, is used to return to the previous
execution stream, whether or not a stack switch was required
to handle the surprise.  Briefly explain how IRET determines whether
it needs to pop three or five register values from the stack.

We understand this question requires command of a level and
quantity of detailed x86 hardware knowledge which we would not
require in an exam setting.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
