
\documentclass[a4paper]{article}

\setlength\textwidth{6.5in}
\setlength\oddsidemargin{0in}
\setlength\evensidemargin{0in}

%\setlength\headheight{0in}
%\setlength\headsep{0in}

%\setlength\topmargin{-0.5in}
%\addtolength{\textheight}{0.5in}


\newcommand{\SIG}[1]{\ensuremath{\mathit{#1}}}
\newcommand{\Idiom}[1]{\textsl{#1}}
\newcommand{\IF}[0]{\textbf{if}}
\newcommand{\FI}[0]{\textbf{fi}}
\newcommand{\SKIP}[0]{\textbf{skip}}
\newcommand{\DO}[0]{\textbf{do}}
\newcommand{\OD}[0]{\textbf{od}}

\usepackage{latexsym}
\usepackage[spanish]{babel}

\title{Programaci\'on Concurrente \\ Pr\'actico 7: Exclusi\'on Mutua}
\author{J. Blanco, N. Wolovick}


\begin{document}
\maketitle

\begin{enumerate}


	%WF99-23
	\item{Dado el siguiente multiprograma, muestre la exclusi\'on mutua de los fragmentos $S.i$\footnote{Probablemente resulte m\'as f\'acil derivarlo como una generalizaci\'on del \Idiom{Safe Sluice} que intentar una verificaci\'on.}.
		\newline
		\begin{small}
		\begin{center}
		\begin{tabular}{|l|}
			\hline
			Pre: $\langle \forall q :: \neg x.q\rangle$ \\
			\hline
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$Comp.p:$ $*$ \= $[$ \= $x.p:=true$ \\
						\> $;$ \> $\IF\ \langle\forall q:q\neq p : \neg x.q\rangle \rightarrow \SKIP\ \FI$ \\
						\> $;$ \> $S.p$ \\
						\> $;$ \> $x.p:=false$ \\
						\> $]$ 
			\end{tabbing}
			\end{minipage}
			\\
			\hline
		\end{tabular}
		\end{center}
		\end{small}
	}


	%WF99-28
	\item{\label{prespinlock}Considere un multiprograma con 2 componentes de tipo $A$, donde en los fragmentos $cs$ no se menciona $x$.
		\newline
		\begin{center}
		\begin{tabular}{|l|}
			\hline
			Pre: $x$ \\
			\hline
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$A:$ $*$ \= $[$ \= $\IF\ x \rightarrow x:=false\ \FI$ \\
						\> $;$ \> $cs$ \\
						\> $;$ \> $x:=true$ \\
						\> $]$ 
			\end{tabbing}
			\end{minipage}
			\\
			\hline
		\end{tabular}
		\end{center}
		\begin{enumerate}
			\item{Muestre exclusi\'on mutua entre los fragmentos $cs$.}
			\item{Muestre la ausencia de deadlock total.}
			\item{?`Hay progreso individual?}
			\item{Extienda las componentes utilizando solamente variables nuevas y skips guardados, de forma tal que el n\'umero de fragmentos $cs$ que se ejecuten en una componente difieran a lo m\'as en 7 respecto a la otra componente\footnote{Es decir, pongale un poco de justicia a este algoritmo.}.}
		\end{enumerate}
	}


	%WF99-33
	\item{Considere el siguiente multiprograma con un n\'umero arbitrario de componentes\footnote{Este es una variaci\'on de muy gruesa granularidad del Algoritmo del Panadero de Lamport [Lam74]. Intente derivar el algoritmo empezando desde la aserci\'on $\{x.p=n?\}$ como pre de $cs.p$.}:
		\newline
		\begin{center}
		\begin{tabular}{|l|}
			\hline
			Pre: $m=0 \wedge n=0$ \\
			\hline
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$Comp.p:$ $*$ \= $[$ \= $ncs.p$ \\
						\> $;$ \> $x.p,m:=m,m+1$ \\
						\> $;$ \> $\IF\ x.p=n \rightarrow \SKIP\ \FI$ \\
						\> $;$ \> $cs.p$ \\
						\> $;$ \> $n:=n+1$ \\
						\> $]$ 
			\end{tabbing}
			\end{minipage}
			\\
			\hline
		\end{tabular}
		\end{center}
		\begin{enumerate}
			\item{Muestre exclusi\'on mutua entre los fragmentos $cs$.}
			\item{Muestre ausencia de deadlock total.}
			\item{Indique si hay progreso individual.}
		\end{enumerate}
	}


	%Inventado
        \item{La complejidad de la soluci\'on del Problema de Exclusi\'on Mutua para $N$ procesos disminuye significativamente cuando la granularidad es ligeramente mayor a sentencias \Idiom{one-point}.

		Por ejemplo con alguna de las siguientes instrucciones at\'omicas
                $\mbox{fetch-and-}\Phi$\footnote{Tambi\'en llamadas \Idiom{inter
lock instructions}.} se pueden lograr algoritmos de mutex muy compactos.
		\begin{small}
		\begin{itemize}
			\item{$\SIG{TestSet}(v,p): v,p:=true,v$}
			\item{$\SIG{FetchAdd}(w,p,e): p,w:=w,w+e$}
			\item{$\SIG{TSL}(v,p): v,p:= false,v$}
			\item{$\SIG{Swap}(v,w): v,w:=w,v$}
			\item{$\SIG{CompareSwap}(t,x,o,n): \langle t:=(o=x);
				\IF\ t \rightarrow x:=n\ \Box\ \neg t \rightarrow  o:=x\ \FI\ \rangle $}
			\item{$\SIG{FetchOr}(w,p,e): p,w:=w,w\vee e$}
			\item{$\SIG{Decr}(v,s): v,s:=v-1,(v-1=0)$}
		\end{itemize}
		\end{small}
                \begin{enumerate}
			\item{Utilice $\SIG{TestSet}$ para lograr un algoritmo de mutex entre $N$ procesos.}
			\item{Demuestre la correcci\'on para $N$ cualquiera\footnote{La demostraci\'on del punto \ref{prespinlock} puede resultar \'util.} .}
			\item{Investigue que alternativas existen para mejorar la performance de este algoritmo en m\'aquinas multiprocesador con caches locales. Incluya un breve argumento que muestre que la correcci\'on del punto anterior se aplica en estas optimizaciones.}
			\item{Elija alguna otra \Idiom{interlock instruction}\footnote{Menos $\SIG{TSL}$.} y proponga el algoritmo de mutex.}
		\end{enumerate}

	}


	%AND2000-3.3
	\item{Desarrolle una soluci\'on al problema de mutex de $N$ procesos utilizando $\SIG{Swap}$.
		\begin{enumerate}
			\item{Demuestre la correcci\'on.}
			\item{Optimice para que funcione bien en arquitecturas $\SIG{MP}$ con cache. Explique el porque de las optimizaciones y como se mantiene la correcci\'on.}
			\item{Utilizando $\SIG{Swap}$ desarrolle una solucion \Idiom{fair} al problema de la secci\'on cr\'{\i}tica, es decir que asegure que eventualmente todos los procesos en espera podr\'an entrar.
				La clave est\'a en ordenar los procesos en, por ejemplo, orden $\SIG{FIFO}$.
				Asuma que cada proceso tiene una identidad \'unica, es decir un entero en el rango $[0,N)$.
				Argumente de manera clara porque su soluci\'on es correcta y justa.
			}
		\end{enumerate}
	}

\end{enumerate}

\end{document}
