-
Notifications
You must be signed in to change notification settings - Fork 17
Expand file tree
/
Copy path4ClockTick.html
More file actions
746 lines (709 loc) · 56.3 KB
/
Copy path4ClockTick.html
File metadata and controls
746 lines (709 loc) · 56.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
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
<!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="#inside-a-whole-clock-tick"
id="toc-inside-a-whole-clock-tick">4. Inside a Whole Clock Tick</a>
<ul>
<li><a href="#clock-task" id="toc-clock-task">1. Clock Task</a>
<ul>
<li><a href="#clock-hardware" id="toc-clock-hardware">Clock
Hardware</a></li>
<li><a href="#clock-software" id="toc-clock-software">Clock
Software</a></li>
</ul></li>
<li><a href="#start-of-minix3" id="toc-start-of-minix3">2. Start of
Minix3</a>
<ul>
<li><a href="#kernelmain.c"
id="toc-kernelmain.c"><span>kernel/main.c</span></a></li>
</ul></li>
<li><a href="#implementation-of-clock-driver-in-minix3"
id="toc-implementation-of-clock-driver-in-minix3">3. Implementation of
Clock Driver in Minix3</a>
<ul>
<li><a href="#interrupt-request-irq"
id="toc-interrupt-request-irq">Interrupt Request (IRQ)</a></li>
</ul></li>
</ul></li>
</ul>
</nav>
<h2 id="operating-systems-design-and-implementation-notes">Operating
Systems Design and Implementation Notes</h2>
<h1 id="inside-a-whole-clock-tick">4. Inside a Whole Clock Tick</h1>
<h5 id="by-jiawei-wang">By Jiawei Wang</h5>
<p>We are now moving closer to looking at the actual <strong>code of
Minix3</strong>.<br> Unlike the introduction sequence in the original
book. I divide the implementation into four parts:<br> * <strong>Clock
Server</strong> (Inside a Hole Clock Tick) * <strong>Process
Scheduler</strong> * <strong>Interprocess Commnuication</strong> *
<strong>System Task</strong></p>
<p><strong>Process management</strong>, <strong>Interprocess
communication</strong>, and <strong>Scheduling</strong></p>
<p>One useful website for learning minix3: <strong><a
href="https://elixir.ortiz.sh/minix/v3.1.8/C/ident/">elixir.ortiz.sh</a></strong><br>
Minix3 Source code used in this note: <strong><a
href="https://github.com/Angold-4/OSDI/tree/master/Minix3">https://github.com/Angold-4/OSDI/tree/master/Minix3</a></strong>
(folked from <a
href="https://github.com/jncraton/minix3">jncraton</a>)<br> <br> Before
the formal introduction with code, let us begin our study of MINIX 3 by
taking a bird’s-eye view of the system. <br> MINIX 3 is structured in
<strong>four layers</strong>, with each layer performing a well-defined
function. <br> <img src="Sources/layer.png" alt="layer" /></p>
<h2 id="clock-task">1. Clock Task</h2>
<p><strong>Clocks (also called timers) are essential to the operation of
any timesharing system.</strong><br> In my opinion, <strong>The Clocks
is the heart of a computer</strong>, so that it can make all components
run regularly. Also, there are several places one could point to and
say, <strong>“This is where Minix3 starts running”</strong>. <br></p>
<h3 id="clock-hardware">Clock Hardware</h3>
<p>The clock is built out of three components: a <strong>crystal
oscillator</strong>, a <strong>counter</strong>, and a <strong>holding
register</strong>.<br></p>
<figure>
<img src="Sources/clock.png" alt="clock" />
<figcaption aria-hidden="true">clock</figcaption>
</figure>
<ul>
<li><strong>Crystal Oscillator:</strong><br>When a piece of quartz
crystal is properly cut and mounted under tension, it can be made to
generate a periodic signal of very high accuracy.</li>
<li><strong>Counter:</strong><br> The signal that <strong>crystal
oscillator</strong> made is fed into the counter to make it count down
to zero. When the counter gets to zero, it causes a CPU interrupt.</li>
<li><strong>Holding Register:</strong><br> After getting to zero and
causing the interrupt, the holding register is automatically copied into
the counter, and the whole process is repeated again indefinitely. These
periodic interrupts are called <strong>clock ticks</strong>.<br></li>
</ul>
<p>The advantage of the <strong>programmable clock</strong> is that its
interrupt frequency can be controlled by software. If a 1-MHz crystal is
used, then the counter is pulsed every microsecond. With 16-bit
registers, interrupts can be programmed to occur at intervals from 1
microsecond to 65.536 milliseconds, <strong>which means the clock ticks
can be changed by adjust the value of registers.</strong> The clock
interrupts repeat 60 times a second as long as MINIX 3 runs.<br></p>
<h3 id="clock-software">Clock Software</h3>
<p>All the clock hardware does is generate interrupts at known
intervals. Everything else involving time must be done by the software,
the <strong>clock driver</strong>.<br> The exact duties of the clock
driver vary among operating systems, but must include the
following:<br></p>
<ul>
<li><p><strong>Maintaining the time of day.</strong><br> In Minix3,
because the known-intervals-interrupts, we can maintain the time of the
day by counting the ticks.<br> but to do that relative to the time the
system was booted, rather than relative to a fixed external
moment.<br>When the time of day is requested, the stored time of day is
added to the counter to get the current time of day. <br></p></li>
<li><p><strong>Preventing processes from running longer than they are
allowed to.</strong><br> Whenever a process is started, the scheduler
should initialize a counter to the value of that process’ quantum in
clock ticks. At every clock interrupt, the clock driver decrements the
quantum counter by 1. When it gets to zero, the clock driver calls the
scheduler to set up another process.<br> <br></p></li>
</ul>
<h2 id="start-of-minix3">2. Start of Minix3</h2>
<p>The <a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/proc.h">kernel/proc.h</a>
defines the process table of kernel.<br></p>
<p>Generally speaking, Minx3 runs from <a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/arch/i386/mpx386.S">kernel/mpx386.s</a>.<br>
After execute <code>cstart()</code> function in <a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/start.c">kernel/start.c</a>,
which set some global variable and other preparations.<br> At line 252.
after the assembly code: <strong><code>jmp main</code></strong>, it
jumps to the main program of Minix3:</p>
<h3 id="kernelmain.c"><a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/main.c">kernel/main.c</a></h3>
<ul>
<li><strong><code>line 76 to 182</code>: Loop the <code>image[]</code>,
initialize the boot process table.</strong><br> The
<strong><code>image[]</code></strong> is defined in the line 114 of
<strong><a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/table.c">kernel/table.c</a>:</strong></li>
</ul>
<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>PUBLIC <span class="kw">struct</span> boot_image image<span class="op">[]</span> <span class="op">=</span> <span class="op">{</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a> <span class="co">/* process nr, pc,flags, qs, queue, stack, traps, ipcto, call, name */</span> </span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>IDLE<span class="op">,</span> idle_task<span class="op">,</span>IDL_F<span class="op">,</span> <span class="dv">8</span><span class="op">,</span> IDLE_Q<span class="op">,</span> IDL_S<span class="op">,</span> <span class="dv">0</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> no_c<span class="op">,</span><span class="st">"idle"</span> <span class="op">},</span></span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>CLOCK<span class="op">,</span>clock_task<span class="op">,</span>TSK_F<span class="op">,</span> <span class="dv">8</span><span class="op">,</span> TASK_Q<span class="op">,</span> TSK_S<span class="op">,</span> TSK_T<span class="op">,</span> <span class="dv">0</span><span class="op">,</span> no_c<span class="op">,</span><span class="st">"clock"</span> <span class="op">},</span></span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>SYSTEM<span class="op">,</span> sys_task<span class="op">,</span>TSK_F<span class="op">,</span> <span class="dv">8</span><span class="op">,</span> TASK_Q<span class="op">,</span> TSK_S<span class="op">,</span> TSK_T<span class="op">,</span> <span class="dv">0</span><span class="op">,</span> no_c<span class="op">,</span><span class="st">"system"</span><span class="op">},</span></span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>HARDWARE<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>TSK_F<span class="op">,</span> <span class="dv">8</span><span class="op">,</span> TASK_Q<span class="op">,</span> HRD_S<span class="op">,</span> <span class="dv">0</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> no_c<span class="op">,</span><span class="st">"kernel"</span><span class="op">},</span></span>
<span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>PM_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SRV_F<span class="op">,</span> <span class="dv">32</span><span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SRV_M<span class="op">,</span> c<span class="op">(</span>pm_c<span class="op">),</span><span class="st">"pm"</span> <span class="op">},</span></span>
<span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>FS_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SRV_F<span class="op">,</span> <span class="dv">32</span><span class="op">,</span> <span class="dv">5</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SRV_M<span class="op">,</span> c<span class="op">(</span>fs_c<span class="op">),</span><span class="st">"vfs"</span> <span class="op">},</span></span>
<span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>RS_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SVM_F<span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SYS_M<span class="op">,</span> c<span class="op">(</span>rs_c<span class="op">),</span><span class="st">"rs"</span> <span class="op">},</span></span>
<span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>MEM_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SVM_F<span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">3</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SYS_M<span class="op">,</span>c<span class="op">(</span>mem_c<span class="op">),</span><span class="st">"memory"</span><span class="op">},</span></span>
<span id="cb1-11"><a href="#cb1-11" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>LOG_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SRV_F<span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">2</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SYS_M<span class="op">,</span>c<span class="op">(</span>drv_c<span class="op">),</span><span class="st">"log"</span> <span class="op">},</span></span>
<span id="cb1-12"><a href="#cb1-12" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>TTY_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SVM_F<span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">1</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SYS_M<span class="op">,</span>c<span class="op">(</span>tty_c<span class="op">),</span><span class="st">"tty"</span> <span class="op">},</span></span>
<span id="cb1-13"><a href="#cb1-13" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>DS_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SVM_F<span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">4</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SYS_M<span class="op">,</span> c<span class="op">(</span>ds_c<span class="op">),</span><span class="st">"ds"</span> <span class="op">},</span></span>
<span id="cb1-14"><a href="#cb1-14" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>MFS_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>SVM_F<span class="op">,</span> <span class="dv">32</span><span class="op">,</span> <span class="dv">5</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SRV_M<span class="op">,</span> c<span class="op">(</span>fs_c<span class="op">),</span><span class="st">"mfs"</span> <span class="op">},</span></span>
<span id="cb1-15"><a href="#cb1-15" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>VM_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>VM_F<span class="op">,</span> <span class="dv">32</span><span class="op">,</span> <span class="dv">2</span><span class="op">,</span> <span class="dv">0</span><span class="op">,</span> SRV_T<span class="op">,</span> SRV_M<span class="op">,</span> c<span class="op">(</span>vm_c<span class="op">),</span><span class="st">"vm"</span> <span class="op">},</span></span>
<span id="cb1-16"><a href="#cb1-16" aria-hidden="true" tabindex="-1"></a> <span class="op">{</span>INIT_PROC_NR<span class="op">,</span> <span class="dv">0</span><span class="op">,</span>USR_F<span class="op">,</span> <span class="dv">8</span><span class="op">,</span> USER_Q<span class="op">,</span> <span class="dv">0</span><span class="op">,</span> USR_T<span class="op">,</span> USR_M<span class="op">,</span> c<span class="op">(</span>usr_c<span class="op">),</span><span class="st">"init"</span> <span class="op">},</span></span>
<span id="cb1-17"><a href="#cb1-17" aria-hidden="true" tabindex="-1"></a><span class="op">};</span></span></code></pre></div>
<ul>
<li><strong><code>line 193 to 211</code>: Return to the assembly code to
start running the current process by calling
<code>restart()</code></strong><br> The
<strong><code>restart()</code></strong> is defined from 436 to 469 of
<strong><a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/arch/i386/mpx386.S">kernel/mpx386.s</a>:</strong></li>
</ul>
<pre class="assembly"><code>/*===========================================================================*/
/* restart */
/*===========================================================================*/
restart:
/* Restart the current process or the next process if it is set. */
cli
call schedcheck
movl proc_ptr, %esp /* will assume P_STACKBASE == 0 */
lldt P_LDT_SEL(%esp) /* enable process' segment descriptors */
cmpl $0, P_CR3(%esp)
jz 0f
mov P_CR3(%esp), %eax
cmpl loadedcr3, %eax
jz 0f
mov %eax, %cr3
mov %eax, loadedcr3
mov proc_ptr, %eax
mov %eax, ptproc
movl $0, dirtypde
0:
lea P_STACKTOP(%esp), %eax /* arrange for next interrupt */
movl %eax, tss+TSS3_S_SP0 /* to save state in process table */
restart1:
decb k_reenter
popw %gs
popw %fs
popw %es
popw %ds
popal
add $4, %esp /* skip return adr */
iret /* continue process */</code></pre>
<p><strong>Then the CPU will start to execute all boot processes that we
initialized before (from 0)</strong></p>
<h2 id="implementation-of-clock-driver-in-minix3">3. Implementation of
Clock Driver in Minix3</h2>
<p>The Minix 3 clock driver is contained in the file <a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/clock.c">kernel/clock.c</a>.</p>
<p>From the boot image table:</p>
<pre><code>{CLOCK,clock_task,TSK_F, 8, TASK_Q, TSK_S, TSK_T, 0, no_c,"clock" },</code></pre>
<p>The <strong><code>CLOCK</code></strong> process has the highest
piority <code>(0)</code>, and it will be executed after the
<strong><code>restart()</code></strong>. <br> The kernel will run it by
calling the <strong><code>clock_task()</code></strong> function.</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true" tabindex="-1"></a><span class="co">/*===========================================================================*</span></span>
<span id="cb4-2"><a href="#cb4-2" aria-hidden="true" tabindex="-1"></a><span class="co"> * clock_task *</span></span>
<span id="cb4-3"><a href="#cb4-3" aria-hidden="true" tabindex="-1"></a><span class="co"> *===========================================================================*/</span></span>
<span id="cb4-4"><a href="#cb4-4" aria-hidden="true" tabindex="-1"></a>PUBLIC <span class="dt">void</span> clock_task<span class="op">()</span></span>
<span id="cb4-5"><a href="#cb4-5" aria-hidden="true" tabindex="-1"></a><span class="op">{</span></span>
<span id="cb4-6"><a href="#cb4-6" aria-hidden="true" tabindex="-1"></a><span class="co">/* Main program of clock task. If the call is not HARD_INT it is an error.</span></span>
<span id="cb4-7"><a href="#cb4-7" aria-hidden="true" tabindex="-1"></a><span class="co"> */</span></span>
<span id="cb4-8"><a href="#cb4-8" aria-hidden="true" tabindex="-1"></a> message m<span class="op">;</span> <span class="co">/* message buffer for both input and output */</span></span>
<span id="cb4-9"><a href="#cb4-9" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> result<span class="op">;</span> <span class="co">/* result returned by the handler */</span></span>
<span id="cb4-10"><a href="#cb4-10" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb4-11"><a href="#cb4-11" aria-hidden="true" tabindex="-1"></a> init_clock<span class="op">();</span> <span class="co">/* initialize clock task */</span></span>
<span id="cb4-12"><a href="#cb4-12" aria-hidden="true" tabindex="-1"></a> </span>
<span id="cb4-13"><a href="#cb4-13" aria-hidden="true" tabindex="-1"></a> <span class="co">/* Main loop of the clock task. Get work, process it. Never reply. */</span></span>
<span id="cb4-14"><a href="#cb4-14" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span><span class="op">(</span>TRUE<span class="op">)</span> <span class="op">{</span></span>
<span id="cb4-15"><a href="#cb4-15" aria-hidden="true" tabindex="-1"></a> <span class="co">/* Go get a message. */</span></span>
<span id="cb4-16"><a href="#cb4-16" aria-hidden="true" tabindex="-1"></a> result <span class="op">=</span> receive<span class="op">(</span>ANY<span class="op">,</span> <span class="op">&</span>m<span class="op">);</span></span>
<span id="cb4-17"><a href="#cb4-17" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb4-18"><a href="#cb4-18" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span><span class="op">(</span>result <span class="op">!=</span> OK<span class="op">)</span></span>
<span id="cb4-19"><a href="#cb4-19" aria-hidden="true" tabindex="-1"></a> minix_panic<span class="op">(</span><span class="st">"receive() failed"</span><span class="op">,</span> result<span class="op">);</span></span>
<span id="cb4-20"><a href="#cb4-20" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb4-21"><a href="#cb4-21" aria-hidden="true" tabindex="-1"></a> <span class="co">/* Handle the request. Only clock ticks are expected. */</span></span>
<span id="cb4-22"><a href="#cb4-22" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>is_notify<span class="op">(</span>m<span class="op">.</span>m_type<span class="op">))</span> <span class="op">{</span></span>
<span id="cb4-23"><a href="#cb4-23" aria-hidden="true" tabindex="-1"></a> <span class="cf">switch</span> <span class="op">(</span>_ENDPOINT_P<span class="op">(</span>m<span class="op">.</span>m_source<span class="op">))</span> <span class="op">{</span></span>
<span id="cb4-24"><a href="#cb4-24" aria-hidden="true" tabindex="-1"></a> <span class="cf">case</span> HARDWARE<span class="op">:</span></span>
<span id="cb4-25"><a href="#cb4-25" aria-hidden="true" tabindex="-1"></a> do_clocktick<span class="op">(&</span>m<span class="op">);</span> <span class="co">/* handle clock tick */</span></span>
<span id="cb4-26"><a href="#cb4-26" aria-hidden="true" tabindex="-1"></a> <span class="cf">break</span><span class="op">;</span></span>
<span id="cb4-27"><a href="#cb4-27" aria-hidden="true" tabindex="-1"></a> <span class="cf">default</span><span class="op">:</span> <span class="co">/* illegal request type */</span></span>
<span id="cb4-28"><a href="#cb4-28" aria-hidden="true" tabindex="-1"></a> kprintf<span class="op">(</span><span class="st">"CLOCK: illegal notify %d from %d.</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span></span>
<span id="cb4-29"><a href="#cb4-29" aria-hidden="true" tabindex="-1"></a> m<span class="op">.</span>m_type<span class="op">,</span> m<span class="op">.</span>m_source<span class="op">);</span></span>
<span id="cb4-30"><a href="#cb4-30" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb4-31"><a href="#cb4-31" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb4-32"><a href="#cb4-32" aria-hidden="true" tabindex="-1"></a> <span class="cf">else</span> <span class="op">{</span></span>
<span id="cb4-33"><a href="#cb4-33" aria-hidden="true" tabindex="-1"></a> <span class="co">/* illegal request type */</span></span>
<span id="cb4-34"><a href="#cb4-34" aria-hidden="true" tabindex="-1"></a> kprintf<span class="op">(</span><span class="st">"CLOCK: illegal request %d from %d.</span><span class="sc">\n</span><span class="st">"</span><span class="op">,</span></span>
<span id="cb4-35"><a href="#cb4-35" aria-hidden="true" tabindex="-1"></a> m<span class="op">.</span>m_type<span class="op">,</span> m<span class="op">.</span>m_source<span class="op">);</span></span>
<span id="cb4-36"><a href="#cb4-36" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb4-37"><a href="#cb4-37" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb4-38"><a href="#cb4-38" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
<p>The <strong><code>clock_task()</code></strong> is also known as
<strong>Clock Driver</strong>.<br>First, it has a main loop, which
waiting for a message from the <code>HARD_INT</code>, and then call
<strong><code>do_clocktick()</code>.</strong><br> Before trying to
understand the execution of the <strong>Clock Driver</strong>, let’s
jump to the first command of the
<strong><code>clock_task()</code></strong>:<br> The
<strong><code>init_clock()</code></strong> function.</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true" tabindex="-1"></a><span class="co">/*===========================================================================*</span></span>
<span id="cb5-2"><a href="#cb5-2" aria-hidden="true" tabindex="-1"></a><span class="co"> * init_clock *</span></span>
<span id="cb5-3"><a href="#cb5-3" aria-hidden="true" tabindex="-1"></a><span class="co"> *===========================================================================*/</span></span>
<span id="cb5-4"><a href="#cb5-4" aria-hidden="true" tabindex="-1"></a>PRIVATE <span class="dt">void</span> init_clock<span class="op">()</span></span>
<span id="cb5-5"><a href="#cb5-5" aria-hidden="true" tabindex="-1"></a><span class="op">{</span></span>
<span id="cb5-6"><a href="#cb5-6" aria-hidden="true" tabindex="-1"></a> <span class="co">/* First of all init the clock system.</span></span>
<span id="cb5-7"><a href="#cb5-7" aria-hidden="true" tabindex="-1"></a><span class="co"> *</span></span>
<span id="cb5-8"><a href="#cb5-8" aria-hidden="true" tabindex="-1"></a><span class="co"> * Here the (a) clock is set to produce a interrupt at</span></span>
<span id="cb5-9"><a href="#cb5-9" aria-hidden="true" tabindex="-1"></a><span class="co"> * every 1/60 second (ea. 60Hz).</span></span>
<span id="cb5-10"><a href="#cb5-10" aria-hidden="true" tabindex="-1"></a><span class="co"> *</span></span>
<span id="cb5-11"><a href="#cb5-11" aria-hidden="true" tabindex="-1"></a><span class="co"> * Running right away.</span></span>
<span id="cb5-12"><a href="#cb5-12" aria-hidden="true" tabindex="-1"></a><span class="co"> */</span></span>
<span id="cb5-13"><a href="#cb5-13" aria-hidden="true" tabindex="-1"></a> arch_init_clock<span class="op">();</span> <span class="co">/* architecture-dependent initialization. */</span></span>
<span id="cb5-14"><a href="#cb5-14" aria-hidden="true" tabindex="-1"></a> </span>
<span id="cb5-15"><a href="#cb5-15" aria-hidden="true" tabindex="-1"></a> <span class="co">/* Initialize the CLOCK's interrupt hook. */</span></span>
<span id="cb5-16"><a href="#cb5-16" aria-hidden="true" tabindex="-1"></a> clock_hook<span class="op">.</span>proc_nr_e <span class="op">=</span> CLOCK<span class="op">;</span></span>
<span id="cb5-17"><a href="#cb5-17" aria-hidden="true" tabindex="-1"></a> </span>
<span id="cb5-18"><a href="#cb5-18" aria-hidden="true" tabindex="-1"></a> put_irq_handler<span class="op">(&</span>clock_hook<span class="op">,</span> CLOCK_IRQ<span class="op">,</span> clock_handler<span class="op">);</span></span>
<span id="cb5-19"><a href="#cb5-19" aria-hidden="true" tabindex="-1"></a> enable_irq<span class="op">(&</span>clock_hook<span class="op">);</span> <span class="co">/* ready for clock interrupts */</span></span>
<span id="cb5-20"><a href="#cb5-20" aria-hidden="true" tabindex="-1"></a> </span>
<span id="cb5-21"><a href="#cb5-21" aria-hidden="true" tabindex="-1"></a> <span class="co">/* Set a watchdog timer to periodically balance the scheduling queues. */</span></span>
<span id="cb5-22"><a href="#cb5-22" aria-hidden="true" tabindex="-1"></a> balance_queues<span class="op">(</span>NULL<span class="op">);</span> <span class="co">/* side-effect sets new timer */</span></span>
<span id="cb5-23"><a href="#cb5-23" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
<p>Inside the function <strong><code>init_clock()</code></strong>. It is
very important to understand these two statements:<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>put_irq_handler<span class="op">(&</span>clock_hook<span class="op">,</span> CLOCK_IRQ<span class="op">,</span> clock_handler<span class="op">);</span> <span class="co">// put_irq_handler: register an interrupt handler</span></span>
<span id="cb6-2"><a href="#cb6-2" aria-hidden="true" tabindex="-1"></a>enable_irq<span class="op">(&</span>clock_hook<span class="op">);</span> <span class="co">/* ready for clock interrupts */</span></span></code></pre></div>
<p><strong>From its name, it has some relationship with interrupt
request (IRQ).</strong></p>
<h3 id="interrupt-request-irq">Interrupt Request (IRQ)</h3>
<blockquote>
<p>Details of interrupt hardware are system dependent, but any system
must have elements functionally equivalent to those to be described for
systems with 32-bit Intel CPUs. Interrupts generated by hardware devices
are electrical signals and are handled in the first place by an
<strong>interrupt controller, an integrated circuit that can sense a
number of such signals and for each one generate a unique data pattern
on the processor’s data bus.</strong></p>
</blockquote>
<blockquote>
<p>This is necessary because the processor itself has only one input for
sensing all these devices, and thus cannot differentiate which device
needs service. PCs using Intel 32-bit processors are normally equipped
with two such controller chips. Each can handle eight inputs, but one is
a slave which feeds its output to one of the inputs of the master, so
fifteen distinct external devices can be sensed by the combination, as
shown in Fig. 2-39. Some of the fifteen inputs are dedicated;
<strong>the clock input, IRQ 0, for instance, does not have a connection
to any socket into which a new adapter can be plugged</strong>. Others
are connected to sockets and can be used for whatever device is plugged
in.</p>
</blockquote>
<figure>
<img src="Sources/interrupt.png" alt="interrupt" />
<figcaption aria-hidden="true">interrupt</figcaption>
</figure>
<p>The code of interrupt controller is in the <strong><a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/arch/i386/mpx386.S">kernel/mpx386.s</a></strong>,
from line 255 to 368.</p>
<pre class="assembly"><code>/*===========================================================================*/
/* hwint00 - 07 */
/*===========================================================================*/
/* Note this is a macro, it just looks like a subroutine. */
#define hwint_master(irq) \
call save /* save interrupted process state */;\
push $irq ;\
call irq_handle /* irq_handle(irq) */;\
pop %ecx ;\
movb $END_OF_INT, %al ;\
outb $INT_CTL /* reenable master 8259 */;\
ret /* restart (another) process */
/* Each of these entry points is an expansion of the hwint_master macro */
.balign 16
hwint00:
/* Interrupt routine for irq 0 (the clock). */
hwint_master(0)</code></pre>
<p><strong>Remember the Clock Hardware we metioned at the begining of
this note?</strong><br> As soon as (or, more accurately, 16.67
milliseconds after) <strong><code>init_clock()</code></strong> runs, the
first clock interrupt occurs, and clock interrupts repeat 60 times a
second as long as Minix 3 runs.</p>
<ol type="1">
<li><p>The CPU <strong>disables</strong> all interrupts when it receives
an interrupt.</p></li>
<li><p>For the <strong>clock interrupt</strong> (IRQ0), which is hard
wired to the chip that generates clock signals with no possibility of
any other device triggering this IRQ. It send a interrupt to 8259
interrupt chip every 16.67 milliseconds.</p></li>
<li><p>Once the chip get that interrupt, it will expanded the marco
<strong><code>hwint_master(0)</code></strong> and execute the assembly
code.</p></li>
</ol>
<h4 id="hwint_master0"><code>hwint_master(0)</code></h4>
<p><strong><code>save()</code></strong> is in <a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/arch/i386/mpx386.S">kernel/mpx386.s</a>
from line 369 to 400.<br> Which is to save the context of the
interrupted process on the stack provided by the CPU.</p>
<pre class="assembly"><code>/*===========================================================================*/
/* save */
/*===========================================================================*/
/*
* Save for protected mode.
* This is much simpler than for 8086 mode, because the stack already points
* into the process table, or has already been switched to the kernel stack.
*/
.balign 16
save:
cld /* set direction flag to a known value */
pushal /* save "general" registers */
pushw %ds /* save ds */
pushw %es /* save es */
pushw %fs /* save fs */
pushw %gs /* save gs */
mov %ss, %dx /* ss is kernel data segment */
mov %dx, %ds /* load rest of kernel segments */
mov %dx, %es /* kernel does not use fs, gs */
mov %esp, %eax /* prepare to return */
incb k_reenter /* from -1 if not reentering */
jne set_restart1 /* stack is already kernel stack */
mov $k_stktop, %esp
push $restart /* build return address for int handler */
xor %ebp, %ebp /* for stacktrace */
jmp *RETADR-P_STACKBASE(%eax)
.balign 4
set_restart1:
push $restart1
jmp *RETADR-P_STACKBASE(%eax)</code></pre>
<p>On line 389:
<strong><code>mov %esp, %eax /* prepare to return */</code></strong><br>
It move the value of return address (the addr that push into stack when
call <strong><code>save()</code></strong> inside
<strong><code>hwint_master()</code></strong> function to register
<strong><code>%eax</code>.</strong> so that it can return back to the
<code>hwint_master()</code> after executing the
<strong><code>jmp</code></strong> at the end of
<strong><code>save()</code></strong>.</p>
<p>line 393 <strong><code>push $restart</code></strong> Is a
brilliant idea. It make sure that after the
<strong><code>hwint_master()</code></strong> return, it will call the
<strong><code>restart()</code></strong> to execute the process which pc
is <strong><code>next_ptr</code></strong>.</p>
<p>After <strong><code>save()</code></strong> return and back to
<strong><code>hwint_master(0)</code></strong>, It will execute
<strong><code>call irq_handle</code></strong> to call the function
<strong><code>irq_handle(irq)</code></strong>, which scans a linked list
of structures that hold, among other things, addresses of functions to
be called to handle an interrupt for a device, and the process numbers
of the device drivers. It is a linked list because a single IRQ line may
be shared with several devices. The handler for each device is supposed
to test whether its device actually needs service.</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb9-1"><a href="#cb9-1" aria-hidden="true" tabindex="-1"></a>PUBLIC <span class="dt">void</span> irq_handle<span class="op">(</span>hook<span class="op">)</span></span>
<span id="cb9-2"><a href="#cb9-2" aria-hidden="true" tabindex="-1"></a>irq_hook_t <span class="op">*</span>hook<span class="op">;</span></span>
<span id="cb9-3"><a href="#cb9-3" aria-hidden="true" tabindex="-1"></a><span class="op">{</span></span>
<span id="cb9-4"><a href="#cb9-4" aria-hidden="true" tabindex="-1"></a><span class="co">/* Call the interrupt handlers for an interrupt with the given hook list.</span></span>
<span id="cb9-5"><a href="#cb9-5" aria-hidden="true" tabindex="-1"></a><span class="co"> * The assembly part of the handler has already masked the IRQ, reenabled the</span></span>
<span id="cb9-6"><a href="#cb9-6" aria-hidden="true" tabindex="-1"></a><span class="co"> * controller(s) and enabled interrupts.</span></span>
<span id="cb9-7"><a href="#cb9-7" aria-hidden="true" tabindex="-1"></a><span class="co"> */</span></span>
<span id="cb9-8"><a href="#cb9-8" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb9-9"><a href="#cb9-9" aria-hidden="true" tabindex="-1"></a> <span class="co">/* Call list of handlers for an IRQ. */</span></span>
<span id="cb9-10"><a href="#cb9-10" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span> <span class="op">(</span>hook <span class="op">!=</span> NULL<span class="op">)</span> <span class="op">{</span></span>
<span id="cb9-11"><a href="#cb9-11" aria-hidden="true" tabindex="-1"></a> <span class="co">/* For each handler in the list, mark it active by setting its ID bit,</span></span>
<span id="cb9-12"><a href="#cb9-12" aria-hidden="true" tabindex="-1"></a><span class="co"> * call the function, and unmark it if the function returns true.</span></span>
<span id="cb9-13"><a href="#cb9-13" aria-hidden="true" tabindex="-1"></a><span class="co"> */</span></span>
<span id="cb9-14"><a href="#cb9-14" aria-hidden="true" tabindex="-1"></a> irq_actids<span class="op">[</span>hook<span class="op">-></span>irq<span class="op">]</span> <span class="op">|=</span> hook<span class="op">-></span>id<span class="op">;</span></span>
<span id="cb9-15"><a href="#cb9-15" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">((*</span>hook<span class="op">-></span>handler<span class="op">)(</span>hook<span class="op">))</span> irq_actids<span class="op">[</span>hook<span class="op">-></span>irq<span class="op">]</span> <span class="op">&=</span> <span class="op">~</span>hook<span class="op">-></span>id<span class="op">;</span> <span class="co">// execute the handler function</span></span>
<span id="cb9-16"><a href="#cb9-16" aria-hidden="true" tabindex="-1"></a> hook <span class="op">=</span> hook<span class="op">-></span>next<span class="op">;</span></span>
<span id="cb9-17"><a href="#cb9-17" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb9-18"><a href="#cb9-18" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb9-19"><a href="#cb9-19" aria-hidden="true" tabindex="-1"></a> <span class="co">/* The assembly code will now disable interrupts, unmask the IRQ if and only</span></span>
<span id="cb9-20"><a href="#cb9-20" aria-hidden="true" tabindex="-1"></a><span class="co"> * if all active ID bits are cleared, and restart a process.</span></span>
<span id="cb9-21"><a href="#cb9-21" aria-hidden="true" tabindex="-1"></a><span class="co"> */</span></span>
<span id="cb9-22"><a href="#cb9-22" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb9-23"><a href="#cb9-23" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb9-24"><a href="#cb9-24" aria-hidden="true" tabindex="-1"></a><span class="pp">#if _WORD_SIZE == 2</span></span></code></pre></div>
<p>As I metioned before, the <strong>IRQ0</strong> is only used for
<strong>Clock Interrupt</strong>, so after execute
<strong><code>put_irq_handler(&clock_hook, CLOCK_IRQ, clock_handler);</code></strong>
in <strong><code>init_clock()</code></strong>. Every 16.67 milliseconds
when clock sent a <strong><code>Clock IRQ</code></strong> to the
<strong><code>hwint_master(0)</code></strong>, it will call
<strong><code>intr_handle(CLOCK)</code></strong>, which will call
<strong><code>clock_handler()</code></strong> function – <strong>which
probably runs more frequently than any other part of the MINIX 3
system</strong>.<br></p>
<h4 id="clock_handler"><code>clock_handler()</code></h4>
<p><strong>To improve the reading experience, I just list two key points
of this function, if you want to read the full code. Please check <a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/clock.c#L179">kernel/clock.c</a>
from line 179 to 265</strong>.<br></p>
<ul>
<li><strong>Update the ticks of running process</strong><br> Update
counters that register how much of the quantum of the current process
has been used and how much total time the current process has used.</li>
</ul>
<div class="sourceCode" id="cb10"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb10-1"><a href="#cb10-1" aria-hidden="true" tabindex="-1"></a><span class="co">/* Get number of ticks and update realtime. */</span></span>
<span id="cb10-2"><a href="#cb10-2" aria-hidden="true" tabindex="-1"></a> ticks <span class="op">=</span> lost_ticks <span class="op">+</span> <span class="dv">1</span><span class="op">;</span></span>
<span id="cb10-3"><a href="#cb10-3" aria-hidden="true" tabindex="-1"></a> lost_ticks <span class="op">=</span> <span class="dv">0</span><span class="op">;</span></span>
<span id="cb10-4"><a href="#cb10-4" aria-hidden="true" tabindex="-1"></a> realtime <span class="op">+=</span> ticks<span class="op">;</span></span>
<span id="cb10-5"><a href="#cb10-5" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb10-6"><a href="#cb10-6" aria-hidden="true" tabindex="-1"></a> <span class="co">/* Update user and system accounting times. Charge the current process for</span></span>
<span id="cb10-7"><a href="#cb10-7" aria-hidden="true" tabindex="-1"></a><span class="co"> * user time. If the current process is not billable, that is, if a non-user</span></span>
<span id="cb10-8"><a href="#cb10-8" aria-hidden="true" tabindex="-1"></a><span class="co"> * process is running, charge the billable process for system time as well.</span></span>
<span id="cb10-9"><a href="#cb10-9" aria-hidden="true" tabindex="-1"></a><span class="co"> * Thus the unbillable process' user time is the billable user's system time.</span></span>
<span id="cb10-10"><a href="#cb10-10" aria-hidden="true" tabindex="-1"></a><span class="co"> */</span></span>
<span id="cb10-11"><a href="#cb10-11" aria-hidden="true" tabindex="-1"></a> </span>
<span id="cb10-12"><a href="#cb10-12" aria-hidden="true" tabindex="-1"></a> proc_ptr<span class="op">-></span>p_user_time <span class="op">+=</span> ticks<span class="op">;</span></span>
<span id="cb10-13"><a href="#cb10-13" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>priv<span class="op">(</span>proc_ptr<span class="op">)-></span>s_flags <span class="op">&</span> PREEMPTIBLE<span class="op">)</span> <span class="op">{</span></span>
<span id="cb10-14"><a href="#cb10-14" aria-hidden="true" tabindex="-1"></a> proc_ptr<span class="op">-></span>p_ticks_left <span class="op">-=</span> ticks<span class="op">;</span></span>
<span id="cb10-15"><a href="#cb10-15" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb10-16"><a href="#cb10-16" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(!</span> <span class="op">(</span>priv<span class="op">(</span>proc_ptr<span class="op">)-></span>s_flags <span class="op">&</span> BILLABLE<span class="op">))</span> <span class="op">{</span></span>
<span id="cb10-17"><a href="#cb10-17" aria-hidden="true" tabindex="-1"></a> bill_ptr<span class="op">-></span>p_sys_time <span class="op">+=</span> ticks<span class="op">;</span></span>
<span id="cb10-18"><a href="#cb10-18" aria-hidden="true" tabindex="-1"></a> bill_ptr<span class="op">-></span>p_ticks_left <span class="op">-=</span> ticks<span class="op">;</span></span>
<span id="cb10-19"><a href="#cb10-19" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span></code></pre></div>
<ul>
<li><strong>If the interrupt handler detects that a process has used its
quantum or that a timer has expired.</strong><br> It send a message to
the <strong>Clock Driver</strong> which waiting for this
<strong>HARD_INT</strong> message.
(<strong><code>clock_task()</code></strong>)</li>
</ul>
<div class="sourceCode" id="cb11"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb11-1"><a href="#cb11-1" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">((</span>next_timeout <span class="op"><=</span> realtime<span class="op">)</span> <span class="op">||</span> <span class="op">(</span>proc_ptr<span class="op">-></span>p_ticks_left <span class="op"><=</span> <span class="dv">0</span><span class="op">)</span> <span class="op">||</span> expired<span class="op">)</span> <span class="op">{</span></span>
<span id="cb11-2"><a href="#cb11-2" aria-hidden="true" tabindex="-1"></a> prev_ptr <span class="op">=</span> proc_ptr<span class="op">;</span> <span class="co">/* store running process */</span></span>
<span id="cb11-3"><a href="#cb11-3" aria-hidden="true" tabindex="-1"></a> mini_notify<span class="op">(</span>proc_addr<span class="op">(</span>HARDWARE<span class="op">),</span> CLOCK<span class="op">);</span> <span class="co">/* send notification */</span></span>
<span id="cb11-4"><a href="#cb11-4" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span> </span></code></pre></div>
<h4 id="do_clocktick"><code>do_clocktick()</code></h4>
<p>When the <strong>Clock Driver</strong>
(<strong><code>clock_task()</code></strong>) recieve the messeage from
<strong><code>mini_notify()</code></strong>, it will call
<strong><code>do_clocktick()</code></strong> to pick a process to run
next.<br> The full code of <strong><code>do_clocktick()</code></strong>
is in <strong><a
href="https://github.com/Angold-4/OSDI/blob/master/Minix3/kernel/clock.c#L101">kernel/clock.c</a></strong>
from line 101 to 154. Also, I only pick a piece of code segment.</p>
<div class="sourceCode" id="cb12"><pre class="sourceCode c"><code class="sourceCode c"><span id="cb12-1"><a href="#cb12-1" aria-hidden="true" tabindex="-1"></a><span class="co">/* A process used up a full quantum. The interrupt handler stored this</span></span>
<span id="cb12-2"><a href="#cb12-2" aria-hidden="true" tabindex="-1"></a><span class="co"> * process in 'prev_ptr'. First make sure that the process is not on the </span></span>
<span id="cb12-3"><a href="#cb12-3" aria-hidden="true" tabindex="-1"></a><span class="co"> * scheduling queues. Then announce the process ready again. Since it has </span></span>
<span id="cb12-4"><a href="#cb12-4" aria-hidden="true" tabindex="-1"></a><span class="co"> * no more time left, it gets a new quantum and is inserted at the right </span></span>
<span id="cb12-5"><a href="#cb12-5" aria-hidden="true" tabindex="-1"></a><span class="co"> * place in the queues. As a side-effect a new process will be scheduled.</span></span>
<span id="cb12-6"><a href="#cb12-6" aria-hidden="true" tabindex="-1"></a><span class="co"> */</span> </span>
<span id="cb12-7"><a href="#cb12-7" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>prev_ptr<span class="op">-></span>p_ticks_left <span class="op"><=</span> <span class="dv">0</span> <span class="op">&&</span> priv<span class="op">(</span>prev_ptr<span class="op">)-></span>s_flags <span class="op">&</span> PREEMPTIBLE<span class="op">)</span> <span class="op">{</span></span>
<span id="cb12-8"><a href="#cb12-8" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb12-9"><a href="#cb12-9" aria-hidden="true" tabindex="-1"></a> dequeue<span class="op">(</span>prev_ptr<span class="op">);</span> <span class="co">/* take it off the queues */</span></span>
<span id="cb12-10"><a href="#cb12-10" aria-hidden="true" tabindex="-1"></a> enqueue<span class="op">(</span>prev_ptr<span class="op">);</span> <span class="co">/* and reinsert it again */</span> </span>
<span id="cb12-11"><a href="#cb12-11" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span></code></pre></div>
<p>The <strong><code>dequeue()</code></strong> and
<strong><code>enqueue()</code></strong> function is a part of the System
Components called <strong>System Scheduler</strong>.<br>Which will be
introduced in the next note. The only thing you need to know is that it
will schedule a new process to run by updating the
<strong><code>next_ptr</code></strong> so that after the
<strong><code>clock_hander()</code></strong> finished and return to
<strong><code>hwint_master(0)</code></strong>, when
<code>hwint_master(0)</code> return, it will call the
<strong><code>restart()</code></strong> function(stack), a process which
pc is <strong><code>next_ptr</code></strong> will be called.</p>
<p><strong>And that is what happend in 16.67 milliseconds of a CPU - A
Clock Tick</strong>.</p>
</section>
</div>
</div>
<div id="disqus_thread"></div>
<script>
var disqus_config = function () {
this.page.url = "https://angold4.org/OSDI/Chapter/Chapter2/4ClockTick.html"
this.page.identifier = "OSDI/Chapter/Chapter2/4ClockTick.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>