\documentclass[solutions]{ictlab}% DO NOT EDIT---WILL BE OVERWRITTEN

\usepackage[pdfpagemode=UseNone,pdfauthor={Nick Urbanik}]{hyperref}

\RCS $Revision: 1.1 $

\usepackage{alltt,key,color,answer2,version,float,biganswerbox}

%\usepackage[nolineno,noindent]{lgrind}
%\usepackage[leftnum,lineno5,noindent]{lgrind}
\renewcommand*{\subject}{Operating Systems and Systems Integration}

\newcommand*{\labTitle}{Memory Management Tutorial}

\definecolor{light-blue}{rgb}{0.4,0.4,1}
\newcommand*{\gl}[1]{\textcolor{light-blue}{#1}} % good link
\newcommand*{\ex}[1]{\textcolor{green}{#1}} % executable file
\newcommand*{\bl}[1]{\colorbox{red}{\textcolor{white}{\textbf{#1}}}} % bad link

\renewcommand{\floatpagefraction}{0.75} % default is .5, to increase
% density.
\renewcommand*{\bottomfraction}{0.6} % default is 0.3
\renewcommand*{\topfraction}{0.85} % default is 0.7
\renewcommand*{\textfraction}{0.1} % default is 0.2

\setlength{\extrarowheight}{1pt}
\floatstyle{ruled}
\floatname{program}{Program}
\newfloat{program}{tbh}{lop}
\renewcommand*{\marks}[1]{}



\newlength{\questionboxheight}
\setlength{\questionboxheight}{2.2cm}

\begin{document}
  \begin{enumerate}
  \item 
    \begin{enumerate}
    \item \marks{2}Compare \emph{swapping} with \emph{paging}.
      
      \begin{biganswerbox}[1.5cm]%
        \begin{solution}%
          \begin{itemize*}
          \item \emph{Swapping} involves changing \emph{all} the \RAM
            associated with a process to disk when more \RAM is
            required by other processes.
      
          \item \emph{Paging} involves writing \emph{pages}, which may
            be \emph{part} of a process' \RAM usage.
        
          \item If swapping is performed without paging, then since
            the memory blocks may be of different sizes, holes in the
            allocatable \RAM may arise that cannot be allocated until
            an adjacent memory block is freed.
          \end{itemize*}
        \end{solution}
      \end{biganswerbox}
   
    \item \marks{2}Swapping is still used together with paging.
      Explain why.
      
      \begin{biganswerbox}
        \begin{solution}%
          For large processes that consume large amounts of \RAM,
          swapping is not a good option, since the delay while
          changing large amounts of \RAM to and from the disk will
          cause the system to apparently freeze from time to time for
          rather too long.
        
          But for small processes, swapping makes sense, since there
          is no point keeping a fraction of the \RAM required for a
          small process when more \RAM pages must be read in before it
          can run.  So virtual memory systems favour paging out all of
          a small process rather than a part, when memory needs to be
          freed.
        \end{solution}
      \end{biganswerbox}
      
     \item \marks{2}Explain the term \emph{dirty page} in a paging system.
      
       \begin{biganswerbox}[8mm]%
         \begin{solution}%
           A page is \emph{dirty} if it has been modified.
         \end{solution}
       \end{biganswerbox}
       
    \item \marks{1}Give one simple example of the use of a read-only
      memory page.
      
       \begin{biganswerbox}[8mm]%
         \begin{solution}%
           Executable code of a running program is stored in a
           read-only page.
         \end{solution}
       \end{biganswerbox}
    
     \item \marks{1}State one major difference between how a paging
       system deals with a read-only page compared with how it deals
       with a read-write page.
      
       \begin{biganswerbox}[10mm]%
         \begin{solution}%
           A read-only page does not need to be written to the disk if
           it is paged out, whereas if a read-write page is dirty, it
           must be written to swap before the memory can be allocated
           to another process.
         \end{solution}
       \end{biganswerbox}
     \end{enumerate}
 
\item Referring to figure~\ref{fig:two-level-paging}, briefly define the
    following terms:
    \begin{enumerate}
    \item \marks{2}\emph{page}

      \begin{biganswerbox}[10mm]%
        \begin{solution}%
          A page is a block of data or machine instructions that may
          be stored in a page frame in memory or be stored on the hard
          disk.  The data belongs to a process.  The computer's memory
          is divided into pages and is managed by the virtual memory
          system through the \acro{MMU}.
        \end{solution}
      \end{biganswerbox}
      
    \item \marks{2}\emph{page table}
      
      \begin{biganswerbox}[10mm]%
        \begin{solution}%
          A \emph{page table} is a an array of data structures that
          contain information about page frames.  Typical of the data
          in each entry: 20 most-significant bits of page frame
          address (a 4\,KB page frame will start at an address with
          the 12 least-significant bits all zero), and various bit
          flags that indicate conditions of the page.
        \end{solution}%
      \end{biganswerbox}
      
  \item In figure~\vref{fig:two-level-paging}, there are additions
    performed indicated by a circle with a `$+$' inside.  Where and
    why is this arithmetic performed?


    \begin{biganswerbox}[10mm]%
      \begin{solution}%
        Where: in the memory management unit (\MMU).  The \MMU is
        special hardware that can perform these additions very
        quickly.
        
        Why: The programs written by the programmer use virtual
        addresses, but in order to execute, these virtual addresses
        must be rapidly mapped to physical addresses that access
        particular locations within particular memory chips.
      \end{solution}
    \end{biganswerbox}
    
    \begin{figure}[h]
    \centering%
    \includegraphics[width=0.5\linewidth]{two-level-paging}
    \caption{A method of paging.}
    \label{fig:two-level-paging}
  \end{figure}
    \end{enumerate}
  \item A computer system has sixteen kilobyte pages and a 64-bit
    address bus, and 64-bit virtual addresses.  In both the page
    table, and the page directory, entries are eight bytes in size.
    The system is shown in figure~\vref{fig:two-level-paging}.  The following
    five parts of this question refer to this computer system.
    \begin{enumerate}
    \item \marks{2}Calculate the number of bits required for the
      offset part of the virtual address, showing your working.

    \begin{biganswerbox}[8mm]%
      \begin{solution}%
        16\,kB$\mbox{} = 2^{14}$ bytes, so there must be 14 bits.
      \end{solution} 
    \end{biganswerbox}
    
    \item \marks{3}Calculate the number of page table entries that are
      required.

      \begin{biganswerbox}[8mm]%
        \begin{solution}%
          We have 64 bits total, so we have $64 - 14 = 50$ bits
          remaining to select a page, hence there must be $2^{50} =
          \mbox{}$1,125,899,906,842,624 pages, each with its own page
          table entry.
        \end{solution}
      \end{biganswerbox}
      
    \item \marks{3}If the page directory and page table are as nearly
      the same size as possible, determine the amount of \RAM required
      to hold each one.

      \begin{biganswerbox}[10mm]%
        \begin{solution}%
          We have $64 - 14 = 50$ bits to share between them.  Since
          both are the same size, and entries are the same size, then
          each has $50 \div 2 = 25$ bits to index each table.  The
          size is then $2^{25} \times 8 = 2^{25 + 3} = 2^{28} =
          \mbox{}$268,435,456 bytes, i.e., a quarter of a gigabyte,
          each, or half a gigabyte total.
        \end{solution}
      \end{biganswerbox}
      
    \item \marks{3}\label{que:problem-with-two-level-paging}Briefly
      list one major problem with the paging scheme shown in
      figure~\ref{fig:two-level-paging} when used with this computer
      system.
      

      \begin{biganswerbox}[8mm]%
        \begin{solution}%
          It is impractical to dedicate half a gigabyte of \RAM to a
          page directory and page table.
        \end{solution}
      \end{biganswerbox}
      
    \item \marks{5}Explain with the aid of a diagram an
      alternative paging method that overcomes the problem you listed
      in the previous part \ref{que:problem-with-two-level-paging}.
      Show how your design overcomes the problem.
      
      \begin{biganswerbox}[5cm]%
        \begin{solution}%
          Three or four levels of paging tables should be used here,
          as in figure~\vref{fig:three-level-paging}.  For a 64-bit
          address space, but with only 16\,KB pages, a three level
          paging system is essential.  If all three tables are about
          the same size, then we have $50 \div 3 = 16.6$, so two
          tables have $2^{17}$ entries, while one has $2^{16}$
          entries.  At eight bytes per entry, then we need a total of
          $2 \times 2^{20} + 2^{19} = \mbox{}$2621440 bytes, a more
          manageable size.  If we go for a four level design, then the
          page tables can be smaller still.  The design requires
          hardware in the memory management unit to support it.
        \end{solution}
      \end{biganswerbox}
      \begin{solution}
        \begin{figure}[htb]
          \centering%
          \includegraphics[width=0.7\linewidth]{three-level-paging}
          \caption{A three level paging system.}
          \label{fig:three-level-paging}
        \end{figure}
      \end{solution}
    \end{enumerate}

  \item
    \begin{enumerate}
    \item \marks{2}List TWO important functions of a paging system in
      an operating system.
      
      \begin{biganswerbox}[2cm]%
        \begin{solution}%
          \begin{itemize*}
          \item Allow applications to run that need more memory than
            is physically available
            
          \item Allow processes to run when only part of the code is
            in memory
            
          \item programs can be relocatable
            
          \item processes can share a single memory image of a library
            or program
            
          \item Allow each program to have its own address space.
          \end{itemize*}
        \end{solution}
      \end{biganswerbox}
      
   \end{enumerate}
    
%%   \item Referring to figure~\ref{fig:paging}, briefly define the
%%     following terms:
%%     \begin{enumerate}
%%     \item \marks{2}\emph{page}

%%       \begin{solution}%
%%     \item[\textbf{Solution:}]A page is a block of data or machine instructions
%%       that may be stored in a page frame in memory or be stored on the
%%       hard disk.  The data belongs to a process.  The computer's
%%       memory is divided into pages and is managed by the virtual
%%       memory system through the \acro{MMU}. 
%%     \end{solution}
    
%%     \item \marks{2}\emph{page table}

%%       \begin{solution}%
%%     \item[\textbf{Solution:}]A \emph{page table} is a an array of data
%%       structures that contain information about page frames.  Typical
%%       of the data in each entry: 20 most-significant bits of page
%%       frame address (a 4\,KB page frame will start at an address with
%%       the 12 least-significant bits all zero), and various bit flags
%%       that indicate conditions of the page. 
%%     \end{solution}
    
    \begin{figure}[h]
      \centering%
      \includegraphics[width=0.5\linewidth]{paging-q}
      \caption{A method of paging.}
      \label{fig:paging}
    \end{figure}
  \item A computer system has eight kilobyte pages and a 64-bit address
    bus.  The following three parts of this question refer to this computer
    system.
    \begin{enumerate}
    \item \marks{3}Calculate the number of page table entries that are
      required.

      \begin{biganswerbox}[10mm]%
        \begin{solution}%
          This is single-level paging.  With 8\,KB pages,
          $\log_{2}8192 = 13$ bits are used for the offset within the
          page, and $64 - 13 = 51$ bits are used to select the page.
          There will be $2^{51} \approx 2.2518\times 10^{15}$ pages,
          so there will be $2.2518\times 10^{15}$ entries in the page
          table.
        \end{solution}
      \end{biganswerbox}
      
    \item \marks{2}\label{que:problem-with-single-level-paging}Briefly
      list one major problem with the paging scheme shown in
      figure~\ref{fig:paging}.
    
       \begin{biganswerbox}[15mm]%
         \begin{solution}%
           If each entry in the page table occupies 32-bits, then the
           page table will occupy about $9\times 10^{15}$ bytes of
           \RAM, which is more than any computers now have.  The
           active page table must be in physical memory, so $9\times
           10^{15}$ bytes of \RAM would need to be always used for the
           page table.  This is \emph{way} too much overhead, and just
           is impractical.
         \end{solution}
       \end{biganswerbox}
       
    \item \marks{5}Explain with the aid of a diagram an alternative
      paging method that overcomes the problem you listed in the
      previous part \ref{que:problem-with-single-level-paging}.

      \begin{biganswerbox}[5cm]%
        \begin{solution}%
          Three (or perhaps four) levels of paging tables should be
          used here, as in figure~\vref{fig:three-level-paging}.  Note
          that for a 64-bit address space, but with only 8\,KB pages,
          a three (or four) level paging system will be preferable.
          The Alpha architecture has a three level design, but only 43
          of the 64-bit virtual address are actually used; the 21
          most-significant bits are all zero.
        \end{solution}
      \end{biganswerbox}
    \end{enumerate}
\end{enumerate}
\end{document}
