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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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}[p]
\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}[p]
\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}
|
