\documentclass[12pt]{article}

\usepackage[T1]{fontenc} 
\usepackage{fullpage,amsmath,amsfonts}

\begin{document}

\title{Foundations of Information Systems}
\author{Winter Semester 2023--24, Exercise 8}
\date{For discussion on Wednesday, December 20, 2023}
\maketitle

\begin{enumerate}
\item Recall the ``simple language'' from class, which has
non-negative integer variables, the statements \texttt{incr(X)} and
\texttt{decr(X)}, as well as while loops of the form
\begin{verbatim}
while(X):
    loop body
\end{verbatim}
In class, we looked at a macro $\mathtt{Y} \leftarrow \mathtt{X}$
which assigns the value of \texttt{X} to \texttt{Y}, while setting
\texttt{X} to zero.  Modify this example so that the end of the
operation, \texttt{X} retains its original value.

\item Show that if a process occupies $m$ bytes of memory, virtual
memory is divided into page frames of $s$ bytes each, and the page
table entry for each page requires $t$ bytes of memory, then the
optimal size of the page frame is
\begin{equation*}
  s = \sqrt{2 \, m \, t} \,.
\end{equation*}
\emph{Hint:} Assume that, on average, half of a page frame is wasted.
Also assume that each page needs exactly one page table entry of $t$
bytes.\footnote{In practice, things are more complicated as page
tables are organized as multilevel trees to be able to efficiently
address non-contiguous blocks of virtual memory.  So the formula given
is just a back-of-the-envelope estimate.}

\item Continuing Problem 2: On 32-bit Intel architectures, the
standard size of a page frame is
$4 \, \mathrm{KB} = 2^{12} \, \mathrm{B}$.  A single entry in the page
table requires $32\,\mathrm{bit} = 4 \, \mathrm{B}$.  What is the
implicit assumption on the typical size of a process?

\item Continuing Problems 2 and 3: On 64-bit architectures, the size
of a page table entry goes up to $64\,\mathrm{bit} = 8 \, \mathrm{B}$.
How does the result change?  Comment!

\item (Forouzan, P7-9.) 
 Three processes ($A$, $B$, and $C$) are running concurrently. Process $A$ has acquired
\texttt{File1}, but needs \texttt{File2}. Process $B$ has acquired \texttt{File3}, but needs \texttt{File1}. Process $C$
has acquired \texttt{File2}, but needs \texttt{File3}. Draw a diagram for these processes. Is this a
deadlock situation?

\item  (Forouzan, P7-10.) Three processes ($A$, $B$, and $C$) are running
concurrently. Process $A$ has acquired \texttt{File1}. Process $B$ has
acquired \texttt{File2}, but needs \texttt{File1}. Process $C$ has
acquired \texttt{File3}, but needs \texttt{File2}. Draw a diagram for
these processes. Is this a deadlock situation? If your answer is
``no'', show how the processes can eventually finish their tasks.

\item One solution to the \emph{dining philosophers problem} demands
that only four of the five philosopher sit at the table at any one
time.  When a philosopher finishes eating, she gets up and lets the
standing philosopher take a seat.  Is this solution free of deadlock?
Is starvation possible?


\end{enumerate}
\end{document}
