\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 proceses.  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 VPN X, the TLB checks to see if it contains X.  If A accessed
its 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 a site has a write-locked copy of some data, which another
site wants to write to. However, the original site flushes the data
due to a cache replacement algorithm. Before the flushing info gets to
the home site however, the second site makes a store-request to the
home site, which generates the exclusive-copy-request.

For this diagram, the cache lines all refer to lines for a particular
address ($A_1$) 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}

It looks like this situation not only results in the
exclusive-copy-request arriving during a transient state. What's worse
is that this protocol results in site 3 NEVER receiving 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 line solves the situation in this scenario.

\bigskip
\problempart{non-FIFO Network}
Finally, it is very likely that this protocol will outright fail in
many situations if FIFO was 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 is no longer the case, then it is fair to
assume a larger set of inputs, and more state to account for every
possibility (although 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. It will then have to wait for a reply
from all sites acknowledging the reset before it resumes).

However, we do not have the above tables. So if FIFO fails, Figure 2 is
one situation where our current system breaks. The idea here is that
site1 requests a read copy of a piece of data, to which the home
replies with a positive answer. This answer gets extremely delayed
however. In the meanwhile, site3 requests to write to the address. The
home sends an invalidation request to site 1, which is quickly replied
to (site1 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 site1 that it can
share-read the data arrives. So site3 is happily editing the data, and
site1 is happily reading the data. Only site1 is reading an old and
inaccurate copy of the data, and none of the sights know this.

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

Another solution to the above problem is to simply define this
behavior as correct. That is: a site editing a value doesn't really
mean that other sites get the latest value, only that they will have a
value that was correct at some point. (This will in fact allow us to
simplify the protocol considerably, at the cost of being
not-very-useful to many programmers).

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