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
|
\documentclass[10pt,a4paper]{article}
\usepackage[margin=2cm]{geometry}
\usepackage{minted}
\usepackage{enumitem}
\setenumerate[1]{label=\alph*.}
% 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}
\parindent0pt
\title{Operating Systems - assignment 1}
\author{Camil Staps\\\small{s4498062}}
\begin{document}
\maketitle
\thispagestyle{fancy}
\section*{3.5}
We could add a counter $c$ to the process control block for each process. Every time the process is dispatched, the counter should be increased by some constant step $s$. The OS should only dispatch a process when $c \ge p$, where $p$ is its priority. The OS should \emph{always} prefer processes in the Ready state over processes in the Ready/Suspend state. When there is no process in the Ready state that meets the requirement above, a process in the Ready/Suspend state is chosen. Possibly, one or more processes need to be suspended for this to be possible. Whenever a process is suspended, its counter $c$ is set to $0$.
This way, we don't swap high priority processes in directly, but rather keep them in an unsuspended state longer than low priority processes. By increasing or decreasing $s$, the time a process is kept unsuspended (and thus the time other processes are kept suspended) can be decreased or increased, respectively. This means that when responsiveness start to be a problem we should increase $s$, however, a smaller $s$ means we need less time for swapping. In other words, $s$ can be tweaked to meet specific requirements. We could even imagine a scheme where $s$ is changed dynamically depending on average response time, or where $s$ is modifiable by the end user.
\section*{3.9}
\begin{enumerate}
\item Yes, this is possible. Suppose a process wants to download a $10MB$ file from the internet onto a disk. Every $200ms$ we receive $2MB$ new data from the network adapter. Writing to the disk goes in blocks of $1kB$ and can be done roughly every $30us$.\footnote{These are but example values.}
If we would have to place the process in either the network queue or the disk I/O queue, we would first download $2MB$ in $200ms$, write it to the disk in $60ms$, and repeat that sequence four more times. The download task would take $5\cdot260=1300ms$.
However, if we could place the process in the network queue and the disk I/O queue \emph{simultaneously}, we could perform the disk writes while we're waiting for the next network response. The task would then take only $5\cdot200=1000ms$.
\item A process is allowed to continue executing while waiting for data as long as that data is not used yet. For example, the following program:
\begin{minted}[linenos,xleftmargin=24pt,tabsize=0]{c}
int i, j;
int* data = doSomeLongIOOperation();
/* Do stuff with i and j */
i += data[0];
/* Do stuff with only j */
\end{minted}
could continue executing line 3 while waiting for the long I/O operation from line 2. After all, \texttt{data} is not needed there. If we arrive at line 4 before the I/O operation finishes, we could even continue execution in line 5, and block when we really need \texttt{i} or \texttt{data} in a later stadium. If the I/O operation finishes before we arrive at line 4, \texttt{data} may be updated `in the background' and the process can continue to run line 4 and 5 sequentially.
This allows a process to wait for two events. When nothing can be done without some event happening first, the process should be blocked. Whenever some operation is called for that would block the process in a traditional scheme, here, we put a pointer to the process and some information about the event we're waiting for in a queue (rather than the event itself). When the pointer is taken from the queue due to an event happening, the process can update the data that relied on that event, and continue execution normally.
Essentially, it is not the process that is blocked but some data kept by the process. Multiple variables may be blocked at some point. If nothing can be done without those variables, the process is blocked. This implies then, that for this to be possible cooperation is needed between the compiler and the OS.
\end{enumerate}
\end{document}
|
