\documentclass[11pt, twoside]{article}
\usepackage{amsmath}
\usepackage{moreverb}
\usepackage{epsfig}
\input{homework}

\begin{document}

\solutions{5}

\begin{problems}
\bigskip

\problem{Virtual Memory}
\medskip

\begin{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problempart{TLB Protection/Status Bits}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent {\bf Question (a):} If a page is modified in memory and then
later needs to be read, the read should see the modifications.  Thus
the page must be written back to disk (unless future reads will access
the copy in memory).  The M bit keeps track of which pages need to be
written back.

In a given TLB entry, the M bit may have changed from 0 to 1, reflecting
that the page was modified and may need to be written back to disk.
When the TLB entry is invalidated, it is about to be deleted from the
TLB.  Thus the M bit must be written to the page table to keep track of
the page's ``dirty'' status.
\medskip

\noindent {\bf Question (b):} When inserting a new VPN into a full TLB,
we'd like to replace the least recently used entry.  The hope is that
such an entry is least likely to be accessed in the future, and if so,
our action would minimize miss rate. The U bit helps us determine which
are the least recently used entries.

Ben is correct.  The U bit and replacement policy affect the system's
performance, not its correctness.  If a heavily accessed page's VPN is
(mistakenly) removed from the TLB, the VPN will simply be reloaded on
the next access, causing a delay, not an error.
\medskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problempart{Multiprocessing \& Context Switch} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent {\bf Question (c):} Suppose we switch from process A to
process B. Each process is allocated a virtual address space which is
independent of the virtual address space of other processes.  Thus we
can have two cases:

\begin{enumerate}
  \item A maps VPN X to PPN S and B maps VPN X to PPN T (same VPN
  mapping to different PPNs).

  \item A maps VPN X to PPN S and B maps VPN Y to PPN S (different VPNs
  mapping to same PPN).
\end{enumerate}

Now, given a request for VPN X, the TLB checks to see if it contains X.
If A accessed A's VPN X, then X will be in the TLB, but it may not map
to same PPN as B's VPN X (case 1).  This is one reason why the TLB must
be flushed.

Setting all the V bits of all the TLB entries to 0 is equivalent to
removing every entry from the TLB, thus avoiding the problem in the
previous paragraph.  This is may not be sufficient, however, since A may
have modified some pages that B needs to read (case 2).  If B always
loads the disk copies of the pages, then A's modifications must be
written back to disk so that B can load them.  However, if B checks
first to see if the desired page is already in memory, then it need not
load from disk, in which case setting the V bits to 0 is sufficient for
flushing the cache.  
\medskip

\noindent {\bf Question (d):} When B begins to execute after the context
switch, it must be unable to use any of A's TLB entries because of the
problem with case 1.  To avoid explicitly flushing the TLB (by setting
all V bits to 0), we could attach the process ID to each TLB entry.
Thus every access to the TLB after the context switch would result in a
miss, even if the VPNs were identical.  Again, this is only sufficient
if B searches for a page in memory before going to disk, as described in
(c).

\end{problemparts}

%%%%%%%%%  Problem 2

\problem{Synchronization in SMPs}
\medskip

\begin{problemparts}
\problempart{Atomic Acquire}
For this problem, we were not told anything about the MSI cache
coherence protocol, so we made the assumption that it works like most
protocols, in which a read doesn't generate messages (or broadcasts)
to other sites, but that writes do (to invalidate other cache
entries). Notably, ALL writes do, even if the written value is the
same as the old one that was there.

The code Louis writes is inefficient in this case:
\begin{listing}{1}
	ADDI Rm, R0, _mutex
	ADDI Ri, R0, 1
Loop:	LWRV Rt, (Rm)
	STCD (Rm), Ri, Rs
	BEQZ Rs, Loop
	BNEZ Rt, Loop
\end{listing}
Specifically, if five threads are all trying to grab the lock, only
one will get it, and the rest will be stuck in the loop (lines 3-6)
until the lock is released. However, this involves letting one of
those threads successfully write a 1 to the mutex address each pass
(even though the mutex was already a 1, and therefore grabbed). This
means that the value of the memory address will be flushed from all
the other caches, only to be loaded back in almost immediately. This
is not really necessary once the mutex has been grabbed. 

\bigskip

\problempart{Improving Efficiency}
To fix this, we can check whether the value is 1 BEFORE trying to set it
ourselves. If it is a 1, we know the mutex has been grabbed, and
therefore know we will not succeed in grabbing it ourselves. We move
line 6 up thus:
\begin{listing}{1}
	ADDI Rm, R0, _mutex
	ADDI Ri, R0, 1
Loop:	LWRV Rt, (Rm)
	BNEZ Rt, Loop
	STCD (Rm), Ri, Rs
	BEQZ Rs, Loop
\end{listing}
Once the mutex is grabbed, NO thread will succeed in getting to the
STCD (the expensive operation). They will all be in a smaller loop
(lines 3-4). However, if it is still free, then at least one thread
will get to the STCD line, and at that point, STCD will decide which
of those gets the mutex.

Another interesting optimization is possible if we assume that the
LWRV instruction is somehow more expensive to the system as a whole
than a basic LOAD operation (not just for the particular CPU calling
the instruction, but to some shared resource among the system).  If
this is the case, we can lower the number of times we call LWRV by
having an early loop that just uses LOAD (no reservation set) to test
the value in the mutex.  If we believe the value to be zero, we
proceed with the reservation system, but if we believe it to be a 1,
we wait in a small pre-loop for it to be a zero:

\begin{listing}{1}
	ADDI Rm, R0, _mutex
	ADDI Ri, R0, 1
pre:	LOAD Rt, (Rm)
	BNEZ Rt, pre
Loop:	LWRV Rt, (Rm)
	BNEZ Rt, Loop
	STCD (Rm), Ri, Rs
	BEQZ Rs, Loop
\end{listing}
This code is indeed SLOWER for every particular instance, but if it
does not slow down the entire machine as a whole, then it could make
the entire system faster.

\end{problemparts}

%%%%%%%%%  Problem 3

\problem{Directory-based cache coherence protocol}
\medskip

\begin{problemparts}
\problempart{Cache State Transitions}
The two new entries in Table 1 are:

\medskip

\begin{tabular}{|l|l|l|l|l|} \hline
12 & C-modified & replace & C-invalid & write-back $\rightarrow$ home \\ \hline
14 & C-modified & exclusive-copy-request & C-invalid &
exclusive-copy-reply $\rightarrow$ home \\ \hline
\end{tabular}

\bigskip
\problempart{Directory State Transitions}
The two new entries in Table 2 are:

\medskip

\begin{tabular}{|l|l|l|l|l|} \hline
4 & H-shared[$S$] & store-request & H-transient[$|S|$] & $\forall s
\in S$, 
invalidate-request $\rightarrow s$ \\ \hline
13 & H-transient & shared-copy-reply & H-shared[$\{j,k\}$] &
load-reply $\rightarrow j$ \\ \hline
\end{tabular}

\bigskip
\problempart{Protocol Understanding}

Figure 1 is a protocol-timing diagram demonstrating a scenario where a
site that is NOT a home site for a piece of data is in a transient state
and yet receives an {\bf exclusive-copy-request}. The basic idea is that
site 1 has a write-locked copy of the data at address A1, the home of
which is site 2, and site 3 wants to write to A1.  However, site 1
flushes the data of A1 due to its cache replacement algorithm. Before
the flushing info gets to site 2 however, site 3 makes a store-request
to site 2, which generates the exclusive-copy-request.

In the diagram, the cache lines refer to lines for the address address
A1, and the vertical lines refer to the current state for that cache
line. The diagonal lines are messages being passed around.

\begin{figure}[htb]
\begin{center}
\epsfig{figure=pset5-1.eps}
\caption{Protocol scenario which demonstrates excl-copy-req in C-transient}
\end{center}
\end{figure}

This situation results in the exclusive-copy-request arriving during a
transient state. What's worse is that, according to the protocol, site 3
NEVER receives a reply to its request. More interestingly, home will
get an exclusive-copy-reply when it is in an H-modified[site1] state,
which in our table, is not documented (although it is pretty obvious
that the entry in the table for this situation should look like:

\medskip

\begin{tabular}{|l|l|l|l|l|} \hline
7.5 & H-modified[$m$] & exclusive-copy-reply & H-modified[$j$] &
  store-reply $\rightarrow j$ \\ \hline
\end{tabular}

Of course, there are other more complex interactions that could occur
here, but the above entry solves the situation in this scenario.

\bigskip
\problempart{non-FIFO Network}
It is very likely that this protocol will outright fail in
many situations if FIFO is not guaranteed. Each site is basically an
FSM which goes from one state to another based on the kind of inputs
it is expecting. If FIFO no longer holds, then it is fair to
assume a larger set of inputs and more states to account for every
possibility\footnote{
  There will have to be a broadcast of 'reset' which will deal with
  situations when the home no longer knows what is going on and wants to
  reset. The home will then have to wait for a reply from all sites
  acknowledging the reset before it resumes.
}.

However, we do not have transition tables for such a system. So if FIFO
fails, Figure 2 is one situation where our current system breaks. The
idea here is that site 1 requests a read copy of a piece of data, to
which the home, site 2, replies with a positive answer. This answer gets
extremely delayed however. In the meanwhile, site 3 requests to write to
the address. The home sends an invalidation request to site 1, which is
quickly replied to (site 1 is still in transient state), and the home
thinks it can now successfully tell site 3 that it may edit the data to
its heart content. Finally the delayed message telling site 1 that it can
share-read the data arrives. So site 3 is happily editing the data, and
site 1 is happily reading the data. However, site 1 is reading {\em
inaccurate} copy of the data, and none of the sites know this.

\begin{figure}[htb]
\begin{center}
\epsfig{figure=pset5-2.eps}
\caption{Protocol scenario which demonstrates problems for non-FIFO}
\end{center}
\end{figure}

Another solution to the above problem is to simply define this behavior
as correct. That is: when a site edits a value, the other sites don't
necessarily get the latest value, but rather they will have a value that
was correct at some point.  This will allow us to simplify the protocol
considerably, at the cost of being not-very-useful to many programmers.

\end{problemparts}
\end{problems}
\end{document}
