From 40dbd4e5cc0a28711af6f9de4c27ce236072d3dc Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Wed, 9 Sep 2015 22:17:18 +0200 Subject: Organisation; assignment 2 --- assignment1.tex | 65 ------------------------------- assignment1/assignment1.tex | 65 +++++++++++++++++++++++++++++++ assignment2/assignment2.txt | 8 ++++ assignment2/hyman.q | 6 +++ assignment2/hyman.xml | 10 +++++ assignment2/hyman.xtr | 95 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 184 insertions(+), 65 deletions(-) delete mode 100644 assignment1.tex create mode 100644 assignment1/assignment1.tex create mode 100644 assignment2/assignment2.txt create mode 100644 assignment2/hyman.q create mode 100644 assignment2/hyman.xml create mode 100644 assignment2/hyman.xtr diff --git a/assignment1.tex b/assignment1.tex deleted file mode 100644 index 6104bdf..0000000 --- a/assignment1.tex +++ /dev/null @@ -1,65 +0,0 @@ -\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} - diff --git a/assignment1/assignment1.tex b/assignment1/assignment1.tex new file mode 100644 index 0000000..6104bdf --- /dev/null +++ b/assignment1/assignment1.tex @@ -0,0 +1,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} + diff --git a/assignment2/assignment2.txt b/assignment2/assignment2.txt new file mode 100644 index 0000000..ceee4fa --- /dev/null +++ b/assignment2/assignment2.txt @@ -0,0 +1,8 @@ +Camil Staps (s4498062) + +1. +De `not blocked[1-i]' en `turn := 1' zijn twee stappen. Als daartussen een context switch plaatsvindt, kunnen beide processen tegelijkertijd in de kritieke sectie terechtkomen. Maken we hetzelfde model waarbij we deze twee stappen samenvoegen, dan is er geen probleem. Zie hyman.xml, hyman.q, hyman.trx. + +2. +Stel dat proces 1 zich in de kritieke sectie bevindt. Als er nu om wat voor reden dan ook nooit een context switch plaatsvindt op het moment dat proces 1 zich in staat `Start' bevindt, dan zal proces 2 nooit opmerken dat proces 1 zijn blocked bit op 0 zet. Proces 2 zou in dat geval dus nooit in de kritieke sectie terechtkomen, maar continue in `WaitBlocked' blijven hangen. + diff --git a/assignment2/hyman.q b/assignment2/hyman.q new file mode 100644 index 0000000..0bd1a71 --- /dev/null +++ b/assignment2/hyman.q @@ -0,0 +1,6 @@ +//This file was generated from (Commercial) UPPAAL 4.0.14 (rev. 5615), May 2014 + +/* + +*/ +E<> (p1.CriticalSection && p2.CriticalSection) diff --git a/assignment2/hyman.xml b/assignment2/hyman.xml new file mode 100644 index 0000000..fb22f25 --- /dev/null +++ b/assignment2/hyman.xml @@ -0,0 +1,10 @@ +// Place global declarations here. +typedef int[0,1] ids; +bool blocked[ids]; +int turn = 0;// Place template instantiations here. +p1 = Process(0); +p2 = Process(1); + +// List one or more processes to be composed into a system. +system p1, p2; \ No newline at end of file diff --git a/assignment2/hyman.xtr b/assignment2/hyman.xtr new file mode 100644 index 0000000..5dfbf2a --- /dev/null +++ b/assignment2/hyman.xtr @@ -0,0 +1,95 @@ +4 +4 +. +. +0 +0 +0 +0 +1 +. +4 +3 +. +. +0 +1 +0 +0 +1 +. +1 7 +. +4 +1 +. +. +0 +1 +0 +0 +1 +. +1 4 +. +4 +0 +. +. +0 +1 +0 +0 +1 +. +1 2 +. +3 +0 +. +. +1 +1 +0 +0 +1 +. +0 7 +. +2 +0 +. +. +1 +1 +0 +0 +1 +. +0 6 +. +2 +3 +. +. +1 +1 +1 +0 +1 +. +1 1 +. +2 +2 +. +. +1 +1 +1 +0 +1 +. +1 6 +. +. -- cgit v1.2.3