added load balancing to lec 18 notes
[kspaans/CS350] / lec11-0609.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{June 9, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 11 -- Segmentation}
11 No office hour on Thursday (the midterm is then, and there is another
12 distinguished Lecture. There will be a tutorial style office hour next week in
13 which adding new system calls to the kernel will be demonstrated. We went over
14 some sample solutions for locks and CVs and looked at potential errors in them.
15
16 \subsection*{Issues with Paging: Sparse Address Spaces}
17 We can calculate how many pages are needed for a given range of addresses.
18 Consider \texttt{0x00400000 - 0x00401B30}, if we know that the page size is 4KB
19 then 12 bits (3 hexadecimal digits) correspond to the offset. So that
20 particular range needs two pages, one for \texttt{0x00400000 - 0x00400FFF} and
21 a second (not full page) for \texttt{0x00401000 - 0x00401B30}.
22
23 The virtual address space that is addressable by a process is usually very
24 large (2GB or more). It would be difficult to allocate physical frames for each
25 of those pages -- but we don't need to. This leaves us with a sparse address
26 space. Likely only a few hundred out of millions of pages would be valid. There
27 is still a problem though, we need a huge page table (think array) to hold the
28 translations for every possible virtual address. The page table would have to
29 be $2^{32} / 2^{12} = 2^{19}$ entries long. Recall that an invalid page means
30 that there is no physical frame backing it. We cannot sparesely fill the page
31 table, beacuse then we'd have to search through it to find entries, rather than
32 being able to index them.
33
34 \subsection*{Segmentation}
35 A memory segment is like a mini address space. It can be given to a process
36 (kind of like with dynamic relocation). Or it can be thought of as seperating
37 a process' address space into chunks (segments). We can take the analogy as far
38 as making segments visible to user applications. A segment can be mapped to a
39 physical chunk of memory, and we'll need a segment table, just like with pages.
40 The number of bits corresponding to the segment number will indicate the
41 number of segments that the system has. Segments will have a max size of
42 $2^{\mathrm{# offset bits}}$. Thus we only need to allocate smaller segment
43 tables instead of large page tables.
44
45 \subsection*{Combinig Segments and Paging}
46 To avoid the need to physically allocate contiguous chunks for segments (and
47 suffer from the external fragmentation that will result) we can further divide
48 segments into pages. Virtual addresses will then have segment numbers, page
49 numbers, and an offset, thus we'll also need a segment table as well as page
50 tables. Given any two of virtual address size, page size, and number of
51 segments, we can derive the third.
52
53 \subsection*{Address Spaces in \emph{OS161}}
54 There is no segment table base register like in the notes, so the MMU doesn't
55 manage the TLB for us. We have to manually populate it (software controlled
56 TLB). This gives us freedome to use whatever kind of data structure for the
57 table that we want. The current address space structure used by \texttt{dumbvm}
58 will be replaced when we do Assignment 3. It records where virtual and physical
59 segments start. It points to the bottom of the stack, which is fixed as 12
60 pages long, extending all the way up to \texttt{0x7FFFFFFF} (the very top of
61 user-addressable memory). Dumbvm currently allocates pages contiguously for
62 segments, this isn't much better than plain segmentation (the simplicity is
63 evident in the current address space structure). We need to know about these
64 details for A2, e.g. for handling memory with \texttt{fork()}.
65
66 On an address exception, the MMU will save the virtual address that caused the
67 exception. This allows the kernel to use it to calculate segment number, page
68 number, and offset so that the TLB can be updated accordingly.
69 \end{document}