% $Id: miunasgn.tex 185 2013-10-23 15:13:30Z danbos $
% Author: Daniel Bosk <daniel.bosk@miun.se>
\documentclass[a4paper]{miunasgn}
\usepackage[utf8]{inputenc}
\usepackage[swedish,english]{babel}
\usepackage{url,hyperref}
\usepackage{prettyref,varioref}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[binary,amssymb]{SIunits}
\usepackage[nofancy,today]{svninfo}
\usepackage[style=alphabetic,natbib=true]{biblatex}
\bibliography{literature}
\usepackage[varioref,prettyref]{miunmisc}

\svnInfo $Id: miunasgn.tex 185 2013-10-23 15:13:30Z danbos $

%\printanswers

\theoremstyle{definition}
\newtheorem{example}{Example}

\courseid{DT011G}
\course{Introduction to Operating Systems}
\assignmenttype{Theory assignment}
\title{Memory}
\author{Daniel Bosk\footnote{%
	This work is licensed under the Creative Commons Attribution-ShareAlike 3.0 
	Unported license.
	To view a copy of this license, visit 
	\url{http://creativecommons.org/licenses/by-sa/3.0/}.
	Some of the questions are derived from the work of 
	\citeauthor*{Silberschatz2009osc}.
}}
\date{\svnId}

\begin{document}
\maketitle
\thispagestyle{foot}
\tableofcontents


\section{Prerequisites}
\label{sec:Prerequisites}
\noindent
\input{literature.tex}


\section{Tasks}
\label{sec:Tasks}
\noindent
\begin{questions}

	%%% MEMORY %%%

	\question\label{q:addressspaces}
	Define the different address spaces
	\begin{parts}
		\part physical address space,
		\part logical address space, and
		\part virtual address space.
	\end{parts}
	\begin{solution}
		According to \citet[p. 319]{Silberschatz2009osc} the physical address space 
		is the addresses which are seen by the hardware, i.e. the actual addresses 
		in the computer system as generated by the memory management unit (MMU).

		The logical address space consists of the addresses sent to the MMU, i.e.  
		the addresses as seen by the CPU, all running processes and the programmer 
		\citep[ch. 8]{Silberschatz2009osc}.

		\citet{Silberschatz2009osc} states that ``virtual address and logical 
		adress [are used] interchangeably'' \citep[p. 319]{Silberschatz2009osc} and 
		thus the virtal address space is the same as the logical address space.
		However, virtual address space is later defined as the ``logical (or 
		virtual) view of how a process is stored in memory'' \citep[p.  
		359]{Silberschatz2009osc} and hence coincides with out definition of 
		logical address space.
	\end{solution}

	\question\label{q:segmentpaging}
	Describe the differences and similarities of paging and segmentation,
	also describe how they can be combined to complete each other.
	\begin{solution}
		According to \citet[sec. 8.4.1]{Silberschatz2009osc} is paging is 
		a technique used to divide physical memory into a set of fixed-sized frames 
		which will be mapped by pages of the same size in the logical address 
		space.
		A process will then allocate a number of pages which will be mapped to 
		frames in the physical address space.

		Segmentation on the other hand is a lot like paging except that it has 
		variable-sized pages called segments \citep[sec.  
		8.6.1]{Silberschatz2009osc}.
		To handle segments a base and limit register is used for each segment.

		As with pages, an entire segment must reside in memory for this scheme to 
		work.
		For very large segments, however, this becomes unfeasable because it might 
		require all other segments to be swapped to disk.
		Thus, if we use paging with segmentation, we can have pages as the 
		underlying scheme and then use segmentation on top of that.
		This way we can have a huge segment which does not have to reside entirely 
		in memory, only the pages we currently use.
	\end{solution}

	\question\label{q:accesstime}
	Consider a paging system where the page table is stored in memory (e.g. in 
	a process' PCB).
	\begin{parts}
		\part If a memory reference takes \unit{100}{\nano\second}, how long does 
		a paged memory reference take?
		\part If we add an associative register to keep parts of the page table in, 
		80 percent of all page references are found in this table, what is the 
		effective access time if a lookup in this register takes 
		\unit{10}{\nano\second}.
	\end{parts}
	\begin{solution}
		As the page table is in memory two memory references must be performed.
		The first one accesses the page table and the second one the actual page.
		Hence a memory access takes \unit{200}{\nano\second}.

		With the associative register the effective access time is
		\begin{eqnarray}
			P(\text{hit})\cdot (10+100) + P(\text{miss})\cdot (10+100+100) &=&
				0.80\cdot (10+100) + 0.20\cdot (10+100+100) \\
			&=& 88 + 42 = \unit{130}{\nano\second}.
		\end{eqnarray}
	\end{solution}

	\question\label{q:pagesize}
	Explain why page sizes are always a power of 2.
	(Note that this explanation can be directly mapped to why the number of host 
	addresses in a subnet is a power of 2, it makes subnet masking that much 
	easier.)
	\begin{solution}
		As we want to divide our \(N\)-bit logical address into page numbers and 
		offsets into pages, this is done in an easy manner if we break the address 
		into a certain amount of bits.
		If we have a page size of \(2^p\) bytes, then we can use the last \(p\) 
		bits in the logical address for referencing inside a page.
		The other \(N-p\) bits can be used for page numbers.
		This would not be possible if the page size was not a power of 2.

		Similarly, in IP addresses we can let the page number correspond to the 
		network part of the address and the page offset correspond to the host part 
		of the address.
		Thus, the subnet mask simply gives us the page size to use.
	\end{solution}

	%%% VIRTUAL MEMORY %%%
	
	\question\label{q:pagefaults}
	Describe the chain of events which takes place when a page fault occurs.
	Start with the process executing the instruction referencing the logical 
	address and end with the process moving on to the next instruction.
	\begin{solution}
		This is stated in detail by \citet[pp. 365-366]{Silberschatz2009osc}.
	\end{solution}

	\question\label{q:translatingaddresses}
	Imagine a computer providing a 32-bit virtual-memory space, i.e. \(2^{32}\) 
	bytes.
	The computer has a page size of 4096 bytes.
	A user process generates the virtual address \(deadbeef_{16}\).
	What is the page number and what offset in that page i referenced?
	(You must explain how you come to this conclusion.)
	\begin{solution}
		As the page size is \(2^{12}\) bytes the 12 low-order bits are used for the 
		offset in the page, in this case \(eef_{16}\).
		The remaining 20 bits, i.e. \(deadb_{16}\), are used to identify the page 
		in the page table.
	\end{solution}

	\question\label{q:thrashing}
	On one of your servers you find these, quite disturbing, statistics:
	\begin{itemize}
		\item The CPU utilization is at 20 percent,
		\item the paging disk utilization is at 98 percent\footnote{%
				This does not mean it is 98 percent full but that it is constantly read 
				from and written to.
			}, and
		\item utilization of other I/O devices is at 5 percent.
	\end{itemize}
	As this system is part of one of the heavily used compute clusters the CPU 
	utilization should be above 70 percent at all times.
	First answer what the problem with the system is and then explain how the 
	following actions will affect the statistics above.
	\begin{parts}
		\part Installing a faster CPU.
		\part Installing a bigger paging disk.
		\part Installing more main memory.
		\part Installing a faster hard disk drive\footnote{%
			Or some sort of RAID system.
		} as the paging disk.
		\part Increasing the page size.
		\part Add prepaging to the page fetch algorithms.
		\part Increasing the level of multiprogramming.
		\part Decreasing the level of multiprogramming.
	\end{parts}
	\begin{solution}
		The system is obviously thrashing, i.e. it does more page swaps than useful 
		computations and I/O rendering the system rather useless \citep[p.  
		386]{Silberschatz2009osc}.

		As the CPU is not the bottleneck in the system installing a faster one will 
		not increase utilization.
		Installing a bigger paging disk will not help either as this will not 
		affect how much it is being used.
		
		Installing more main memory however will help as more pages can be kept in 
		memory and thus decreasing the level of page swapping, meaning the system 
		will get more time to do actual work.

		Installing a faster paging disk might help a little as paging takes less 
		time giving more time to the CPU to do actual work with the data.

		Increasing the page size will work if memory access is sequential.
		However, if it is random, e.g. with a high degree of multiprogramming, it 
		will increase the number of page faults and decrease CPU utilization.
		And thus decreasing the degree of multiprogramming will yield fewer page 
		faults and higher CPU utilization whereas increasing the degree of 
		multiprogramming will make things worse.

		Adding prepaging to the page fetching algorithms will also only work if 
		access is sequential, i.e. predictable, and will hence not work if the 
		access is random.
	\end{solution}

	\question\label{q:belady}
	Describe Belady's anomaly.
	\begin{solution}
		According to \citet[p. 374]{Silberschatz2009osc}, Belady's anomaly occurs 
		for some page-replacement algorithms.
		What Belady's anomaly means is that the the page-fault rate will increase 
		as the number of allocated frames increases, which is quite the opposite of 
		what is expected.
		However, there are algorithms which are unaffected by this \citep[e.g. OPT, 
		section 9.4.3]{Silberschatz2009osc}.
	\end{solution}
\end{questions}


%%% EXAMINATION %%%
\input{examination.tex}


\printbibliography
\end{document}
