added load balancing to lec 18 notes
[kspaans/CS350] / lec17-0702.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{July 2, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 17 -- Scheduling}
11 First, some notes about A3. At boot the kernel code and data are loaded into
12 the lowest portion of memory (recall that \texttt{0x80000000} gets mapped
13 directly to \texttt{0x00000000}). \texttt{Runprogram()} reads the ELF file to
14 decide how big the program's segments are and what will go in them. When doing
15 this it immediately allocates frames of memory and adjusts the thread's address
16 space struct accordingly. \texttt{Load\_elf()} will then fill these allocated
17 segments accordingly from the contents of the ELF file. Page faults will occur
18 immediately as \texttt{load\_elf()} tries to write to the fresh pages in
19 memory. The kernel takes the data from the thread's address space structure and
20 fills the TLB.
21
22 In A3 we will be implementing dynamic loading of pages. This means that memory
23 will not actually be allocated until that page is used by the program. The
24 point is that our OS should let us ``run'' programs that have huge ELF files
25 (larger than the amount of physical memory \emph{SYS161} has) that, if loaded
26 directly into memory when run, would cause the system to run out of memory.
27 Since the programs will only touch a small number of pages within their address
28 spaces, they should be able to work. There are tests specifically for this. We
29 will also implement a page freer so that \emph{OS161} won't crash all the time.
30 It should be able to reclaim pages that have been entirely freed (E.G. when a
31 thread terminates). The \textt{kfree()} already handles allocation and freeing
32 within subpages, but once a whole page it touched, the kernel does not try to
33 reclaim it. It will be a \textbf{physical memory manager}.
34
35 Some gotchas to watch out for! Page faults should happen as segments get filled
36 with data and code. However, we will be doing this while inside of the
37 interrupt handler. Page faults should not be generated when inside of the page
38 fault handler! We need to make sure that the TLB is properly filled before
39 trying to touch any memory when inside of the page fault handler. A similar
40 example is when we find a segment in the ELF file that is marked as read-only.
41 If the page is marked as read-only before we start copying bits into it,
42 \emph{bad} things will happen.
43
44 A tip for avoiding this is to remember that kernel virtual addresses
45 (\texttt{0x80000000} and up) map directly to physical addresses. They cannot
46 generate page faults. Therefore we can substitute kernel vritual addresses for
47 any userspace virtual address without having to worry about generating more
48 page faults. (We will get a ``bus error'' if we touch invalid kernel virtual
49 addresses.)
50
51 \subsection*{What's a Scheduler?}
52 The scheduler is a kernel program (subsystem?) that decides which processes get
53 to run next whenever a thread blocks, yields, exits, or gets pre-empted (and
54 has used up it's quantum, if the schedules defines such a thing). We say that
55 programs divide their life between CPU bursts and I/O bursts. CPU bursts
56 involve computation, whereas I/O Bursts involve the process being blocked
57 waiting for I/O to complete. That is to say, it schedules a processes CPU
58 bursts.
59
60 \subsection*{Preemptive and Non-preemptive Scheduling Algorithms}
61 First-Come First-Served, Round-Robin, Shortest Job First, Shortest Remaining
62 Time First, Highest Respone Ratio Next. There is a concept of the ``ready
63 queue''. Processes get put in the queue as they are created or become
64 unblocked. There is also a wait queue where blocked processes go. Some
65 algorithms aim to lower average time spent in the wait queue (SJF). For this
66 to be practical however, the lengths of the processes CPU bursts would have to
67 be predicted. This can be done by taking an exponential average of previous
68 burst lengths for example. Note that starvation can happen with SJF if there is
69 a long job waiting, but new and shorter jobs keep appearing. HRRN will prevent
70 this since each process's status gets updated as time goes on, so eventually
71 the long job will get selected (waiting time is accounted for in the ratio).
72
73 Another idea is to prioritize processes. This can help schedule more important
74 ones better. This can also lead to starvation though. To avoid this the kernel
75 should have a way of modifying the priority of processes so that ones which
76 wait too long will have a chance to run. (Think of the UNIX \texttt{nice}
77 program.)
78 \end{document}