%\input{params}
\documentclass[11pt,twoside]{article}
    
\usepackage{graphics}
\newcommand{\nand}{|}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\printlayout
\askaboutsolutions

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut6}
\newcommand{\tutnum}{6}
\newcommand{\tutdate}{October 13, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}

\problem \textbf{ Concurrent reads in $\ms{Split-SC}$}

In class, we discussed a version of $\ms{SC}$, $\ms{Split-SC}$, that together
with $\ms{Env}$ behaves like $\ms{CM}$. This was achieved through the
use of locks. Each read/write access to a location sets a lock
on that location and no further read/writes are possible on that 
location till the lock is released. Although this works correctly, 
it is inefficient as it forces the reads to happen sequentially, which
is really not necessary (convince yourself about this). Modify the 
behavior of $\ms{Env}$ to allow concurrent reads.

The original specification of $\ms{Env}$ is reproduced below:
\begin{tabbing}
XXX\=XXX\= \kill
$Q$: $\ms{locks}$, a mapping from $A$ to $I$, \\
indicating for each memory address, which caches have currently
active operations \\
$Q_0$:  for all $a$, $\ms{locks}(a) = \emptyset$ \\
$L$: Input and output reverse those of $\ms{Split-SC}$: \\
\> Input: \\
\> \> $\ms{respond}(v,i)$, $v \in V$, $i \in I$ \\
\> \> $\ms{respond}(\ms{OK},i)$, $i \in I$ \\
\> Output: \\
\> \> $\ms{request}(\ms{read}(a),i)$, $a \in A$, $i \in I$ \\
\> \> $\ms{request}(\ms{write}(a,v),i)$, $a \in A$, $v \in V$, $i \in I$ \\
\> Internal: None \\
\\
Transitions: \\
\> $\ms{respond}(*,i)$ \\
\> Can occur: anytime \\
\> Effect: for all $a$, $\ms{locks}(a) := \ms{locks}(a) - \{ i \}$ \\
\> \> (That is, throw away locks held by $i$.) \\
\\
\> $\ms{request}(\ms{read}(a),i)$ \\
\> Can occur: $\ms{locks}(a) = \emptyset$ \\
\> Effect: $\ms{locks}(a) := \{ i \}$
\\
\> $\ms{request}(\ms{write}(a,v),i)$ \\
\> Can occur: $\ms{locks}(a) = \emptyset$ \\
\> Effect: $\ms{locks}(a) := \{ i \}$
\end{tabbing}

\solution{
\medskip
\textbf{Solution:}\\

The only transition of $\ms{Env}$ that needs to be changed is:

\begin{tabbing}
XXX\=XXX\= \kill
\> $\ms{request}$($\ms{read}$(a),i) \\
\> Can occur: $\ms{locks}$(a) = $\emptyset$ \\
\> Effect: Nothing \\
\end{tabbing}

In other words, now we no longer place a lock on a location if it's 
a read operation. It's clear that the composition of $\ms{Split-SC}$
and $\ms{Env}$ still implements $\ms{CM}$.

}

\end{problems}

\end{document}












