1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
\documentclass[10pt,a4paper]{article}
\usepackage[margin=2cm]{geometry}
\usepackage{pdfpages}
% textcomp package is not available everywhere, and we only need the Copyright symbol
% taken from http://tex.stackexchange.com/a/1677/23992
\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}}
\usepackage{fancyhdr}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\fancyhead{}
\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
\pagestyle{fancy}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{enumitem}
\setenumerate[1]{label=\alph*.}
\setenumerate[2]{label=(\roman*)}
\parindent0pt
\title{Operating Systems - assignment 6}
\author{Camil Staps\\\small{s4498062}}
\begin{document}
\maketitle
\thispagestyle{fancy}
\section*{8.1}
\begin{enumerate}
\item Given a virtual address $a$ with page and offset $a=(p,o)$ we find entry $p$ in the page table. This gives a page frame number $f$. We then take the physical address $f\cdot 1024 + o$.
\item \begin{enumerate}
\item Entry $1$ gives frame $7$. This gives us $7\cdot1024 + 052 = 7220$.
\item Entry $2$ does not correspond to a frame, so this address is invalid.
\item Entry $5$ gives frame $0$. This gives us $0\cdot1024 + 499 = 499$.
\end{enumerate}
\end{enumerate}
\section*{8.2}
\begin{enumerate}
\item The \texttt{j} variable doesn't generate page faults because for all $n$ all $A[n,i]$ are in the same page (and the same for $B$ and $C$). The \texttt{i} variable generates page faults every four iterations, and then for every array. This gives us a total of $\frac34$ page faults per addition executed.
\item Yes, the indices should be swapped (e.g. $C[j,i]$ instead of $C[i,j]$).
\item Every four iterations of $j$, that is, $16$ per array or $48$ in total. That gives a frequency of $48/64^2 = \frac3{256} \approx 0.0117$.
\end{enumerate}
\section*{8.4}
See the next page.
I don't count the first three references. The optimal algorithm has $6$ page faults over $17$ references, which is approximately $35\%$. The FIFO algorithm has $10$ page faults on the same number of references, approximately $59\%$. The LRU algorithm has $7$ page faults, approximately $41\%$.
\includepdf{exercise-8-4.pdf}
\end{document}
|
