\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 2005, Homework Assignment 1.} \\
\Large{Due Sunday, February 27, 8pm}
\end{center}

Please observe the non-standard 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-s05-users/\$USER/hw1/\$USER.ps}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \newpage
\titledquestion{CLOCKNAFORK}{10}

In an attempt to improve the reference kernel for the Fall 2005
students, Professor Maggs decides to provide support for the new
CLOCKNAFORK brand hardware clock, soon to be integrated into all
modern processors.  The CLOCKNAFORK is a 32-bit clock incremented
precisely every millisecond, with increments synchronized via
radiowave to the U.S., European, and Asian atomic clocks.  The 32-bit
value, however, does not denote any particular absolute time, and
values may differ from processor to processor (and be set or
initialized by software).  When the clock holds the value $2^{32}-1$,
the next increment resets the value to 0.  The clock is read in two
steps, by reading two 16-bit words from the {\tt CLOCKNAFORK\_MSW} and
{\tt CLOCKNAFORK\_LSW} 16-bit ports.

Maggs adds the following function to the kernel:

\begin{verbatim}
/* reads and then returns the 32-bit CLOCKNAFORK value */

unsigned int clocknafork(void){

  unsigned short lsw; /* least significant word (16 bits) of clock */
  unsigned short msw; /* most significant word (16 bits) of clock */

  lsw = inw(CLOCKNAFORK_LSW);  /* read 16-bits from LSW port */
  msw = inw(CLOCKNAFORK_MSW);  /* read 16-bits from MSW port */

  return (unsigned)((msw << 16) | lsw);  /* compose 32-bit clock value */
}
\end{verbatim}
    
In the fall, an unsuspecting 15-410 student working on the P1
assignment (DOOM 0.3) decides to test the {\tt clocknafork()}
function, and writes the following short program.

\begin{verbatim}

int kernel_main(void){
  unsigned int oldclock;
  unsigned int clock;
  int i;

  oldclock = clocknafork();

  for (i = 0; i < 6; i++){
    sleep(1);
    clock = clocknafork();
    printf("difference: %d\n",clock - oldclock);
    oldclock = clock;
  }

  while (1)
    continue;
}
\end{verbatim}

Once, when running the program, the student observes the following
puzzling output:

\begin{verbatim}
difference: 1001
difference: 1000
difference: 1000
difference: 66535
difference: -64535
difference: 1000
\end{verbatim}

After sending this output to {\tt staff-410\@cs.cmu.edu}, the teaching
assistants, and Professor Eckhardt especially, make great mirth of
Professor Maggs's blunder.

\subsection{5pts}
Explain the puzzling output.

\subsection{5pts}
Show how to improve the accuracy of function {\tt clocknafork()}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \newpage
\titledquestion{Mutex Mutation}{10}

Still reeling from the CLOCKNAFORK debacle, Professor Maggs decides to
restore his reputation by actually doing Project~4 before it is
inflicted on the students.  As you may recall, for Project~2 we told
you not to worry about mutex deadlocks.  Wily Professor Eckhardt tells
Professor Maggs that it should be easy to return to the thread library
and implement a mechanism for {\em detecting} mutex deadlocks.  Not
knowing any better, and surprising nobody, Professor Maggs cranks out a
solution in under 15 minutes at 3am.  His solution is outlined below.
Your job will be to grade it.

\paragraph{Data structures} Every mutex is assigned a unique
32-bit number when it is initialized, and this number is stored in the
mutex data structure as {\tt mutexid}.  (For this problem, don't worry
about the space of numbers being exhausted.)  Each mutex records the
tid of the thread that holds it as {\tt owner}.  Furthermore, the
mutex data structures are held together in a singly-linked list, using
a {\tt next} pointer stored in the mutex data structure.  The linked
list is protected by a global mutex called {\tt mutexmutex}.  A thread
control block (TCB) records which mutex the thread last attempted to
acquire, and how many times it has yielded while attempting to acquire
that mutex.

\paragraph{Acquiring a mutex} To acquire a mutex $m$, a thread $t$ first
must acquire {\tt mutexmutex}, trying repeatedly until it
succeeds.  Once it succeeds, it attempts to acquire $m$.  If that
succeeds, then its tid is written to mutex $m$'s {\tt owner} field,
and {\tt mutexmutex} is released.

\paragraph{Failing to acquire a mutex} If a thread $t$ fails to acquire a
mutex $m$ then it must release {\tt mutexmutex} and yield, and
attempt to acquire $m$ again when control next returns to the thread.
If, however, the number of attempts to acquire the mutex $m$ reaches a
certain large threshold, then the thread checks for deadlock.  It does
this by looking for a cycle among the threads, including itself, that
are waiting for mutexes.

To perform this search, the thread first
must acquire the mutex protecting the TCB data structure in addition
to {\tt mutexmutex}, which it already holds.  The search for a cycle
takes place in a directed graph where each node represents a
thread.  There is an edge between threads $t_1$ and $t_2$ if thread
$t_1$ is waiting for a mutex that is held by thread $t_2$.  Note that
we haven't stored the graph representation using the standard
adjacency list or adjacency matrix data structures.  In order for
thread $t_1$ to determine which thread holds the mutex that it is
waiting on, it simply scans the global linked list of all mutexes to
locate the owner.  The search for a cycle begins at the thread $t$
that failed to
acquire the mutex, and simply follows edges until the search returns
to $t$ or the search can proceed no further.  If a cycle is detected,
then deadlock is detected.

If no deadlock is detected, then the thread $t$ resets its yield
count, releases {\tt mutexmutex} and yields again.

\paragraph{Releasing a mutex} In order to release a mutex $m$, a thread
must first acquire {\tt mutexmutex}.  After releasing $m$, it
releases {\tt mutexmutex}.

\subsection{10pts} Identify what you believe are 
the two largest performance problems with
this scheme (specify which you believe to be the worst
versus the second-worst, and why).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Burning Question}{10}

Consider a simpleminded CD-duplication kiosk with multiple
terminals.  When a user approaches a terminal and activates
the duplication program, the program allocates two CD
burner drives (each is capable of reading and writing), prompts
the user to insert the source disc into one drive and a blank
target disc into the other, and then copies the bits.  You
may assume that the allocation code is of the form

\begin{verbatim}
  source_drive = allocate_drive();
  target_drive = allocate_drive();
  printf("Place source in drive %d, blank in drive %d\n",
      source_drive, target_drive);
  ...
\end{verbatim}

Imagine that a particular kiosk has three terminals and
four CD burners.  If this system can deadlock, draw a
picture of it in a deadlocked state.  If not, provide
a brief proof of why it cannot deadlock.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titledquestion{Racy Bakers}{10}

Consider Lamport's Bakery algorithm (Figure~7.5 in the text).
Using the table below and the execution-trace format presented
in the lecture slides, illustrate a plausible sequence of events
which would take place as Thread~A enters its critical section,
Thread~B and Thread~C ``choose the same ticket number,''
Thread~A leaves its critical section, and then either Thread~B
or Thread~C enters its critical section.
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 & 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}
