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