-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcs350.html
More file actions
387 lines (377 loc) · 16.2 KB
/
cs350.html
File metadata and controls
387 lines (377 loc) · 16.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>cs350</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<link rel="stylesheet" href="../pandoc.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.js"></script>
<script>document.addEventListener("DOMContentLoaded", function () {
var mathElements = document.getElementsByClassName("math");
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") { katex.render(texText.data, mathElements[i], { displayMode: mathElements[i].classList.contains("display"), throwOnError: false } );
}}});</script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="cs-350">CS 350</h1>
<p>An OS is a system that manages resources, creates execution environments, loads programs, and provides common services and utilities.</p>
<ul>
<li>Started as simple I/O libraries, batch processors.</li>
</ul>
<h2 id="three-views-of-an-os">Three Views of an OS</h2>
<ol type="1">
<li><strong>Application View</strong>: What services does it provide?</li>
<li><strong>System View</strong>: What problem does it solve?</li>
<li><strong>Implementation View</strong>: How is it built?</li>
</ol>
<h3 id="application-view">Application View</h3>
<p>Provides an execution environment for running programs.</p>
<ul>
<li>Provides program with processor time and memory space that it needs.</li>
<li>Provides interfaces through which program can use networks, storage, I/O devices, other system hardware components. We want to abstract hardware from application programs.</li>
<li>Isolates running programs from another and prevents undesirable interactions.</li>
</ul>
<h3 id="system-view">System View</h3>
<ul>
<li>Manages hardware resources of a computer system including processors, memory, disks, network interfaces, I/O devices, etc.</li>
<li>Allocates resources among running programs.</li>
<li>Controls the sharing of resources among programs.</li>
</ul>
<p>The OS itself also uses resources.</p>
<h3 id="implementation-view">Implementation View</h3>
<ul>
<li>Concurrency arises naturally in an OS when it supports concurrent applications, because it must interact directly with the hardware.</li>
<li>Hardware interactions impose timing constraints.</li>
</ul>
<p><strong>Kernel</strong>: Part of OS that responds to system calls, interrupts, and exceptions.</p>
<p><strong>Operating System</strong>: OS as a while includes the kernel, and may include other related programs to provide services for applications.</p>
<ul>
<li>Utility programs.</li>
<li>Command interpreters.</li>
<li>Programming libraries.</li>
</ul>
<p>The <strong>execution environment</strong> provides by the OS includes a variety of <strong>abstractions</strong>.</p>
<ul>
<li><strong>Files and file systems</strong>. Secondary storage.</li>
<li><strong>Address spaces</strong>. Primary memory (RAM).</li>
<li><strong>Processes, threads</strong>. Program execution.</li>
<li><strong>Sockets, pipes</strong>. Network or other message channels.</li>
</ul>
<h1 id="threads-and-concurrency">Threads and Concurrency</h1>
<blockquote>
<p>Better utilization of the CPU.</p>
</blockquote>
<p>What is a tread? It is a sequence of instructions.</p>
<ul>
<li>A normal <strong>sequential program</strong> consists of a single thread of execution.</li>
<li>Threads provide a way for programmers to express <strong>concurrency</strong> in a program.</li>
<li>In threaded concurrent programs, there are multiple threads of execution, all occuring at the same time.</li>
</ul>
<p>OS/161 Thread Interface.</p>
<blockquote>
<p>kern/include/thread.h</p>
</blockquote>
<pre><code>int thread_fork(
const char* name,
struct proc* proc,
void (*func)(void*, unsigned long),
void* data1,
unsigned long data2);
// Terminate the calling thread.
void thread_exit(void);
// Voluntarily yield execution.
void thread_yield(void);</code></pre>
<h2 id="implementing-concurrent-threads">Implementing Concurrent Threads</h2>
<blockquote>
<p>What options exist?</p>
</blockquote>
<ol type="1">
<li>Hardware support. <span class="math inline">P</span> processors, <span class="math inline">C</span> cores, <span class="math inline">M</span> multithreading per core. <span class="math inline">PCM</span> threads can execute <strong>simultaneously</strong>.</li>
<li>Timesharing. Multiple threads take turns on the same hardware, rapidly switching between threads.</li>
<li>Hardware support <strong>and</strong> timesharing. <span class="math inline">PCM</span> threads running simultaneously with timesharing.</li>
</ol>
<h3 id="context-switching">Context Switching</h3>
<blockquote>
<p>Various Stack Frames <span class="math inline">\to</span> <strong>thread_yield</strong> <span class="math inline">\to</span> <strong>thread_switch</strong> <span class="math inline">\to</span> <strong>switchframe</strong>.</p>
</blockquote>
<blockquote>
<p>kern/arch/mips/thread/switch.S</p>
</blockquote>
<pre><code>switchframe_switch:
/* a0: switchframe pointer of old thread. */
/* a1: switchframe pointer of new thread. */
/* Allocate space for 10 registers. */
addi sp, sp, -40
/* Return address. */
sw ra, 36(sp)
/* Globals pointer. */
sw gp, 32(sp)
sw s8, 28(sp)
sw s6, 24(sp)
sw s5, 20(sp)
sw s4, 16(sp)
sw s3, 12(sp)
sw s2, 8(sp)
sw s1, 4(sp)
sw s0, 0(sp)
/* Store old stack pointer in old thread. */
sw sp, 0(a0)</code></pre>
<blockquote>
<p>Loading data from the new stack pointer is similar. Uses <strong>nop</strong> operation in order to ensure loads have completed before usage.</p>
</blockquote>
<h4 id="context-switch-causes">Context Switch Causes</h4>
<ol type="1">
<li>Running thread calls <strong>thread_yield</strong>. Voluntarily allows other threads to run.</li>
<li>Running thread calls <strong>thread_exit</strong>. Running thread is terminated.</li>
<li>Running thread blocks, with call to <strong>wchan_sleep</strong>.</li>
<li>Running thread is <em>preempted</em>. Involuntarily stops running.</li>
</ol>
<h4 id="thread-states">Thread States</h4>
<ol type="1">
<li><strong>Running</strong>. Currently executing.</li>
<li><strong>Ready</strong>. Ready to execute.</li>
<li><strong>Blocked</strong>. Waiting for something, not ready to execute.</li>
</ol>
<h3 id="timesharing-and-preemption">Timesharing and Preemption</h3>
<ul>
<li><strong>Timesharing</strong>. Concurrency achieved by rapidly switching between theads.
<ul>
<li>How rapidly? <strong>Scheduling quantum</strong>.</li>
<li>Must have an <strong>upper bound</strong> on how long a thread can run before it must yield the CPU.</li>
</ul></li>
<li>How do you stop a running thread that never yields, blocks, or exits?
<ul>
<li><strong>Preemption</strong> forces a running thread to stop running.</li>
<li>Thread library must have a means of “getting control”.</li>
<li>Normally accomplished using <strong>interrupts</strong>.
<ul>
<li>Thread library places a procedure called an <em>interrupt handler</em>.</li>
</ul>
<ol type="1">
<li>Creates a <em>trap frame</em> to record thread context at the time of the interrupt.</li>
<li>Determines which device caused interrupt, device-specific processing.</li>
<li>Restores saved thread context from trap frame and resumes execution of the thread.</li>
</ol></li>
</ul></li>
</ul>
<h3 id="preemptive-scheduling">Preemptive Scheduling</h3>
<ul>
<li>Preemptive scheduler uses the <strong>scheduling quantum</strong> to impose a time limit on running threads.</li>
<li>Periodic timer interrupts allow running time to be tracked.</li>
<li>If thread run too long, timer interrupt handler preempts the thread by calling <strong>thread_yield</strong>.</li>
<li>Preempted thread changes state from running to ready, and is placed on the <em>ready queue</em>.</li>
<li>Scheduled quantum is reset each time a thread gets to run, no concept of leftover time.</li>
</ul>
<blockquote>
<p>OS/161 threads use <em>preemptive round-robin scheduling</em>.</p>
</blockquote>
<p>Every time an interrupt is called, a <strong>trap frame</strong> is the first. Then the interrupt handler stack frame is called, followed by the normal context switching procedures.</p>
<p>When returning from the <strong>trap_frame</strong>, the original state is restored.</p>
<h2 id="locks-mutex">Locks (Mutex)</h2>
<p>Before entering a critical section, acquire a lock. Upon leaving, release the lock.</p>
<p>Implemented in hardware because we need an atomic <strong>test-and-set</strong>.</p>
<pre><code>Acquire(bool* lock) {
while (Xchg(true, lock) == true);
}
Release(bool* lock) {
*lock = false;
}</code></pre>
<blockquote>
<p><strong>printf</strong> forces the execution of threads to be a certain way, and can hide race conditions in your code!</p>
</blockquote>
<h3 id="arm">ARM</h3>
<pre><code>ARMTestAndSet(addr, value) {
// Load value.
tmp = LDREX addr
// Store new value.
result = STREX value, addr
if (result == SUCCEED) return tmp
return TRUE
}
Acquire(bool *lock) {
while(ARMTestAndSet(lock, true) == true) {};
}</code></pre>
<h3 id="spinlocks-in-os161">Spinlocks in OS/161</h3>
<ul>
<li><p>“Spins” repeatedly until the lock is available.</p>
<p>struct spinlock { volatile spinlock_data_t lk_lock; struct cpu* lk_holder; };</p>
<p>void spinlock_init(struct spinlock* lk); void spinlock_acquire(struct spinlock* lk); void spinlock_release(struct spinlock* lk);</p></li>
</ul>
<blockquote>
<p><em>spinlock_acquire</em> calls <em>spinlock_data_testandset</em> in a loop until the lock is acquired. It <strong>turns off interrupts</strong> on the cpu.</p>
</blockquote>
<p>Spinlocks are not efficient, if we want large chunks of code protected, we should use a <strong>lock</strong> (<strong>mutex</strong>). The difference is that spinlocks spin, locks <strong>block</strong>.</p>
<h3 id="thread-blocking">Thread Blocking</h3>
<ul>
<li>When a thread blocks, it stops running.
<ul>
<li>Context switch from blocking thread to a new thread.</li>
<li>Waits.</li>
</ul></li>
<li>Eventually, a blocked thread is signaled and awakened by another thread.</li>
</ul>
<h3 id="wait-channels-in-os161">Wait Channels in OS/161</h3>
<blockquote>
<p>Wait channels are used to implement thread blocking.</p>
</blockquote>
<pre><code>void wchan_sleep(struct wchan* wc);
void wchan_wakeall(struct wchan* wc);
void wchan_wakeone(struct wchan* wc);
void wchan_lock(struct wchan* wc);</code></pre>
<ul>
<li>Blocks calling thread on wait channel wc.</li>
<li>Unblocks all threads sleeping on wait channel.</li>
<li>Unblock one thread sleeping on wait channel.</li>
<li>Prevent operations on wait channel.</li>
</ul>
<h2 id="semaphores">Semaphores</h2>
<ul>
<li>A semaphore is an object with an interger value, supporting two operations.</li>
</ul>
<ol type="1">
<li><strong>P</strong>: If the semaphore value is greater than 0, decrement. Otherwise wait until we can.</li>
<li><strong>V</strong>: Increment the value of the semaphore.</li>
</ol>
<blockquote>
<p><strong>P</strong> and <strong>V</strong> are <strong>atomic</strong>.</p>
</blockquote>
<ul>
<li><strong>Binary semaphore</strong>. Single resource, behaves like a lock but does not keep track of ownership.</li>
<li><strong>Counting semaphore</strong>. Arbitrary number of resources.</li>
</ul>
<p>Example.</p>
<pre><code>volatile int total = 0;
struct semaphore *total_sem;
total_sem = sem_create("total_mutex", 1);
void add() {
int i;
for (i = 0; i < N; ++i) {
P(sem);
total++;
V(sem);
}
}</code></pre>
<h2 id="condition-variables">Condition Variables</h2>
<ul>
<li>Condition variable is intended to work together with a lock. Only available from <strong>within the critical section that is protected by the lock</strong>.
<ul>
<li><strong>wait</strong>. Causes calling thread to block, releases the lock associated with condition variable. Reaquires lock once thread is unblocked.
<ul>
<li>Release lock and put me to sleep.</li>
<li>Acquire lock and return.</li>
<li><strong>Note</strong>. Implementation of <strong>cv_wait</strong> will be asked on examinations.</li>
<li><strong>MESA Style Rough Steps</strong>. lock wchan, release lock, sleep, acquire luck</li>
<li><strong>Note</strong>. Reccomended to use CV on traffic question.</li>
</ul></li>
<li><strong>signal</strong>. If threads are blocked on signaled condition variable, one of the threads are unblocked.</li>
<li><strong>broadcast</strong>. Like signal, but unblocks all threads blocked on that variable.</li>
</ul></li>
</ul>
<h1 id="a1-hint-aside">A1 Hint Aside</h1>
<ol type="1">
<li>Implement locks.</li>
<li>Implement condition variables.</li>
<li>Traffic simulation.
<ul>
<li>Improve flow of cars through the intersecation, currently only implements one car at a time.</li>
<li>Modify synchonization with locks, CVs, semaphores.
<ul>
<li>Semaphores are not recommended. CVs are.</li>
</ul></li>
</ul></li>
</ol>
<ul>
<li>You <strong>don’t</strong> need an individual lock for each CV.</li>
<li>You are not going to own the lock as you go through the intersection.</li>
<li>Need to check safely whether the car can enter the intersection and safely remove once they are out of the intersection.
<ul>
<li>Lock is used to protect the modification of the intersection, not for actually going through.</li>
</ul></li>
<li>Recommended number of CVs is <strong>4</strong>.</li>
</ul>
<p>Multiple ways to to keep track of where cars are in the intersection.</p>
<ul>
<li>OS/161 provides an array, queue, and a few other data structure libraries. Documentation can be found in the test directory.
<ul>
<li>Possible to do with simply counters.</li>
</ul></li>
<li>Can’t use wait channels directly.</li>
<li>Don’t modify traffic.c</li>
</ul>
<blockquote>
<p><strong>sy2, uw1, sy3</strong> are the tests to run.</p>
</blockquote>
<ul>
<li>Initialize your lock variables for CV.</li>
</ul>
<h2 id="volatile-and-race-conditions">Volatile and Race Conditions</h2>
<ul>
<li>Race conditions are mostly your fault, but they can also come from the <strong>compiler</strong> and <strong>CPU</strong>.
<ul>
<li>Optimizations.</li>
<li><strong>Memory models</strong> describe how threads access to memory in shared regions behave. Tells compiler and CPU which optimizations can be performed.
<ul>
<li>OS/161 does not have this.</li>
<li>CPU also has memory model which re-orders loads and stores. There are assembly level barriers to prevent race conditions at each level.</li>
</ul></li>
<li>Register optimizations.</li>
</ul></li>
<li>Keyword <strong>volatile</strong> disables the optimizations forcing a value to be loaded and stored to memory with each use. Prevents compiler from re-ordering loads and stores for that variable.</li>
</ul>
<h2 id="deadlocks">Deadlocks</h2>
<pre><code>lock lock_a, lock_b
int FuncA() {
lock_acquire(lock_a);
lock_acquire(lock_b);
...
lock_release(lock_a);
lock_relase(lock_b);
}
int FuncB() {
lock_acquire(lock_b);
lock_acquire(lock_a);
...
lock_relase(lock_b);
lock_release(lock_a);
}</code></pre>
<ul>
<li>Multiple threads are asleep waiting for each other. <strong>Deadlock</strong>.</li>
</ul>
<ol type="1">
<li><strong>No Hold and Wait</strong>. Prevent a thread from requesting resources if it currently has resources allocated to it. Either get them all at once, or have none.</li>
<li><strong>Resource Ordering</strong>. Order the resource types and require each thread acquire resources in increasing type order.</li>
</ol>
<p>Example.</p>
<pre><code>lock A, B
try_acquire() {
spin_acquire(lk->spin);
if (lk->held) {
release(lk->spin);
return false;
}
lk->held = true;
lk->owner = me;
release(lk->spin);
return true;
}
FuncA() {
acquire(A)
while(!try_acquire(B)) {
release(A);
acquire(A);
}
}</code></pre>
</body>
</html>