%%------------------------------------------------------------------------
\section{Deadlock Issues in \ccdsm/}
%%------------------------------------------------------------------------
\label{sec:deadlocks}
%%------------------------------------------------------------------------

We mentioned earlier that the basic cause of deadlock in incorrect
\ccdsm/ implementations is the dependence of memory operations on
coherency actions, which owing to limited hardware resources, can at
times depend on other memory operations.  In this section, we will
show some examples of deadlock scenarios that can arise when the
underlying hardware does not make provision to avoid them.

\outline{Push-outs need separate bus resources from reads.}

Consider two sites, $A$ and $B$, and two processors $P_A$ and $P_B$ at
sites $A$ and $B$ respectively.  Also assume that some bus resource at
each processor is limited and shared by all bus operations.  For
concreteness and simplicity, let us consider the case where there is
only 1 data buffer and 1 address buffer at the bus interface of each
procssor.  Also, let us assume that when a cache line read bus
operation is issued by a processor and accepted on the bus, the read
takes up both the data and address buffer and neither are released
until the read operation completes.  Let us also assume that when a
processor snoops the bus and finds a read operation for a cache line
that it has in dirty state, it provide notification that it has the
cache line in dirty state, and will provide the data.  However, in
order to actually supply this data on the bus, it needs to acquire the
data and address buffers in the processor's bus interface.  

Given this set up, the following sequence of actions will lead to a
deadlock.  (These events are illustrated with the time-line digram in
Figure~\ref{fig:deadlock-timeline-1}.)
\begin{enumerate}
\item
Processor $P_A$ reads cache line $x$ that is currently in dirty state
in processor $P_B$'s cache.  At the same time Processor $P_B$ reads
cache line $y$ which is in dirty state in processor $P_A$'s cache.
\item
Independent of the actual implementation details of the \ccdsm/
system, coherence action has to be taken to obtain the dirty cache
line $x$ from $P_B$, and the dirty cache line $y$ from $P_A$.  This is
usually done via some kind of flush bus operation.  
\item
However, when the flush bus operation is done on the two buses,
neither $P_A$ nor $P_B$ can supply the dirty cache lines immediately
because they are out of data and address buffer in their bus
interfaces.  
\item
This is a deadlock situation since $P_A$ will not flush out the dirty
cache line $y$ until its read of $x$ is complete, while $P_B$ will not
flush out the dirty cache line $x$ until its read of $y$ is complete
\end{enumerate}
The problem in this case does not arise in a single snoopy bus system
because only one single bus operation happens on the bus at any one
time.  However, in this multiple site system, the only way to avoid
this deadlock is to make sure that extra bus resources are provided
so that the flush operation can complete.  We should also point out
that in our example, we are already assuming that the bus itself is
not blocked until the read operation completes.  Otherwise, it is not
even possible to put the flush operation on the bus!

This deadlock situation is very obvious, and any snoopy bus protocol
that is meant to be extended over multiple sites has taken care of it.
The lesson for implementing \ccdsm/ is that the paths added to connect
different sites also have to preserve the same division in resources
between read requests, and flush requests so that deadlock is not
introduced.

\outline{Flush blocking write-backs, either at initiator or at home}

Our next example shows that operations like flush, which are usually
implemented in such a way that they cannot complete until the dirty
data is removed from the processor, and written back to main memory
can introduce further sources of deadlocks.  Suppose the path that a
dirty cache line has to travel in order to get back to the main memory
in its home site has only limited buffering.  If the hardware at the
last part of this path is also used for issuing flush operations, and
it blocks until the flush operation completes, we can end up with
deadlocks.  The sequence of action illustrating this is described
below and shown in Figure~\ref{fig:deadlock-timeline-2}.  Again, we
will assume two sites $A$ and $B$ with processors $P_A$ and $P_B$
respectively.  

\begin{enumerate}
\item 
$P_A$ acquires many cache lines, $x_i$'s with their home on site $B$
and wrote to them so that they end up cached in the dirty state in
$P_A$.  Similarly, $P_B$ acquires many cache lines, $y_j$'s with their
home on site $A$ and wrote to them so that they end up cached in the
dirty state in $P_B$.
\item 
Now a series of reads from possibly other sites caused the $x_i$'s and
$y_j$'s to be flushed back to their home sites, to be written back to
main memory as the new readers are not writing to these lines and do
not acquire ownership of these lines.
\item 
At some point, all the buffering from site $A$ to site $B$ gets
filled up with dirty cache lines $x_i$'s, while the buffering from
site $B$ to site $A$ are filled with dirty cache lines $y_j$'s.
\item 
Unfortunately, the combined write-back/flush device that writes the
dirty cache lines $y_j$'s back to memory at $A$ is busy trying to
flush another dirty $x_i$ cache line, which cannot move out because
there is no more buffering for it.  Since the write-back/flush device
is incorrectly designed to wait till the flush completes, a deadlock
can occur as the same situation may be happening at site $B$.  
\end{enumerate}
The lesson from this example is that the write-backs must not ever be
blocked anywhere on their way back to their home main memory.  In
particular, it is not okay to utilize the same piece of single
threaded hardware for performing blocking operations like flush, and
servicing write-backs.  

\outline{Write-back capture servicing and write-backs need separate
resources} 

Even more subtle write-back blockage deadlocks can occur if more fancy
caching schemes are used.  Consider the example where a cache line may
be cached at some sites, but uncached at others.  This seems
reasonable from a performance point of view if some sites do not reuse
the value and sees no reason for caching it, while other sites use it
a lot and wants to cache it.  Now, consider the case where a cache
line $z$ is cached for writing by processor $P_A$ at the home site,
and another site $B$ performs an uncached ``write-through'' to part of
the cache line.  In general, when the latter write arrives at the home
site $A$, the dirty cache line $z$ has to be implicitly flushed from
$P_A$ before the uncached write is allowed to occur.

If the device that does the uncache write also services write-backs,
and blocks on an uncached write that has to wait for the implicit
flush, we can easily construct a deadlock situation similar to the
previous example, except the blocking flush in the previous example is
now replaced by a blocking uncached write.  This is done by blocking
the implicit flush of $z$ behind other write-backs going to a remote
site $B$.  In most microprocessor designs, the implicit flush of $z$
has to share buffer resources in the bus interface with these other
write-backs.  If at $B$, the same thing is happening, with $A$ being
the destination of write-backs, a deadlock has occurred.  

Thus, if cached and uncached writes are allowed to the same cache
line, and the snoopy bus protocol behaves in the above manner, a
correct implementation that uncached write-backs must not share
resources with other write-backs in a manner that allows the former to
block the latter.  Of course one easy way out of this deadlock problem
is to disallow such mixing of cached and uncached access to the same
cache line.  

\outline{Sharing of cacheable, writeable data between sP and dP}

In \start/'s setting, there is a temptation to allow the sP to share
cacheable, writeable data between the other processors at the site,
which we call the computer processors (cP's).  This could, for
example, be used as a means for the dPs to communicate with the sP and
vice versa.  Unfortunately, this is unsafe as the sP may now read data
which is dirty in one of the dPs.  As a result, an attempt by the sP
to read the data will block until the dP is able to push the dirty
data out.  As we saw in the previous example, any wait by the sP for
the dPs can lead to deadlock as the buffer resource needed to effect
this implicit flush of dirty data may be occupied, and needs the sP to
actively service requests in order to free it up.  

Data sharing is still possible between the sP and dP, but it must be
through either uncached, or (maybe) write-through memory(!!I'm not
100\% sure that write-through is okay.  A write-through may be held up
till the implicit invalidation of cache copies is done.  This may rely
on resources used for other push-outs.  Once this happens, a write by
the sP may be delayed till a dP can invalidate its copy, and this
cannot happen because the dP is stuck trying to do say a write-back
that is ultimately waiting for the sP.  I think even write-through
cannot be allowed.).

It is interesting to note that since OS data-structures on SMPs are
usually cacheable and writeable by any processor, this prohibition on
sharing cacheable, writeable memory between the dPs and the sP means
that the sP cannot be running the same OS that is running on the other
sP.  For this reason, the sP will in most likelihood have to run
firmware code without VM, although it is conceivable that the sP could
run a simple OS of its own, that does not share any resource with the
other OS.

%%------------------------------------------------------------------------
%% Section End
%%------------------------------------------------------------------------
