-
Notifications
You must be signed in to change notification settings - Fork 154
/
Copy path4.4.html
1465 lines (915 loc) · 118 KB
/
4.4.html
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
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE HTML>
<html lang="" >
<head>
<meta charset="UTF-8">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<title>来自外部的声音 · GitBook</title>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="description" content="">
<meta name="generator" content="GitBook 3.2.3">
<link rel="stylesheet" href="gitbook/style.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-intopic-toc/style.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-page-footer-ex/style/plugin.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-callouts/plugin.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-highlight/website.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-search/search.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-fontsettings/website.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-theme-comscore/test.css">
<link rel="stylesheet" href="styles.css">
<meta name="HandheldFriendly" content="true"/>
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<link rel="apple-touch-icon-precomposed" sizes="152x152" href="gitbook/images/apple-touch-icon-precomposed-152.png">
<link rel="shortcut icon" href="gitbook/images/favicon.ico" type="image/x-icon">
<link rel="next" href="4.5.html" />
<link rel="prev" href="4.3.html" />
</head>
<body>
<div class="book">
<div class="book-summary">
<div id="book-search-input" role="search">
<input type="text" placeholder="Type to search" />
</div>
<nav role="navigation">
<ul class="summary">
<li class="chapter " data-level="1.1" data-path="index.html">
<a href="index.html">
Introduction
</a>
</li>
<li class="chapter " data-level="1.2" data-path="PA0.html">
<a href="PA0.html">
PA0 - 世界诞生的前夜: 开发环境配置
</a>
<ul class="articles">
<li class="chapter " data-level="1.2.1" data-path="0.1.html">
<a href="0.1.html">
Installing GNU/Linux
</a>
</li>
<li class="chapter " data-level="1.2.2" data-path="0.2.html">
<a href="0.2.html">
First Exploration with GNU/Linux
</a>
</li>
<li class="chapter " data-level="1.2.3" data-path="0.3.html">
<a href="0.3.html">
Installing Tools
</a>
</li>
<li class="chapter " data-level="1.2.4" data-path="0.4.html">
<a href="0.4.html">
Configuring vim
</a>
</li>
<li class="chapter " data-level="1.2.5" data-path="0.5.html">
<a href="0.5.html">
More Exploration
</a>
</li>
<li class="chapter " data-level="1.2.6" data-path="0.6.html">
<a href="0.6.html">
Getting Source Code for PAs
</a>
</li>
</ul>
</li>
<li class="chapter " data-level="1.3" data-path="PA1.html">
<a href="PA1.html">
PA1 - 开天辟地的篇章: 最简单的计算机
</a>
<ul class="articles">
<li class="chapter " data-level="1.3.1" data-path="1.1.html">
<a href="1.1.html">
在开始愉快的PA之旅之前
</a>
</li>
<li class="chapter " data-level="1.3.2" data-path="1.2.html">
<a href="1.2.html">
开天辟地的篇章
</a>
</li>
<li class="chapter " data-level="1.3.3" data-path="1.3.html">
<a href="1.3.html">
RTFSC
</a>
</li>
<li class="chapter " data-level="1.3.4" data-path="1.4.html">
<a href="1.4.html">
基础设施
</a>
</li>
<li class="chapter " data-level="1.3.5" data-path="1.5.html">
<a href="1.5.html">
表达式求值
</a>
</li>
<li class="chapter " data-level="1.3.6" data-path="1.6.html">
<a href="1.6.html">
监视点
</a>
</li>
<li class="chapter " data-level="1.3.7" data-path="1.7.html">
<a href="1.7.html">
如何阅读手册
</a>
</li>
</ul>
</li>
<li class="chapter " data-level="1.4" data-path="PA2.html">
<a href="PA2.html">
PA2 - 简单复杂的机器: 冯诺依曼计算机系统
</a>
<ul class="articles">
<li class="chapter " data-level="1.4.1" data-path="2.1.html">
<a href="2.1.html">
不停计算的机器
</a>
</li>
<li class="chapter " data-level="1.4.2" data-path="2.2.html">
<a href="2.2.html">
RTFSC(2)
</a>
</li>
<li class="chapter " data-level="1.4.3" data-path="2.3.html">
<a href="2.3.html">
程序, 运行时环境与AM
</a>
</li>
<li class="chapter " data-level="1.4.4" data-path="2.4.html">
<a href="2.4.html">
基础设施(2)
</a>
</li>
<li class="chapter " data-level="1.4.5" data-path="2.5.html">
<a href="2.5.html">
输入输出
</a>
</li>
</ul>
</li>
<li class="chapter " data-level="1.5" data-path="PA3.html">
<a href="PA3.html">
PA3 - 穿越时空的旅程: 批处理系统
</a>
<ul class="articles">
<li class="chapter " data-level="1.5.1" data-path="3.1.html">
<a href="3.1.html">
最简单的操作系统
</a>
</li>
<li class="chapter " data-level="1.5.2" data-path="3.2.html">
<a href="3.2.html">
穿越时空的旅程
</a>
</li>
<li class="chapter " data-level="1.5.3" data-path="3.3.html">
<a href="3.3.html">
用户程序和系统调用
</a>
</li>
<li class="chapter " data-level="1.5.4" data-path="3.4.html">
<a href="3.4.html">
文件系统
</a>
</li>
<li class="chapter " data-level="1.5.5" data-path="3.5.html">
<a href="3.5.html">
精彩纷呈的应用程序
</a>
</li>
</ul>
</li>
<li class="chapter " data-level="1.6" data-path="PA4.html">
<a href="PA4.html">
PA4 - 虚实交错的魔法: 分时多任务
</a>
<ul class="articles">
<li class="chapter " data-level="1.6.1" data-path="4.1.html">
<a href="4.1.html">
多道程序
</a>
</li>
<li class="chapter " data-level="1.6.2" data-path="4.2.html">
<a href="4.2.html">
虚实交错的魔法
</a>
</li>
<li class="chapter " data-level="1.6.3" data-path="4.3.html">
<a href="4.3.html">
超越容量的界限
</a>
</li>
<li class="chapter active" data-level="1.6.4" data-path="4.4.html">
<a href="4.4.html">
来自外部的声音
</a>
</li>
<li class="chapter " data-level="1.6.5" data-path="4.5.html">
<a href="4.5.html">
编写不朽的传奇
</a>
</li>
</ul>
</li>
<li class="chapter " data-level="1.7" data-path="blank.html">
<a href="blank.html">
杂项
</a>
<ul class="articles">
<li class="chapter " data-level="1.7.1" data-path="FAQ.html">
<a href="FAQ.html">
常见问题(FAQ)
</a>
</li>
<li class="chapter " data-level="1.7.2" data-path="why.html">
<a href="why.html">
为什么要学习计算机系统基础
</a>
</li>
<li class="chapter " data-level="1.7.3" data-path="linux.html">
<a href="linux.html">
Linux入门教程
</a>
</li>
<li class="chapter " data-level="1.7.4" data-path="man.html">
<a href="man.html">
man入门教程
</a>
</li>
<li class="chapter " data-level="1.7.5" data-path="git.html">
<a href="git.html">
git入门教程
</a>
</li>
<li class="chapter " data-level="1.7.6" data-path="nemu-isa-api.html">
<a href="nemu-isa-api.html">
NEMU ISA相关API说明文档
</a>
</li>
<li class="chapter " data-level="1.7.7" data-path="changelog.html">
<a href="changelog.html">
更新日志
</a>
</li>
<li class="chapter " data-level="1.7.8" data-path="i386-intro.html">
<a href="i386-intro.html">
i386手册指令集阅读指南
</a>
</li>
<li class="chapter " data-level="1.7.9" data-path="exec.html">
<a href="exec.html">
指令执行例子
</a>
</li>
</ul>
</li>
<li class="divider"></li>
<li>
<a href="https://www.gitbook.com" target="blank" class="gitbook-link">
Published with GitBook
</a>
</li>
</ul>
</nav>
</div>
<div class="book-body">
<div class="body-inner">
<div class="book-header" role="navigation">
<!-- Title -->
<h1>
<i class="fa fa-circle-o-notch fa-spin"></i>
<a href="." >来自外部的声音</a>
</h1>
</div>
<div class="page-wrapper" tabindex="-1" role="main">
<div class="page-inner">
<div id="book-search-results">
<div class="search-noresults">
<section class="normal markdown-section">
<h2 id="分时多任务">分时多任务</h2>
<p>多道程序成功地实现了任务的并发执行, 但这种并发不一定是公平的.
如果一个进程长时间不触发I/O操作, 多道程序系统并不会主动将控制权切换到其它进程,
这样其它进程就得不到运行的机会.
想象一下, 如果你在开黑的时候, Windows突然在后台进行自动更新,
队友就打电话问你怎么老掉线, 你一定会非常不爽.
所以多道程序系统更多还是用在批处理的场景当中, 它能保证CPU满负荷运转,
但并不适合用于交互式的场景.</p>
<p>如果要用于交互式场景, 系统就要以一定的频率在所有进程之间来回切换,
保证每个进程都能及时得到响应, 这就是分时多任务.
从触发上下文切换的角度看, 分时多任务可以分成两类.
第一类是<a href="https://en.wikipedia.org/wiki/Cooperative_multitasking" target="_blank">协同多任务</a>, 它的工作方式基于一个约定:
用户进程周期性地主动让出CPU的控制权, 从而让其它进程得到运行的机会.
这件事需要操作系统提供一个特殊的系统调用, 那就是我们在PA3中实现的<code>SYS_yield</code>.
在PA3中看似没什么用的<code>SYS_yield</code>, 其实是协同多任务操作系统中上下文切换的基石.</p>
<p>说是"协同", 是因为这个机制需要所有进程一起合作,
共同遵守这个约定, 整个系统才能正确工作.
一些简单的嵌入式操作系统或者实时操作系统会采用协同多任务,
因为这些系统上运行的程序都是固定的那么几个,
让它们共同遵守约定来让出CPU并不困难.
但试想一下, 在多用户操作系统中, 运行程序的来源是无法预知的,
如果有一个恶意进程故意不遵守这个约定, 不调用<code>SYS_yield</code>,
或者无意陷入了死循环, 整个系统将会被这个进程独占.
上古时期的某些Windows版本就采用了协同多任务的设计,
操作系统经常会被一些有bug的程序弄垮.</p>
<p>之所以协同多任务会出现这样的问题, 是系统将上下文切换的触发条件寄托在进程的行为之上.
我们知道调度一个进程的时候, 整个计算机都会被它所控制,
无论是计算, 访存, 还是输入输出, 都是由进程的行为来决定的.
为了修复这个漏洞, 我们必须寻找一种无法由进程控制的机制.</p>
<h2 id="来自外部的声音">来自外部的声音</h2>
<p>回想起我们考试的时候, 在试卷上如何作答都是我们来控制的,
但等到铃声一响, 无论我们是否完成答题, 都要立即上交试卷.
我们希望的恰恰就是这样一种效果:
时间一到, 无论正在运行的进程有多不情愿, 操作系统都要进行上下文切换.
而解决问题的关键, 就是时钟.
我们在IOE中早就已经加入了时钟了, 然而这还不能满足我们的需求,
我们希望时钟能够主动地通知处理器, 而不是被动地等着处理器来访问.</p>
<p>这样的通知机制, 在计算机中称为硬件中断.
硬件中断的实质是一个数字信号, 当设备有事件需要通知CPU的时候,
就会发出中断信号. 这个信号最终会传到CPU中, 引起CPU的注意.</p>
<p>第一个问题就是中断信号是怎么传到CPU中的.
支持中断机制的设备控制器都有一个中断引脚, 这个引脚会和CPU的INTR引脚相连,
当设备需要发出中断请求的时候, 它只要将中断引脚置为高电平, 中断信号就会一直传到CPU的INTR引脚中.
但计算机上通常有多个设备, 而CPU引脚是在制造的时候就固定了,
因而在CPU端为每一个设备中断分配一个引脚的做法是不现实的.</p>
<p>为了更好地管理各种设备的中断请求,
IBM PC兼容机中都会带有Intel 8259 PIC(Programmable Interrupt Controller, 可编程中断控制器),
而RISC-V系统中用得比较多的中断控制器则是<a href="https://github.com/riscv/riscv-plic-spec/blob/master/riscv-plic.adoc" target="_blank">PLIC(Platform Level Interrupt Controller)</a>.
中断控制器最主要的作用就是充当设备中断信号的多路复用器,
即在多个设备中断信号中选择其中一个信号, 然后转发给CPU.</p>
<p>第二个问题是CPU如何响应到来的中断请求.
CPU每次执行完一条指令的时候, 都会看看INTR引脚, 看是否有设备的中断请求到来.
一个例外的情况就是CPU处于关中断状态, 此时即使INTR引脚为高电平, CPU也不会响应中断.
CPU的关中断状态和中断控制器是独立的,
中断控制器只负责转发设备的中断请求, 最终CPU是否响应中断还需要由CPU的状态决定.</p>
<p>CPU的关中断状态可以通过软件来控制, 不同的ISA对此有不同的定义, 具体地:</p>
<ul>
<li>在x86中, 如果EFLAGS中的IF位为0, 则CPU处于关中断状态</li>
<li>在mips32中, 如果status中的IE位为0, 或EXL位为1, 或ERL位为1, 则CPU处于关中断状态</li>
<li>在riscv32中, 如果mstatus中的MIE位为0, 则CPU处于关中断状态<ul>
<li>事实上, riscv32标准的中断响应机制还有更多内容, 在PA中我们进行了简化.
如需了解完整的中断响应机制, 请查阅相关手册.</li>
</ul>
</li>
</ul>
<p>如果中断到来的时候, CPU没有处在关中断状态, 它就要马上响应到来的中断请求.
我们刚才提到中断控制器会生成一个中断号, CPU将会保存中断上下文,
然后把这个中断作为异常处理过程的原因, 找到并跳转到入口地址, 进行一些和设备相关的处理.
这个过程和之前提到的异常处理十分相似.</p>
<p>对CPU来说, 设备的中断请求何时到来是不可预测的,
在处理一个中断请求的时候到来了另一个中断请求也是有可能的.
如果希望支持中断嵌套 -- 即在进行优先级低的中断处理的过程中,
响应另一个优先级高的中断 -- 那么堆栈将是保存中断上下文信息的唯一选择.
如果选择把上下文信息保存在一个固定的地方, 发生中断嵌套的时候,
第一次中断保存的上下文信息将会被优先级高的中断处理过程所覆盖, 从而造成灾难性的后果.</p>
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="灾难性的后果这个问题有点难度"><i class="fa fa-question-circle"></i> 灾难性的后果(这个问题有点难度)</h5></div><div class="panel-body"><p>假设硬件把中断信息固定保存在某个内存地址(例如<code>0x1000</code>)的位置, AM也总是从这里开始构造上下文.
如果发生了中断嵌套, 将会发生什么样的灾难性后果?
这一灾难性的后果将会以什么样的形式表现出来?
如果你觉得毫无头绪, 你可以用纸笔模拟中断处理的过程.</p></div></div>
<!-- -->
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="如何支持中断嵌套"><i class="fa fa-question-circle"></i> 如何支持中断嵌套</h5></div><div class="panel-body"><p>思考一下, x86, mips32和riscv32的软硬件该分别如何协同, 来支持中断嵌套?</p></div></div>
<h2 id="抢占多任务">抢占多任务</h2>
<p>分时多任务的第二类就是<a href="https://en.wikipedia.org/wiki/Preemption_(computing)#Preemptive_multitasking" target="_blank">抢占多任务</a>,
它基于硬件中断(通常是时钟中断)强行进行上下文切换,
让系统中的所有进程公平地轮流运行.
在抢占多任务操作系统中, 中断是其赖以生存的根基:
只要中断的东风一刮, 操作系统就会卷土重来,
一个故意死循环的恶意程序就算有天大的本事,
此时此刻也要被请出CPU, 从而让其它程序得到运行的机会,</p>
<p>在NEMU中, 我们只需要添加时钟中断这一种中断就可以了.
由于只有一种中断, 我们也不需要通过中断控制器进行中断的管理,
直接让时钟中断连接到CPU的INTR引脚即可.
而对于时钟中断的中断号, 不同的ISA有不同的约定.
时钟中断通过<code>nemu/src/device/timer.c</code>中的<code>timer_intr()</code>触发, 每10ms触发一次.
触发后, 会调用<code>dev_raise_intr()</code>函数(在<code>nemu/src/device/intr.c</code>中定义).
你需要:</p>
<ul>
<li>在cpu结构体中添加一个<code>bool</code>成员<code>INTR</code>.</li>
<li>在<code>dev_raise_intr()</code>中将INTR引脚设置为高电平.</li>
<li>在<code>cpu_exec()</code>中for循环的末尾添加轮询INTR引脚的代码,
每次执行完一条指令就查看是否有硬件中断到来:<pre><code class="lang-c"><span class="hljs-keyword">word_t</span> intr = isa_query_intr();
<span class="hljs-keyword">if</span> (intr != INTR_EMPTY) {
cpu.pc = isa_raise_intr(intr, cpu.pc);
}
</code></pre>
</li>
<li>实现<code>isa_query_intr()</code>函数(在<code>nemu/src/isa/$ISA/system/intr.c</code>中定义):</li>
</ul>
<pre><code class="lang-c"><span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IRQ_TIMER 32 <span class="hljs-comment">// for x86</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IRQ_TIMER 0 <span class="hljs-comment">// for mips32</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IRQ_TIMER 0x80000007 <span class="hljs-comment">// for riscv32</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> IRQ_TIMER 0x8000000000000007 <span class="hljs-comment">// for riscv64</span></span>
<span class="hljs-keyword">word_t</span> isa_query_intr() {
<span class="hljs-keyword">if</span> ( ??? ) {
cpu.INTR = <span class="hljs-literal">false</span>;
<span class="hljs-keyword">return</span> IRQ_TIMER;
}
<span class="hljs-keyword">return</span> INTR_EMPTY;
}
</code></pre>
<ul>
<li>修改<code>isa_raise_intr()</code>中的代码, 让处理器进入关中断状态:<ul>
<li>x86 - 在保存EFLAGS寄存器后, 将其IF位置为<code>0</code></li>
<li>mips32 - 将status.EXL位置为<code>1</code><ul>
<li>你还需要修改eret指令的实现, 将status.EXL置为<code>0</code></li>
</ul>
</li>
<li>riscv32 - 将mstatus.MIE保存到mstatus.MPIE中, 然后将mstatus.MIE位置为<code>0</code><ul>
<li>你还需要修改mret指令的实现, 将mstatus.MPIE还原到mstatus.MIE中, 然后将mstatus.MPIE位置为<code>1</code></li>
</ul>
</li>
</ul>
</li>
</ul>
<p>在软件上, 你还需要:</p>
<ul>
<li>在CTE中添加时钟中断的支持, 将时钟中断打包成<code>EVENT_IRQ_TIMER</code>事件.</li>
<li>Nanos-lite收到<code>EVENT_IRQ_TIMER</code>事件之后, 调用<code>schedule()</code>来强制当前进程让出CPU,
同时也可以去掉我们之前在设备访问中插入的<code>yield()</code>了.</li>
<li>为了可以让处理器在运行用户进程的时候响应时钟中断, 你还需要修改<code>kcontext()</code>和<code>ucontext()</code>的代码,
在构造上下文的时候, 设置正确中断状态, 使得将来恢复上下文之后CPU处于开中断状态.</li>
</ul>
<div class="panel panel-warning"><div class="panel-heading"><h5 class="panel-title" id="实现抢占多任务"><i class="fa fa-edit"></i> 实现抢占多任务</h5></div><div class="panel-body"><p>根据讲义的上述内容, 添加相应的代码来实现抢占式的分时多任务.</p><p>为了测试时钟中断确实在工作, 你可以在Nanos-lite收到<code>EVENT_IRQ_TIMER</code>事件后用<code>Log()</code>输出一句话.</p></div></div>
<!-- -->
<div class="panel panel-success"><div class="panel-heading"><h5 class="panel-title" id="硬件中断与difftest"><i class="fa fa-lightbulb-o"></i> 硬件中断与DiffTest</h5></div><div class="panel-body"><p>对DiffTest来说, 我们无法直接给QEMU注入时钟中断,
从而无法保证在中断到来时QEMU与NEMU处于相同的状态.
不过, 伴你一路走来的基础设施, 相信也已经帮你排除了绝大部分的bug了,
接下来的一小段路就试试靠自己吧.</p></div></div>
<!-- -->
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="中断和用户进程初始化"><i class="fa fa-question-circle"></i> 中断和用户进程初始化</h5></div><div class="panel-body"><p>我们知道, 用户进程从Navy的<code>_start</code>开始运行, 并且在<code>_start</code>中设置正确的栈指针.
如果在用户进程设置正确的栈指针之前就到来了中断,
我们的系统还能够正确地进行中断处理吗?</p></div></div>
<h3 id="基于时间片的进程调度">基于时间片的进程调度</h3>
<p>在抢占多任务操作系统中, 由于时钟中断以固定的速率到来,
时间被划分成长度均等的时间片, 这样系统就可以进行基于时间片的进程调度了.</p>
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="优先级调度"><i class="fa fa-edit"></i> 优先级调度</h5></div><div class="panel-body"><p>我们可以修改<code>schedule()</code>的代码, 给仙剑奇侠传分配更多的时间片,
使得仙剑奇侠传调度若干次, 才让hello内核线程调度1次.
这是因为hello内核线程做的事情只是不断地输出字符串,
我们只需要让hello内核线程偶尔进行输出, 以确认它还在运行就可以了.</p></div></div>
<p>我们会发现, 给仙剑奇侠传分配更多的时间片之后, 其运行速度有了一定的提升.
这再次向我们展现了"分时"的本质:
程序之间只是轮流使用处理器, 它们并不是真正意义上的"同时"运行.</p>
<p>真实系统中的调度问题比上面仙剑奇侠传的例子要复杂得多.
比如双十一节, 全国一瞬间向阿里巴巴的服务器发起购物请求,
这些请求最终会被转化成上亿个进程在成千上万台服务器中被处理.
在数据中心中如何调度数量如此巨大的进程, 来尽可能提高用户的服务质量,
是阿里巴巴一直都面临的严峻挑战.</p>
<h3 id="抢占和并发">抢占和并发</h3>
<p>如果没有中断的存在, 计算机的运行就是完全确定的.
根据计算机的当前状态, 你完全可以推断出下一条指令执行后, 甚至是执行100条指令后计算机的状态.
但如果让计算机支持中断, 状态机的行为就变得难以预测了.</p>
<p><img src="images/vme.png" alt="vme"></p>
<p>为了对中断的行为进行建模, 我们对<code>fex()</code>函数的定义进行扩展:
除了判断当前状态是否需要抛出异常, 如果当前处理器处于开中断状态, 还需要判断是否有中断到来.
这说明在每条指令执行的时候, 计算机都将有可能因为中断到来而跳转到中断处理函数.</p>
<p>中断给计算机系统带来的不确定性可以说是一把双刃剑.
比如GNU/Linux内核会维护一个entropy pool, 用于收集系统中的熵(不确定性).
每当中断到来的时候, 就会给这个pool添加一些熵.
通过这些熵, 我们就可以生成真正的随机数了, <code>/dev/random</code>就是这样做的.
有了真正的随机数, 恶意程序的攻击也变得相对困难了(比如<a href="https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44271.pdf" target="_blank">ASLR</a>), 系统的安全也多了一分保障.</p>
<p>但另一方面, 中断的存在也不得不让程序在一些问题的处理上需要付出额外的代价.
由于中断随时可能会到来, 如果两个进程有一个共享的变量<code>v</code>(比如迅雷多线程下载共享同一个文件缓冲区),
一个进程<code>A</code>往<code>v</code>中写<code>0</code>, 刚写完中断就到来,
但当下次<code>A</code>再次运行的时候, <code>v</code>的值就可能不再是<code>0</code>了.
从某种程度上来说, 这也是并发惹的祸: 可能进程<code>B</code>在并发地修改<code>v</code>的值, 但<code>A</code>却不知情.
这种由于并发造成的bug, 还带有不确定性的烙印: 如果中断到来的时机不一样, 就不会触发这个bug了.
所以这种bug又叫<a href="https://en.wikipedia.org/wiki/Heisenbug" target="_blank">Heisenbug</a>, 和量子力学的测不准原理类似,
你想调试它的时候, 它可能就不出现了.</p>
<p>不但是用户进程之间可能会有共享变量, 操作系统内核更是并发bug的重灾区.
比如并发写同一个文件的多个用户进程会共享同一个文件偏移量,
如果处理不当, 可能就会导致写数据丢失.
更一般地, 用户进程都会并发地执行系统调用,
操作系统还需要保证它们都能按照系统调用的语义正确地执行.</p>
<p>啊, 还是不剧透那么多了, 大家到了操作系统课再慢慢体(xiang)会(shou)乐(tong)趣(ku)吧,
也许到时候你就会想念PA单线程的好了.</p>
<h2 id="内核栈和用户栈">内核栈和用户栈</h2>
<p>我们之前把如下问题作为最难的思考题留给大家思考:</p>
<pre><code>为什么目前不支持并发执行多个用户进程?
</code></pre><p>现在我们就来揭晓问题的答案: 这是因为用户栈的访问造成的.</p>
<h3 id="问题分析">问题分析</h3>
<p>为了方便描述, 我们假设某一时刻, 操作系统将要从用户进程A切换到用户进程B.
具体地, 在A运行的时候, 栈指针<code>sp</code>会指向A的用户栈.
当A执行系统调用, 或者中断到来的时候, 就会经过CTE陷入操作系统.
这时, 操作系统决定要调度用户进程B, 它就会把B的上下文返回给CTE,
并期望CTE依次进行如下操作:</p>
<ul>
<li>通过<code>__am_switch()</code>切换到B的虚拟地址空间</li>
<li>在<code>trap.S</code>中恢复B的上下文</li>
</ul>
<p>如果我们再仔细考虑过程中的细节, 就会发现其中的问题.
具体地, <code>__am_switch()</code>切换到B的虚拟地址空间之前,
需要先读出B的上下文结构中的地址空间描述符指针<code>pdir</code>(x86为<code>cr3</code>).
而B的上下文结构是上一次B进入CTE时在B的用户栈上创建的,
但B的用户栈并不在A的虚拟地址空间里面!</p>
<p>于是, 为了正确读出B的地址空间描述符指针, 我们需要先切换到B的虚拟地址空间;
但另一方面, 为了切换到B的虚拟地址空间, 我们需要先正确读出B的地址空间描述符指针!
这形成了一个"鸡和蛋"的循环依赖问题.
实际执行时, <code>__am_switch()</code>的代码将会读出一个错误的地址空间描述符指针,
从而无法正确切换到B的虚拟地址空间.</p>
<p>为了打破上述循环依赖, 我们不能将地址空间描述符指针保存到用户栈中,
而是应该将它保存到一个所有用户进程都可见的地址空间中.
显然, 这个所有用户进程都可见的地址空间, 就是内核的虚拟地址空间,
因为所有虚拟地址空间都会包含内核映射, 这保证了无论操作系统切换到哪一个用户进程,
代码都可以通过内核映射访问内核的虚拟地址空间.</p>
<p>不过作为一个地址空间描述符指针, 其值在创建用户进程上下文的时候就已经确定,
并在每次进入CTE时, 其值都是一致的.
因此, 我们完全不必在中断异常到来时保存它, 只要在创建用户进程上下文时将其存放在PCB中,
需要切换虚拟地址空间时, 就直接从B的PCB中读出地址空间描述符指针即可.
当然, PCB是操作系统的概念, AM并不了解, 因此还需要VME提供一个新的API <code>switch_addrspace()</code>:
操作系统在<code>schedule()</code>中选择进程B之后, 先通过<code>switch_addrspace()</code>切换到B的虚拟地址空间,
再返回到CTE并恢复B的上下文.</p>
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="打破循环依赖的方法"><i class="fa fa-question-circle"></i> 打破循环依赖的方法</h5></div><div class="panel-body"><p>如上文所述, 将地址空间描述符指针存放在PCB中,
并在VME中添加一个新API <code>switch_addrspace()</code>,
从正确性来考虑, 这一方案是否可行?</p></div></div>
<p>我们把上述方案的正确性分析作为思考题留给大家.
假设上述方案是正确的, 但在真实的操作系统中, 在用户栈上保存上下文却会引入安全漏洞.
一个恶意程序可以执行如下的指令序列:</p>
<pre><code>la sp, kernel_addr
ecall
</code></pre><p>如果操作系统把上下文保存到<code>sp</code>所指向的内存位置,
位于<code>kernel_addr</code>的内核数据将会受到恶意破坏!</p>
<p>因此, 操作系统不能相信陷入内核时栈指针的值, 在进行任何栈操作之前(包括保存上下文),
操作系统都需要先把栈指针指向一个自己准备的栈, 这个过程称为"栈切换"(stack switching).
在这之后, 保存上下文的位置就在操作系统的掌控之下, 从而解决了上述恶意程序的问题.
这个操作系统自己准备的栈, 就是我们之前介绍的内核栈.</p>