\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 2007, Homework Assignment 1.} \\
\Large{Due Wednesday, February 28, 6:59:59 p.m.}
\end{center}

\begin{center}
{\Large You need} {\large only complete} 14 of the 24 points.
\end{center}

Note: in an exam setting we would not ask you to write as much assembly
code as the first problem.

%{\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-s07-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-s07-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{Stack Madness}{10}

Doubtless one consequence of working on a thread library is some
frustration with how disturbingly \textit{linear} C's stacks are.
Let's explore what a different approach might look like.

Stack frames will be allocated as follows.  A global array of \verb|void *|
named \texttt{frametops} will be initialized by the C startup code
so that each pointer points to the top four-byte word of a 4-kilobyte
page.  A global integer named \texttt{framenum}, which will count
downward, will indicate which frame is currently in use.
So the \texttt{\%esp} values for the current function's stack
will range from \verb|frametops[framenum]| down to
\verb|frametops[framenum]-4092|.  You can assume that
\verb|frametops[0]| contains an ``illegal pointer'' which will
generate a page fault---so this stack will eventually refuse to grow
downward, as a regular linear stack also does.

The C declarations for the data structures are as follows.
\begin{verbatim}
void *frametops[N_FRAMES];
int framenum = N_FRAME - 1;
\end{verbatim}

\subsection{7pts} Present the handful of ``function entry''
assembly-language instructions necessary to store the
calling function's \texttt{\%esp} in the top word of the
callee's new stack page and the caller's \texttt{\%ebp}
in the next word down.  Recall that some registers are
caller-save and others are callee-save, and don't forget
to maintain any necessary invariants.  We realize that
this setup makes it clumsy to access function parameters
(yuck---whose idea was this, anyway?).

\subsection{2pts} Present the ``function return'' instructions
necessary to sanely return to the caller.

\subsection{1pt} Indicate an important limitation this
approach imposes on function behavior.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Get to work!}{10}

Consider a real-time system which must respond very quickly to
incoming requests from the outside world, though it is acceptable
if there is some start-up delay when the system is powered on
or at other application-dependent idle times.

We wish to use the
``thread group'' or ``worker thread'' abstraction of the Project~2
``thrgrp'' library, but wish to add an additional call,
\texttt{thrgrp\_prepare(int n)},
which should ensure that the next \texttt{n} invocations of
\texttt{thrgrp\_create()} should start running the first
instruction of the indicated \texttt{func} ``as soon as possible
without writing distastefully low-level code.''

\subsection{9pts}
Indicate which data structures you would add to the existing
\texttt{thrgrp\_group\_t}.
Sketch out what your \texttt{thrgrp\_prepare()} would do and
how you would modify the \texttt{thrgrp\_create()} we
provided you with.  You may be brief.

\subsection{1pts} If you can think of a desirable modification to
\texttt{thrgrp\_bottom()} or \texttt{thrgrp\_join()}, explain.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Plumbers}{4}

Consider a plumbing company staffed by
Alice, Bob, and Cameron.
Each worker has an individual ``one size fits all'' policy for choosing tools,
regardless of the job to be accomplished.
Each worker's maximum tool usage is as follows.

\begin{tabular}[h]{|l|r|r|}
\multicolumn{1}{c}{Worker} &
 \multicolumn{1}{c}{Wrenches} &
 \multicolumn{1}{c}{Hammers} \\ \hline
Alice   & 2 & 1 \\ \hline
Bob     & 2 & 2 \\ \hline
Cameron & 1 & 2 \\ \hline
\end{tabular}

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

\begin{tabular}[b]{|l|r|r|}
\multicolumn{1}{c}{Who} &
 \multicolumn{1}{c}{Wrenches} &
 \multicolumn{1}{c}{Hammers} \\
\hline
Alice      & 1 & 0 \\ \hline
Bob        & 1 & 1 \\ \hline
Cameron    & 0 & 1 \\ \hline
Available  & 1 & 0 \\ \hline
\end{tabular}

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

\begin{tabular}[b]{|l|r|r|}
\multicolumn{1}{c}{Who} &
 \multicolumn{1}{c}{Wrenches} &
 \multicolumn{1}{c}{Hammers} \\
\hline
Alice      & 2 & 1 \\ \hline
Bob        & 2 & 2 \\ \hline
Cameron    & 0 & 0 \\ \hline
Available  & 0 & 0 \\ \hline
\end{tabular}

\end{document}
