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{minted}
% 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}
\parindent0pt
\title{Operating Systems - assignment 4}
\author{Camil Staps\\\small{s4498062}}
\begin{document}
\maketitle
\thispagestyle{fancy}
\section*{6.11}
\begin{enumerate}
\item No process is marked, because no process has all zeros in the allocation matrix.
\item $W \coloneqq (2,1,1,2)$.
\item Take $i=1$.
\item Mark $P_1$, $W \coloneqq (2,1,2,2)$.
\setcounter{enumi}{2}
\item Take $i=3$.
\item Mark $P_3$, $W \coloneqq (2,2,3,2)$.
\setcounter{enumi}{2}
\item Both $Q_2 > W$ and $Q_4 > W$, so we terminate.
\end{enumerate}
There are unmarked processes ($P_2,P_4$), therefore, deadlock exists, for exactly those processes.
\section*{6.18}
\begin{enumerate}[label=\alph*.]
\item If there are two types of philosophers, the fourth condition of deadlock (circular wait) is not fulfilled. Lefties and righties can never be in a chain waiting for resources. Therefore, deadlock cannot occur.
\item On a table with two philosophers, of which one is a lefty and one a righty, it is obvious to see that one philosopher will start eating and when he is done, the other one can grab the forks. No starvation occurs.
If on a table with $k$ philosophers no starvation occurs, and we add another philosopher $p$, this new philosopher is placed between two philosophers who, at some point, will eat. Then at some point the first fork $p$ wants to take will be free, and also at some point the other fork $p$ needs will be free. Hence, $p$ will also eat.
From the principle of induction it now follows that starvation cannot occur on a table with $n\ge2$ philosophers, as long as there is at least one lefty and one righty.
\end{enumerate}
\end{document}
|
