Lecture 3 notes done, webpages generated too
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Wed, 13 May 2009 01:50:39 +0000 (21:50 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Wed, 13 May 2009 01:50:39 +0000 (21:50 -0400)
lec03-0512.tex [new file with mode: 0644]

diff --git a/lec03-0512.tex b/lec03-0512.tex
new file mode 100644 (file)
index 0000000..05f6a1c
--- /dev/null
@@ -0,0 +1,87 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{May 12, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle
+
+\section*{Lecture 3 -- Implementing Threads}
+A question to start: How would we go about implementing the creation of new
+threads for use by \texttt{thread\_fork()}? First, we should allocate memory
+for that thread's stack. Then we need to setup the correct registers for this
+stack, similarly to what \texttt{switch.S} does, see the image on slide 11 of
+the course notes. Considering that one of the arguments to
+\texttt{thread\_fork()} is a pointer to a function that should be executed by
+that thread, we can deduce that the value pushed into the \texttt{ra} register
+in that stack should be the address of that function. Note that we don't
+start running the thread yet! The thread has to wait until someone else
+yield's execution to it.
+
+\subsection*{Scheduling}
+Choosing which thread we want to run next is ``scheduling''. This can be done
+after \texttt{thread\_yield()} is called, or it can be done after certain
+interrupts (preemptive multitasking).
+
+\subsection*{Preemption}
+Interrupts can involuntarily stop a thread's execution. Generally it is the
+system's hardware will generate interrupts (e.g. strokes of the keyboard,
+packets on the network interface, clock-tick from the hardware real-time clock).
+ Interrupts can force a context switch,
+where the CPU, at the end of a fetch-execute cycle, will jump to (change PC
+to) a specific location in memory (to be discovered later!) where the
+exception-handling code lies. This cases a ``trap frame'' to be saved in the
+middle of the currently running program, then the exception-handler is allowed
+to do whatever it wishes (including calling other kernel functions). It must
+figure out what to do based on the type of interrupt. It can then optionally
+call \texttt{thread\_yield()} to yield to the scheduler or just resume the same
+program (if, for example the interrupt is from a clock tick). See picture
+in hardcopy notes. The code that does this is in
+\texttt{kern/mips/mips/exception.S}, more details can be seen there.
+
+Note that the current thread's running program can get interrupted anywhere!
+And this is where execution will continue when the thread gets handed CPU time
+again. That is, execution will start with the exception-handler code, whose
+stack frames will get popped until the trap frame get loaded back into the
+CPU registers, and the program starts running again where it was interrupted.
+
+\subsection*{Round-Robin Scheduling}
+It's preemptive! The idea is that we maintain a queue of runable threads, and
+each one gets an equal timeslice on the processor(s). We call them ``quanta'',
+and can be any number of clock ticks we want. This is implemented with the
+hardware real-time clock. It periodically interrupts the CPU. The exception-
+handler can maintain a variable to count the number of clock ticks that a
+thread has used (initialized at 0 everytime a thread is started) and while
+the count is less than the maximum amount allowed by the scheduler the
+exception-handler can return execution directly back to the running program.
+This is fast, and needs to be since it is typically happening many times a
+second. Currently \emph{OS161} is
+configured to have clock interrupts at a rate of 100 Hz. If the
+incremented counter is beyond the allowed amount, then the exception-handler
+can jump the scheduler, preempting the current thread. If the quanta is $t$
+clock ticks, then we can expect the scheduler to be called one in every $t$
+clock interrupts.
+
+\subsection*{Concurrency}
+On a multiprocessor system multiple threads can actually be running at any given
+time, whereas on a uniprocessor system, the user get the perception that
+multiple threads are running at once (due to preemptive scheduling). So in
+either case we can have ``concurrent'' access to shared resources.
+
+Since multiple threads can have access to global variables or dynamically
+allocated data structures, bad things can happen when they are accessed and
+modified concurrently. To save ourselves trouble, we want to enforce
+``mutual exlcusion'' on ``critical sections'' of code where shared memory is
+accessed. See the linked-list code examples in the course notes.
+
+\subsection*{Implementing Mutual Exclusion}
+One method to implement mutexes is to use the hardware to temporarily turn off
+interrupts. A couple of disadvantages are that it only works on uniprocessor
+systems (since preemption is what causes concurrency) and when interrupts are
+turned off they get ignored, which means we can miss things. For example,
+keystrokes or network packets, or losing track of time. To modify the handling
+of interrupts, \texttt{splhigh()}, \texttt{spl0()}, \texttt{splx()}. See
+\texttt{kern/arch/mips/include/spl.h} for more information.
+
+\end{document}