\documentclass{ictlab}
%\documentclass[solutions]{ictlab}

\RCS $Revision: 1.5 $

\usepackage{alltt,key,xr,amstext,answer2}
\usepackage[hang,bf,nooneline]{caption2}
\externaldocument[lt-]{../../linux_training-plus-config-files-ossi/build/masterfile}
\ifx\pdftexversion\undefined \else
  \usepackage[pdfpagemode=None,pdfauthor={Nick Urbanik}]{hyperref}
\fi
\renewcommand*{\subject}{Operating Systems and Systems Integration}
\providecommand*{\NT}{\acro{NT}\xspace}
\providecommand*{\IP}{\acro{IP}\xspace}
\providecommand*{\DNS}{\acro{DNS}\xspace}
\providecommand*{\BDC}{\acro{BDC}\xspace}
\providecommand*{\ACL}{\acro{ACL}\xspace}

\newcommand*{\labTitle}{Tutorial on Memory Management, Deadlock and
  Operating System Types}

\begin{document}

\section{Background}
\label{sec:background}

\subsection{Memory management}
\label{memory-management}

\begin{description}
\item[Virtual memory:] is a method of managing memory automatically by
  the operating sytem so that the combined size of memory available to
  all processes running on the computer may be more than the physical
  memory available by using the hard disk to hold what is not in
  physical memory.
      
\item[swapping:] involves moving all the content of memory associated
  with a process from \RAM to hard disk, and back as the operating
  system needs memory to run other processes.  This is inefficient for
  large processes.  Results in holes, where \RAM allocated to two
  large processes may have a hole between them which is too small to
  use for any process.
  
\item[paging:] all memory is divided into chunks called \emph{pages}.
  All pages are of a fixed size.  The pages in \RAM used by a process
  do not have to be contiguous (next to one another), so no problem of
  holes.
\item[Memory Management Unit:] is hardware that sits between the \CPU
  and the system buses, translating virtual addresses used by programs
  into physical addresses.  The \MMU is connected as shown in
  figure~\vref{fig:mmu}.  The \MMU and \CPU organisation fix the size
  of the pages, page tables and various other aspects of paging.
  \begin{figure}[htb]
    \centering%
    \includegraphics[width=0.5\columnwidth]{mmu}
    \caption{The memory management unit is shown here converting
      virtual addresses from the \CPU to physical addresses.}
    \label{fig:mmu}
  \end{figure}
\item[Virtual addresses:] are the addresses used by a user's program.
  The programmer can write the program as if the program has access to
  as much memory as required, without worrying about whether the
  addresses are used by other processes.  All addresses in the program
  are \emph{virtual addresses}, and are translated by the \MMU to
  physical addresses.
     
  \begin{figure}[htb]
    \centering%
    \includegraphics[width=0.4\columnwidth]{paging-labeled}
    \caption{A single-level paging system.  Virtual memory addresses
      are 32-bit.  Pages are 4K each.}
    \label{fig:paging}
  \end{figure}
  \begin{figure}[htb]
    \centering%
    \includegraphics[width=0.55\columnwidth]{multilevel-paging-labeled}
    \caption{A multi-level paging system.  On the Intel platform,
      virtual memory addresses are 32-bit.  Pages are 4K each.  The
      page tables are themselves pages, also of 4K each.  Since each
      page table entry is 4 bytes in size on the Intel platform, there
      are $1024 = 2^{10}$ entries in each of the page tables.  So
      there are ten bits required for the page number part of the
      virtual address.  The page directory itself is a 4K page, each
      entry is 4 bytes, so there are 1024 entries, one for each page
      table.  So there are ten bits required for the directory part of
      the virtual address.}
    \label{fig:multilevel-paging}
  \end{figure}

\item[What is going on in those diagrams?] To make sense of
  figure~\vref{fig:multilevel-paging}, let's look at some of the main
  points.  First, this is the representation of an Intel memory
  management system.  Other architectures have different sizes of
  pages, different numbers of levels of page tables (e.g, the Compaq
  Alpha has three levels---see later).
  \begin{itemize}
  \item The virtual address is the address used by any user programs
    running on the computer.
  \item The page contains any data used by user programs, including
    the executable programs themselves.
  \item The directory table and page table are both pages
    themselves, and are the same size.
  \item On the Intel architecture, each entry in the page and
    directory tables is four bytes in size.
  \item The most significant 10 bits of the virtual address are an
    index into the directory table, and are in the range of 0 to
    $2^{10}-1= 1023$.  Let's call it the directory number.
  \item Similarly, the ten bits for the page index number are also an
    index in the range 0 to 1023.
  \item The \texttt{cr3} register is a \CPU register that stores the
    address of the directory table.
  \item To determine the address of the current page table entry, the
    \MMU adds the contents of \texttt{cr3} to the directory number
    $\times$ the size of a directory table entry (4).
  \item To determine the address of the current page table, the \MMU
    reads the content of the current directory table entry.
  \item To determine the address of the current page, the \MMU adds
    the number $\times$ the size of a page table entry to the address
    of the current page.
  \item To determine the actual entry in the page (the content of the
    virtual address), the \MMU adds the offset from the virtual
    address to the address of the current page table.
  \end{itemize}
  
\item[Why we need multilevel paging (single level paging won't do):]
  Many people seemed unable to understand why the single level page
  table shown in the lectures needs $2^{20} \times 4$ bytes of \RAM,
  and why multilevel paging does not.  The key is that for virtual
  memory to work, there must be page table entries for the entire
  virtual address space.  If the virtual addresses are 32 bits long,
  and each page is 4-kilobytes ($2^{12}$ bytes) in size, then there
  \emph{must} be $2^{32} \div 2^{12} = 2^{32-12} = 2^{20}$ entries,
  one for each page.  On the Intel platform, each entry is 4 bytes, so
  the total size of all page table entries is $4\times 2^{20} =
  4$\,MB\@.  The single-level paging scheme shown in
  figure~\vref{fig:paging} shows the page table in one piece, so it
  must all be in \RAM.
  
  It is silly to keep all this in memory at once, since most page
  table entries are never used.  For example, virtual memory in
  today's computers is unlikely to be 4\,GB unless the computer is a
  very busy server.

  The solution is to have only the necessary page entries in \RAM, and
  to have any others that have been used some time ago on the hard
  disk.  \emph{It is more sensible to split the page table into pages that can
  be paged in and out of memory.}  This is what multilevel paging
  achieves.

\item[Explaining the ``Example of paging: Intel x86''] The example in
  the notes has confused many people since many of you do not know the
  meaning of \texttt{0x20000000} (or what \texttt{0x}\emph{nnnn}
  means).  The prefix \texttt{0x} indicates a hexadecimal value in the
  C programming language.  You can have statements such as:
\begin{verbatim}
int i = 0x123;
\end{verbatim}
  which assigns the value 123\hex to the variable \texttt{i}.  All
  that I am showing here is what the components of the virtual address
  are.  The example is simply showing the components of the virtual
  address \texttt{0x20021406} (i.e., 20021406\hex).

  
  The offset within the page is the least significant 12 bits, i.e.,
  406\hex.
  
  The page number is the next 10 bits, i.e., 21\hex.  Note that the
  only allowable page numbers are 0 to 3F\hex, since the process has
  been allocated pages in the range 20000000\hex--2003FFFF\hex.  If
  any address used by this process were outside that range, the \OS
  would terminate the process with a segmentation fault.
  
  The most significant ten bits give the directory:

  \begin{tabular}[t]{cccccccc}
    2 & 0 & 0 & 2 & 1 & 4 & 0 & 6\\
    0010 & 0000 & 0000 & 0010 & 0001 & 0100 & 0000 & 0110
  \end{tabular}

  If you count the ten most significant bits, you get
  0010\,0000\,00\bin, i.e., 80\hex.

\item[The Compaq Alpha architecture uses a three-level paging system:]
  \label{que:compaq-alpha}The Compaq Alpha processor has 64-bit
  virtual addresses, and a 64-bit data bus.  It also has 8\,kB pages.
  There are a lot of 8\,kB pages in $2^{64}$ bytes: $\mbox{8\,kB} =
  2^{13}$ bytes, so we have $2^{64} \div 2^{13} = 2^{64-13=51}$ pages.
  Each page must have one page table entry.  So we would need $2^{51}
  = \mbox{}$2,251,799,813,685,248 page table entries.  This is too
  many to fit in a two-level paging system, so the Alpha memory
  management system uses three level paging.
  \begin{figure}[htb]
    \centering%
    \includegraphics[width=0.55\columnwidth]{three-level-paging-example}
    \caption{A three-level paging system.}
    \label{fig:three-level-paging}
  \end{figure}
  
\item[Linux uses a three-level paging system:] Since some
  architectures, such as the Compaq Alpha architecture, use
  three-level paging, to ensure portability, Linux implements a
  three-level paging system.
\end{description}

\subsection{Types of Operating System}
\label{sec:types-of-os}

\begin{description}
\item[Types of OS] There are four main types of operating system
  (according to Andrew Tanenbaum, \emph{Modern Operating Systems}):
  \begin{description}
  \item[Monolithic OS] is an OS where there is one level of privelege,
    and where all kernel functions execute in the same address space.
    Andrew described this organisation as ``the big mess'' which would
    be very hard to port to new architectures.
    
  \item[Layered Kernel] is an organisation where the kernel is divided
    into different layers, where a special system call is required to
    communicate between each layer.  Each layer may have a different
    level of \emph{privelege}.  However, there is some overhead in
    communicating between each layer, and dividing operating system
    functions into layers that minimise communication between the
    layers is hard.
    
  \item[Microkernel client-server] is an organisation where as much of
    the OS function is done in ``user space'' servers rather than in
    the priveleged level of the kernel.  The kernel mainly routes
    requests from client programs to these user-space servers.  This
    should result in a much more portable OS with a very small kernel.
    
  \item[Virtual Machine] is another organisation for operating
    systems; most famous example is IBM 390 mainframe.  Now it runs
    Linux on hundreds or thousands of virtual machines with virtual
    hardware.  If one virtual machine crashes, no problem to other
    virtual machines.  The crashed virtual machine can simply be
    rebooted without affecting any others.  
    
    The main advantage is that the peak demands on all the servers can
    be averaged out.  Normally, a smaller server must be made powerful
    enough to handle peak demand.  Most of the time, this extra
    capacity is unused.  With hundreds of virtual servers, some
    virtual servers can meet peak demands (and so get more processing
    power from the mainframe), while others that have less than
    average demand can use less \CPU power from the mainframe.  In
    this way, the total \CPU power of the mainframe can be less than
    the total \CPU power of many racks of smaller servers, (and
    require much less electrical power, less air-conditioning and
    cooling, and less physical space), but still meet all the peak
    demands placed on the individual virtual servers.
    
    VMware provides software equivalent of a virtual machine.  IBM 390
    has hardware support.
  \end{description}

\item[Andy was wrong!] Linux has a \emph{monolithic} organisation,
  whereas Windows NT/2000 has a microkernel organisation.  Andrew
  Tanenbaum argued with Linus Torvalds about the design of Linux for a
  long time.  However, history has shown that Andy was wrong in some
  respects.
  
  The Linux kernel is much smaller and simpler than the Windows
  kernel, and is far easier to understand.  The Linux kernel divides
  the hardware control into dynamically loadable kernel modules.
  Linux runs on a huge number of hardware platforms; Windows has
  reduced the number of platforms it can run on to one.
\end{description}

\section{Questions}
\label{sec:questions}

\subsection{Memory Management}
\label{sec:memory-management-questions}

\begin{enumerate}
  \item What is \emph{virtual memory}?
    \LinesForWriting{2}{Virtual memory is a method of managing memory
      automatically by the operating sytem so that the combined size
      of memory available to all processes running on the computer may
      be more than the physical memory available by using the hard
      disk to hold what is not in physical memory.}

\item Why do we need memory
  management?\LinesForWriting{4}{Because programs grow as
    fast as \RAM becomes cheaper, and because sometimes we need to run
    programs that need more \RAM than we actually have.  We need
    \emph{virtual memory}.  Virtual memory removes the need for the
    programmer to be aware of the details of what memory a particular
    system will provide to each program.}

\item What is a \emph{Memory Management Unit} (\acro{MMU})?
    \LinesForWriting{2}{A memory management unit is hardware that maps
      virtual addresses onto physical memory.  The \MMU is connected as
      shown in figure~\vref{fig:mmu}.\\
%%       \begin{figure}[htb]
%%         \centering%
%%         \includegraphics[width=0.5\columnwidth]{mmu}
%%         \caption{The memory management unit is shown here converting virtual addresses from the \CPU to physical addresses.}
%%         \label{fig:mmu}
%%       \end{figure}
      }

    \item Paging in a virtual memory system allows nearly all contents
    of \RAM to be paged to and from the hard disk.  However, there
    must be some pages that are never swapped to disk.  List one
    example, and give reasons.%
    \LinesForWriting{3}{}
    
  \item For a hypothetical computer architecture, the following
    assumptions are made:
    \begin{itemize*}
    \item we are using two-level paging;
    \item the virtual addresses are 64 bits in size;
    \item size of a page is 8\,kB;
    \item size of both a page table entry, and also a directory table
      entry is 8 bytes;
    \item the size of the directory table and page table are as close
      to each other as possible,
    \end{itemize*}
    calculate the size of the page directory and page table, in
    bytes.  Note: they will need to be bigger than a single page.
    \LinesForWriting{4}{}

    
  \begin{figure}[htb]
    \centering%
    \includegraphics[width=0.55\columnwidth]{multilevel-paging-example-labeled}
    \caption{An example of an Intel two-level paging system.}
    \label{fig:multilevel-example-paging}
  \end{figure}
\item Figure~\vref{fig:multilevel-example-paging} shows an example of
  an Intel two-level memory management system, with both page
  directory entries and page table entries occupying four bytes.  Some
  values are shown.  If this shows a snapshot of the system while a
  program accesses a character variable,
    \begin{enumerate}
    \item What is the address of the variable as the program sees
      it?\\ \answerbox{The virtual address, 0x20021406}
    \item What is the address of the coloured entry in the directory
      table?\\ \answerbox{The \CPU register + directory index $\times$
      size of page directory entry = af0000\hex$\mbox{} + 80\hex
      \times 4 = \mbox{}$af0200\hex.}
  \item What is the address of the coloured entry in the page table?\\ 
    \answerbox{The content of the page directory entry + page index
      $\times$ size of page table entry = 110ff000\hex$\mbox{} +
      21\hex \times 4 = \mbox{}$110ff084\hex.}
  \item What is the physical address of the variable?\answerbox{The
      content of the page table entry + offset = 11a00000\hex$\mbox{}
      + 406\hex = \mbox{}$11a00406\hex.}
    \item What is the content of the variable?\answerbox{The content
    of the current location in the page, 2a\hex = 42.}
    \end{enumerate}
\end{enumerate}

\subsection{Deadlock}
\label{sec:deadlock-questions}

\begin{enumerate}
\item What is \emph{deadlock} in the context of a computer operating
    system?%
    \LinesForWriting{2}{%
      \emph{Deadlock} is a condition where a set of processes are each
      waiting for a resource that is being exclusively held by another
      process in the set.
%
      }
    
    \item \label{que:conditions-for-deadlock}List four conditions for
      deadlock to occur in a computer's
    operating system.%
    \LinesForWriting{4}{%
      \begin{description}
      \item[Mutual exclusion] where only one process can use a
        resource at one time
      \item[Hold and wait:] processes holding resources given earlier
        can request new resources
      \item[No preemption] resources given to a process cannot be
        forcibly taken away by the operating system
      \item[Circular wait:] where each process is waiting for a
        resource held by another
      \end{description}
%
      }

    \begin{figure}[htb]
      \centering%
      \begin{minipage}[t]{0.1\columnwidth}
\begin{verbatim}
Process P
...
Get A
...
Get B
...
Release A
...
Release B
...
\end{verbatim}
      \end{minipage}%
      \hspace{0.1\columnwidth}%
      \begin{minipage}[t]{0.1\columnwidth}
\begin{verbatim}
Process Q
...
Get B
...
Get A
...
Release B
...
Release A
...
\end{verbatim}
      \end{minipage}
      \caption{Two processes that can deadlock.}
      \label{fig:deadlock}
    \end{figure}
  \item Two processes are shown in figure~\vref{fig:deadlock}.
    \begin{enumerate}
    \item Show some steps that each process can take so that
      deadlock must happen.%
      \LinesForWriting{4}{%
        There are two different main scenarios where deadlock can
        occur, here is one:
        \begin{description}
        \item[1] Process P gets resource A
        \item[2] Process Q gets resource B
        \item[3] Process P requests resource B
        \item[4] Process Q requests resource A
        \end{description}
        and here is the other:
        \begin{description}
        \item[1] Process Q gets resource B
        \item[2] Process P gets resource A
        \item[3] Process Q requests resource A
        \item[4] Process P requests resource B
        \end{description}
        In fact, steps 3 and 4 could take place in either order, it
        doesn't affect the fact that we have deadlock.
%
        }
      
      \item Explain one method that you could use to avoid any
        possibility of these two processes being deadlocked.%
      \LinesForWriting{4}{%
        There are many methods---see the lecture notes.  They all
        depend on removing one or more of the conditions for deadlock
        described in question~\vref{que:conditions-for-deadlock}.  I
        include a number of methods here:
        \begin{description}
        \item[Prevent Circular wait:] order the allocation of
          resources so that they are always allocated in the same
          order.  So if \emph{both} P and Q \texttt{Get A}, then
          \texttt{Get B}, then \texttt{Release A}, then
          \texttt{Release B}, circular wait is eliminated, and
          there is no deadlock.

        \item[Prevent mutual exclusion:] here we prevent the first
          condition.  In most cases, this is not a choice; a resource
          can either be shared or it cannot.  However, if both process
          P and process Q can both hold A or both hold B, then there
          is no deadlock.
        \item[Prevent hold and wait:] here we do not allow either
          process P or process Q to proceed until it has all the
          resources it needs.

          Alternatively, we could modify either P or Q so that it does
          not hold two resources at a time.  Then deadlock is
          impossible.  We could modify P as shown in
          figure~\vref{fig:no-hold-and-wait}.  Note that in this
          example, Q is not changed at all.
          
        \item[Allow preemption:] If the \OS can forcibly remove A from
          process P, then process Q can continue.  Similarly if the
          \OS removes B from Q, then process P can continue, and there
          is no deadlock.
        \end{description}
%
        }
  \end{enumerate}
  \ifthenelse{\boolean{Solutions}}{%
    \begin{figure}[htb]
      \centering%
      \begin{minipage}[t]{0.1\columnwidth}
\begin{verbatim}
Process P
...
Get A
...
Release A
...
Get B
...
Release B
...
\end{verbatim}
      \end{minipage}%
      \hspace{0.1\columnwidth}%
      \begin{minipage}[t]{0.1\columnwidth}
\begin{verbatim}
Process Q
...
Get B
...
Get A
...
Release B
...
Release A
...
\end{verbatim}
      \end{minipage}
      \caption{Two processes that can can \emph{not} deadlock
        because one of the processes does not hold one resource
        while waiting for another.}
      \label{fig:no-hold-and-wait}
    \end{figure}
%
   }{}
   
 \item A client-server application has at least two processes, each on
   a different computer.  The client makes requests of the server, the
   server responds by transferring data over the network to the
   client.  Generally, the client will initiate the requests; the
   server does not initiate any requests.  However, both the client
   and the server perform two way communication over the network.

   Describe how a client-server application can be deadlocked.

\par%
\fbox{%
  \begin{minipage}[t][6cm]{\linewidth}
    \mbox{}
  \end{minipage}%
}
\end{enumerate}
\end{document}