lecture 4 notes
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Thu, 14 May 2009 20:25:27 +0000 (16:25 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Thu, 14 May 2009 20:25:27 +0000 (16:25 -0400)
lec04-0514.tex [new file with mode: 0644]

diff --git a/lec04-0514.tex b/lec04-0514.tex
new file mode 100644 (file)
index 0000000..9ce1a1b
--- /dev/null
@@ -0,0 +1,59 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{May 14, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle
+
+\section*{Lecture 4 -- Implementing Mutual Exclusion}
+There are a bunch of different ways that we can implement mutexes, to varying
+levels of complexity and generality.
+
+\subsection*{Peterson's Algorithm}
+Peterson's Algorithm is cool because we can implement it in C, without needing
+any assembly language or hardware-specific instructions. It only relies on
+the atomicity of load/store instructions. The \texttt{turn} variable protects
+against deadlock in the case where both threads try to enter the critical
+section at the same time. It, however, only works on two threads.
+
+\subsection*{Hardware Specific Instructions}
+Built-in stuff like ``test-and-set'', ``compare-and-swap'' or on modern MIPS
+hardware, ``load-link/store-conditional''. \emph{SYS161} does not support this,
+so we rely on controlling interrupts. An example of how we can implement a
+spinlock in C: \\
+\texttt{while (TestAndSet(\&lock,true) {}}
+
+Spinlocks are useful on multicore systems, because they avoid the overhead of
+putting threads to sleep, or yielding. Especially if the lock is only expected
+to be held for a short period of time, then the thread will remain busy doing
+nothing until the lock is freed, or until it uses up it's timeslice (quanta)
+and gets preempted. On uniprocessor systems, this is not very useful, since the
+only thing the thread can do is spin until it gets preempted.
+
+\subsection*{Semaphores}
+Can be implemented by disabling interrupts to get atomic actions (\emph{OS161}),
+using Peterson's Algorithm, or by using hardware-specific atomic instructions.
+Some mnemonics that I like for remembering how to use semaphores:
+\texttt{P()} for ``push down''. It decrements the semaphore's value unless it
+is 0, in which case the thread is put to sleep. \texttt{V()} for ``vroom up''
+will increment the semaphore's value and wakeup any threads that are sleeping
+on it - it's like telling them that the resource is available again. We can
+use this to implement a mutex like so:
+\begin{enumerate}
+\item Initialize semaphore with a value of 1, spawn threads.
+\item Thread will \texttt{P()} the semaphore before entering it's critical
+      section, and \texttt{V()} it on exit.
+\end{enumerate}
+Another example of use can be the producer-consumer problem. This can be hard
+to get right when you are using multiple semaphores at the same time. The order
+needs to be correct, especially for \texttt{P()}'s, since they are blocking
+functions (e.g. they will sleep if the resource is not available.
+
+Another use is in the \emph{OS161} thread tests, or in the cat and mouse example
+code in the course notes. The forked threads will \texttt{V()} when they are
+complete, and the parent thread \texttt{P()}'s to make sure that all it's
+children are done before exiting itself. This is called ``barrier synchronization''.
+
+\end{document}