lecture 16 notes done
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Tue, 30 Jun 2009 23:35:58 +0000 (19:35 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Tue, 30 Jun 2009 23:35:58 +0000 (19:35 -0400)
lec16-0630.tex [new file with mode: 0644]

diff --git a/lec16-0630.tex b/lec16-0630.tex
new file mode 100644 (file)
index 0000000..a71df60
--- /dev/null
@@ -0,0 +1,84 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{June 30, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle 
+
+\section*{Lecture 16 -- VM Paging Policies}
+Info about dirty/clean pages can supplement ``use'' info to help make
+scheduling choices. Consider the ``Enhanced Second Chance Algorithm'' in which
+non-recently used and clean pages are given eviction priority.
+
+\subsection*{Asynchronously Cleaning Pages}
+Making applications wait while we clean pages in order to swap in new ones is
+not ideal. Instead, we can clean pages asynchronously, while the hard disk
+isn't being used and another process is blocked, or when the OS is otherwise
+idle. The disadvantage is that if we are too agressive in cleaning pages and
+a process dirties them soon afterwards, then the work to clean that page or
+pages will have been wasted. This can be implemented by a dedicated kernel
+thread that sweeps the page table at an appropriate time.
+
+\paragraph*{Prefetching}
+We can further hide latency by trying to guess which pages will be requested
+next. If the kernel can guess correctly, then the process will not incurr
+page faults. If the kernel guesses incorrectly, then not only will processes
+page fault, but it's possible that the kernel evicted a useful page in order
+to prefetch the new one. Prefetching implies that we're no longer doing demand
+paging. A simple but common prefetching technique is ``sequential readahead''.
+When page $x$ is requested, page $x + 1$ will probably be needed as well, so
+prefetch it.
+
+\paragraph*{Choice of Page Size}
+Some hardware lets you select the page size that you want. There are some
+tradeoffs between using larger or smaller pages. Larges pagesize means smaller
+page table, larger TLB footprint (amount of memory covered by entries in the
+TLB which means fewer TLB misses), and more efficient I/O. More efficient
+because there will be fewer pages that need to be swapped less often, and
+because reading a larger file from disk does not necessarily take a
+linearly-proportional amount of time. However the downsides are that larger
+page can have more irrelevant information in it and more internal
+fragmentation (proportional to the size of the page).
+
+\paragraph*{Application Behaviour: Belady's Anomaly}
+The anomaly is where a page replacement policy performs worse when given more
+memory to work with. This can be seen in FIFO, with a bad enough reference
+string. It turns out that there are some strategies which we can guarantee
+will perform no worse when given more memory. These are called \textbf{stack
+policies}. We define a stack policy as one where for all reference strings,
+all memory sizes (amount of physical memory) $m$, and at any time $t$ then
+the number of pages occupying memory of size $m$ is a subset of those occupying
+an amount of memory $m + 1$. To be more precise: $B(m,t) \subseteq B(m + 1,t)$.
+This means that the policy enforces a total ordering on all pages in physical
+memory. Total ordering means every page is given a specific ordering. Therefore
+if this doesn't change when we add memory, then the page replacement policy
+cannot possibly do any \emph{worse} with more memory. How can we decide if a
+page replacement algorithm is a stack policy? First, we are given that LRU is
+one such algorithm. But when considering others, a sufficient (but not
+necessary) condition is the ordering property. As long as things aren't changed
+if memory is added. Consider FIFO, if memory is added, the order of elements in
+$B(m,t)$ can change. Similarly, the clock algorithm is not a stack policy.
+
+\paragraph*{How much memory does a process use?}
+The \texttt{ps} command in Linux can give us this information. How many of a
+processes pages are in memory? This is called the \texttt{Resident Set Size}.
+The total number of pages comprising the process can be called the
+\texttt{Virtual Space Size}. There is a notion of the \texttt{working set} of
+a process. This is the set of pages that are used most frequently. Admittedly
+this is a slippery concept, and so hard to take advantage of fully in practice.
+If the OS can keep the working set of a process in memory, then that process
+should incurr very few page faults. These properties can be loosely used to
+prioritize pages for eviction. To find the ideal working set of a process, the
+graph of page faults per unit time against the number of pages used.
+
+\paragraph*{Thrashing}
+When the number of page faults are too high, lots of swapping to and from disk
+will happen. This is called \textbf{thrasing}. When we are trying to increase
+the multiprogramming level of the OS, if we increase it too much, there will
+be contention on resources and probably thrashing. If the level is too low,
+resources will be left idle. To try and speedup the recovery of a system that
+is thrasing, processes can be killed (very mean) or they can be suspended.
+Suspension just means moving all of the processes' pages to disk.
+\end{document}