-
Notifications
You must be signed in to change notification settings - Fork 154
/
Copy path1.2.html
1002 lines (486 loc) · 54.6 KB
/
1.2.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="1.3.html" />
<link rel="prev" href="1.1.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 active" 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 " 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>先驱希望创造一个计算机的世界, 并赋予它执行程序的使命.
让我们一起来帮助他, 体验创世的乐趣.</p>
<p>大家都上过程序设计课程, 知道程序就是由代码和数据组成.
例如一个求<code>1+2+...+100</code>的程序, 大家不费吹灰之力就可以写出一个程序来完成这件事情.
不难理解, 数据就是程序处理的对象, 代码则描述了程序希望如何处理这些数据.
先不说仙剑奇侠传这个庞然大物, 为了执行哪怕最简单的程序, 最简单的计算机又应该长什么样呢?</p>
<h3 id="最简单的计算机">最简单的计算机</h3>
<p>为了执行程序, 首先要解决的第一个问题, 就是要把程序放在哪里.
显然, 我们不希望自己创造的计算机只能执行小程序.
因此, 我们需要一个足够大容量的部件, 来放下各种各样的程序, 这个部件就是存储器.
于是, 先驱创造了存储器, 并把程序放在存储器中, 等待着CPU去执行.</p>
<p>等等, CPU是谁? 你也许很早就听说过它了, 不过现在还是让我们来重新介绍一下它吧.
CPU是先驱最伟大的创造, 从它的中文名字"中央处理器"就看得出它被赋予了至高无上的荣耀:
CPU是负责处理数据的核心电路单元, 也就是说, 程序的执行全靠它了.
但只有存储器的计算机还是不能进行计算.
自然地, CPU需要肩负起计算的重任, 先驱为CPU创造了运算器, 这样就可以对数据进行各种处理了.
如果觉得运算器太复杂, 那就先来考虑一个加法器吧.</p>
<p>先驱发现, 有时候程序需要对同一个数据进行连续的处理.
例如要计算<code>1+2+...+100</code>, 就要对部分和<code>sum</code>进行累加,
如果每完成一次累加都需要把它写回存储器, 然后又把它从存储器中读出来继续加, 这样就太不方便了.
同时天下也没有免费的午餐, 存储器的大容量也是需要付出相应的代价的,
那就是速度慢, 这是先驱也无法违背的材料特性规律.
于是先驱为CPU创造了寄存器, 可以让CPU把正在处理中的数据暂时存放在其中.</p>
<p>寄存器的速度很快, 但容量却很小, 和存储器的特性正好互补,
它们之间也许会交织出新的故事呢, 不过目前我们还是顺其自然吧.</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>如果没有寄存器, 计算机还可以工作吗?
如果可以, 这会对硬件提供的编程模型有什么影响呢?</p><p>就算你是二周目来思考这个问题, 你也有可能是第一次听到"编程模型"这个概念.
不过如果一周目的时候你已经仔细地阅读过ISA手册, 你会记得确实有这么个概念.
所以, 如果想知道什么是编程模型, RTFM吧.</p></div></div>
<p>为了让强大的CPU成为忠诚的奴仆, 先驱还设计了"指令", 用来指示CPU对数据进行何种处理.
这样, 我们就可以通过指令来控制CPU, 让它做我们想做的事情了.</p>
<p>有了指令以后, 先驱提出了一个划时代的设想:
能否让程序来自动控制计算机的执行?
为了实现这个设想, 先驱和CPU作了一个简单的约定: 当执行完一条指令之后, 就继续执行下一条指令.
但CPU怎么知道现在执行到哪一条指令呢?
为此, 先驱为CPU创造了一个特殊的计数器, 叫"程序计数器"(Program Counter, PC).
在x86中, 它有一个特殊的名字, 叫<code>EIP</code>(Extended Instruction Pointer).</p>
<p>从此以后, 计算机就只需要做一件事情:</p>
<pre><code class="lang-c"><span class="hljs-keyword">while</span> (<span class="hljs-number">1</span>) {
从PC指示的存储器位置取出指令;
执行指令;
更新PC;
}
</code></pre>
<p>这样, 我们就有了一个足够简单的计算机了.
我们只要将一段指令序列放置在存储器中, 然后让PC指向第一条指令,
计算机就会自动执行这一段指令序列, 永不停止.</p>
<p>例如, 下面的指令序列可以计算<code>1+2+...+100</code>, 其中<code>r1</code>和<code>r2</code>是两个寄存器,
还有一个隐含的程序计数器<code>PC</code>, 它的初值是<code>0</code>.
为了帮助大家理解, 我们把指令的语义翻译成C代码放在右侧, 其中每一行C代码前都添加了一个语句标号:</p>
<pre><code>// PC: instruction | // label: statement
0: mov r1, 0 | pc0: r1 = 0;
1: mov r2, 0 | pc1: r2 = 0;
2: addi r2, r2, 1 | pc2: r2 = r2 + 1;
3: add r1, r1, r2 | pc3: r1 = r1 + r2;
4: blt r2, 100, 2 | pc4: if (r2 < 100) goto pc2; // branch if less than
5: jmp 5 | pc5: goto pc5;
</code></pre><p>计算机执行以上的指令序列, 最后会在<code>PC=5</code>处的指令陷入死循环,
此时计算已经结束, <code>1+2+...+100</code>的结果会存放在寄存器<code>r1</code>中.</p>
<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>在看到上述例子之前, 你可能会觉得指令是一个既神秘又难以理解的概念.
不过当你看到对应的C代码时, 你就会发现指令做的事情竟然这么简单!
而且看上去还有点蠢, 你随手写一个for循环都要比这段C代码看上去更高级.</p><p>不过你也不妨站在计算机的角度来理解一下,
计算机究竟是怎么通过这种既简单又笨拙的方式来计算<code>1+2+...+100</code>的.
这种理解会使你建立"程序如何在计算机上运行"的最初原的认识.</p></div></div>
<p>这个全自动的执行过程实在是太美妙了!
事实上, 开拓者图灵在1936年就已经提出<a href="https://en.wikipedia.org/wiki/Universal_Turing_machine" target="_blank">类似的核心思想</a>, "计算机之父"可谓名不虚传.
而这个流传至今的核心思想, 就是"存储程序".
为了表达对图灵的敬仰, 我们也把上面这个最简单的计算机称为"图灵机"(Turing Machine, TRM).
或许你已经听说过"图灵机"这个作为计算模型时的概念,
不过在这里我们只强调作为一个最简单的真实计算机需要满足哪些条件:</p>
<ul>
<li>结构上, TRM有存储器, 有PC, 有寄存器, 有加法器</li>
<li>工作方式上, TRM不断地重复以下过程:
从PC指示的存储器位置取出指令, 执行指令, 然后更新PC</li>
</ul>
<p>咦? 存储器, 计数器, 寄存器, 加法器, 这些不都是数字电路课上学习过的部件吗?
也许你会觉得难以置信, 但先驱说, 你正在面对着的那台无所不能的计算机, 就是由数字电路组成的!
不过, 我们在程序设计课上写的程序是C代码.
但如果计算机真的是个只能懂0和1的巨大数字电路, 这个冷冰冰的电路又是如何理解凝结了人类智慧结晶的C代码的呢?
先驱说, 计算机诞生的那些年还没有C语言, 大家都是直接编写对人类来说晦涩难懂的机器指令,
那是他所见过的最早的对电子计算机的编程方式了.
后来人们发明了高级语言和编译器, 能把我们写的高级语言代码进行各种处理, 最后生成功能等价的, CPU能理解的指令.
CPU执行这些指令, 就相当于是执行了我们写的代码.
今天的计算机本质上还是"存储程序"这种天然愚钝的工作方式,
是经过了无数计算机科学家们的努力, 我们今天才可以轻松地使用计算机.</p>
<div class="panel panel-danger"><div class="panel-heading"><h5 class="panel-title" id="计算机是个状态机"><i class="fa fa-bullhorn"></i> 计算机是个状态机</h5></div><div class="panel-body"><p>既然计算机是一个数组逻辑电路, 那么我们可以把计算机划分成两部分,
一部分由所有时序逻辑部件(存储器, 计数器, 寄存器)构成, 另一部分则是剩余的组合逻辑部件(如加法器等).
这样以后, 我们就可以从状态机模型的视角来理解计算机的工作过程了:
在每个时钟周期到来的时候, 计算机根据当前时序逻辑部件的状态,
在组合逻辑部件的作用下, 计算出并转移到下一时钟周期的新状态.</p><p>计算机的这个视角有什么用呢?
好像除了让你明白计算机硬件不再那么神秘之外, 也没什么特别的用处.
毕竟ICS课不要求大家用硬件描述语言来实现计算机硬件,
大家只要相信这件事能做成就可以了.</p><p>不过对于程序来说, 这个视角的作用会超乎你的想象.</p></div></div>
<h3 id="重新认识程序-程序是个状态机">重新认识程序: 程序是个状态机</h3>
<p>如果把计算机看成一个状态机, 那么运行在计算机上面的程序又是什么呢?</p>
<p>我们知道程序是由指令构成的, 那么我们先看看一条指令在状态机的模型里面是什么.
不难理解, 计算机正是通过执行指令的方式来改变自身状态的,
比如执行一条加法指令, 就可以把两个寄存器的值相加, 然后把结果更新到第三个寄存器中;
如果执行一条跳转指令, 就会直接修改PC的值, 使得计算机从新PC的位置开始执行新的指令.
所以在状态机模型里面, 指令可以看成是计算机进行一次状态转移的输入激励.</p>
<p>ICS课本的1.1.3小节中介绍了一个很简单的计算机.
这个计算机有4个8位的寄存器, 一个4位PC, 以及一段16字节的内存(也就是存储器),
那么这个计算机可以表示比特总数为<code>B = 4*8 + 4 + 16*8 = 164</code>,
因此这个计算机总共可以有<code>N = 2^B = 2^164</code>种不同的状态.
假设这个在这个计算机中, 所有指令的行为都是确定的,
那么给定<code>N</code>个状态中的任意一个, 其转移之后的新状态也是唯一确定的.
一般来说<code>N</code>非常大, 下图展示了<code>N=50</code>时某计算机的状态转移图.</p>
<p><img src="images/state-machine.png" alt="state-machine"></p>
<p>现在我们就可以通过状态机的视角来解释"程序在计算机上运行"的本质了:
给定一个程序, 把它放到计算机的内存中,
就相当于在状态数量为<code>N</code>的状态转移图中指定了一个初始状态,
程序运行的过程就是从这个初始状态开始, 每执行完一条指令, 就会进行一次确定的状态转移.
也就是说, 程序也可以看成一个状态机! 这个状态机是上文提到的大状态机(状态数量为<code>N</code>)的子集.</p>
<p>例如, 假设某程序在上图所示的计算机中运行,
其初始状态为左上角的8号状态, 那么这个程序对应的状态机为</p>
<pre><code>8->1->32->31->32->31->...
</code></pre><p>这个程序可能是:</p>
<pre><code>// PC: instruction | // label: statement
0: addi r1, r2, 2 | pc0: r1 = r2 + 2;
1: subi r2, r1, 1 | pc1: r2 = r1 - 1;
2: nop | pc2: ; // no operation
3: jmp 2 | pc3: goto pc2;
</code></pre><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>以上一小节中<code>1+2+...+100</code>的指令序列为例, 尝试画出这个程序的状态机.</p><p>这个程序比较简单, 需要更新的状态只包括<code>PC</code>和<code>r1</code>, <code>r2</code>这两个寄存器,
因此我们用一个三元组<code>(PC, r1, r2)</code>就可以表示程序的所有状态, 而无需画出内存的具体状态.
初始状态是<code>(0, x, x)</code>, 此处的<code>x</code>表示未初始化.
程序<code>PC=0</code>处的指令是<code>mov r1, 0</code>, 执行完之后<code>PC</code>会指向下一条指令, 因此下一个状态是<code>(1, 0, x)</code>.
如此类推, 我们可以画出执行前3条指令的状态转移过程:</p><pre><code>(0, x, x) -> (1, 0, x) -> (2, 0, 0) -> (3, 0, 1)
</code></pre><p>请你尝试继续画出这个状态机, 其中程序中的循环只需要画出前两次循环和最后两次循环即可.</p></div></div>
<p>通过上面必做题的例子, 你应该更进一步体会到"程序是如何在计算机上运行"了.
我们其实可以从两个互补的视角来看待同一个程序:</p>
<ul>
<li>一个是以代码(或指令序列)为表现形式的静态视角,
大家经常说的"写程序"/"看代码", 其实说的都是这个静态视角. 这个视角的一个好处是描述精简,
分支, 循环和函数调用的组合使得我们可以通过少量代码实现出很复杂的功能.
但这也可能会使得我们对程序行为的理解造成困难.</li>
<li>另一个是以状态机的状态转移为运行效果的动态视角, 它直接刻画了"程序在计算机上运行"的本质.
但这一视角的状态数量非常巨大, 程序代码中的所有循环和函数调用都以指令的粒度被完全展开,
使得我们难以掌握程序的整体语义.
但对于程序的局部行为, 尤其是从静态视角来看难以理解的行为,
状态机视角可以让我们清楚地了解相应的细节.</li>
</ul>
<div class="panel panel-info"><div class="panel-heading"><h5 class="panel-title" id="程序的状态机视角有什么好处"><i class="fa fa-comment-o"></i> 程序的状态机视角有什么好处?</h5></div><div class="panel-body"><p>有一些程序看上去很简单, 但行为却不那么直观, 比如递归.
要很好地理解递归程序在计算机上如何运行, 从状态机视角来看程序行为才是最有效的做法,
因为这一视角可以帮助你理清每一条指令究竟如何修改计算机的状态, 从而实现宏观上的递归语义.
ICS理论课的第三章会专门分析其中的细节, 我们在这里就不展开讨论递归的具体行为了.</p></div></div>
<!-- -->
<div class="panel panel-danger"><div class="panel-heading"><h5 class="panel-title" id="程序在计算机上运行的微观视角-程序是个状态机"><i class="fa fa-bullhorn"></i> "程序在计算机上运行"的微观视角: 程序是个状态机</h5></div><div class="panel-body"><p>"程序是个状态机"这一视角对ICS和PA来说都是非常重要的,
因为"理解程序如何在计算机上运行"就是ICS和PA的根本目标.
至于这个问题的宏观视角, 我们将会在PA的中期来介绍.</p><p>这一小节的文字对你来说应该不难理解, 但如果你将来没有养成从状态机视角理解程序行为的意识,
你可能会感到PA非常困难, 因为在PA中你需要不断地和代码打交道.
如果你不能从微观视角理解某些关键代码的行为, 你也无法从宏观视角完全弄清楚程序究竟是如何运行的.</p></div></div>
<footer class="page-footer-ex"> <span class="page-footer-ex-copyright"> By <a href="https://sashimi-yzh.github.io/" target="_blank">Zihao Yu</a>, 采用<a href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/" target="_blank">知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议</a>发布 </span>            <span class="page-footer-ex-footer-update"> 此页面修订于: 2023-02-25 08:25:35 </span> </footer>
</section>
</div>
<div class="search-results">
<div class="has-results">
<h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
<ul class="search-results-list"></ul>
</div>
<div class="no-results">
<h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
</div>
</div>
</div>
</div>
</div>
</div>
<a href="1.1.html" class="navigation navigation-prev " aria-label="Previous page: 在开始愉快的PA之旅之前">
<i class="fa fa-angle-left"></i>
</a>
<a href="1.3.html" class="navigation navigation-next " aria-label="Next page: RTFSC">
<i class="fa fa-angle-right"></i>
</a>
</div>
<script>
var gitbook = gitbook || [];
gitbook.push(function() {
gitbook.page.hasChanged({"page":{"title":"开天辟地的篇章","level":"1.3.2","depth":2,"next":{"title":"RTFSC","level":"1.3.3","depth":2,"path":"1.3.md","ref":"1.3.md","articles":[]},"previous":{"title":"在开始愉快的PA之旅之前","level":"1.3.1","depth":2,"path":"1.1.md","ref":"1.1.md","articles":[]},"dir":"ltr"},"config":{"gitbook":"3.x.x","theme":"default","variables":{},"plugins":["theme-comscore","intopic-toc","localized-footer","page-footer-ex","callouts"],"pluginsConfig":{"callouts":{"option":{"alert":"info","picto":"fa-edit"},"flag":{"alert":"success","picto":"fa-flag"},"question":{"alert":"info","picto":"fa-question-circle"},"info":{"alert":"info","picto":"fa-info-circle"},"todo":{"alert":"warning","picto":"fa-edit"},"caution":{"alert":"danger","picto":"fa-bullhorn"},"danger":{"alert":"danger","picto":"fa-exclamation"},"showTypeInHeader":false},"intopic-toc":{"isCollapsed":false,"isScrollspyActive":true,"label":"导航","maxDepth":6,"mode":"nested","selector":".markdown-section h2, .markdown-section h3, .markdown-section h4","visible":true},"page-footer-ex":{"copyright":"By [Zihao Yu](https://sashimi-yzh.github.io/), 采用[知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议](http://creativecommons.org/licenses/by-nc-sa/3.0/cn/)发布","markdown":true,"update_format":"YYYY-MM-DD HH:mm:ss","update_label":"此页面修订于: "},"search":{},"localized-footer":{"filename":"FOOTER.md","hline":"true"},"lunr":{"maxIndexSize":1000000,"ignoreSpecialCharacters":false},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"theme-comscore":{},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"styles":{"website":"styles.css","pdf":"styles.css"}},"file":{"path":"1.2.md","mtime":"2023-02-25T00:25:35.599Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2025-01-03T02:26:44.310Z"},"basePath":".","book":{"language":""}});
});
</script>
</div>
<script src="gitbook/gitbook.js"></script>
<script src="gitbook/theme.js"></script>
<script src="gitbook/gitbook-plugin-intopic-toc/anchor.min.js"></script>
<script src="gitbook/gitbook-plugin-intopic-toc/gumshoe.polyfills.min.js"></script>
<script src="gitbook/gitbook-plugin-intopic-toc/plugin.js"></script>
<script src="gitbook/gitbook-plugin-search/search-engine.js"></script>
<script src="gitbook/gitbook-plugin-search/search.js"></script>
<script src="gitbook/gitbook-plugin-lunr/lunr.min.js"></script>
<script src="gitbook/gitbook-plugin-lunr/search-lunr.js"></script>
<script src="gitbook/gitbook-plugin-sharing/buttons.js"></script>
<script src="gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
<script src="gitbook/gitbook-plugin-theme-comscore/test.js"></script>
</body>