half done lec 5 notes
[kspaans/CS350] / lec04-0514.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{May 14, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle
9
10 \section*{Lecture 4 -- Implementing Mutual Exclusion}
11 There are a bunch of different ways that we can implement mutexes, to varying
12 levels of complexity and generality.
13
14 \subsection*{Peterson's Algorithm}
15 Peterson's Algorithm is cool because we can implement it in C, without needing
16 any assembly language or hardware-specific instructions. It only relies on
17 the atomicity of load/store instructions. The \texttt{turn} variable protects
18 against deadlock in the case where both threads try to enter the critical
19 section at the same time. It, however, only works on two threads.
20
21 \subsection*{Hardware Specific Instructions}
22 Built-in stuff like ``test-and-set'', ``compare-and-swap'' or on modern MIPS
23 hardware, ``load-link/store-conditional''. \emph{SYS161} does not support this,
24 so we rely on controlling interrupts. An example of how we can implement a
25 spinlock in C: \\
26 \texttt{while (TestAndSet(\&lock,true) {}}
27
28 Spinlocks are useful on multicore systems, because they avoid the overhead of
29 putting threads to sleep, or yielding. Especially if the lock is only expected
30 to be held for a short period of time, then the thread will remain busy doing
31 nothing until the lock is freed, or until it uses up it's timeslice (quanta)
32 and gets preempted. On uniprocessor systems, this is not very useful, since the
33 only thing the thread can do is spin until it gets preempted.
34
35 \subsection*{Semaphores}
36 Can be implemented by disabling interrupts to get atomic actions (\emph{OS161}),
37 using Peterson's Algorithm, or by using hardware-specific atomic instructions.
38 Some mnemonics that I like for remembering how to use semaphores:
39 \texttt{P()} for ``push down''. It decrements the semaphore's value unless it
40 is 0, in which case the thread is put to sleep. \texttt{V()} for ``vroom up''
41 will increment the semaphore's value and wakeup any threads that are sleeping
42 on it - it's like telling them that the resource is available again. We can
43 use this to implement a mutex like so:
44 \begin{enumerate}
45 \item Initialize semaphore with a value of 1, spawn threads.
46 \item Thread will \texttt{P()} the semaphore before entering it's critical
47       section, and \texttt{V()} it on exit.
48 \end{enumerate}
49 Another example of use can be the producer-consumer problem. This can be hard
50 to get right when you are using multiple semaphores at the same time. The order
51 needs to be correct, especially for \texttt{P()}'s, since they are blocking
52 functions (e.g. they will sleep if the resource is not available.
53
54 Another use is in the \emph{OS161} thread tests, or in the cat and mouse example
55 code in the course notes. The forked threads will \texttt{V()} when they are
56 complete, and the parent thread \texttt{P()}'s to make sure that all it's
57 children are done before exiting itself. This is called ``barrier synchronization''.
58
59 \end{document}