lec 15 notes done
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Mon, 29 Jun 2009 04:27:46 +0000 (00:27 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Mon, 29 Jun 2009 04:27:46 +0000 (00:27 -0400)
lec15-0625.tex [new file with mode: 0644]

diff --git a/lec15-0625.tex b/lec15-0625.tex
new file mode 100644 (file)
index 0000000..89d7c9e
--- /dev/null
@@ -0,0 +1,62 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{June 25, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle 
+
+\section*{Lecture 15 -- Page Replacement Policies}
+These are implemented by the OS, which ideally will use data from hardware
+and user applications to make smart decisions.
+
+\subsection*{Application Behaviour and Policies}
+First In First Out is a very naive policy, and it faults too much! It does not
+consider things like locality, frequency of use, recent use history,
+cleanliness of the page, etc. Optimal
+decisions for page eviction can be made if we know the future. If we know
+exactly what pages an application is going to use and when, we can create
+the perfect policy -- this is hard to do in real life.
+
+\paragraph*{Locality}
+Pages containing program text will naturally show very strong spatial locality,
+as the processor increments the PC and fetches instructions. Variables in stack
+frames, procedural and block-oriented programming, and loops cause temporal
+locality.
+
+\paragraph*{Least Recently Used}
+Locality means that LRU is close to an optimal strategy. It is impractical to
+implement because it means the kernel would have to keep track of every read
+and write to memory. This would slow the system down, since the VM subsystem is
+far too fast. An easier method is if the TLB has a ``use bit''. \emph{SYS161}
+does not however.
+
+\paragraph*{Faking a Use Bit}
+To fake it, leave pages as invalid initially when they are added to the TLB.
+This will have the overhead of some extra exceptions. But those exceptions can
+be used to keep track of when pages are being used. The OS can periodically
+clear the use bit to make the data more relevant. Eviction can only happen for
+pages that do not have their use bit set when a page is requested.
+
+\paragraph*{Least Frequently Used}
+A count can be kept of the frequency with which a page is used. The kernel
+would need help to do this though. This also ignore temporal locality.
+Another complication is: when do old uses become forgotten? If you don't clear
+them out, then you end up with old pages that are hard to evic because their
+counts are so high. And new pages will have a hard time sticking, even if they
+are frequently used.
+
+\paragraph*{Page Cleanliness}
+Pages are copied out of secondary storage into main memory. What happens if the
+page gets modified? Then we call it \textbf{dirty}. If this page gets
+evicted, it will need to be \textbf{written back} to secondary storage. This
+adds cost to the eviction. \emph{SYS161} doesn't have a clean bit. We can fake
+it by leaving pages as read-only initially, and changing them on write
+(assuming we can keep track of which ones were supposed to be writable in the
+first place).
+
+\subsection{Clock Algorithm}
+A pointer wraps around in the page table, like a circular buffer, pointing at
+who to evic next, only is ``use bit'' isn't set.
+\end{document}