added load balancing to lec 18 notes
[kspaans/CS350] / lec09-0602.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{June 2, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle
9
10 \section*{Lecture 9 -- Processes}
11 Remember that context switches will only occur while we are executing kernel
12 code, I.E. after the exception handler has been called. This is how the kernel
13 preempts threads. So the order is roughly \textsf{Interrupt $\to$ trap
14 frame $\to$ mips\_syscall() $\to$ Kernel Code} with preemption
15 happening potentially somewhere inside the exception handling. We are free to
16 change choices like these, since we can modify the scheduler whenever we want.
17
18 \subsection*{Processes}
19 \emph{OS161} currently only supports sequential processes, so process
20 implentation details can be put into the thread structure. We can see this in
21 the address space and current working directory pointers.
22
23 There are system calls for managing processes, such as \texttt{fork()} and
24 \texttt{execv()}, as well as other for exiting from processes or getting a
25 process' identifier. For assignment 2 we will be implementing processes. Some
26 of the choices we'll be faced with are: how are processes initialized, how can
27 processes have more than one thread, what are the relationships between
28 processes (parent/child) and what do they mean, and how can processes
29 communicate?
30
31 \subsection*{Virtual Memory}
32 Processes each have their own, seperate address spaces. Hardware, such as the
33 MMU, helps to translate the virtual addresses that userspace (process) code
34 uses into physical addresses that correspond to real hardware. The hardware
35 will also arbitrate access to memory; it will throw exceptions if a program
36 reads or writes to the wrong parts of memory, or for a variety of other reasons
37 that we'll see soon. There are different schemes for managing virtual memory.
38 In the real world, a combination of these is usually used.
39
40 \paragraph*{Dynamic Relocation}
41 Virtual addresses spaces are made up of varying sized, contiguously allocated
42 chunks of physical memory. The physical address is built from a relocation
43 address (can be stored in a special ``relocation register'') plus the offset
44 within the address space, which is the virtual address. So each virtual address
45 space starts at 0 and is uniquely identified by it's relocation address. These
46 chunks have a size that can change as well. This scheme can lead to 
47 \textbf{external fragmentation}, where physical memory has unsable gaps between
48 virtual address space chunks. It's hard to fix because moving the virtual space
49 to a new physical location is tricky and slow (loading and storing each word
50 explicitly).
51
52 \paragraph*{Paging}
53 The hardware sets a physical page size (always a multiple of 2, for speed
54 reasons), 4KB in the case of MIPS. Virtual address space is split into
55 pages, which are directly mapped to physical ``frames''. Each process has
56 an associated page table to map virtual addresses to physical ones. The
57 virtual address has an offset and a page number, and a Page Table Entry
58 specifies a frame that corresponds to the page. The PTE can also have some
59 flag bits, to mark pages as read-only, executable, dirty, etc. A special
60 register holds the address of the page table. Notice that this is more overhead
61 than the dynamic relocation scheme. The kernel must manage the page table. This
62 leads to \textbf{internal fragmentation} where we lose memory at the end of
63 every unfilled page. A page number can be calculated using ($V$ is the virtual
64 address)
65 \[ \left\lfloor \frac{V}{\mathrm{page size}} \right\rfloor \] 
66 and offset is $V \bmod \mathrm{page size}$.
67
68 \end{document}