lec 14 notes done
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Wed, 24 Jun 2009 19:07:18 +0000 (15:07 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Wed, 24 Jun 2009 19:07:18 +0000 (15:07 -0400)
lec14-0623.tex [new file with mode: 0644]

diff --git a/lec14-0623.tex b/lec14-0623.tex
new file mode 100644 (file)
index 0000000..23a4490
--- /dev/null
@@ -0,0 +1,71 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{June 23, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle 
+
+\section*{Lecture 14 -- Exploiting Secondary Storage}
+We want to be able to handle virtual address spaces that are larger than the
+amount of physical memory in the system. We do this by mapping virtual pages
+onto the hard disk, ``paging'' them. This lets us make more efficient use of
+available physical memory by putting unused pages on the slower but larger hard
+disk. The page table entries ``valid'' bits now can mean that the page is in
+main memory. ``Invalid'' pages are in secondary memory.
+
+\subsection*{Problem: Large Page Tables}
+When the virtual addresses get bigger, it means the page tables for them will
+also get bigger. If the virtual address size is 48 bits, and the page size is
+8KB, then we have $2^48 / 2^13 = 2^35$ multiplied by 4 or more bytes per page
+table entry, giving a page table of at least 128GB! This is practically
+unmanageable. The solutions for this are: multi-level page tables, or inverted
+page tables.
+
+\paragraph*{Multi-level Page Tables}
+Since the whole page table at once would be too big, we divide it into, say,
+page-sized chunks and then have higher-order page tables that link to lower-
+order ones. This way, the whole table can fit into a physical frame of memory
+and it's entries can point to successively lower-level page tables which will
+eventually fully translate the virtual address. The virtual address will need
+to be partitioned into multiple page numbers, reffering to each level of
+page table. This increases the complexity and overhead of translating addresses
+which means that the TLB is even more important.
+
+\subparagraph*{Example 1}
+Consider a 48-bit virtual address, $2^13$ (8KB) page size, and 8-byte page
+tables. $2^13 / 2^3 = 2^10$ page table entries per frame. There are $2^35$
+page table entries needed. And with $2^10$ addressable entries per ``page
+table'' this means we will need 4 levels of page tables: $5 + 10 + 10 + 10$
+bits.
+
+\paragraph*{Inverted Page Tables}
+Entries in an inverted page table map physical addresses to virtual addresses.
+Therefore it describes the contents of physical memory. It also needs to keep
+process-ids in each table entry, so that it can know which process the
+translations belong to. This also means that translation is slowed down, since
+the table would need to be linearly searched. A hash table can be used to hash
+virtual address and map it to the correct page table entry. This structure
+means that the OS is free to use whatever methods it wants to track address
+translation outside of the page table. For example, it will still have to
+manage translations for virtual addresses that are not currently in physical
+memory (hash anchor table).
+
+\subsection*{Paging Policies}
+\textbf{Demand Paging} -- pages are moved into main memory when they are
+requested, when a page fault occurs. \textbf{Prefetching} -- the OS tries to
+guess what will be needed next and move it into main memory before it is
+requested. A replacement policy is how the OS decides which pages to
+\textbf{evict} (move from main to secondary memory) when main memory is full
+but a new page needs to be brought in. The OS can make decisions
+\textbf{locally} or \textbf{globally}. Local policies are process-specific. The
+OS considers only the process's own pages when deciding which pages to replace.
+Global policies are process-agnostic. Every page in the system is considered
+equally for replacement when a new page is requested. This means that process
+$A$'s requests can result in process $B$'s pages being evicted. This can all
+differ depending on whether the system's MMU is software or hardware
+controlled. If the MMU is software controlled, then the OS must be able to add
+new translations to the TLB. If it's hardware controlled, then the OS doesn't
+have to worry about this.
+\end{document}