-
Notifications
You must be signed in to change notification settings - Fork 154
/
Copy path4.3.html
1413 lines (894 loc) · 130 KB
/
4.3.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.4.html" />
<link rel="prev" href="4.2.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 active" data-level="1.6.3" data-path="4.3.html">
<a href="4.3.html">
超越容量的界限
</a>
</li>
<li class="chapter " 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>现代操作系统不使用分段还是有一定的道理的.
有<a href="http://arcade.cs.columbia.edu/interference-sc12.pdf" target="_blank">研究表明</a>, Google数据中心中的1000台服务器在7分钟内就运行了上千个不同的程序,
其中有的是巨大无比的家伙(Google内部开发程序的时候为了避免不同计算机上的动态库不兼容的问题,
用到的所有库都以静态链接的方式成为程序的一部分, 光是程序的代码段就有几百MB甚至上GB的大小,
感兴趣的同学可以阅读<a href="https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44271.pdf" target="_blank">这篇文章</a>), 有的只是一些很小的测试程序.
让这些特征各异的程序都占用连续的存储空间并不见得有什么好处:
一方面, 那些巨大无比的家伙们在一次运行当中只会触碰到很小部分的代码,
其实没有必要分配那么多内存把它们全部加载进来;
另一方面, 小程序运行结束之后, 它占用的存储空间就算被释放了,
也很容易成为"碎片空洞" - 只有比它更小的程序才能把碎片空洞用起来.
分段机制的简单朴素, 在现实中也许要付出巨大的代价.</p>
<p>事实上, 我们需要一种按需分配的虚存管理机制.
之所以分段机制不好实现按需分配, 就是因为段的粒度太大了,
为了实现这一目标, 我们需要反其道而行之:
把连续的存储空间分割成小片段, 以这些小片段为单位进行组织, 分配和管理.
这正是分页机制的核心思想.</p>
<h3 id="分页">分页</h3>
<p>在分页机制中, 这些小片段称为页面, 在虚拟地址空间和物理地址空间中也分别称为虚拟页和物理页.
分页机制做的事情, 就是把一个个的虚拟页分别映射到相应的物理页上.
显然, 这一映射关系并不像分段机制中只需要一个段基址寄存器就可以描述的那么简单.
分页机制引入了一个叫"页表"的结构, 页表中的每一个表项记录了一个虚拟页到物理页的映射关系,
来把不必连续的物理页面重新组织成连续的虚拟地址空间.
因此, 为了让分页机制支撑多任务操作系统的运行, 操作系统首先需要以物理页为单位对内存进行管理.
每当加载程序的时候, 就给程序分配相应的物理页(注意这些物理页之间不必连续),
并为程序准备一个新的页表, 在页表中填写程序用到的虚拟页到这些物理页的映射关系.
等到程序运行的时候, 操作系统就把之前为这个程序填写好的页表设置到MMU中,
MMU就会根据页表的内容进行地址转换, 把程序的虚拟地址空间映射到操作系统所希望的物理地址空间上.</p>
<p><img src="images/Os-paging.png" alt="os-paging"></p>
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="虚存管理中pic的好处"><i class="fa fa-question-circle"></i> 虚存管理中PIC的好处</h5></div><div class="panel-body"><p>我们之前提到, PIC的其中一个好处是可以将代码加载到任意内存位置执行.
如果配合虚存管理, PIC还有什么新的好处呢? (Hint: 动态库已经在享受这些好处了)</p></div></div>
<p>i386是x86史上首次引进分页机制的处理器, 它把物理内存划分成以4KB为单位的页面,
同时也采用了二级页表的结构.
为了方便叙述, i386给第一级页表取了个新名字叫"页目录".
虽然听上去很厉害, 但其实原理都是一样的.
每一张页目录和页表都有1024个表项, 每个表项的大小都是4字节,
除了包含页表(或者物理页)的基地址, 还包含一些标志位信息.
因此, 一张页目录或页表的大小是4KB, 要放在寄存器中是不可能的, 因此它们要放在内存中.
为了找到页目录, i386提供了一个CR3(control register 3)寄存器, 专门用于存放页目录的基地址.
这样, 页级地址转换就从CR3开始一步一步地进行, 最终将虚拟地址转换成真正的物理地址,
这个过程称为一次page table walk.</p>
<pre><code> PAGE FRAME
+-----------+-----------+----------+ +---------------+
| DIR | PAGE | OFFSET | | |
+-----+-----+-----+-----+-----+----+ | |
| | | | |
+-------------+ | +------------->| PHYSICAL |
| | | ADDRESS |
| PAGE DIRECTORY | PAGE TABLE | |
| +---------------+ | +---------------+ | |
| | | | | | +---------------+
| | | | |---------------| ^
| | | +-->| PG TBL ENTRY |--------------+
| |---------------| |---------------|
+->| DIR ENTRY |--+ | |
|---------------| | | |
| | | | |
+---------------+ | +---------------+
^ | ^
+-------+ | +---------------+
| CR3 |--------+
+-------+
</code></pre><p>我们不打算给出分页过程的详细解释, 请你结合i386手册的内容和课堂上的知识,
尝试理解i386分页机制, 这也是作为分页机制的一个练习.
i386手册中包含你想知道的所有信息, 包括这里没有提到的表项结构, 地址如何划分等.</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"><ul>
<li>i386不是一个32位的处理器吗, 为什么表项中的基地址信息只有20位, 而不是32位?</li>
<li>手册上提到表项(包括CR3)中的基地址都是物理地址, 物理地址是必须的吗? 能否使用虚拟地址?</li>
<li>为什么不采用一级页表? 或者说采用一级页表会有什么缺点?</li>
</ul></div></div>
<p>页级转换的过程并不总是成功的, 因为i386也提供了页级保护机制, 实现保护功能就要靠表项中的标志位了.
我们对一些标志位作简单的解释:</p>
<ul>
<li>present位表示物理页是否可用, 不可用的时候又分两种情况:<ol>
<li>物理页面由于交换技术被交换到磁盘中了, 这就是你在课堂上最熟悉的Page fault的情况之一了,
这时候可以通知操作系统内核将目标页面换回来, 这样就能继续执行了</li>
<li>进程试图访问一个未映射的线性地址, 并没有实际的物理页与之相对应, 因此这就是一个非法操作咯</li>
</ol>
</li>
<li>R/W位表示物理页是否可写, 如果对一个只读页面进行写操作, 就会被判定为非法操作</li>
<li>U/S位表示访问物理页所需要的权限, 如果一个ring 3的进程尝试访问一个ring 0的页面, 当然也会被判定为非法操作</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>上文只介绍了i386的分页机制, 事实上, 其它ISA的分页机制也是大同小异,
理解了i386分页机制之后, mips32和riscv32的分页机制也就不难理解了.</p><p>当然, 具体细节还是得RTFM.</p></div></div>
<!-- -->
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="riscv64需要实现三级页表"><i class="fa fa-comment-o"></i> riscv64需要实现三级页表</h5></div><div class="panel-body"><p>riscv32的Sv32机制只能对32位的虚拟地址进行地址转换, 但riscv64的虚拟地址最长是64位,
因此需要有另外的机制来支持更长的虚拟地址的地址转换.
在PA中, 如果你选择了riscv64, 那只需要实现Sv39三级页表的分页机制即可,
而且PA只会使用4KB小页面, 不会使用2MB的大页面, 因此你无需实现Sv39的大页面功能.
具体细节请RTFM.</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>程序设计课上老师告诉你, 当一个指针变量的值等于NULL时, 代表空, 不指向任何东西.
仔细想想, 真的是这样吗? 当程序对空指针解引用的时候, 计算机内部具体都做了些什么?
你对空指针的本质有什么新的认识?</p></div></div>
<p>和分段机制相比, 分页机制更灵活, 甚至可以使用超越物理地址上限的虚拟地址.
现在我们从数学的角度来理解这两点.
撇去存储保护机制不谈, 我们可以把这分段和分页的过程分别抽象成两个数学函数:</p>
<pre><code> y = seg(x) = seg.base + x
y = page(x)
</code></pre><p>可以看到, <code>seg()</code>函数只不过是做加法.
如果仅仅使用分段机制, 我们还要求段级地址转换的结果不能超过物理地址上限:</p>
<pre><code> y = seg(x) = seg.base + x < PMEM_MAX
=> x < PMEM_MAX - seg.base
=> x <= PMEM_MAX
</code></pre><p>我们可以得出这样的结论: 仅仅使用分段机制, 虚拟地址是无法超过物理地址上限的.
而分页机制就不一样了, 我们无法给出<code>page()</code>具体的解析式,
是因为填写页目录和页表实际上就是在用枚举自变量的方式定义<code>page()</code>函数,
这就是分页机制比分段机制灵活的根本原因.
虽然"页级地址转换结果不能超过物理地址上限"的约束仍然存在,
但我们只要保证每一个函数值都不超过物理地址上限即可,
并没有对自变量的取值作明显的限制, 当然自变量本身也就可以比函数值还大.
这就已经把分页的"灵活"和"允许使用超过物理地址上限"这两点特性都呈现出来了.</p>
<p>i386采用段页式存储管理机制.
不过仔细想想, 这只不过是把分段和分页结合起来罢了, 用数学函数来理解, 也只不过是个复合函数:</p>
<pre><code>paddr = page(seg(vaddr))
</code></pre><p>而"虚拟地址空间"和"物理地址空间"这两个在操作系统中无比重要的概念,
也只不过是这个复合函数的定义域和值域而已.</p>
<p>最后, 支持分页机制的处理器能识别什么是页表吗?
我们以一个页面大小为1KB的一级页表的地址转换例子来认识这个问题:</p>
<pre><code class="lang-c">pa = (pg_table[va >> <span class="hljs-number">10</span>] & ~<span class="hljs-number">0x3ff</span>) | (va & <span class="hljs-number">0x3ff</span>);
</code></pre>
<p>可以看到, 处理器并没有表的概念: 地址转换的过程只不过是一些访存和位操作而已.
这再次向我们展示了计算机的本质:
一堆美妙的, 蕴含着深刻数学智慧和工程原理的... 门电路!
然而这些小小的门电路操作却成为了今天多任务操作系统的根基,
支撑着千千万万程序的运行, 归根到底还是离不开计算机系统抽象的核心思想.</p>
<h3 id="状态机视角下的虚存管理机制">状态机视角下的虚存管理机制</h3>
<p>从状态机视角来看, 虚存管理机制是什么呢?</p>
<p>为了描述虚存管理机制在状态机视角的行为, 我们需要对状态机<code>S = <R, M></code>的访存行为进行扩展.
具体地, 我们需要增加一个函数<code>fvm: M -> M</code>, 它就是我们上文讨论的地址转换的映射,
然后把状态机中所有对<code>M</code>的访问<code>M[addr]</code>替换成<code>M[fvm(addr)]</code>, 就是虚存管理机制的行为.
例如指令<code>mov $1, addr</code>, 在虚存机制关闭时, 它的行为是TRM定义的:</p>
<pre><code>M[addr] <- 1
</code></pre><p>而在虚存机制打开时, 它的行为则是:</p>
<pre><code>M[fvm(addr)] <- 1
</code></pre><p>我们刚才已经讨论过, 地址转换的过程可以通过访存和位操作来实现,
这说明<code>fvm()</code>函数的行为也是可以通过状态机视角来描述的.</p>
<p><img src="images/vme.png" alt="vme"></p>
<p>比较特殊的是<code>fvm()</code>这个函数. 回顾PA3介绍的状态机模型中引入的<code>fex()</code>函数,
它实际上并不属于状态机的一部分, 因为抛出异常的判断方式是和状态机的具体状态无关的.
而<code>fvm()</code>函数则有所不同, 它可以看做是是状态机的一部分,
这是因为<code>fvm()</code>函数是可以通过程序进行修改的: 操作系统可以决定如何建立虚拟地址和物理地址之间的映射.
具体地, <code>fvm()</code>函数可以认为是系统寄存器<code>SR</code>的一部分, 操作系统通过修改<code>SR</code>来对虚存进行管理.</p>
<h3 id="tlb---地址转换的加速">TLB - 地址转换的加速</h3>
<p>细心的你会发现, 在不改变页目录基地址, 页目录和页表的情况下,
如果连续访问同一个虚拟页的内容, 页级地址转换的结果都是一样的.
事实上, 这种情况太常见了, 例如程序执行的时候需要取指令,
而指令的执行一般都遵循局部性原理, 大多数情况下都在同一个虚拟页中执行.
但进行page table walk是要访问内存的, 如果有方法可以避免这些没有必要的page table walk,
就可以提高处理器的性能了.</p>
<p>一个很自然的想法就是将页级地址转换的结果存起来,
在进行下一次的页级地址转换之前, 看看这个虚拟页是不是已经转换过了,
如果是, 就直接取出之前的结果, 这样就可以节省不必要的page table walk了.
这不正好是cache的思想吗? 这样一个特殊的cache, 叫TLB.
我们可以从CPU cache的知识来理解TLB的组织:</p>
<ul>
<li>TLB的基本单元是项, 一项存放了一次页级地址转换的结果
(其实就是一个页表项, 包括物理页号和一些和物理页相关的标志位), 功能上相当于一个cache block.</li>
<li>TLB项的tag由虚拟页号来充当, 表示这一项对应于哪一个虚拟页号.</li>
<li>TLB的项数一般不多, 为了提高命中率, TLB一般采用全相联或者组相联的组织方式.</li>
<li>由于页目录和页表一旦建立之后, 一般不会随意修改其中的表项, 因此TLB不存在写策略和写分配方式的问题.</li>
</ul>
<p>实践表明, 大小64项的TLB, 命中率可以高达90%, 有了TLB之后, 果然大大节省了不必要的page table walk.</p>
<p>听上去真不错!
不过在现代的多任务操作系统中, 如果仅仅简单按照上述方式来使用TLB, 却会导致致命的后果.
我们知道, 操作系统会为每个进程分配不同的页目录和页表, 虽然两个进程可能都会从0x8048000开始执行,
但分页机制会把它们映射到不同的物理页, 从而做到存储空间的隔离.
当然, 操作系统进行进程切换的时候也需要更新CR3的内容,
使得CR3寄存器指向新进程的页目录, 这样才能保证分页机制将虚拟地址映射到新进程的物理存储空间.</p>
<p>现在问题来了, 假设有两个进程, 对于同一个虚拟地址0x8048000,
操作系统已经设置好正确的页目录和页表, 让1号进程映射到物理地址0x1234000,
2号进程映射到物理地址0x5678000, 同时假设TLB一开始所有项都被置为无效.
这时1号进程先运行, 访问虚拟地址0x8048000, 查看TLB发现未命中, 于是进行page table walk,
根据1号进程的页目录和页表进行页级地址转换, 得到物理地址0x1234000, 并填充TLB.
假设此时发生了进程切换, 轮到2号进程来执行, 它也要访问虚拟地址0x8048000, 查看TLB,
发现命中, 于是不进行page table walk, 而是直接使用TLB中的物理页号, 得到物理地址0x1234000.
2号进程竟然访问了1号进程的存储空间, 但2号进程和操作系统对此都毫不知情!</p>
<p>出现这个致命错误的原因是, TLB没有维护好进程和虚拟地址映射关系的一致性:
TLB只知道有一个从虚拟地址0x8048000到物理地址0x1234000的映射关系,
但它并不知道这个映射关系是属于哪一个进程的.
找到问题的原因之后, 解决它也就很容易了, 只要在TLB项中增加一个域ASID(address space ID),
用于指示映射关系所属的进程即可, mips32就是这样做的.
x86的做法则比较"野蛮", 在每次更新CR3时强制冲刷TLB的内容,
由于进程切换必定伴随着CR3的更新, 因此一个进程运行的时候, TLB中不会存在其它进程的映射关系.
当然, 为了防止冲刷过猛, 页表项中有一个Global位, 那些Global位为1的映射关系则不会被冲刷,
比如可以把内核中<code>do_syscall()</code>所在的页面的Global位设置为1,
这样系统调用的处理过程就不会出现TLB miss了.</p>
<h3 id="软件管理的tlb">软件管理的TLB</h3>
<p>对于x86和riscv32来说, TLB一般都是由硬件来负责管理的:
当TLB miss时, 硬件逻辑会自动进行page table walk, 并将地址转换结果填充到TLB中,
软件不知道也无需知道这一过程的细节.
对PA来说, 这是一个好消息: 既然对软件透明, 那么就可以简化了.
因此如果你选择了x86或者riscv32, 你不必在NEMU中实现TLB.</p>
<p>但mips32就不一样了, 为了降低硬件设计的复杂度,
mips32规定, page table walk和TLB填充都由软件来负责.
很自然地, 在mips32中, TLB miss被设计成一种异常:
当TLB miss时, CPU将会抛出异常, 由软件来进行page table walk和TLB填充.</p>
<p>于是mips32需要把TLB的状态暴露给软件, 让软件可以来对TLB进行管理.
为了实现这一点, mips32至少需要添加以下内容:</p>
<ul>
<li>CP0寄存器, 包括entryhi, entrylo0, entrylo1, index这四个寄存器.
其中entryhi寄存器存放虚拟页号相关的信息, entrylo0寄存器和entrylo1寄存器存放物理页号相关的信息.</li>
<li>CP0指令<ul>
<li>tlbp, 用于寻找与entryhi寄存器中匹配的TLB项, 若找到, 则将index寄存器设置为该TLB项的序号</li>
<li>tlbwi, 用于将entryhi, entrylo0和entrylo1这三个寄存器的内容写入到index序号所指示的TLB项中</li>
<li>tlbwr, 用于将entryhi, entrylo0和entrylo1这三个寄存器的内容写入到随机一个TLB项中</li>
<li>让mtc0和mfc0支持上述四个CP0寄存器的访问</li>
</ul>
</li>
</ul>
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="mips32的tlb管理是否更简单"><i class="fa fa-question-circle"></i> mips32的TLB管理是否更简单?</h5></div><div class="panel-body"><p>有一种观点认为, mips32的分页机制更简单. 你认同吗?
尝试分别在现在, 以及完成这部分内容之后回答这个问题.</p></div></div>
<p>TLB管理是一个考量软硬件tradeoff的典型例子,
mips32把这件事交给软件来做, 毫无疑问会引入额外的性能开销.
在一些性能不太重要的嵌入式场景中, 这并不会有什么大问题;
但如果是在一些面向高性能的场景中, 这种表面上简单的机制就成为了性能瓶颈的来源:
例如在数据中心场景中, 程序需要访问的数据非常多, 局部性也很差,
TLB miss是非常常见的现象, 这种情况下, 软件管理TLB的性能开销就会被进一步放大.</p>
<p>在mips32中, 为了进一步降低page table walk带来的性能开销,
一个TLB表项其实管理的是连续两个虚拟页面的映射关系,
于是物理页号相关的寄存器有entrylo0和entrylo1两个,
分别用于表示这两个虚拟页面对应的物理页号.
具体地, 假设虚拟地址和物理地址的长度都是32位, 并采用4KB页面大小,
那么entryhi寄存器中的虚拟页号则是19位, entrylo0和entrylo1寄存器中的物理页号为20位.
这样的好处是, 在一次page table walk中可以同时填充两个虚拟页面的地址转换结果,
期望通过程序的局部性获得一些性能收益.
不过在数据中心场景面前, 这都是杯水车薪了.</p>
<h2 id="将虚存管理抽象成vme">将虚存管理抽象成VME</h2>
<p>虚存管理的具体实现自然是架构相关的, 比如在x86中用于存放页目录基地址的CR3,
在riscv32上并不叫这个名字, 访问这个寄存器的指令自然也各不相同.
再者, 不同架构中的页面大小可能会有差异, 页表项的结构也不尽相同,
更不用说有的架构还可能有多于两级的页表结构了.
于是, 我们可以将虚存管理的功能划入到AM的一类新的API中,
名字叫VME(Virtual Memory Extension).</p>
<p>老规矩, 我们来考虑如何将虚存管理的功能抽象成统一的API.
换句话说, 虚存机制的本质究竟是什么呢?
我们在上文已经讨论过这个问题了: 虚存机制, 说白了就是个映射(或函数).
也就是说, 本质上虚存管理要做的事情, 就是在维护这个映射.
但这个映射应该是每个进程都各自维护一份, 因此我们需要如下的两个API:</p>
<pre><code class="lang-c"><span class="hljs-comment">// 创建一个默认的地址空间</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">protect</span><span class="hljs-params">(AddrSpace *as)</span></span>;
<span class="hljs-comment">// 销毁指定的地址空间</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">unprotect</span><span class="hljs-params">(AddrSpace *as)</span></span>;
</code></pre>
<p>其中<code>AddrSpace</code>是一个结构体类型, 定义了地址空间描述符的结构(在<code>abstract-machine/am/include/am.h</code>中定义):</p>