\documentclass[11pt]{article}

\usepackage{simplemargins}
\setleftmargin{1in}
\setrightmargin{1in}
\settopmargin{2in}
\setbottommargin{1in}

\def\choice#1{\left\{ \begin{array}{ll} #1 \end{array} \right.}
\def\AND{\mbox{ and }}
\def\OR{\mbox{ or }}
\def\NOT{\mbox{ not }}
\def\RULE#1#2#3{{\bf #1} \\
                \begin{tabular}{ll}
                        & $\mathrm{#2}$ \\
                  $\to$ & $\mathrm{#3}$ \\
                \end{tabular}}
\def\BIGRULE#1#2#3#4#5{
                     {\bf #1} \\
                     \begin{tabular}{ll}
                              & $\mathrm{#2}$ \\
                              & $\mathrm{#3}$ \\
                        $\to$ & $\mathrm{#4}$ \\
                              & $\mathrm{#5}$ \\
                     \end{tabular}}
%\def\RULE#1#2#3{
%  \noindent\bf #1 \\
%  \phantom{$\to$} \em $\mathrm{#2}$ \\
%           $\to$  \em $\mathrm{#3}$ \\ \relax
%}
\def\IF{\mbox{\quad \it\ if\ }}
\def\WHERE{\mbox{\quad \it where }}





\title{6.823 Problem Set 6}
\author{Chris Laas}
\date{May 5, 2000}

\pagestyle{myheadings}
\markright{Chris Laas \hfil 6.823 \hfil 5/5/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}

\begin{document}
\maketitle




\section*{Problem 6-1}
\begin{enumerate}

\item%(a)

\begin{verbatim}
try:    LWRV r3, (r2)
        SWCD (r2), r1, r4
        BEQZ r4, spin
        MOV r1, r3
\end{verbatim}


\item%(b)

The processor must check whether its own reservation has been
cancelled, and must cancel other processors' reservations, if any.
This is relatively costless for the issuing processor if the SMP uses
snoopy caches which detect writes going over the bus.


\item%(c)

\begin{verbatim}
        ADD r2, r0, mutex
try:    LWRV r1, (r2)
        BEQZ r1, try
        ADD r1, r0, r0
        SWCD (r2), r1, r3
        BEQZ r3, try
\end{verbatim}

In the old mechanism, the processor trying to set the semaphore could
have its reservation cancelled by the spinning process, causing it to
have to try again (potentially over and over again until it
succeeds).  With this mechanism, the spinning process polls the
semaphore location without cancelling any reservations; thus, the
semaphore is set correctly the first time, and exactly one blocking
process will be sent on its way.


\item%(d)

Imagine that several processors are each running several processes
which reserve the memory address M.  Let's pay attention to one
processor, running tasks A and B.  Task A issues a LWRV to reserve the
location M, and there is immediately a context switch to task B.  Task
B issues a LWRV to reserve M, then issues a SWCD on the location with
a new value, and again there is a context switch to task A.  Now,
since the processor doesn't cancel the reservation on a context
switch, task A continues on to perform its SWCD on location M,
succeeding because it sees that it has a valid reservation on the
location.  However, sequential consistency has been violated, because
the value in memory location M was changed (by task B) in between the
times that task A read the location and wrote the location, and thus
task A was using a stale value of the memory location value when it
performed the store.


\end{enumerate}
\newpage








\section*{Problem 6-3}
\begin{enumerate}

\item%(a)



\end{enumerate}
\newpage






\end{document}
