lec 10 notes done
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Thu, 4 Jun 2009 21:09:52 +0000 (17:09 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Thu, 4 Jun 2009 21:09:52 +0000 (17:09 -0400)
lec10-0604.tex [new file with mode: 0644]

diff --git a/lec10-0604.tex b/lec10-0604.tex
new file mode 100644 (file)
index 0000000..b533bcd
--- /dev/null
@@ -0,0 +1,67 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{June 4, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle 
+
+\section*{Lecture 10 -- Paging}
+We are reminded that A2 hints are up on the website now, and that the midterm
+next week covers up to slide 10 of the Virtual Memory slides.
+
+\subsection*{Addresses}
+Virtual addreses page numbers can be calculated given the virtual address
+(vaddr) and the size of pages (pagesize).
+\[ \left \lfloor \frac{\mathrm{vaddr}}{\mathrm{pagesize}} \right \rfloor \]
+The offset can similarly me calculated.
+\[ \mathrm{vaddr} \bmod \mathrm{pagesize} \]
+The addresses themselves can be built: Vaddr $=$ (Page Number) $\cdot$ 
+(Page Size) $+$ Offset, Paddr $=$ (Frame Number) $\cdot$ (Page Size) + Offset.
+For example, if we have a virtual address \texttt{0xDEADBEEF} then 20 bits make
+up the page number and 12 the offset: \texttt{0xDEADB} and \texttt{0xEEF}
+respectively. Consider the virtual address \texttt{0x004201A8} with a page size
+of $2^{10}$. The page number and offset are now split in the middle of one of
+the hex characters, making this trickier. The offset is \texttt{0x1A8}, but
+remember that it only uses the lower order two bits of the \texttt{1}. The
+page number will be \texttt{0x1080} this comes from \texttt{0x00420} plus
+the high order bits from the \texttt{1}. Since they are both zeros, it's like a
+left shift operation on \texttt{0x00420}, or multiplication by 4. Make sure you
+can do this for the midterm!
+\subsection*{Memory Protection}
+The Page Table we saw in Tuesday has some extra flag bits. These give
+attributes to the pages, such as read-only, valid (we'll learn the meaning of
+validity later), etc. If a process tries to access pages that are either not
+in the page table, or marked as invalid, then the MMU will raise exceptions
+which the kernel must handle. The kernel may kill the process, or allocate some
+memory, or any number of things. If the exception is because the page number is
+not in the table, then perhaps the kernel would need to allocate the memory for
+that page. The MMU is given a pointer to the page table
+as well as it's size. The kernel would need to update these whenever a context
+switch happens.
+\subsection*{Speed of Translation}
+And other questions like, what if a process is only using a sparse number of
+pages from it's address space? And what does the kernel do about virtual
+memory? Does it use virtual addresses all the time too?
+
+
+The page table, in memory, is a concern if we need to translate virtual
+addresses during every CPU cycle. Accessing that memory will be costly. Enter
+the Translation Lookaside Buffer (TLB). It's a simple page number to frame
+number cache -- a part of the MMU hardware.
+Contrast this with dynamic relocation, where all that is needed is the single,
+fast register. \emph{SYS161} has a TLB with 64 entires (it's usually a small
+cache, since it has to be implemented in hardare). The TLB is software
+controlled as well (some are hardware controlled and do more things
+automatically). Part of the kernel's job is managing the TLB. It needs to add
+new entries when they are needed (i.e. as part of handling an exception),
+remove old ones, and flush the TLB when a context switch occurs. The new
+processes' page table will not correspond to entires in the TLB. Think of how
+we could optimize this (Sean's idea) by pre-loading PTEs from the page table
+that the kernel maintains into the TLB during a context switch.
+\emph{OS161} provides some low-level functions for modifying the TLB. (In
+fact, \emph{SYS161}'s TLB has ``tags'' that could be used to distinguish
+between TLB entries that belong to different processes, but currently it is
+not used.
+\end{document}