\documentclass[12pt]{article}

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

\usepackage{tikz}
\usetikzlibrary{graphs, positioning}

\begin{document}

\title{Foundations of Information Systems}
\author{Winter Semester 2024--25, Exercise 8}
\date{For discussion on Wednesday, December 18, 2024}
\maketitle

\begin{enumerate}

\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 1: 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 1 and 2: 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?

\item Consider the following generalized dining philosopher's problem.
There are six philosophers, needing pairwise shared resources to eat.
They follow the Chandy--Misra protocol, i.e., resources are either
\emph{dirty} (``D'') or \emph{clean} (``C'').  The resources are
attached to edges of the following graph, with the initial
configuration as shown:
\begin{center}
\begin{tikzpicture}[every edge/.style={draw, thick}]

    % Define positions of nodes in a circle
    \foreach \i/\label in {1/1, 2/2, 3/3, 4/4, 5/5, 6/6} {
        \node[draw, circle, minimum size=1cm] (\label) at (\i*360/6:3cm) {\label};
    }

    % Add straight edges with random labels
    \draw (1) -- node[near start, above] {D} (2);
    \draw (2) -- node[near start, above left] {D} (3);
    \draw (3) -- node[very near end, left] {D} (4);
    \draw (4) -- node[near end, below] {D} (5);
    \draw (5) -- node[near end, below right] {D} (6);
    \draw (6) -- node[near end, above right] {D} (1);
    \draw (3) -- node[very near end, below] {D} (1);
    \draw (4) -- node[very near end, above] {D} (6);

\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Show that the initial graph is acyclic.
\item Assume that all philosophers are hungry at the same time, once
they have eaten, they will not get hungry again.  In which order do
they get to eat?  If there is ambiguity, assume that a philosopher who
can eat will eat immediately, and before honoring any a request for a
resource \emph{before}.
\end{enumerate}

\end{enumerate}
\end{document}

