added load balancing to lec 18 notes
[kspaans/CS350] / lec16-0630.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{June 30, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 16 -- VM Paging Policies}
11 Info about dirty/clean pages can supplement ``use'' info to help make
12 scheduling choices. Consider the ``Enhanced Second Chance Algorithm'' in which
13 non-recently used and clean pages are given eviction priority.
14
15 \subsection*{Asynchronously Cleaning Pages}
16 Making applications wait while we clean pages in order to swap in new ones is
17 not ideal. Instead, we can clean pages asynchronously, while the hard disk
18 isn't being used and another process is blocked, or when the OS is otherwise
19 idle. The disadvantage is that if we are too agressive in cleaning pages and
20 a process dirties them soon afterwards, then the work to clean that page or
21 pages will have been wasted. This can be implemented by a dedicated kernel
22 thread that sweeps the page table at an appropriate time.
23
24 \paragraph*{Prefetching}
25 We can further hide latency by trying to guess which pages will be requested
26 next. If the kernel can guess correctly, then the process will not incurr
27 page faults. If the kernel guesses incorrectly, then not only will processes
28 page fault, but it's possible that the kernel evicted a useful page in order
29 to prefetch the new one. Prefetching implies that we're no longer doing demand
30 paging. A simple but common prefetching technique is ``sequential readahead''.
31 When page $x$ is requested, page $x + 1$ will probably be needed as well, so
32 prefetch it.
33
34 \paragraph*{Choice of Page Size}
35 Some hardware lets you select the page size that you want. There are some
36 tradeoffs between using larger or smaller pages. Larges pagesize means smaller
37 page table, larger TLB footprint (amount of memory covered by entries in the
38 TLB which means fewer TLB misses), and more efficient I/O. More efficient
39 because there will be fewer pages that need to be swapped less often, and
40 because reading a larger file from disk does not necessarily take a
41 linearly-proportional amount of time. However the downsides are that larger
42 page can have more irrelevant information in it and more internal
43 fragmentation (proportional to the size of the page).
44
45 \paragraph*{Application Behaviour: Belady's Anomaly}
46 The anomaly is where a page replacement policy performs worse when given more
47 memory to work with. This can be seen in FIFO, with a bad enough reference
48 string. It turns out that there are some strategies which we can guarantee
49 will perform no worse when given more memory. These are called \textbf{stack
50 policies}. We define a stack policy as one where for all reference strings,
51 all memory sizes (amount of physical memory) $m$, and at any time $t$ then
52 the number of pages occupying memory of size $m$ is a subset of those occupying
53 an amount of memory $m + 1$. To be more precise: $B(m,t) \subseteq B(m + 1,t)$.
54 This means that the policy enforces a total ordering on all pages in physical
55 memory. Total ordering means every page is given a specific ordering. Therefore
56 if this doesn't change when we add memory, then the page replacement policy
57 cannot possibly do any \emph{worse} with more memory. How can we decide if a
58 page replacement algorithm is a stack policy? First, we are given that LRU is
59 one such algorithm. But when considering others, a sufficient (but not
60 necessary) condition is the ordering property. As long as things aren't changed
61 if memory is added. Consider FIFO, if memory is added, the order of elements in
62 $B(m,t)$ can change. Similarly, the clock algorithm is not a stack policy.
63
64 \paragraph*{How much memory does a process use?}
65 The \texttt{ps} command in Linux can give us this information. How many of a
66 processes pages are in memory? This is called the \texttt{Resident Set Size}.
67 The total number of pages comprising the process can be called the
68 \texttt{Virtual Space Size}. There is a notion of the \texttt{working set} of
69 a process. This is the set of pages that are used most frequently. Admittedly
70 this is a slippery concept, and so hard to take advantage of fully in practice.
71 If the OS can keep the working set of a process in memory, then that process
72 should incurr very few page faults. These properties can be loosely used to
73 prioritize pages for eviction. To find the ideal working set of a process, the
74 graph of page faults per unit time against the number of pages used.
75
76 \paragraph*{Thrashing}
77 When the number of page faults are too high, lots of swapping to and from disk
78 will happen. This is called \textbf{thrasing}. When we are trying to increase
79 the multiprogramming level of the OS, if we increase it too much, there will
80 be contention on resources and probably thrashing. If the level is too low,
81 resources will be left idle. To try and speedup the recovery of a system that
82 is thrasing, processes can be killed (very mean) or they can be suspended.
83 Suspension just means moving all of the processes' pages to disk.
84 \end{document}