almost done lec 11 notes
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Wed, 10 Jun 2009 15:17:00 +0000 (11:17 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Wed, 10 Jun 2009 15:17:00 +0000 (11:17 -0400)
lec11-0609.tex [new file with mode: 0644]

diff --git a/lec11-0609.tex b/lec11-0609.tex
new file mode 100644 (file)
index 0000000..ade78f7
--- /dev/null
@@ -0,0 +1,62 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{June 9, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle 
+
+\section*{Lecture 11 -- Segmentation}
+No office hour on Thursday (the midterm is then, and there is another
+distinguished Lecture. There will be a tutorial style office hour next week in
+which adding new system calls to the kernel will be demonstrated. We went over
+some sample solutions for locks and CVs and looked at potential errors in them.
+
+\subsection*{Issues with Paging: Sparse Address Spaces}
+We can calculate how many pages are needed for a given range of addresses.
+Consider \texttt{0x00400000 - 0x00401B30}, if we know that the page size is 4KB
+then 12 bits (3 hexadecimal digits) correspond to the offset. So that
+particular range needs two pages, one for \texttt{0x00400000 - 0x00400FFF} and
+a second (not full page) for \texttt{0x00401000 - 0x00401B30}.
+
+The virtual address space that is addressable by a process is usually very
+large (2GB or more). It would be difficult to allocate physical frames for each
+of those pages -- but we don't need to. This leaves us with a sparse address
+space. Likely only a few hundred out of millions of pages would be valid. There
+is still a problem though, we need a huge page table (think array) to hold the
+translations for every possible virtual address. The page table would have to
+be $2^{32} / 2^{12} = 2^{19}$ entries long. Recall that an invalid page means
+that there is no physical frame backing it. We cannot sparesely fill the page
+table, beacuse then we'd have to search through it to find entries, rather than
+being able to index them.
+
+\subsection*{Segmentation}
+A memory segment is like a mini address space. It can be given to a process
+(kind of like with dynamic relocation). Or it can be thought of as seperating
+a process' address space into chunks (segments). We can take the analogy as far
+as making segments visible to user applications. A segment can be mapped to a
+physical chunk of memory, and we'll need a segment table, just like with pages.
+The number of bits corresponding to the segment number will indicate the
+number of segments that the system has. Segments will have a max size of
+$2^{\mathrm{# offset bits}}$. Thus we only need to allocate smaller segment
+tables instead of large page tables.
+
+\subsection*{Combinig Segments and Paging}
+To avoid the need to physically allocate contiguous chunks for segments (and
+suffer from the external fragmentation that will result) we can further divide
+segments into pages. Virtual addresses will then have segment numbers, page
+numbers, and an offset, thus we'll also need a segment table as well as page
+tables. Given any two of virtual address size, page size, and number of
+segments, we can derive the third.
+
+\subsection*{Address Spaces in \emph{OS161}}
+There is no segment table base register like in the notes, so the MMU doesn't
+manage the TLB for us. We have to manually populate it (software controlled
+TLB). This gives us freedome to use whatever kind of data structure for the
+table that we want. The current address space structure used by \texttt{dumbvm}
+will be replaced when we do Assignment 3. It records where virtual and physical
+segments start. It points to the bottom of the stack, which is fixed as 12
+pages long, extending all the way up to \texttt{0x7FFFFFFF} (the very top of
+user-addressable memory).
+\end{document}