\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, Fall 2008, Homework Assignment 1.} \\
%\Large{Due Wednesday, February 27, 20:59:59 p.m.}
\Large{Due Monday, October 6, 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} 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-f08-users/\$USER/hw1/\$USER.ps} or
{\tt /afs/cs.cmu.edu/academic/class/15410-f08-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{Nuts \& Bolts}{10}

Uh-oh...somebody's skeleton game kernel just got into trouble.

\begin{verbatim}
simics> c
Hello from a brand new kernel!
[cpu0] (@ cycle 15054660) Exception 13: General_Protection_Exception
Psuedo-exception 1035 caught!
[cpu0] cs:0x001021a8 p:0x001021a8  cmp byte ptr [eax],0x0
_doprnt (fmt=0x1041cf "foo says %d\n", args=0x106aac "", radix=0, putc=0x101f90,
    putc_arg=0x106958 "\230i\020") at /foo/p1/410kern/stdio/doprnt.c:208
208             while (*fmt != '\0') {
simics> bt
#0 0x1021a8 in _doprnt (fmt=0x1041cf "foo says %d\n", args=0x106aac "", radix=0, putc=0x101f90,
    putc_arg=0x106958 "\230i\020") at /foo/p1/410kern/stdio/doprnt.c:208
#1 0x10205c in vsnprintf (s=0x106998 "Hello from a brand new kernel!", size=255,
    fmt=0x1041cf "foo says %d\n", args=0x106aac "")
    at /foo/p1/410kern/stdio/sprintf.c:73
#2 0x101f7d in SIM_printf (fmt=0x1041cf "foo says %d\n")
    at /foo/p1/410kern/simics/simics_c.c:11
#3 0x100b9c in kernel_main (mbinfo=0x2a020, argc=1, argv=0x106ba4, envp=0x67eac)
    at /foo/p1/kern/game.c:64
#4 0x100ac2 in mb_entry (info=0x2a020, istack=0x106b00) at /foo/p1/410kern/entry.c:32
#5 0x100a0f in _start () in kernel
#6 0xfe30 in ?? ()
simics>
\end{verbatim}

Here's the code:
\begin{verbatim}
int kernel_main(mbinfo_t *mbinfo, int argc, char **argv, char **envp)
{

    lmm_remove_free( &malloc_lmm, (void*)USER_MEM_START, -8 - USER_MEM_START );
    lmm_remove_free( &malloc_lmm, (void*)0, 0x100000 );

    handler_install(tick);
    interrupt_setup();

    lprintf( "Hello from a brand new kernel!" );

    extern int foo(void);
    lprintf("foo says %d\n", foo());

    while (1) {
        continue;
    }

    return -1;
}

\end{verbatim}

Here is a register dump (excerpted from ``pregs -all'', in the same
oddball order which Simics uses).

{\tt
\begin{tabular}[b]{|l|r|}
\hline
Register & Value \\ \hline
EAX & 0x001041cf \\ \hline
ECX & 0x00106b3c \\ \hline
EDX & 0x001069b5 \\ \hline
EBX & 0x0002a020 \\ \hline
ESP & 0x001067e8 \\ \hline
EBP & 0x00106930 \\ \hline
ESI & 0x0002a204 \\ \hline
EDI & 0x0002a205 \\ \hline
EIP & 0x001021a8 \\ \hline
EFLAGS & 0x00200006 \\ \hline
ES & 0x0018 \\ \hline
CS & 0x0010 \\ \hline
SS & 0x0010 \\ \hline
DS & 0x0000 \\ \hline
FS & 0x0018 \\ \hline
GS & 0x0018 \\ \hline
\end{tabular}
}

What went wrong?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Dining Philosophers}{10}

Consider the following modification of the standard
dining-philosophers scenario.
Some philosophers are ``right-handed'' and run the
following code:

\begin{verbatim}
while (1) {
  acquire_chopstick(right); /* "may" block */
  acquire_chopstick(left);  /* "may" block */

  eat();

  release_chopstick(right);
  release_chopstick(left);

  think();
}
\end{verbatim}

However, other philosophers are ``left-handed'' and
run this code instead:

\begin{verbatim}
while (1) {
  acquire_chopstick(left);  /* "may" block */
  acquire_chopstick(right); /* "may" block */

  eat();

  release_chopstick(left);
  release_chopstick(right);

  think();
}
\end{verbatim}

Explain why, at any table with a mixture of left-handed and
right-handed philosophers, deadlock cannot occur.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Zero Terror in the Bakery}{20}

Consider the Bakery Algorithm as presented in class.
As you know from 15-213, ``an \texttt{int} is not an
integer.''  One unfortunate feature of real-world
\texttt{int}s is that they overflow.
In order to stave this off as long as possible,
assume that the code presented in class has been
adjusted so that the \texttt{number[]} array
is declared as \texttt{unsigned~int}.

Using the tabular format presented in class,
show how overflow wreaks havoc with the
Bakery Algorithm.  You may use more or fewer
lines or columns.

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

\end{document}
