added load balancing to lec 18 notes
[kspaans/CS350] / lec14-0623.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{June 23, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 14 -- Exploiting Secondary Storage}
11 We want to be able to handle virtual address spaces that are larger than the
12 amount of physical memory in the system. We do this by mapping virtual pages
13 onto the hard disk, ``paging'' them. This lets us make more efficient use of
14 available physical memory by putting unused pages on the slower but larger hard
15 disk. The page table entries ``valid'' bits now can mean that the page is in
16 main memory. ``Invalid'' pages are in secondary memory.
17
18 \subsection*{Problem: Large Page Tables}
19 When the virtual addresses get bigger, it means the page tables for them will
20 also get bigger. If the virtual address size is 48 bits, and the page size is
21 8KB, then we have $2^48 / 2^13 = 2^35$ multiplied by 4 or more bytes per page
22 table entry, giving a page table of at least 128GB! This is practically
23 unmanageable. The solutions for this are: multi-level page tables, or inverted
24 page tables.
25
26 \paragraph*{Multi-level Page Tables}
27 Since the whole page table at once would be too big, we divide it into, say,
28 page-sized chunks and then have higher-order page tables that link to lower-
29 order ones. This way, the whole table can fit into a physical frame of memory
30 and it's entries can point to successively lower-level page tables which will
31 eventually fully translate the virtual address. The virtual address will need
32 to be partitioned into multiple page numbers, reffering to each level of
33 page table. This increases the complexity and overhead of translating addresses
34 which means that the TLB is even more important.
35
36 \subparagraph*{Example 1}
37 Consider a 48-bit virtual address, $2^13$ (8KB) page size, and 8-byte page
38 tables. $2^13 / 2^3 = 2^10$ page table entries per frame. There are $2^35$
39 page table entries needed. And with $2^10$ addressable entries per ``page
40 table'' this means we will need 4 levels of page tables: $5 + 10 + 10 + 10$
41 bits.
42
43 \paragraph*{Inverted Page Tables}
44 Entries in an inverted page table map physical addresses to virtual addresses.
45 Therefore it describes the contents of physical memory. It also needs to keep
46 process-ids in each table entry, so that it can know which process the
47 translations belong to. This also means that translation is slowed down, since
48 the table would need to be linearly searched. A hash table can be used to hash
49 virtual address and map it to the correct page table entry. This structure
50 means that the OS is free to use whatever methods it wants to track address
51 translation outside of the page table. For example, it will still have to
52 manage translations for virtual addresses that are not currently in physical
53 memory (hash anchor table).
54
55 \subsection*{Paging Policies}
56 \textbf{Demand Paging} -- pages are moved into main memory when they are
57 requested, when a page fault occurs. \textbf{Prefetching} -- the OS tries to
58 guess what will be needed next and move it into main memory before it is
59 requested. A replacement policy is how the OS decides which pages to
60 \textbf{evict} (move from main to secondary memory) when main memory is full
61 but a new page needs to be brought in. The OS can make decisions
62 \textbf{locally} or \textbf{globally}. Local policies are process-specific. The
63 OS considers only the process's own pages when deciding which pages to replace.
64 Global policies are process-agnostic. Every page in the system is considered
65 equally for replacement when a new page is requested. This means that process
66 $A$'s requests can result in process $B$'s pages being evicted. This can all
67 differ depending on whether the system's MMU is software or hardware
68 controlled. If the MMU is software controlled, then the OS must be able to add
69 new translations to the TLB. If it's hardware controlled, then the OS doesn't
70 have to worry about this.
71 \end{document}