-
Notifications
You must be signed in to change notification settings - Fork 17
Expand file tree
/
Copy path2Communication.html
More file actions
664 lines (632 loc) · 50.3 KB
/
Copy path2Communication.html
File metadata and controls
664 lines (632 loc) · 50.3 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
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
<!DOCTYPE html>
<html lang="en"
xmlns:og="http://ogp.me/ns#"
xmlns:fb="https://www.facebook.com/2008/fbml">
<head>
<title>Angold-4 Organization</title>
<!-- Using the latest rendering mode for IE -->
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link href="../../../images/favicon.png" rel="icon">
<link rel="canonical" href=".">
<meta name="author" content="Angold Wang" />
<meta property="og:site_name" content="Angold-4" />
<!-- <meta property="og:type" content="article"/> -->
<meta property="og:title" content="Angold-4 Organization"/>
<meta property="og:url" content="."/>
<!-- Bootstrap -->
<link rel="stylesheet" href="../../../theme/css/bootstrap.flatly.min.css" type="text/css"/>
<link href="../../../theme/css/font-awesome.min.css" rel="stylesheet">
<!-- <link href="https://cdnjs.cloudflare.com/ajax/libs/typicons/2.0.9/typicons.min.css" rel="stylesheet"> -->
<link href="../../../theme/css/pygments/monokai.css" rel="stylesheet">
<link rel="stylesheet" href="../../../theme/css/style.css" type="text/css"/>
<style>
#TOC li {
list-style: none;
}
#TOC ul {
padding-left: 1.3em;
}
#TOC > ul {
padding-left: 0;
}
#TOC a:not(:hover) {
text-decoration: none;
}
li {
font-size: 18px;
}
p {
font-size: 18px;
}
a {
font-size: 18px;
}
k
code {
font-family: Menlo, Monaco, 'Lucida Console', Consolas, monospace;
font-size: 85%;
margin: 0;
}
pre {
margin: 1em 0;
overflow: auto;
}
pre code {
padding: 0;
overflow: visible;
overflow-wrap: normal;
}
.sourceCode {
background-color: transparent;
overflow: visible;
}
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%;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
pre > code.sourceCode { white-space: pre; position: relative; }
pre > code.sourceCode > span { display: inline-block; line-height: 1.25; }
pre > code.sourceCode > span:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode > span { color: inherit; text-decoration: inherit; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
pre > code.sourceCode { white-space: pre-wrap; }
pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
}
pre.numberSource code
{ counter-reset: source-line 0; }
pre.numberSource code > span
{ position: relative; left: -4em; counter-increment: source-line; }
pre.numberSource code > span > a:first-child::before
{ content: counter(source-line);
position: relative; left: -1em; text-align: right; vertical-align: baseline;
border: none; display: inline-block;
-webkit-touch-callout: none; -webkit-user-select: none;
-khtml-user-select: none; -moz-user-select: none;
-ms-user-select: none; user-select: none;
padding: 0 4px; width: 4em;
color: #aaaaaa;
}
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
div.sourceCode
{ }
@media screen {
pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; }
}
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
code span.at { color: #7d9029; } /* Attribute */
code span.bn { color: #40a070; } /* BaseN */
code span.bu { } /* BuiltIn */
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
code span.ch { color: #4070a0; } /* Char */
code span.cn { color: #880000; } /* Constant */
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
code span.dt { color: #902000; } /* DataType */
code span.dv { color: #40a070; } /* DecVal */
code span.er { color: #ff0000; font-weight: bold; } /* Error */
code span.ex { } /* Extension */
code span.fl { color: #40a070; } /* Float */
code span.fu { color: #06287e; } /* Function */
code span.im { } /* Import */
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
code span.op { color: #666666; } /* Operator */
code span.ot { color: #007020; } /* Other */
code span.pp { color: #bc7a00; } /* Preprocessor */
code span.sc { color: #4070a0; } /* SpecialChar */
code span.ss { color: #bb6688; } /* SpecialString */
code span.st { color: #4070a0; } /* String */
code span.va { color: #19177c; } /* Variable */
code span.vs { color: #4070a0; } /* VerbatimString */
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
</style>
</head>
<body>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
<!-- <script src="https://code.jquery.com/jquery-2.2.4.min.js" integrity="sha256-BbhdlvQf/xTY9gja0Dq3HiwQF8LaCRTXxZKRutelT44=" crossorigin="anonymous"></script> -->
<div class="navbar navbar-default navbar-fixed-top" role="navigation">
<div class="container">
<div class="navbar-header">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-ex1-collapse">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
<a href="http://angold4.org" class="navbar-brand">
<img src="../../../images/logo.png" width="32"/> Angold4 </a>
</div>
<div class="collapse navbar-collapse navbar-ex1-collapse">
<ul class="nav navbar-nav">
<li><a href="../../../about.html">About</a>
<li><a href="../../../blogs.html">Blogs</a>
<li><a href="../../../projects.html">Projects</a>
</ul>
<ul class="nav navbar-nav navbar-right">
<li> <a title="Youtube" href="https://www.youtube.com/channel/UC3ZAjh2LHhm-FrgxgBtgMzQ" target="_new"><i class="fa fa-youtube"></i> Youtube</a>
</li>
</div>
<!-- /.navbar-collapse -->
</div>
</div> <!-- /.navbar -->
<div class="container">
<div class="row">
<div class="col-lg-12">
<section id="content" class="body">
<nav id="TOC" role="doc-toc">
<ul>
<li><a href="#operating-systems-design-and-implementation-notes"
id="toc-operating-systems-design-and-implementation-notes">Operating
Systems Design and Implementation Notes</a></li>
<li><a href="#interprocess-communication"
id="toc-interprocess-communication">2. Interprocess Communication</a>
<ul>
<li><a href="#thread" id="toc-thread">1. Thread</a>
<ul>
<li><a href="#thread-vs-process" id="toc-thread-vs-process">Thread vs
Process</a></li>
</ul></li>
<li><a href="#race-condition" id="toc-race-condition">2. Race
Condition</a></li>
<li><a href="#mutual-exclusion" id="toc-mutual-exclusion">3. Mutual
Exclusion</a>
<ul>
<li><a href="#strict-alternation" id="toc-strict-alternation">Strict
Alternation</a></li>
<li><a href="#mutexes" id="toc-mutexes">Mutexes</a></li>
</ul></li>
<li><a href="#condition-variable" id="toc-condition-variable">4.
Condition Variable</a></li>
</ul></li>
</ul>
</nav>
<h2 id="operating-systems-design-and-implementation-notes">Operating
Systems Design and Implementation Notes</h2>
<h1 id="interprocess-communication">2. Interprocess Communication</h1>
<h5 id="by-jiawei-wang">By Jiawei Wang</h5>
<p>In this note, we will look at some of the issues related to this
<strong>Interprocess Communication(IPC)</strong> <br> There are three
issues here:<br> 1. How one process can pass information to another? 2.
How can we make sure two or more processes do not get into each other’s
way when engaging in critical activities? 3. How to make sure the
sequence of related processes?(i.e. one process must run after
another)</p>
<h2 id="thread">1. Thread</h2>
<p><strong>Thread</strong> is also called as “<strong>lightweight
process</strong>”.<br>Means there are often situations to have multiple
processes of control in the <strong>same address space</strong>. ###
Introduction <strong>Example: <a
href="https://github.com/Angold-4/OSDI/blob/master/Chapter/Chapter2/Codes/threads.c">Codes/threads.c</a></strong></p>
<div class="sourceCode" id="cb1"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> x <span class="op">=</span> <span class="dv">2</span><span class="op">;</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a><span class="co">// threads shared memory</span></span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> routine<span class="op">()</span> <span class="op">{</span></span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a> x<span class="op">++;</span></span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"Test from threads %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> getpid<span class="op">());</span></span>
<span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a> sleep<span class="op">(</span><span class="dv">3</span><span class="op">);</span></span>
<span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"The value of x is %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> x<span class="op">);</span></span>
<span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-11"><a href="#cb1-11" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> routine2<span class="op">()</span> <span class="op">{</span></span>
<span id="cb1-12"><a href="#cb1-12" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"Test from threads %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> getpid<span class="op">());</span></span>
<span id="cb1-13"><a href="#cb1-13" aria-hidden="true" tabindex="-1"></a> sleep<span class="op">(</span><span class="dv">3</span><span class="op">);</span></span>
<span id="cb1-14"><a href="#cb1-14" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"The value of x is %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> x<span class="op">);</span></span>
<span id="cb1-15"><a href="#cb1-15" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb1-16"><a href="#cb1-16" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-17"><a href="#cb1-17" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> main<span class="op">(</span><span class="dt">int</span> argc<span class="op">,</span> <span class="dt">char</span><span class="op">*</span> argv<span class="op">[])</span> <span class="op">{</span></span>
<span id="cb1-18"><a href="#cb1-18" aria-hidden="true" tabindex="-1"></a> pthread_t t1<span class="op">,</span> t2<span class="op">;</span></span>
<span id="cb1-19"><a href="#cb1-19" aria-hidden="true" tabindex="-1"></a> <span class="co">// pthread_create 2nd parameter is the property of this thread</span></span>
<span id="cb1-20"><a href="#cb1-20" aria-hidden="true" tabindex="-1"></a> <span class="co">// 4th parameter is the arguments of function(3rd parameter)</span></span>
<span id="cb1-21"><a href="#cb1-21" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>t1<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="cf">return</span> <span class="dv">1</span><span class="op">;</span></span>
<span id="cb1-22"><a href="#cb1-22" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>t2<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine2<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="cf">return</span> <span class="dv">2</span><span class="op">;</span></span>
<span id="cb1-23"><a href="#cb1-23" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-24"><a href="#cb1-24" aria-hidden="true" tabindex="-1"></a> <span class="co">// pthread_join is used for waiting the return of the thread (otherwise the thread will not be executed)</span></span>
<span id="cb1-25"><a href="#cb1-25" aria-hidden="true" tabindex="-1"></a> <span class="co">// the 2nd parameter is the addr of storing the return value</span></span>
<span id="cb1-26"><a href="#cb1-26" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>t1<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb1-27"><a href="#cb1-27" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>t2<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb1-28"><a href="#cb1-28" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb1-29"><a href="#cb1-29" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
<p>We use the POSIX P-threads package to simulating threads in C
language.<br> <strong>Output:</strong></p>
<pre><code>❯ ./a.out
Test from threads 81205
Test from threads 81205
The value of x is 3
The value of x is 3</code></pre>
<p>These two threads shares the same address location and belong to the
same process.<br> <img src="Sources/thread.png" alt="thread" /></p>
<h3 id="thread-vs-process">Thread vs Process</h3>
<figure>
<img src="Sources/threads.png" alt="threads" />
<figcaption aria-hidden="true">threads</figcaption>
</figure>
<p>When several processes each have multiple threads, we have
<strong>two levels of parallelism</strong> present:</p>
<h4 id="process-level">1. Process level</h4>
<ul>
<li><strong>Process Scheduler</strong> (Inside kernel)
<ul>
<li>Please refer <strong><a
href="https://github.com/Angold-4/OSDI/blob/master/Chapter/Chapter2/5Scheduler.md">OSDI
5. Process Scheduler</a></strong></li>
</ul></li>
<li><strong>Scheduling is absolutely required on two occasions:</strong>
<ol type="1">
<li>When a process exits. (<strong><code>dequeue()</code></strong>)</li>
<li>When a process block(waiting) on I/O, or a semaphore.
(<strong><code>enqueue()</code></strong>)</li>
</ol></li>
<li><strong>Scheduling is not necessary but usually at these
times:</strong>
<ol type="1">
<li>When a new process is created.
(<strong><code>enqueue()</code></strong>)</li>
<li>When an I/O <strong>(hardware)</strong> interrupt occurs.
(<strong><code>hwint() -> dequeue() enqueue()</code></strong>)</li>
<li>When a clock interrupt occurs.
(<strong><code>dequeue() + enqueue()</code></strong>)</li>
</ol></li>
</ul>
<h4 id="threads-level">2. Threads level</h4>
<ul>
<li><p><strong>Thread Scheduler</strong> (“Inside” each
process)</p></li>
<li><p>For the <strong>user-level</strong> threads:</p>
<ul>
<li>The kernel is <strong>not aware of the existence of
threads</strong>, It operates as it always does.</li>
<li>Picking a process e.g, A, and giving A control for its quantum.</li>
<li>The <strong>thread scheduler</strong> inside A decides which thread
to run, say A1.</li>
<li>Since there are no clock interrupts to multiprogram threads, this
thread may continue running as long as it wants to. If it uses up the
process’ entire quantum, the kernel will select another process to
run.</li>
</ul></li>
<li><p>For the <strong>kernel-level</strong> threads:</p>
<ul>
<li>Unlike user-level, the kernel can pick a particular thread to
run.</li>
<li>Like process, the thread is given a quantum and is forceably
suspended if it exceeds the quantum.</li>
</ul></li>
<li><p>The major difference between user-level and kernel-level threads
is the <strong>Performance</strong></p>
<ul>
<li>Doing a thread switch with user-level threads takes a handful of
machine instructions. since all threads will inside one address
space.</li>
<li>Switching kernel-level threads requires a full context switch.
(changing the memory map, invalidating the cache)</li>
</ul></li>
</ul>
<p><strong>Note that in order to facilitate implementation in C
language,<br>I will use threads instead of processes to introduce some
interprocess examples.<br></strong> Below we will discuss the problem in
the context of <strong>threads</strong>.<br>But please keep in mind that
the same problems and solutions also apply to
<strong>processes</strong>.<br></p>
<h2 id="race-condition">2. Race Condition</h2>
<p><strong>Example: <a
href="https://github.com/Angold-4/OSDI/blob/master/Chapter/Chapter2/Codes/race.c">Codes/race.c</a></strong></p>
<div class="sourceCode" id="cb3"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> mails <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb3-2"><a href="#cb3-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb3-3"><a href="#cb3-3" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> routine<span class="op">()</span> <span class="op">{</span></span>
<span id="cb3-4"><a href="#cb3-4" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> <span class="dv">1000000</span><span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb3-5"><a href="#cb3-5" aria-hidden="true" tabindex="-1"></a> mails<span class="op">++;</span></span>
<span id="cb3-6"><a href="#cb3-6" aria-hidden="true" tabindex="-1"></a> <span class="co">// read mails: </span></span>
<span id="cb3-7"><a href="#cb3-7" aria-hidden="true" tabindex="-1"></a> <span class="co">// movl _mails(%rip), %eax</span></span>
<span id="cb3-8"><a href="#cb3-8" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb3-9"><a href="#cb3-9" aria-hidden="true" tabindex="-1"></a> <span class="co">// increment</span></span>
<span id="cb3-10"><a href="#cb3-10" aria-hidden="true" tabindex="-1"></a> <span class="co">// addl $1, %eax</span></span>
<span id="cb3-11"><a href="#cb3-11" aria-hidden="true" tabindex="-1"></a> </span>
<span id="cb3-12"><a href="#cb3-12" aria-hidden="true" tabindex="-1"></a> <span class="co">// write mails</span></span>
<span id="cb3-13"><a href="#cb3-13" aria-hidden="true" tabindex="-1"></a> <span class="co">// movl %eax, _mails(%rip)</span></span>
<span id="cb3-14"><a href="#cb3-14" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb3-15"><a href="#cb3-15" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb3-16"><a href="#cb3-16" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb3-17"><a href="#cb3-17" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> main<span class="op">(</span><span class="dt">int</span> argc<span class="op">,</span> <span class="dt">char</span><span class="op">*</span> argv<span class="op">[])</span> <span class="op">{</span></span>
<span id="cb3-18"><a href="#cb3-18" aria-hidden="true" tabindex="-1"></a> pthread_t p1<span class="op">,</span> p2<span class="op">;</span></span>
<span id="cb3-19"><a href="#cb3-19" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>p1<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb3-20"><a href="#cb3-20" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">1</span><span class="op">;</span></span>
<span id="cb3-21"><a href="#cb3-21" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb3-22"><a href="#cb3-22" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>p2<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb3-23"><a href="#cb3-23" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">2</span><span class="op">;</span></span>
<span id="cb3-24"><a href="#cb3-24" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb3-25"><a href="#cb3-25" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb3-26"><a href="#cb3-26" aria-hidden="true" tabindex="-1"></a> <span class="co">// waiting for threads finish</span></span>
<span id="cb3-27"><a href="#cb3-27" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>p1<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb3-28"><a href="#cb3-28" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>p2<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb3-29"><a href="#cb3-29" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb3-30"><a href="#cb3-30" aria-hidden="true" tabindex="-1"></a> <span class="co">// race condition</span></span>
<span id="cb3-31"><a href="#cb3-31" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"Number of mails: %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> mails<span class="op">);</span> <span class="co">// Number of mails: 1289819 </span></span>
<span id="cb3-32"><a href="#cb3-32" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb3-33"><a href="#cb3-33" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb3-34"><a href="#cb3-34" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb3-35"><a href="#cb3-35" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
<p><strong>Before I give the output, let’s see the program - which plus
one to the mails <code>(1000000 x 2)</code> times</strong></p>
<pre><code>❯ ./a.out
Number of mails: 1289819</code></pre>
<p><strong>But it give me the <code>1289819</code> instead of
<code>2000000</code> we expected</strong>.<br> <strong>Why this
happend?</strong><br></p>
<p>Processes or threads that are working together may share some common
storage that each one can read and write.<br> When two or more
processes(threads) are reading or writing some shared data at the same
time. <br> This may cause <strong>Race Condition.</strong><br></p>
<p><a href="https://www.youtube.com/watch?v=FY9livorrJI">This</a> video
explains the causes of <strong>Race Condition</strong>.<br></p>
<p><strong>When we check the assembly code of <code>mail++;</code>
inside the for loop:<br></strong></p>
<pre class="assembly"><code> movl _mails(%rip), %eax ## read mails
addl $1, %eax ## increment
movl %eax, _mails(%rip) ## write mails</code></pre>
<p><strong>As I metioned in <a
href="https://github.com/Angold-4/OSDI/blob/master/Chapter/Chapter2/1Introprogress.md">Introduction
to Processes</a>: <br></strong> > At any instant of time, the CPU is
running only one program</p>
<p>Imagine that when thread#1 executes at <code>mail++</code>. At that
time he executes the first line of the assembly code.<br>Which put the
current mail value into a CPU register <code>%eax</code>.<br> Then
assume the <strong>Prcocess Scheduler</strong> temporary blocked this
thread#1 let’s say the algorithm may think that it runs too long. And
let thread#2 who is waiting to run.<br> <strong>Let’s assume at that
time, the value of <code>mail</code> is <code>27</code>. Now stored in
register <code>%eax</code> of thread#1.</strong><br> Then thread#2 start
to run. At some time (like 0.1 secs after), the <strong>Process
Scheduler</strong> temporary blocked thread#2 and wake up thread#1
because of the same reason.<br> <strong>thread#2 add <code>mails</code>
multiple times, let’s assume the value of <code>mails</code> is
<code>48</code>.</strong><br> <br> <strong>Now here comes the Race
Condition:<br></strong> Back to thread#1, When thread#1 restore all the
value of registers and start running
(<code>movl %eax, _mails(%rip)</code>).<br> <strong>Now the
<code>mails</code> becomes <code>28</code>! instead of <code>49</code>
we wished!</strong><br> <strong>The difficulty above occurred because
thread#2 started using one of the shared variables before thread#1 was
finished with it.</strong></p>
<h2 id="mutual-exclusion">3. Mutual Exclusion</h2>
<p><strong>How to avoid Race Conditions?</strong><br> The key to
preventing trouble here and in many other situations involving shared
memory, shared files, and shared everything else is to find some way to
<strong>prohibit more than one process from reading and writing the
shared data at the same time. <br></strong> <img
src="Sources/mutual.png" alt="mutual" /></p>
<p>Put in other words, what we need is <strong>mutual exclusion</strong>
— some way of making sure that if one process is using a shared variable
or file, the other processes will be excluded from doing the same
thing.<br> <br> <strong>Here I will give two ways to avoid Race
Conditions:</strong> 1. Strict Alternation 2. Mutexes (Binary
Semaphore)</p>
<h3 id="strict-alternation">Strict Alternation</h3>
<p><strong>Example: <a
href="Codes/mutual.c">Codes/mutual.c</a></strong><br></p>
<div class="sourceCode" id="cb6"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb6-1"><a href="#cb6-1" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> mails <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb6-2"><a href="#cb6-2" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> turn <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb6-3"><a href="#cb6-3" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb6-4"><a href="#cb6-4" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> routine1<span class="op">()</span> <span class="op">{</span></span>
<span id="cb6-5"><a href="#cb6-5" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> <span class="dv">1000000</span><span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb6-6"><a href="#cb6-6" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span><span class="op">(</span>turn <span class="op">!=</span> <span class="dv">0</span><span class="op">);</span> <span class="co">// busy waiting</span></span>
<span id="cb6-7"><a href="#cb6-7" aria-hidden="true" tabindex="-1"></a> mails<span class="op">++;</span></span>
<span id="cb6-8"><a href="#cb6-8" aria-hidden="true" tabindex="-1"></a> turn <span class="op">=</span> <span class="dv">1</span><span class="op">;</span></span>
<span id="cb6-9"><a href="#cb6-9" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb6-10"><a href="#cb6-10" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb6-11"><a href="#cb6-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb6-12"><a href="#cb6-12" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> routine2<span class="op">()</span> <span class="op">{</span></span>
<span id="cb6-13"><a href="#cb6-13" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> <span class="dv">1000000</span><span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb6-14"><a href="#cb6-14" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span><span class="op">(</span>turn <span class="op">!=</span> <span class="dv">1</span><span class="op">);</span> <span class="co">// busy waiting</span></span>
<span id="cb6-15"><a href="#cb6-15" aria-hidden="true" tabindex="-1"></a> mails<span class="op">++;</span></span>
<span id="cb6-16"><a href="#cb6-16" aria-hidden="true" tabindex="-1"></a> turn <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb6-17"><a href="#cb6-17" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb6-18"><a href="#cb6-18" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb6-19"><a href="#cb6-19" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb6-20"><a href="#cb6-20" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> main<span class="op">(</span><span class="dt">int</span> argc<span class="op">,</span> <span class="dt">char</span><span class="op">*</span> argv<span class="op">[])</span> <span class="op">{</span></span>
<span id="cb6-21"><a href="#cb6-21" aria-hidden="true" tabindex="-1"></a> pthread_t p1<span class="op">,</span> p2<span class="op">;</span></span>
<span id="cb6-22"><a href="#cb6-22" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>p1<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine1<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb6-23"><a href="#cb6-23" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">1</span><span class="op">;</span></span>
<span id="cb6-24"><a href="#cb6-24" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb6-25"><a href="#cb6-25" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>p2<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine2<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb6-26"><a href="#cb6-26" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">2</span><span class="op">;</span></span>
<span id="cb6-27"><a href="#cb6-27" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb6-28"><a href="#cb6-28" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb6-29"><a href="#cb6-29" aria-hidden="true" tabindex="-1"></a> <span class="co">// waiting for threads finish</span></span>
<span id="cb6-30"><a href="#cb6-30" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>p1<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb6-31"><a href="#cb6-31" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>p2<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb6-32"><a href="#cb6-32" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb6-33"><a href="#cb6-33" aria-hidden="true" tabindex="-1"></a> <span class="co">// race condition</span></span>
<span id="cb6-34"><a href="#cb6-34" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"Number of mails: %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> mails<span class="op">);</span> <span class="co">// Number of mails: 2000000</span></span>
<span id="cb6-35"><a href="#cb6-35" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb6-36"><a href="#cb6-36" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">0</span><span class="op">;</span> </span>
<span id="cb6-37"><a href="#cb6-37" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
<p><strong>By adding an int variable <code>turn</code> to the
program.<br>We can make sure in any time, only one thread can run in the
critical region.</strong></p>
<p>This code gives us the right example in most cases.<br>But in some
cases, like thread#2 runs much long in noncritical region than
thread#1:<br> > Page 92:<br><strong>When process 0 leaves the
critical region, it sets turn to 1, to allow process 1 to enter its
critical region.<br>Suppose that process 1 finishes its critical region
quickly, so both processes are in their noncritical regions, with turn
set to 0. Now process 0 executes its whole loop quickly, exiting its
critical region and setting turn to 1. At this point turn is 1 and both
processes are executing in their noncritical regions.</strong></p>
<blockquote>
<p><strong>Suddenly, process 0 finishes its noncritical region and goes
back to the top of its loop. Unfortunately, it is not permitted to enter
its critical region now, because turn is 1 and process 1 is busy with
its noncritical region. It hangs in its while loop until process 1 sets
turn to 0. Put differently, taking turns is not a good idea when one of
the processes is much slower than the other.</strong></p>
</blockquote>
<p><strong>Another problem it will caused is called “Busy
Waiting”</strong><br> Inside the for-loop each iterations, there is a
while-loop continuously testing a variable until some value
appearsm.<br>This is called <strong>busy waiting</strong>.<br> It should
usually be avoided, since it wastes CPU time. Only when there is a
reasonable expectation that the wait will be short is busy waiting
used.<br></p>
<h3 id="mutexes">Mutexes</h3>
<p><strong>A mutex is a variable that can be in one of two states:
unlocked or locked.</strong><br> <strong>Two procedures are used with
mutexes:</strong><br> * When a process (or thread) needs access to a
critical region, it calls <code>mutex_lock()</code>. <br>If the mutex is
currently unlocked (meaning that the critical region is available), the
call succeeds and the calling thread is free to enter the critical
region.<br> * On the other hand, if the mutex is already locked, the
caller is blocked until the process in the critical region is finished
and calls <code>mutex_unlock()</code>.</p>
<p><strong>Example <a
href="Codes/mutex.c">Codes/mutex.c</a></strong></p>
<div class="sourceCode" id="cb7"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb7-1"><a href="#cb7-1" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> mails <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb7-2"><a href="#cb7-2" aria-hidden="true" tabindex="-1"></a>pthread_mutex_t mutex<span class="op">;</span></span>
<span id="cb7-3"><a href="#cb7-3" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb7-4"><a href="#cb7-4" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> routine<span class="op">()</span> <span class="op">{</span></span>
<span id="cb7-5"><a href="#cb7-5" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> <span class="dv">0</span><span class="op">;</span> i <span class="op"><</span> <span class="dv">1000000</span><span class="op">;</span> i<span class="op">++)</span> <span class="op">{</span></span>
<span id="cb7-6"><a href="#cb7-6" aria-hidden="true" tabindex="-1"></a> pthread_mutex_lock<span class="op">(&</span>mutex<span class="op">);</span></span>
<span id="cb7-7"><a href="#cb7-7" aria-hidden="true" tabindex="-1"></a> mails<span class="op">++;</span> <span class="co">// any time, only one thread can run this instruction</span></span>
<span id="cb7-8"><a href="#cb7-8" aria-hidden="true" tabindex="-1"></a> pthread_mutex_unlock<span class="op">(&</span>mutex<span class="op">);</span></span>
<span id="cb7-9"><a href="#cb7-9" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb7-10"><a href="#cb7-10" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb7-11"><a href="#cb7-11" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb7-12"><a href="#cb7-12" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> main<span class="op">(</span><span class="dt">int</span> argc<span class="op">,</span> <span class="dt">char</span><span class="op">*</span> argv<span class="op">[])</span> <span class="op">{</span></span>
<span id="cb7-13"><a href="#cb7-13" aria-hidden="true" tabindex="-1"></a> pthread_t p1<span class="op">,</span> p2<span class="op">;</span></span>
<span id="cb7-14"><a href="#cb7-14" aria-hidden="true" tabindex="-1"></a> pthread_mutex_init<span class="op">(&</span>mutex<span class="op">,</span> NULL<span class="op">);</span> <span class="co">// deafult</span></span>
<span id="cb7-15"><a href="#cb7-15" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>p1<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb7-16"><a href="#cb7-16" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">1</span><span class="op">;</span></span>
<span id="cb7-17"><a href="#cb7-17" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb7-18"><a href="#cb7-18" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>pthread_create<span class="op">(&</span>p2<span class="op">,</span> NULL<span class="op">,</span> <span class="op">&</span>routine<span class="op">,</span> NULL<span class="op">)</span> <span class="op">!=</span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb7-19"><a href="#cb7-19" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">2</span><span class="op">;</span></span>
<span id="cb7-20"><a href="#cb7-20" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb7-21"><a href="#cb7-21" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb7-22"><a href="#cb7-22" aria-hidden="true" tabindex="-1"></a> <span class="co">// waiting for threads finish</span></span>
<span id="cb7-23"><a href="#cb7-23" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>p1<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb7-24"><a href="#cb7-24" aria-hidden="true" tabindex="-1"></a> pthread_join<span class="op">(</span>p2<span class="op">,</span> NULL<span class="op">);</span></span>
<span id="cb7-25"><a href="#cb7-25" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb7-26"><a href="#cb7-26" aria-hidden="true" tabindex="-1"></a> pthread_mutex_destroy<span class="op">(&</span>mutex<span class="op">);</span></span>
<span id="cb7-27"><a href="#cb7-27" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"Number of mails: %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> mails<span class="op">);</span> <span class="co">// Number of mails: 2000000</span></span>
<span id="cb7-28"><a href="#cb7-28" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb7-29"><a href="#cb7-29" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb7-30"><a href="#cb7-30" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
<h2 id="condition-variable">4. Condition Variable</h2>
<p><strong>Let’s now focus on the 3rd question we metioned in the
begining:</strong><br></p>
<blockquote>
<p><strong>How to make sure the sequence of related processes?</strong>
<br></p>
</blockquote>
<p>Consider that case - A <strong>gas station.</strong><br>
<strong>Assumue that a gas station can produce 15 liter petrol per
seconds, and there are many cars waiting for refueling.<br></strong>
<strong>Each cars need to be fueled 40 liters once and then
leave.</strong><br> <br> <strong>In this case, we cannot recieve more
cars when the gas station is out of fuel.</strong><br> There must have a
sequence between two events:<br> * The gas station has more than 40
liter gas. * Here comes the car to be refueled.</p>
<p>The solution lies in the introduction of <strong>condition
variables</strong>.<br> Along with three operations on them,
<strong><code>wait</code></strong>, <strong><code>signal</code></strong>
and <strong><code>boardcast</code></strong>.<br></p>
<ul>
<li><p><strong><code>wait</code></strong> This action causes the calling
process(thread) to <strong>block</strong>, and <strong>waiting</strong>
for the <code>signal</code> from other processes(threads) to wake it
up.</p></li>
<li><p><strong><code>signal</code></strong> Wake up one process(thread)
waiting on this condition variable (if any). <br> If a signal is done on
a condition variable on which several processes are waiting, only one of
them, determined by the <strong>process scheduler</strong>, is
revived.</p></li>
<li><p><strong><code>boardcast</code></strong> Wake up all waiting
processes(threads)</p></li>
</ul>
<p><strong>Example: <a
href="Code/conditionvar.c">Code/conditionvar.c</a></strong></p>
<div class="sourceCode" id="cb8"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb8-1"><a href="#cb8-1" aria-hidden="true" tabindex="-1"></a><span class="co">// condition variable -- for sequence</span></span>
<span id="cb8-2"><a href="#cb8-2" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb8-3"><a href="#cb8-3" aria-hidden="true" tabindex="-1"></a>pthread_mutex_t mutexFuel<span class="op">;</span></span>
<span id="cb8-4"><a href="#cb8-4" aria-hidden="true" tabindex="-1"></a>pthread_cond_t condFuel<span class="op">;</span></span>
<span id="cb8-5"><a href="#cb8-5" aria-hidden="true" tabindex="-1"></a><span class="dt">int</span> fuel <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb8-6"><a href="#cb8-6" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb8-7"><a href="#cb8-7" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> fuel_filling<span class="op">(</span><span class="dt">void</span><span class="op">*</span> arg<span class="op">)</span> <span class="op">{</span></span>
<span id="cb8-8"><a href="#cb8-8" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span> <span class="op">(</span><span class="dv">1</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb8-9"><a href="#cb8-9" aria-hidden="true" tabindex="-1"></a> pthread_mutex_lock<span class="op">(&</span>mutexFuel<span class="op">);</span></span>
<span id="cb8-10"><a href="#cb8-10" aria-hidden="true" tabindex="-1"></a> fuel <span class="op">+=</span> <span class="dv">15</span><span class="op">;</span></span>
<span id="cb8-11"><a href="#cb8-11" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"Filled fuel... %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> fuel<span class="op">);</span></span>
<span id="cb8-12"><a href="#cb8-12" aria-hidden="true" tabindex="-1"></a> pthread_mutex_unlock<span class="op">(&</span>mutexFuel<span class="op">);</span></span>
<span id="cb8-13"><a href="#cb8-13" aria-hidden="true" tabindex="-1"></a> pthread_cond_signal<span class="op">(&</span>condFuel<span class="op">);</span></span>
<span id="cb8-14"><a href="#cb8-14" aria-hidden="true" tabindex="-1"></a> sleep<span class="op">(</span><span class="dv">1</span><span class="op">);</span></span>
<span id="cb8-15"><a href="#cb8-15" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb8-16"><a href="#cb8-16" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb8-17"><a href="#cb8-17" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb8-18"><a href="#cb8-18" aria-hidden="true" tabindex="-1"></a><span class="dt">void</span><span class="op">*</span> car<span class="op">(</span><span class="dt">void</span><span class="op">*</span> arg<span class="op">)</span> <span class="op">{</span></span>
<span id="cb8-19"><a href="#cb8-19" aria-hidden="true" tabindex="-1"></a> pthread_mutex_lock<span class="op">(&</span>mutexFuel<span class="op">);</span></span>
<span id="cb8-20"><a href="#cb8-20" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span> <span class="op">(</span><span class="dv">1</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb8-21"><a href="#cb8-21" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span> <span class="op">(</span>fuel <span class="op"><</span> <span class="dv">40</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb8-22"><a href="#cb8-22" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"No fuel. Waiting...</span><span class="sc">\n</span><span class="st">"</span><span class="op">);</span></span>
<span id="cb8-23"><a href="#cb8-23" aria-hidden="true" tabindex="-1"></a> <span class="co">// every time when got a signal from other threads by calling pthread_cond_signal()</span></span>
<span id="cb8-24"><a href="#cb8-24" aria-hidden="true" tabindex="-1"></a> <span class="co">// it will be executed after that wait </span></span>
<span id="cb8-25"><a href="#cb8-25" aria-hidden="true" tabindex="-1"></a> pthread_cond_wait<span class="op">(&</span>condFuel<span class="op">,</span> <span class="op">&</span>mutexFuel<span class="op">);</span></span>
<span id="cb8-26"><a href="#cb8-26" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span> </span>
<span id="cb8-27"><a href="#cb8-27" aria-hidden="true" tabindex="-1"></a> fuel <span class="op">-=</span> <span class="dv">40</span><span class="op">;</span></span>
<span id="cb8-28"><a href="#cb8-28" aria-hidden="true" tabindex="-1"></a> printf<span class="op">(</span><span class="st">"Got fuel. Now left: %d</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span> fuel<span class="op">);</span></span>
<span id="cb8-29"><a href="#cb8-29" aria-hidden="true" tabindex="-1"></a> pthread_mutex_unlock<span class="op">(&</span>mutexFuel<span class="op">);</span></span>
<span id="cb8-30"><a href="#cb8-30" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb8-31"><a href="#cb8-31" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
</section>
</div>
</div>
<div id="disqus_thread"></div>
<script>
var disqus_config = function () {
this.page.url = "https://angold4.org/OSDI/Chapter/Chapter2/2Communication.html"
this.page.identifier = "OSDI/Chapter/Chapter2/2Communication.html"
};
(function() { // DON'T EDIT BELOW THIS LINE
var d = document, s = d.createElement('script');
s.src = 'https://angold.disqus.com/embed.js';
s.setAttribute('data-timestamp', +new Date());
(d.head || d.body).appendChild(s);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
<footer>
<div class="well well-lg" id="footer-well">
<div class="container">
<div class="row">
<div class="col-xs-6">
<a href="https://angold4.org" title="Angold-4 Organization" class="image-link"><img src="../../../images/logo.png" class="cmudb-logo" /></a>
</div>
<div class="col-xs-6">
<p class="pull-right"><i class="fa fa-arrow-up"></i> <a href="#">Back to top</a></p>
</div>
</div>
</div>
</div>
</footer>
<!-- Include all compiled plugins (below), or include individual files as needed -->
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script src="../../../theme/js/bootstrap.min.js"></script>
<!-- Enable responsive features in IE8 with Respond.js (https://github.com/scottjehl/Respond) -->
<script src="../../../theme/js/respond.min.js"></script>
<!-- Fix scrolling issues to internal HREFs that get positioned behind navbar -->
<!-- http://stackoverflow.com/questions/10732690/offsetting-an-html-anchor-to-adjust-for-fixed-header -->
<script src="../../../theme/js/href_scroll.js"></script>
<!-- You know what this is and you know what he did to me... -->
<script src="../../../theme/js/tim-kraska-betrayed-me.js"></script>
</body>
</html>