\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}