\documentstyle[12pt]{article}
\setlength{\textheight}{8.625in}
\setlength{\topmargin}{-1cm}
\setlength{\oddsidemargin}{+1mm}
\setlength{\textwidth}{6.5in}
%\renewcommand{\baselinestretch}{1.1}
%\parskip=1.5ex
\newcommand{\mc}{\multicolumn}
%\pagestyle{empty}
\begin{document}
{
\Large \bf
\begin{center}
Comprehensive Exam: Operating Systems\\
Solutions\\
\end{center}
}

\begin{enumerate}
\item
Advantages of having two or more page sizes:
\begin{enumerate}
\item Smaller internal segmentation
\item Application dependent on page size to reduce the number of page
faults 
\end{enumerate}
\noindent Disadvantages of having two or more page sizes:
\begin{enumerate}
\item Complicated page table maintenance
\begin{itemize}
\item  hard to keep track of sizes of each page
\item  complicated page replacement algorithm
\item  difficulty in choosing page sizes for a given application
\end{itemize}
\item External fragmentation
\end{enumerate}
Large number of page sizes is not equivalent
to segmentation beacuase
\begin{itemize}
\item paging is typically transparent. 
\item segmentation allows for multiple linear address space.
\end{itemize}
\item
 Each process $P$ maintains a
vector denoted by $V\_P$ of size $(N-1)$, where $N$ is the number of
processes in the system. An element of $V\_P$ is an ordered pair $(P',t)$
where $P'$ is the ID of the destination process of a message and $t$ is a
vector timestamp. The processes in the system are assumed to use vector
clocks. 
Let
\begin{itemize}
\item $t_M=$ logical time at the sending of message $M$.
\item $t_{P_i}=$ present/current time at process $P_i$.
\end{itemize}

{\bf The Protocol}
\\
{\em Sending of a message $M$ from process $P_1$ to process $P_2$}
\begin{itemize}
\item Send message $M$ (timestamped $t_M$) along with $V\_{P_1}$ to process
$P_2$.
\item Insert pair $(P_2,t_M)$ into $V\_P_1$. If $V\_P_1$ contains a pair
$(P_2,t)$, it simply  gets overwritten by the new pair $(P_2,t_M)$. Note
that the pair $(P_2,t_M)$ was not sent to $P_2$. Any future message
carrying the pair $(P_2,t_M)$ cannot be delivered to $P_2$ until $t_M<t_{P_2}$.
\end{itemize}

{\em Arrival of a message $M$ at process $P_2$}
\\
If $V\_M$ (the vector accompanying message $M$) does not contain any pair
$(P_2,t)$\\
\mbox{\hspace{3em}}then the message can be delivered\\
\mbox{\hspace{5em}}else (* A pair $(P_2,t)$ exists in $V\_M $ *)\\
\mbox{\hspace{6em}}If $t\not<$ $t_{P_2}$ then\\
\mbox{\hspace{7em}}the message cannot be delivered (*it is buffered for
later delivery*)\\
\mbox{\hspace{6em}}else\\
\mbox{\hspace{7em}}the message can be delivered.\\ \\
If message $M$ can be delivered at process $P_2$, then the following three
actions are taken:
\begin{enumerate}
\item Merge $V\_M$ accompanying $M$ with $V\_P_2$ in the following
manner:
\begin{itemize}
\item If $(\exists(P,t)\in V\_M$, such that $P\ne P_2)$ and
$\forall(P',t)\in  V\_P_2,P'\ne P)$, then insert $(P,t)$ into $V\_P_2$. This
rule performs the following: if there is no entry for process $P$ in
$V\_P_2$, and $V\_M$ contains an entry for process $P$, insert that entry
into $V\_P_2$.
\item $\forall P,P\ne P_2$, if $((P,t)\in V\_M)\wedge ((P,t')\in V\_P_2)$,
then the algorithm takes the following actions: $(P,t)\in V\_P_2$ can be
substituted by the pair $(P,t_{\rm sup})$ where $t_{\rm sup}$ is such that
$\forall i,t_{\rm sup}[i]=\max(t[i[,t'[i])$. 

 Due to the above two actions, the algorithm satisfies the following two
conditions:
\end{itemize}
\begin{enumerate} 
\item No message can be delivered to $P$ as long as $t'<t_P$ is not true.
\item No message can be delivered to $P$ as long as $t<t_P$ is not true.
\end{enumerate} 
\item Update site $P_2$'s logical clock.
\item Check for the buffered messages that can now be delivered since local
clock has been updated.
\end{enumerate}




\item

\noindent
type cigarette-smoker=monitors\\
\mbox{\hspace{2em}}var agent : condition;\\
\mbox{\hspace{4em}}self[0$..$2] : condition\\
\mbox{\hspace{2em}}procedure entry smoke (i : 0$..$2)\\
\mbox{\hspace{4em}}begin\\
\mbox{\hspace{6em}}repeat\\
\mbox{\hspace{8em}}smoke;\\
\mbox{\hspace{8em}}agent.signal\\
\mbox{\hspace{8em}}self[i].wait\\
\mbox{\hspace{6em}}until false\\
\mbox{\hspace{4em}}end;
\\
\mbox{\hspace{2em}}procedure entry agent()\\
\mbox{\hspace{4em}}begin\\
\mbox{\hspace{6em}}repeat\\
\mbox{\hspace{8em}}random = (0$..$2);\\
\mbox{\hspace{8em}}provide (material [(rand+1) mod 3], material
                    [(rand+2)mod 3])\\
\mbox{\hspace{8em}}self[rand].signal; agent.wait;\\
\mbox{\hspace{6em}}until false\\
\mbox{\hspace{4em}}and;\\
\mbox{\hspace{4em}}begin\\
\mbox{\hspace{6em}}self[0].wait;\\
\mbox{\hspace{6em}}self[1].wait;\\
\mbox{\hspace{6em}}self[2]. wait;\\
\mbox{\hspace{6em}}agent()\\
\mbox{\hspace{4em}}end\\
end;

\bigskip

The solution makes the following assumptions:
\begin{enumerate}
\item If $P$ signals $Q$, $Q$ waits until $P$ leaves the monitor or
waits for another condition.
\item At each step, once the agent provides the material, the smoker who
has the remaining material is ready to smoke.
\end{enumerate}
\end{enumerate}

\end{document}

