completed lec 20,21,22 -- still need lec 23
[kspaans/CS350] / lec15-0625.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{June 25, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 15 -- Page Replacement Policies}
11 These are implemented by the OS, which ideally will use data from hardware
12 and user applications to make smart decisions.
13
14 \subsection*{Application Behaviour and Policies}
15 First In First Out is a very naive policy, and it faults too much! It does not
16 consider things like locality, frequency of use, recent use history,
17 cleanliness of the page, etc. Optimal
18 decisions for page eviction can be made if we know the future. If we know
19 exactly what pages an application is going to use and when, we can create
20 the perfect policy -- this is hard to do in real life.
21
22 \paragraph*{Locality}
23 Pages containing program text will naturally show very strong spatial locality,
24 as the processor increments the PC and fetches instructions. Variables in stack
25 frames, procedural and block-oriented programming, and loops cause temporal
26 locality.
27
28 \paragraph*{Least Recently Used}
29 Locality means that LRU is close to an optimal strategy. It is impractical to
30 implement because it means the kernel would have to keep track of every read
31 and write to memory. This would slow the system down, since the VM subsystem is
32 far too fast. An easier method is if the TLB has a ``use bit''. \emph{SYS161}
33 does not however.
34
35 \paragraph*{Faking a Use Bit}
36 To fake it, leave pages as invalid initially when they are added to the TLB.
37 This will have the overhead of some extra exceptions. But those exceptions can
38 be used to keep track of when pages are being used. The OS can periodically
39 clear the use bit to make the data more relevant. Eviction can only happen for
40 pages that do not have their use bit set when a page is requested.
41
42 \paragraph*{Least Frequently Used}
43 A count can be kept of the frequency with which a page is used. The kernel
44 would need help to do this though. This also ignore temporal locality.
45 Another complication is: when do old uses become forgotten? If you don't clear
46 them out, then you end up with old pages that are hard to evic because their
47 counts are so high. And new pages will have a hard time sticking, even if they
48 are frequently used.
49
50 \paragraph*{Page Cleanliness}
51 Pages are copied out of secondary storage into main memory. What happens if the
52 page gets modified? Then we call it \textbf{dirty}. If this page gets
53 evicted, it will need to be \textbf{written back} to secondary storage. This
54 adds cost to the eviction. \emph{SYS161} doesn't have a clean bit. We can fake
55 it by leaving pages as read-only initially, and changing them on write
56 (assuming we can keep track of which ones were supposed to be writable in the
57 first place).
58
59 \subsection{Clock Algorithm}
60 A pointer wraps around in the page table, like a circular buffer, pointing at
61 who to evic next, only is ``use bit'' isn't set.
62 \end{document}