lecture 7 notes good to go
[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.
39
40 Remember that the kernel is just a program like any other. The difference is
41 that it runs in privileged mode. It can exectute privileged instructions
42 (change CPU state) and access certain memory addresses that regular programs
43 can't. The kernel even has it's own slice of memory that's kept seperate from
44 other programs. Normal programs should not be able to modify any of the
45 kernel's code or data. The kernel is not, however, a process. We'll learn more
46 about this soon.
47
48 \subsection*{System Calls}
49 System calls are the interface that the kernel provides to userspace. They are
50 like procedure calls, except that they run in a different memory address space
51 and they are run in privileged mode. Because it is kernel code that makes up
52 the body of the system call, it naturally runs in the kernel's address space
53 and runs at the kernel's privilege level.
54
55 System calls are supported by
56 machine dependant instructions (\texttt{syscall} in the case of MIPS, and
57 \texttt{int 80h} or some such on x86). This is necessary in order to change
58 the privilege level of the code (normal procedure calls can't do this). This
59 essentially means that a system call causes a software interrupt, which jumps
60 into the exception handler, which notices that a system call has occurred and
61 jumps to the correct procedure in the kernel. The special instruction will also
62 do some custodial work, such as saving the PC into \$29 (RA).
63
64 Function prototypes, in \emph{OS161} are defined in \texttt{unistd.h}, and each
65 system call has a man page describing it. Our userspace application gets linked
66 with the standard library, which wraps around system calls. So if we look at a
67 disassembled program (see course notes) we'll notice that our system call gets
68 compiled into a regular procedure call. This jumps into the part of the
69 executable that contains the standard library, which then performs the system
70 call for us. Also notice that the standard library provides global variables
71 like \texttt{errno} which get mutated by system calls to contain special error
72 values. These are all defined in \texttt{errno.h} to have unique meanings --
73 telling the application what kind of error occured.
74
75 \end{document}