
\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}}
\newcommand{\AWAIT}[0]{\textbf{await}}

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

\title{Programaci\'on Concurrente \\ Pr\'actico 1: Algunos Problemas de Concurrencia}
\author{J. Blanco, N. Wolovick}


\begin{document}
\maketitle

\begin{enumerate}

	\item{ El siguiente programa sufre de deadlock.
		Intente mejorar su condici\'on de progreso insertando sentencias $x:=True$
		en la componente $A$ y $y:=True$ en la componente $B$.
		\newline
		\begin{center}
		\begin{tabular}{|l|l|}
			\hline
			\multicolumn{2}{|l|}{Pre: $true$} \\
			\hline
			\begin{minipage}[t]{1in}
			\begin{tabbing}
	       	        	$A:$ \= $y:=False;$ \\
	                       	\> $\IF\ y \rightarrow \SKIP\ \FI$ 
			\end{tabbing}
			\end{minipage}
			&
			\begin{minipage}[t]{1in}
			\begin{tabbing}
	                	$B:$ \= $x:=False;$ \\
	                       	\> $\IF\ x \rightarrow \SKIP\ \FI$ 
			\end{tabbing}
			\end{minipage}
			\\
			\hline
		\end{tabular}
		\end{center}
		
		De argumentos convincentes que muestren que ambas componentes siempre terminan.
	}

	\item{Una primitiva de sincronizaci\'on importante es la \emph{barrera}, tambi\'en
		denominada \emph{sincronizaci\'on de inclusi\'on mutua}.

		Operacionalmente una barrera entre $n$ procesos se comporta bloqueando
		las componentes hasta que \emph{todas} hayan entrado a ella, es decir
		que ning\'un proceso sale de la barrera hasta que todos hayan entrado.

		En el siguiente ejemplo nunca puede darse que la sentencia $T_0$
		est\'e ejecutando mientras $S_1$ \'o $S_2$ lo hacen.
		\newline
		\begin{center}
		\begin{tabular}{|l|l|l|}
			\hline
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$P_0$: \= $S_0;$ \\
					\> $``barrera'';$ \\
					\> $T_0$
			\end{tabbing}
			\end{minipage}
			&
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$P_1$: \= $S_1;$ \\
					\> $``barrera'';$ \\
					\> $T_1$
			\end{tabbing}
			\end{minipage}
			&
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$P_2$: \= $S_2;$ \\
					\> $``barrera'';$ \\
					\> $T_2$
			\end{tabbing}
			\end{minipage}
			\\
			\hline
		\end{tabular}
		\end{center}
		\begin{enumerate}
			\item{Implemente una barrera para $n=2$ procesos utilizando $\IF$
				bloqueantes o $\AWAIT$.
				Indicar la precondici\'on necesaria y 
				aclarar el grado de atomicidad
				utilizando la notaci\'on $<S_i>$.
			}
			\item{Generalice a cualquier $n$.
			}
		\end{enumerate}  
	}

	
	\item{La siguiente es una soluci\'on utilizando sem\'aforos del problema del
		Productor-Consumidor. \'Este se dice correcto cuando el consumidor toma
		todos los datos que el productor genera\footnote{Pensar que $produce()$ genera la secuencia ordenada de todos los naturales y $consume(x)$ imprime su par\'ametro, luego la sincronizaci\'on ser\'a correcta cuando el consumidor imprima de manera ordenada todos los naturales.}.
		Las \'unicas variables compartidas entre productores y consumidores son los sem\'aforos y el arreglo $b$.
		La variable $i$ se comparte entre los productores y $j$ entre los consumidores.
		\newline
		\begin{small}
		\begin{center}
		\begin{tabular}{|l|l|}
			\hline
			\multicolumn{2}{|l|}{Pre: $\langle\forall i:0\leq i<N:def(b.i)\rangle \wedge i=0 \wedge j=0 \wedge empty=N \wedge full=0$} \\
			\hline
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$Prod$: $*$\=$[$ \= $x:=produce();$ \\
					\>	\> $P(empty);$  \\
					\>	\> $b.i:=x;$ \\
					\>	\> $i:=(i+1)\ mod\ N;$ \\
					\>	\> $V(full)$ \\
					\> $]$
			\end{tabbing}
			\end{minipage}
			&
			\begin{minipage}[t]{1in}
			\begin{tabbing}
				$Cons$: $*$\=$[$ \= $P(full);$ \\
					\>	\> $x:=b.j;$ \\
					\>	\> $j:=(j+1)\ mod\ N;$ \\
					\>	\> $V(empty);$ \\
					\>	\> $consume(x)$ \\
					\> $]$
			\end{tabbing}
			\end{minipage}
			\\
			\hline
		\end{tabular}
		\end{center}
		\end{small}
		\begin{enumerate}
			\item{Para 1 productor y 1 consumidor, argumente si la soluci\'on es
				correcta. En caso de no serla muestre un contraejemplo y 
				proponga una soluci\'on.
			}
			\item{Idem al anterior solo que para $n$ productores y $m$
				consumidores, con $n,m>1$.
			}
		\end{enumerate}
	}
	

	\item{Se tienen $n$ procesos del tipo $A$ y $m$ procesos del tipo $B$, con 
		$0<n,m$, que comparten los sem\'aforos generales $b$ y $done$.
		Analizar el tipo de sincronizaci\'on que se realiza e indicar si 
		existe riesgo de deadlock, en caso de que sea posible, 
		encontrar una soluci\'on.
		\newline
		\begin{center}
		\begin{tabular}{|l|l|}
			\hline
			\begin{minipage}[t]{1in}
			\begin{tabbing}
	       	        	$A:$ \=  \\
				\>	$\vdots$ \\
				\>	$P(b);$ \\
				\>	$P(b);$ \\
				\>	$V(done);$ \\
				\>	$V(done);$ \\
				\>	$\vdots$ 
			\end{tabbing}
			\end{minipage}
			&
			\begin{minipage}[t]{1in}
			\begin{tabbing}
	       	        	$B:$ \=  \\
				\>	$\vdots$ \\
				\>	$V(b);$ \\
				\>	$P(done);$ \\
				\>	$\vdots$ 
			\end{tabbing}
			\end{minipage}
			\\
			\hline
		\end{tabular}
		\end{center}
	}

	\item{Implemente un sem\'aforo general utilizando solamente sem\'aforos binarios.
		Especifique el invariante de representaci\'on.
	}
	
	\item{Se tiene un solo ba\~no en la Facultad, el cual puede ser usado tanto por hombres como por
		mujeres, aunque no al mismo tiempo (unisex).

		Si representamos la cantidad de hombres y mujeres dentro del ba\~no con $nm$, $nw$,
		la acci\'on de ingresar un hombre se codifica con $nm:=nm+1$, idem para las otras 3
		acciones.
		\begin{enumerate}
			\item{Especificar el problema a trav\'es de un invariante.}
			\item{Construir una soluci\'on usando monitores.}
			\item{Modificar la especificaci\'on y la soluci\'on si se agrega la restricci\'on
				de que a lo sumo $N$ personas puedan estar en el ba\~no al mismo tiempo.
			}
			\item{Discuta que problemas de \emph{fairness} tienen las soluciones obtenidas.}
		\end{enumerate}
	}
\end{enumerate}

\end{document}
