%\documentclass[colorBG,slideColor,troispoints,pdf]{prosper}
\documentclass[colorBG,total,slideColor,pdf]{prosper}
%\documentclass[colorBG,slideColor,ps]{prosper}

\usepackage{alltt,key,xr,cols,rcs,acro,nick,%
  graphicx,varioref,explanation,booktabs,multicol}
\usepackage[nolineno,noindent]{lgrind}

%\definecolor{green}{rgb}{0,1,0}

\RCS $Revision: 1.0 $

\renewcommand*{\bs}{\texttt{\char '134}} % Backslash `\'
%\newcommand*{\labTitle}{LDAP Directories}1
\newcommand*{\subject}{Operating Systems and Systems Integration}
\newcommand*{\emphcolour}[1]{\emph{\red#1}}

\providecommand*{\RPM}{\acro{RPM}\xspace}
\providecommand*{\CD}{\acro{CD}\xspace}
\providecommand*{\IPC}{\acro{IPC}\xspace}
\providecommand*{\UID}{\acro{UID}\xspace}
\providecommand*{\GID}{\acro{GID}\xspace}
\providecommand*{\SMP}{\acro{SMP}\xspace}
\providecommand*{\API}{\acro{API}\xspace}
\providecommand*{\OK}{\acro{OK}\xspace}
\providecommand*{\IETF}{\acro{IETF}\xspace}
\providecommand*{\MS}{\acro{MS}\xspace}
\providecommand*{\LILO}{\acro{LILO}\xspace}
\providecommand*{\HCI}{\acro{HCI}\xspace}
\providecommand*{\KDE}{\acro{KDE}\xspace}
\providecommand*{\MBR}{\acro{MBR}\xspace}
\providecommand*{\BSD}{\acro{BSD}\xspace}
\providecommand*{\GPL}{\acro{GPL}\xspace}
\providecommand*{\MB}{\acro{MB}\xspace}

\title{\mbox{}\blue{}Memory Management}%
\subtitle{How does the Operating System manage memory?}
\author{Nick Urbanik \texttt{<nicku(at)vtc.edu.hk>}\\
  \footnotesize{}Copyright Conditions: GNU FDL (see
  \url{http://www.gnu.org/licenses/fdl.html})}%
\institution{Department of Information and Communications Technology}%
\slideCaption{OSSI --- Memory Management --- ver. \RCSRevision}
\Logo{\includegraphics[width=15mm]{ict-logo-smaller}}


\begin{document}
\maketitle

\begin{slide}{Why memory management?}
  \begin{itemize}
  \item Memory gets cheaper
  \item Programs get bigger:
    \begin{quote}
      ``Programs expand to fill the memory available to hold them''
    \end{quote}
  \item Memory is nearly always precious
  \end{itemize}
\end{slide}

\begin{slide}{Issues of memory management}
  \begin{itemize}
  \item If run out of memory
    \begin{itemize}
    \item cannot start a new process, or
    \item process cannot continue
    \end{itemize}
  \item Often, all memory is used.
  \item How solve this?
    \begin{itemize}
    \item Buy more memory
    \item Use the hard disk to simulate more memory
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Virtual memory}
  \begin{itemize}
  \item \emphcolour{Virtual memory} uses the hard disk to simulate \RAM
  \item Windows:
    \begin{itemize}
    \item swap file
    \end{itemize}
  \item Linux can use:
    \begin{itemize}
    \item swap file(s) or
    \item swap partition(s)
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Swapping}
  \begin{itemize}
  \item Where the \emphcolour{entire} memory used by each process is:
    \begin{itemize}
    \item swapped in (from disk to \RAM), or
    \item swapped out (from \RAM to disk)
    \end{itemize}
  \item The unit that is written to or from the disk is the process
  \item Problems:
    \begin{itemize}
    \item Gaps between used \RAM may be too small to use, so they are
      wasted
      \begin{itemize}
      \item This problem is called \emphcolour{fragmentation}
      \item A consequence of units written to or from the hard disk
        having \emphcolour{different sizes}
      \item Gaps are called ``holes''
      \end{itemize}
    \item Swapping a big process is too inefficient, it takes too long
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Fragmentation of \RAM}
  \begin{center}
    \includegraphics[width=0.9\slideWidth]{holes}
  \end{center}
\end{slide}

\begin{slide}{Paging}
  \begin{itemize}
  \item Modern OS uses \emphcolour{paging}
  \item Each process uses fixed sized chunks of memory called
    \emphcolour{pages}
  \item \emphcolour{All} the virtual memory is divided into pages
  \item The {\green{}pages do not have to be contiguous} (all
    physically next to each other), so no holes
  \item Each process has its own \emphcolour{virtual}
    \emphcolour{address space}
  \item Hardware maps from virtual addresses to real addresses
  \end{itemize}
\end{slide}

\begin{slide}{\MMU: Memory Management Unit}
  \begin{itemize}
  \item All desktop systems use hardware called a \emphcolour{MMU}
  \item Quickly maps \emphcolour{virtual addresses} to real addresses
    (corresponding to voltages on the physical \RAM address pins)
  \item \emphcolour{Hardware} specific to \CPU organisation
  \end{itemize}
\end{slide}

\begin{slide}{Memory Management Unit}
  \begin{center}
    \includegraphics[width=\slideWidth]{mmu}
  \end{center}
\end{slide}

\begin{slide}{Basic idea of paging: page tables}
  \begin{itemize}
  \item Virtual address has two parts:
  \item \emphcolour{Page number}
  \item \emphcolour{Page offset}
  \item Each \emphcolour{page table entry} is physical address of
    start of page
  \end{itemize}
\end{slide}

\begin{slide}{Page tables}
  \begin{center}
    \includegraphics[width=0.75\slideWidth]{paging}
  \end{center}
\end{slide}

\begin{slide}{The \MMU does the arithmetic}
  \begin{itemize}
  \item The Memory Management Unit performs the arithmetic very
    quickly
  \item Contains special registers to store page table entries
  \end{itemize}
\end{slide}

\begin{slide}{Problems}
  \begin{itemize}
  \item If:
    \begin{itemize}
    \item each page is 4\,KB, and
    \item virtual memory addresses are 32 bits,
    \end{itemize}
  \item Then need page tables with $32 - 12 = 20$ bit indexes
  \item Need page tables to contain $2^{20}$ (more than a million) entries
  \item Require lots more \RAM!
  \end{itemize}
\end{slide}

\begin{slide}{Multilevel paging}
  \begin{center}
    \includegraphics[width=0.8\slideWidth]{multilevel-paging}
  \end{center}
\end{slide}

\begin{slide}{Page faults}
  \begin{itemize}
  \item What if application asks for a page not in \RAM?
  \item CPU gets a \emphcolour{page fault exception}
  \item Operating system decides how to handle this
  \item Could also occur if process tries to access \RAM outside of
    its allocation of pages
  \end{itemize}
\end{slide}

\begin{slide}{Paging on Intel x86 --- 1}
  \begin{itemize}
  \item 
    \begin{tabular}[t]{@{}lll@{}}
      Bits 31\ldots22: & Directory:  & 10 bits \\
      Bits 21\ldots12: & page table: & 10 bits \\
      Bits 11\ldots0:  & offset:     & 12 bits
    \end{tabular}
  \end{itemize}
\end{slide}

\begin{slide}{Paging on Intel x86 --- 2}
  \begin{itemize}
  \item Page directory, page table entries contain:
    \begin{itemize}
    \item Present flag: 1 if in \RAM, 0 if paged out
    \item 20 MS\,bits of page frame physical address
    \item Dirty flag (page table only): set when the page is written to
    \item Access rights info
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Example of paging: Intel x86}
  \begin{itemize}
  \item Dir: 10 bits, table: 10 bits, offset 12
  \item Say kernel assigns 64 pages to a process: 0x20000000 to
    0x2003f{}f{}f{}f
  \item We don't care about the physical address
  \item Virtual address = 0x20021406
  \item We are determining the offset within the page for this
    address, the page number, and the value of the directory entry
  \item 10 most significant bits = 0x080
  \item Middle 10 bits = 0x21 = 33
    \begin{itemize}
    \item Note: can only be in range 0 to 63 decimal
    \end{itemize}
  \item Offset 0x406
  \end{itemize}
\end{slide}

\begin{slide}{Intel Paging Example}
  \begin{center}
    \includegraphics[width=0.8\slideWidth]{multilevel-paging-example}
  \end{center}
\end{slide}

\begin{slide}{The Arithmetic}
  \begin{itemize}
  \item Note: 0xnnnn is the notation in the C programming language for a
    hexadecimal number nnnn\hex
  \item Most significant 12 bits is 0x{\blue{}20}{\cyan{}0}
  \item in binary: {\blue{}0010\,0000\,00}{\green{}00}
  \item the ten MS bits are {\blue{}00\,1000\,0000}
  \item In Hex, that's {\blue{}0x80}
  \item 0x{\blue{}20}{\cyan{}0}{\green{}21}{\red{}406} =
    {\blue{}0010\,0000\,00}{\green{}00\,0010\,0001}\,{\red{}0100\,0000\,0110}
\end{itemize}
\end{slide}

\begin{slide}{Paging Example (continued)}
  \begin{itemize}
  \item If present flag is 0, page not in \RAM
  \item \emphcolour{Page exception} is generated
  \item Operating system then decides what to do:
    \begin{itemize}
    \item Start to read page into \RAM
    \item (Probably) schedule new process
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Linux uses three level paging}
  \begin{itemize}
  \item Linux runs on many other architectures than Intel
  \item Alpha hardware implements 3 level paging
  \item Linux uses 3 level paging for ease of porting to other architectures
  \end{itemize}
\end{slide}

\begin{slide}{Three Level Paging}
  \begin{center}
    \includegraphics[width=0.9\slideWidth]{three-level-paging-example-2}
  \end{center}
\end{slide}

\begin{slide}{Alpha Memory Management}
  \begin{center}
    \includegraphics[width=\slideWidth]{three-level-paging-zeros-at-top}
  \end{center}
\end{slide}

\begin{slide}{Hewlett-Packard Alpha}
  \begin{itemize}
  \item The Alpha is a 64-bit \CPU
  \item page frames are 8\,KB long, offset is 13 bits
  \item Only least significant 43 bits of address are used (most
    significant bits all zero)
  \item Three level of page tables, so remaining 30 bits of address
    split into three 10-bit fields.  So page tables each hold
    $2^{10}=1024$ entries
\end{itemize}
\end{slide}

\begin{slide}{Memory management policies}
  \begin{itemize}
  \item If low on \RAM, which pages should be written to disk?
  \item How decide which pages to read from disk for a process just
    starting to run again?
  \end{itemize}
\end{slide}
\end{document}