From cd0b2381922ae6679232ffcf04b598f4ac2c0b91 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Thu, 1 Oct 2015 21:55:55 +0200
Subject: Assignment 5

---
 assignment5/assignment5.tex | 112 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)
 create mode 100644 assignment5/assignment5.tex

(limited to 'assignment5/assignment5.tex')

diff --git a/assignment5/assignment5.tex b/assignment5/assignment5.tex
new file mode 100644
index 0000000..fa461d5
--- /dev/null
+++ b/assignment5/assignment5.tex
@@ -0,0 +1,112 @@
+\documentclass[10pt,a4paper]{article}
+
+\usepackage[margin=2cm]{geometry}
+\usepackage{url}
+
+% 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{tikz}
+\usepackage{pgfplots}
+
+\usepackage{enumitem}
+
+\parindent0pt
+
+\title{Operating Systems - assignment 5}
+\author{Camil Staps\\\small{s4498062}}
+
+\begin{document}
+
+\maketitle
+\thispagestyle{fancy}
+
+\section*{7.7}
+See figure \ref{fig:7-7}. At the moment I don't see how to add text inside this plot (which is itself already an ugly hack), but from left to right the memory blocks are allocated to process A, B, D and C. White blobs are free.
+
+\begin{figure}[h]
+    \centering
+    \begin{tikzpicture}[every path/.style={draw=black}]
+        \begin{axis}[
+                xbar stacked, xmin=0, xmax=512, xtick={0,64,...,512},
+                symbolic y coords={Ret C, Ret D, Ret B, Req D, Ret A, Req C, Req B, Req A, Initial},
+                ytick=data
+            ]
+            \addplot+[xbar,white]     plot coordinates {(0  ,Initial) (0  ,Req A) (0  ,Req B) (0  ,Req C) (128,Ret A) (128,Req D) (128,Ret B) (256,Ret D) (512,Ret C)};
+            \addplot+[xbar,white]     plot coordinates {(0  ,Initial) (0  ,Req A) (0  ,Req B) (0  ,Req C) (0  ,Ret A) (0  ,Req D) (64 ,Ret B) (0  ,Ret D) (0  ,Ret C)};
+            \addplot+[xbar,lightgray] plot coordinates {(0,Initial)   (128,Req A) (128,Req B) (128,Req C) (0  ,Ret A) (0  ,Req D) (0  ,Ret B) (0  ,Ret D) (0  ,Ret C)};
+            \addplot+[xbar,gray]      plot coordinates {(0,Initial)   (0  ,Req A) (64 ,Req B) (64 ,Req C) (64 ,Ret A) (64 ,Req D) (0  ,Ret B) (0  ,Ret D) (0  ,Ret C)};
+            \addplot+[xbar,white]     plot coordinates {(512,Initial) (128,Req A) (64 ,Req B) (64 ,Req C) (64 ,Ret A) (0  ,Req D) (0  ,Ret B) (0  ,Ret D) (0  ,Ret C)};
+            \addplot+[xbar,lightgray] plot coordinates {(0,Initial)   (0  ,Req A) (0  ,Req B) (0  ,Req C) (0  ,Ret A) (64 ,Req D) (64 ,Ret B) (0  ,Ret D) (0  ,Ret C)};
+            \addplot+[xbar,gray]      plot coordinates {(0,Initial)   (0  ,Req A) (0  ,Req B) (256,Req C) (256,Ret A) (256,Req D) (256,Ret B) (256,Ret D) (0  ,Ret C)};
+            \addplot+[xbar,white]     plot coordinates {(0,Initial)   (256,Req A) (256,Req B) (0  ,Req C) (0  ,Ret A) (0  ,Req D) (0  ,Ret B) (0  ,Ret D) (0  ,Ret C)};
+        \end{axis}
+    \end{tikzpicture}
+    \caption{Memory allocation to four processes using the buddy system}
+    \label{fig:7-7}
+\end{figure}
+
+\section*{7.10}
+\begin{enumerate}[label=\alph*.]
+    \item Yes, this is possible. Then you would get a buddy tree as in figure \ref{fig:7-10a}.
+
+        \begin{figure}[h]
+            \centering
+            \begin{tikzpicture}[level 1/.style={sibling distance=4cm},
+                            level 2/.style={sibling distance=2cm},
+                            level 3/.style={sibling distance=1cm},
+                            every node/.style={circle,draw}]
+                \node {8}
+                    child { node {5}
+                        child { node {3}
+                            child { node {2}
+                                child { node {1} }
+                                child { node {1} }
+                            }
+                            child { node {1}
+                            }
+                        }
+                        child { node {2}
+                            child { node {1} }
+                            child { node {1} }
+                        }
+                    }
+                    child { node {3}
+                        child { node {2}
+                            child { node {1} }
+                            child { node {1} }
+                        }
+                        child { node {1}
+                        }
+                    };
+            \end{tikzpicture}
+            \caption{Buddy tree using the Fibonacci sequence}
+            \label{fig:7-10a}
+        \end{figure}
+
+    \item The advantage is that there are more blob sizes to choose from. Whereas in the binary buddy system we would choose between 8, 4 and 4 as blobs to allocate at some level, here, we can choose between 8, 5 and 3. This extra option will in the end lead to more efficient memory usage. An obvious disadvantage however is that memory typically comes in powers of two. In this example, 8 happens to be a power of two as well, however, there is no Fibonacci number greater than 8 which is a power of two\footnote{\url{http://math.stackexchange.com/a/795808/63495}}.
+\end{enumerate}
+
+\section*{7.14}
+\begin{enumerate}[label=\alph*.]
+    \item Since $198<248$, this is in the first block. The address is then $660+198=858$.
+    \item Since $2156>1472=248+422+198+604$, a segmentation fault occurs.
+    \item Idem, with $1530>1472$.
+    \item Idem, with $3444>1472$.
+    \item Since $222<248$, this is in the first block. The address is then $660+222=882$.
+\end{enumerate}
+
+\end{document}
+
-- 
cgit v1.2.3

