added load balancing to lec 18 notes
[kspaans/CS350] / lec07-0526.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{May 26, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle
9
10 \section*{Lecture 7 -- Deadlocks and Processes}
11 For assignment A1, note that the CV's functions are only supposed to be called
12 from inside of a critical section. I.E. the lock parameter should be checked to
13 make sure the calling thread holds it.
14
15 \subsection*{Deadlock Detection and Prevention}
16 We look at an algorithm for detecting deadlocks, given a ``graph'' describing
17 the allocated resources, requested resources, and thread states. Constantly
18 checking this is expensive though. Alternatively we can have strategies to
19 prevent deadlock.
20
21 ``No Hold and Wait'' notices that we only get deadlock because we can wait on
22 a resource while also holding some resources. We only let threads acquire
23 one or more resources at one time and force them to release those before
24 requesting more. This will prevent deadlocks.
25
26 ``Resource Ordering'' lets us put restrictions on the order in which resources
27 are allocated. This means that we can't have cyclic dependancies. Each resource
28 is assigned an increasing number $i$. After allocating resource number $i$, a
29 thread can't allocate any more resources of number $\le i$.
30
31 \subsection*{Processes}
32 Processes are an abstraction of a program's encapsulation. A ``process''
33 carries around a bunch of extra information about itself: open files, sockets,
34 attributes, virtual memory. All of this is shared between the one or more
35 threads that are part of the process. Multiprogramming, therefore, means
36 basically multiple processes (each possibly with multiple threads). Processes
37 also keep programs isolated from each other. This means if a program crashes,
38 it can't hurt or disrupt it's neighbour. It also means processes can't talk.
39 If they want to share data or information, they can ask the kernel to do it
40 for them (IPC).
41
42 Remember that the kernel is just a program like any other. The difference is
43 that it runs in privileged mode. It can exectute privileged instructions
44 (change CPU state) and access certain memory addresses that regular programs
45 can't. The kernel even has it's own slice of memory that's kept seperate from
46 other programs. Normal programs should not be able to modify any of the
47 kernel's code or data. The kernel is not, however, a process. We'll learn more
48 about this soon.
49
50 \subsection*{System Calls}
51 System calls are the interface that the kernel provides to userspace. They are
52 like procedure calls, except that they run in a different memory address space
53 and they are run in privileged mode. Because it is kernel code that makes up
54 the body of the system call, it naturally runs in the kernel's address space
55 and runs at the kernel's privilege level.
56
57 System calls are supported by
58 machine dependant instructions (\texttt{syscall} in the case of MIPS, and
59 \texttt{int 80h} or some such on x86). This is necessary in order to change
60 the privilege level of the code (normal procedure calls can't do this). This
61 essentially means that a system call causes a software interrupt, which jumps
62 into the exception handler, which notices that a system call has occurred and
63 jumps to the correct procedure in the kernel. The special instruction will also
64 do some custodial work, such as saving the PC into \$29 (RA).
65
66 Function prototypes, in \emph{OS161} are defined in \texttt{unistd.h}, and each
67 system call has a man page describing it. Our userspace application gets linked
68 with the standard library, which wraps around system calls. So if we look at a
69 disassembled program (see course notes) we'll notice that our system call gets
70 compiled into a regular procedure call. This jumps into the part of the
71 executable that contains the standard library, which then performs the system
72 call for us. Also notice that the standard library provides global variables
73 like \texttt{errno} which get mutated by system calls to contain special error
74 values. These are all defined in \texttt{errno.h} to have unique meanings --
75 telling the application what kind of error occured.
76
77 \end{document}