completed lec 20,21,22 -- still need lec 23
[kspaans/CS350] / lec03-0512.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{May 12, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle
9
10 \section*{Lecture 3 -- Implementing Threads}
11 A question to start: How would we go about implementing the creation of new
12 threads for use by \texttt{thread\_fork()}? First, we should allocate memory
13 for that thread's stack. Then we need to setup the correct registers for this
14 stack, similarly to what \texttt{switch.S} does, see the image on slide 11 of
15 the course notes. Considering that one of the arguments to
16 \texttt{thread\_fork()} is a pointer to a function that should be executed by
17 that thread, we can deduce that the value pushed into the \texttt{ra} register
18 in that stack should be the address of that function. Note that we don't
19 start running the thread yet! The thread has to wait until someone else
20 yield's execution to it.
21
22 \subsection*{Scheduling}
23 Choosing which thread we want to run next is ``scheduling''. This can be done
24 after \texttt{thread\_yield()} is called, or it can be done after certain
25 interrupts (preemptive multitasking).
26
27 \subsection*{Preemption}
28 Interrupts can involuntarily stop a thread's execution. Generally it is the
29 system's hardware will generate interrupts (e.g. strokes of the keyboard,
30 packets on the network interface, clock-tick from the hardware real-time clock).
31  Interrupts can force a context switch,
32 where the CPU, at the end of a fetch-execute cycle, will jump to (change PC
33 to) a specific location in memory (to be discovered later!) where the
34 exception-handling code lies. This cases a ``trap frame'' to be saved in the
35 middle of the currently running program, then the exception-handler is allowed
36 to do whatever it wishes (including calling other kernel functions). It must
37 figure out what to do based on the type of interrupt. It can then optionally
38 call \texttt{thread\_yield()} to yield to the scheduler or just resume the same
39 program (if, for example the interrupt is from a clock tick). See picture
40 in hardcopy notes. The code that does this is in
41 \texttt{kern/mips/mips/exception.S}, more details can be seen there.
42
43 Note that the current thread's running program can get interrupted anywhere!
44 And this is where execution will continue when the thread gets handed CPU time
45 again. That is, execution will start with the exception-handler code, whose
46 stack frames will get popped until the trap frame get loaded back into the
47 CPU registers, and the program starts running again where it was interrupted.
48
49 \subsection*{Round-Robin Scheduling}
50 It's preemptive! The idea is that we maintain a queue of runable threads, and
51 each one gets an equal timeslice on the processor(s). We call them ``quanta'',
52 and can be any number of clock ticks we want. This is implemented with the
53 hardware real-time clock. It periodically interrupts the CPU. The exception-
54 handler can maintain a variable to count the number of clock ticks that a
55 thread has used (initialized at 0 everytime a thread is started) and while
56 the count is less than the maximum amount allowed by the scheduler the
57 exception-handler can return execution directly back to the running program.
58 This is fast, and needs to be since it is typically happening many times a
59 second. Currently \emph{OS161} is
60 configured to have clock interrupts at a rate of 100 Hz. If the
61 incremented counter is beyond the allowed amount, then the exception-handler
62 can jump the scheduler, preempting the current thread. If the quanta is $t$
63 clock ticks, then we can expect the scheduler to be called one in every $t$
64 clock interrupts.
65
66 \subsection*{Concurrency}
67 On a multiprocessor system multiple threads can actually be running at any given
68 time, whereas on a uniprocessor system, the user get the perception that
69 multiple threads are running at once (due to preemptive scheduling). So in
70 either case we can have ``concurrent'' access to shared resources.
71
72 Since multiple threads can have access to global variables or dynamically
73 allocated data structures, bad things can happen when they are accessed and
74 modified concurrently. To save ourselves trouble, we want to enforce
75 ``mutual exlcusion'' on ``critical sections'' of code where shared memory is
76 accessed. See the linked-list code examples in the course notes.
77
78 \subsection*{Implementing Mutual Exclusion}
79 One method to implement mutexes is to use the hardware to temporarily turn off
80 interrupts. A couple of disadvantages are that it only works on uniprocessor
81 systems (since preemption is what causes concurrency) and when interrupts are
82 turned off they get ignored, which means we can miss things. For example,
83 keystrokes or network packets, or losing track of time. To modify the handling
84 of interrupts, \texttt{splhigh()}, \texttt{spl0()}, \texttt{splx()}. See
85 \texttt{kern/arch/mips/include/spl.h} for more information.
86
87 \end{document}