/
index.html
773 lines (646 loc) · 39.3 KB
/
index.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
<!DOCTYPE html>
<html class="no-js" lang="en-US" prefix="og: http://ogp.me/ns# fb: http://ogp.me/ns/fb#">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<meta name="description" content="">
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="keywords" content="cs, ">
<meta property="og:type" content="article"/>
<meta property="og:description" content=""/>
<meta property="og:title" content="Computer science a kernel programmer's perspective : firoyang.org"/>
<meta property="og:site_name" content="Firo Website"/>
<meta property="og:image" content="" />
<meta property="og:image:type" content="image/jpeg" />
<meta property="og:image:width" content="" />
<meta property="og:image:height" content="" />
<meta property="og:url" content="http://firoyang.org/cs/cs/">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2015-02-27"/>
<meta property="article:modified_time" content="2015-02-27"/>
<meta property="article:tag" content="cs">
<base href="http://firoyang.org/">
<title> Computer science a kernel programmer's perspective</title>
<link rel="canonical" href="http://firoyang.org/cs/cs/">
<link rel='stylesheet' type='text/css'>
<link rel="stylesheet" href="/static/css/style.css">
<link rel="shortcut icon" href="/favicon.ico" type="image/x-icon" />
</head>
<body lang="en" itemscope itemtype="http://schema.org/Article">
<header id="header">
<link rel="stylesheet" href="static/css/font-awesome.min.css">
<nav id="nav">
<div id="title"><a href="/">Firo Notes</a></div>
<div>
</div>
</nav>
<nav id="nav">
<ul id="mainnav">
<li>
<a href="/review/">
<span class="icon"> <i aria-hidden="false" class="fa fa-thumbs-o-up"></i></span>
<span> review</span>
</a>
</li>
<li>
<a href="/firo/">
<span class="icon"> <i aria-hidden="true" class="fa fa-male"></i></span>
<span> firo </span>
</a>
</li>
<li>
<a href="/history/">
<span class="icon"> <i aria-hidden="false" class="fa fa-institution"></i></span>
<span> history </span>
</a>
</li>
<li>
<a href="/about">
<span class="icon"> <i aria-hidden="true" class="fa fa-rocket"></i></span>
<span> Firo </span>
</a>
</li>
<li>
<a href="/howto/">
<span class="icon"> <i aria-hidden="true" class="fa fa-gamepad"></i></span>
<span> howto </span>
</a>
</li>
<li>
<a href="/kernel/">
<span class="icon"> <i aria-hidden="true" class="fa fa-linux"></i></span>
<span> kernel </span>
</a>
</li>
<li>
<a href="/net/">
<span class="icon"> <i aria-hidden="true" class="fa fa-globe"></i></span>
<span> net </span>
</a>
</li>
<li>
<a href="/philosophy/">
<span class="icon"> <i aria-hidden="true" class="icon-leaf"></i></span>
<span> philosophy </span>
</a>
</li>
<li>
<a href="/lyubishchev/">
<span class="icon"> <i aria-hidden="true" class="fa fa-hourglass-half"></i></span>
<span> lyubishchev </span>
</a>
</li>
<li>
<a href="/cs/">
<span class="icon"> <i aria-hidden="true" class="fa fa-laptop"></i></span>
<span> cs </span>
</a>
</li>
<li>
<a href="/linguistics/">
<span class="icon"> <i aria-hidden="true" class="fa fa-language"></i></span>
<span> linguistics </span>
</a>
</li>
</ul>
</nav>
<nav id="nav">
</nav>
</header>
<link rel="stylesheet" href="highlight.js/styles/monokai-sublime.css">
<script src="highlight.js/highlight.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
<section id="main">
<h1 itemprop="name" >Computer science a kernel programmer's perspective</h1>
<aside id="meta">
<div>
<section id="datecount">
<h4 id="date"> Fri Feb 27, 2015 </h4>
</section>
<ul id="tags">
<li> <a href="http://firoyang.org//tags/cs">cs</a> </li>
</ul>
</div>
</aside>
<meta itemprop="wordCount" content="2222">
<meta itemprop="datePublished" content="2015-02-27">
<meta itemprop="url" content="http://firoyang.org/cs/cs/">
<div>
<article itemprop="articleBody" id="content">
<h1 id="reference:067ec0f34de866d1b35db70204ef4b7d">Reference</h1>
<p><a href="http://www.bravegnu.org/gnu-eprog/">Vijay Kumar B’s Embedded Programming with the GNU Toolchain</a></p>
<h1 id="the-architecture-of-computer-science:067ec0f34de866d1b35db70204ef4b7d">The Architecture of Computer science</h1>
<p>SICP states that cs focuses on process.<br />
What process is is the set of changes and quantaties.而这些changes 和 quantaties live in model of computation.<br />
我们可以说一个process就是一个从属于model of computation的changes和quantaties的一次排列和集合.<br />
所以model of computation至少是change的集合 和 quantaty的集合的集合.processess 本身就是暗含着data/quantaties的.<br />
Why can processes being? It’s model of computation.<br />
这就是cs的form, process和model of computation. What is the material of cs?<br />
cs 的material 是symbolic.<br />
For now, we have noticed that the form of cs is changes and quantities.<br />
And the material of cs is symbolic(or, symbolic system).<br />
Both form and material are properties of being/abyss.<br />
人类的思维使用多种materials(vision, animation, graphics,or, feelings)去express a concept。<br />
可以说程序设计语言就是标准描述 process的Semiotic system。<br />
所以, pl对process的elements or origins做了合适的描述。<br />
sicp研究的符号规则层面的process 和 data。 design pattern研究的是语义层面的。<br />
PL 给了我们一种视角, 从process的元素的角度去描述process.<br />
form language(BNF->syntax, regex->lexical)藐视pl的语法.<br />
form language可以通过automata鉴别.automata等价于form system lambda calculus.<br />
自动机被相应的form grammar分类.<br />
我们的目的是规范化人类思维的表达形式.以此来达到交流, 具现化.<br />
我们要明白, pl的所有内容都是围绕the set of changes and quantaties建立的,<br />
也就是说pl是能指, 而所指便是the set of changes and quantaties.<br />
syntax句法不是我们关注的, 我们关注的是semantic.从semantic角度去尽可能的描述changes和quantaty.<br />
quantaties and changes: type system<br />
我们给quantaties附上特定的类型, 表达特定的含义,<br />
primitive expression: 数学量, 符号学字符, function<br />
combination: compound elements<br />
abstraction: name an elements<br />
relation: inference, relaton of changes, Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules;<br />
也就是Jhone Locke的binary relation.<br />
process 可以看成人的意志力展示.origins加入interence不关注changes. logic就是研究过程/changes和过程/changes之间的关系.<br />
control flow描述设定的就是这种order/relation.核心不在于有没有if else, 而是是否有足够的表达能力.<br />
表达changes之间的relation/order.可能是一种图的感觉, 就比如if else引起了tree这种order的产生.<br />
也就是说语言的表达力. changes要类似automata的四通八达的感觉.<br />
process由 changes, inference/relation, quantaties组成.因为这是由人的意志will 参与的process.<br />
inference 强调的是order of changes/computation,也就是control flow.<br />
Why does the order of execution matter?<br />
Then we need programming:sicp c3(c2/c1)<br />
then interpreter: sicp c4<br />
link load<br />
computation model: sicp c5<br />
if else: 表示的是relation(changes之间的关系, order, causality, inference)<br />
也就是说pl包含:<br />
changes, quantaties, relation. 这几种表述.<br />
pl和machine/model of computation近乎等价, progrm是machin的超集. program 是process.而pl不是.<br />
所以pl和machine都对process有表达的能力.pl和machine的form一致, 但material不同. 他们都是process元素的集合.<br />
programming是排列组合这些process elements的craft.可以说这些元素是data, 可以转变为process.<br />
这里面我们就定义programmer的skills, crafts, 是一种排力组合的能力, 不严禁的通俗的理解.<br />
design pattern 更注重宏观process. 他们排布process. 单这些process是处理别的process.high-order process(procedure?)<br />
而algorithm, 可以认为是关注的是primitive/ process.<br />
图灵机加入的”感知”,正是laking of causal.<br />
之于表述computational process, 认为(hypothesis?)自然语言和pl是具有相同能力的.<br />
programming的目的之一是把思维结果转为pl形式表达出来.<br />
另外, 我们现在能总结出, cs的两大主题就是:the form of process and how to express more better.<br />
process的内在, 以及如何表达process.cs剩下的问题都是programmer 码农的问题.<br />
现在我们来研究纯粹的process.继承sicp的定义.<br />
procedure是process的体现. process >= procedure. 所谓的local evolution, 等价于c,lisp的function.<br />
procedure 是一changes(quantaties, relation)有限的集合.<br />
一个process可以包含多个procedure, 也可以只有一个procedure(如, 递归, 迭代).<br />
还有另外一个就是data.process和data唇亡齿寒.<br />
process: procedure, computation/changes.<br />
data->: compound data, quantaty.<br />
我们研究的重点似乎时relation吧?<br />
process和data既像一物两面, 又像唇亡齿寒.<br />
下面开始,<br />
从combination, abstraction, relation这三个方面属性的process.<br />
从简单到复杂, 先关注process.<br />
如果process只有一个procedure. elementary process.<br />
似乎我们可以得到一个关于process的坐标系: procedure 的种类和数量.<br />
这里, 我们不关注algorithm.<br />
这里, 关注design pattern, GoF, elemental design pattern, POSA.<br />
从坐标系角度只考虑process和process之间的关系:<br />
1 只有一种quality的procedure, 完成的process.<br />
那么数量上如果构成大于1, 也就是procedure call procedure.<br />
可以是iteration or recursion; 我门的坐标系反应不出来.<br />
需要另外一个属性, procedure 自身是否是运算的参数.<br />
坐标系改下, procedure的数量换成procedure是否参与运算. 如果参与computation就是递归.<br />
默认procedure 数量>=2.<br />
我们再一次发现, procedures之间可能并不是直接调用的.<br />
所以一个小坐标系, 能表达的太有限, 要废弃掉.从属性角度看.但可以明确procedures出现次数是2个以上.<br />
当然, 我们是从process角度分析问题的.<br />
只有一种procedure,<br />
* call/order relation<br />
参与 computaton 是 recursive, otherwise, iteration.<br />
iter(a,i, n)<br />
if (i<n)
a = a * (a +1)
i++;
return iter(a, i, n)//tail call><br />
看来这个问题的实质是process是否作为计算的对象.而recursive和iteration是某个general的特例.<br />
loose relation: sequence(特例iteration), 是computation之间的关系.<br />
strict relation: computation是内在的关系. computation被抽象data<br />
primitive computation可以调function, function可以调primitive computation.<br />
computation function 经过抽象变成data.data反过来又可构成computation.<br />
可以说没有data, 全是computation!?那这么说(所谓的”recursive”, 就司空见惯了.)<br />
function反应的是computation 序列集合.自身调用自身, 首先满足这种 order sequence的关系.<br />
似乎称之为recursive是没问题的. 但一个只能反应sequence, or和sequence等价的”recursive”.<br />
又有多大价值呢?recursive意义又有多大呢? 究竟, process的核心是什么呢? 是computation.<br />
回答显示世界的recursive, 一个画面不断重复自身的画面!<br />
<img src="https://upload.wikimedia.org/wikipedia/commons/6/62/Droste.jpg" alt="recursion" /><br />
我们发现, 他们总是在表达一个完整的个体.<br />
画面的recursion, 依然在一个画面下.<br />
function的recursion, 确实表现在一个function内.<br />
但是从computation角度, recursive的function表述的是computation的连续sequence.<br />
也就是说recursion是有对象的,对于process是computation是对象.<br />
对于recursion process, 只有一个computation, 而iteration的process是多个computation的order/sequence集合.<br />
所以要区分computation和procedure/function. function是computation和sequence集合.他反应的是computation之间的关系.<br />
并不能反应computation自身内在关系.这也是我们混淆了recursion procedure的原因.<br />
想想, 集合的复合还是computation sequence. 而computation自身的复合却是一个computation,自身的演变.<br />
让我们体悟到了function和computation的区别.不同对象的交互operation差异.<br />
对函数的讨论研究等价与, 讨论computation之间的关系.也就是把function全部替换成了computation.<br />
所以recursive function就成了不断内嵌sequence computation了, 递归全无.<br />
computation 内在的组合, 我们讨论了, 相似对象/function的情况.<br />
如果一个computation内部,是由不同computation组成的.就是非递归的情况,edp叫Conglomeration.合理<br />
computation内在讨论先停下.<br />
我们关注computations之间的关系.<br />
无论是computation的内部还是,computation之间data都成了纽带.<br />
我们只讨论具有relation的process/computation.<br />
如果通过共同的操作的data,<br />
这就是并发的问题, 也就是changes.<br />
如果共同的data, 不是作为操作的对象知识表达一个relation.<br />
这是能想到的通过data的processes/computations之间的交互.<br />
似乎量changes/computation/process 之间的relation, 只能是<br />
causality and synchronization?(FIXME).<br />
Causality: Observer(发起者主动, 结果者被动), polling(结果者主动)<br />
state pattern(发起者的状态), Strategy Pattern(根据对象的选择行为)<br />
Command Pattern(?decoupling, 貌似就是个Observer不过把状态给了接收者处理),<br />
Mediator Pattern(decoupling),<br />
design pattern 关注的是form, syntax.<br />
研究process/procedure/function/computation 到 data<br />
Simple Factory Pattern类似strategy pattern, 根据(接收者类型产生对象)<br />
Factory Method Pattern类似(Mediator pattern, 将对象生成放给子类)<br />
没有relation(or relationless)的process联系到一起.<br />
adapter pattern<br />
还有一种两个procedure concurrent, 要分开 order sequence化.<br />
concurrent是design pattern等价的.<br />
这样design pattern也融合进来了.<br />
下面应该是SICP的chapter 3. chapter 3依然是对process的form的阐释和补全, 结合pl的语义进行挖掘.<br />
另一方面结合具体的实现开始kernel相关的(可能涉及到hard ware), 分布式系统理解.<br />
还有一个link load interpreter这方面的工作.</p>
<h1 id="programming:067ec0f34de866d1b35db70204ef4b7d">programming</h1>
<p>Abstraction is vital in helping us to cope with the complexity of<br />
large systems.<br />
Effective program synthesis also requires organizational principles that<br />
can guide us in formulating the overall design of a program.<br />
orgnizational principles应该是architecture pattern.<br />
我理解的programming的核心应该是modeling, modeling最直接的体现就是architecture pattern.<br />
相较于design pattern, ap更注重整体?<br />
不对, 这块不能把ap直接加进来, 逻辑不严密, 不完整.就先叫op吧.<br />
why modular,we are not creating something.<br />
It’s just about the being.<br />
abstraction is vital in helping us to cope with the complexity of<br />
large systems. 通过抽象构造的material层级, 逐级清晰.<br />
世界以我们所认为的那样方式运行着.<br />
modular , that is, so that they can be divided “naturally” into co-<br />
herent parts that can be separately developed and maintained.<br />
I think it’s because of the form.<br />
model as modeled, action in local.<br />
object-based approach and the stream-processing approach<br />
objec is the form of this world. what about stream?</p>
<p>The difficulties of dealing with objects, change, and identity are a fundamental<br />
consequence of the need to grapple with time in our computational models.<br />
Concurrent 增加了更多的难度, 但只是double的关系不是quality上的.</p>
<p>The stream approach can be most<br />
fully exploited when we decouple simulated time in our model from the<br />
order of the events that take place in the computer during evaluation.<br />
We will accomplish this using a technique known as delayed evaluation .<br />
stream 解耦了我模拟的时间和event的order.event有orderbut no time.<br />
We don’t care time. 隐约中我们引入了另一个origin of world, time.<br />
我想还是需要关心时间的只是在stream的form里面不存在时间了.<br />
leak of causal is abstraction.<br />
second origin, state, An object is said to “have<br />
state” if its behavior is influenced by its history.<br />
We can characterize an object’s state by one or more state vari-<br />
ables.<br />
有很多objects, 一些objects可能影响others’s state, couple the state variables.<br />
modular 需要decomposed into computational objects modeling actual objects.<br />
model指整体如substitution 和environment.<br />
Each computational object must have its own lo-<br />
cal state variables describing the actual object’s state.<br />
我们用computational object model actual, 每个 computational object must have its own local state variales.<br />
local state variables 描述actual object’s state. why local?</p>
<p>If we choose to model the flow of time in the system by the elapsed time<br />
in the computer, then we must have a way to construct computational<br />
objects whose behaviors change as our programs run. In particular, if<br />
we wish to model state variables by ordinary symbolic names in the<br />
programming language, then the language must provide an assignment<br />
operator to enable us to change the value associated with a name.<br />
从state variables 扯到 assignment operator.<br />
因为state variables是记录actual objects的state的, state可能随时间改变.<br />
我们必须改变state variables, 就需要assignment operator.表述一个关系, change.<br />
一个对象自己的state variables 被称为 local?<br />
形参?<br />
massage passing 类似strategy pattern</p>
<p>From the point of view of one part of a complex process, the other<br />
parts appear to change with time. They have hidden time-varying local<br />
state. If we wish to write computer programs whose structure reflects<br />
this decomposition, we make computational objects (such as bank ac-<br />
counts and random-number generators) whose behavior changes with<br />
time. We model state with local state variables, and we model the changes<br />
of state with assignments to those variables.<br />
整体上, a process, one part 看另外一面是<br />
A process hide time-varying local state in modular, but with a changes behavior. encapuslation.<br />
= changes, variable states</p>
<p>In general, programming with assignment forces us to carefully consider the relative orders<br />
of the assignments to make sure that each statement is using the correct<br />
version of the variables that have been changed. is issue simply does<br />
not arise in functional programs.</p>
<p>函数调用对应的是substitution model<br />
model of evaluation<br />
environments<br />
An environment is a sequence of frames . Each frame is a table (pos-<br />
sibly empty) of bindings , which associate variable names with their cor-<br />
responding values. (A single frame may contain at most one binding<br />
for any variable.) Each frame also has a pointer to its enclosing environ-<br />
ment , unless, for the purposes of discussion, the frame is considered to<br />
be global . e value of a variable with respect to an environment is the<br />
value given by the binding of the variable in the first frame in the en-<br />
vironment that contains a binding for that variable. If no frame in the<br />
sequence specifies a binding for the variable, then the variable is said to<br />
be unbound in the environment.<br />
所以programming实际讨论的是意义的问题.不是某种形式<br />
3.4<br />
e central issue lurking beneath the complexity of state, sameness,<br />
and change is that by introducing assignment we are forced to admit<br />
time into our computational models. Before we introduced assignment,<br />
all our programs were timeless, in the sense that any expression that<br />
has a value always has the same value.<br />
so time is changing.<br />
the execution of assignment<br />
statements delineates<br />
moments in time when values change. e result of evaluating an ex-<br />
pression depends not only on the expression itself, but also on whether<br />
the evaluation occurs before or aer these moments. Building models<br />
in terms of computational objects with local state forces us to confront<br />
time as an essential concept in programming.<br />
we use assignmnet to record state/history.<br />
We implemented the time variation of the states of the model objects in the computer<br />
with assignments to the local variables of the model objects.<br />
必须意识到change被modeled 到assignment.<br />
model change in terms of sequences<br />
list sequence is inefficient than the standard iterative style.<br />
Streams are a clever idea that allows one to use sequence manipu-<br />
lations without incurring the costs of manipulating sequences as lists.<br />
With streams we can achieve the best of both worlds: We can formu-<br />
late programs elegantly as sequence manipulations, while aaining the<br />
efficiency of incremental computation.<br />
stream 比list好,elegantly as sequence manipulation, efficiency as incremental computation.<br />
(delay ⟨ exp ⟩ ) delayed object很有趣, 类似Brandon的enhanced greensight.连接是空, 穿越时空.</p>
<h1 id="chapter-4-metalinguistic-abstraction:067ec0f34de866d1b35db70204ef4b7d">Chapter 4 Metalinguistic abstraction</h1>
<p>It is no exaggeration to regard this as the most fundamental idea in<br />
programming:<br />
e evaluator, which determines the meaning of expres-<br />
sions in a programming language, is just another program.</p>
<p>SICP, 暂时看到这里.<br />
programming 是modeling. 看了sicp差不多了.<br />
interpreter:<br />
EOPL<br />
PLAI<br />
<a href="http://papl.cs.brown.edu/2016/">http://papl.cs.brown.edu/2016/</a><br />
另外PL也到这里吧.<br />
source code写出来如何让run?<br />
<a href="https://www.zhihu.com/question/19918532">弱类型、强类型、动态类型、静态类型语言的区别是什么?</a><br />
c语言是弱类型语言的意思是:它的类型是给编译器看的,让编译器在初次分配内存的时候好分配一个指定大小的空间。在实际操作中你可以随意更改变量的类型(强制或自动)。<br />
c语言实际是对内存直接操作的一门语言。也就是说如果给你四个字节的内存,你喜欢把它当成int来操作也行,当成四个char操作也行,随你喜欢。<br />
<a href="http://stackoverflow.com/questions/430182/is-c-strongly-typed">Is C strongly typed?</a><br />
I spent a few weeks, about a year ago, trying to sort out the terminology of “strongly typed,” “statically typed,” “safe,” etc., and found it amazingly difficult. As your message points out, the usage of these terms is so various as to render them almost useless. –Benjamin C. Pierce</p>
<h1 id="program-execution:067ec0f34de866d1b35db70204ef4b7d">program execution</h1>
<p>run的目的是source code 对应到ISA.<br />
最容易想到的就是compilation.<br />
我们把compilation和interpreter当成从source code 到runnable program之间的某种form的变化.<br />
先略过compilation, 也就是我们现在编译出了最简单形式的一个程序foo 输出hello world用到了一个新lib.<br />
<a href="https://lwn.net/Articles/631631/">How programs get run: ELF binaries</a><br />
我们知道了个大概, 那么我们最关心的事, 现在lib和foo都进入内存了, 那么foo是如何调用到lib的函数.<br />
原来是直接利用address_space 最memory map private就共享了.<br />
不需要显示维护library的list列表的.<br />
这样程序就运行起来了.<br />
硬件可以理解为programs的的interpreter. 理解为model of computations, 由set of changs and state/quantaties and relations 组成.<br />
所以硬件也可以看成是抽象的! 只不过不能自动.<br />
研究memory的是时候我们会区分到RAM和SRAM到电容和logic gates.也就是最终的实现.<br />
这个时候, 我们发现material成了我们理解问题的所必须考虑的方面了.<br />
也就是说理解到了电路这个层次, 我们就完成了standalone, Completeness的.<br />
也就是hardware的material完成了我们的认知, 就是认知闭环了.<br />
所以已经关注很多cpu的和process运行相关的指令, 对于理解lock锁(包括所谓的lockfree无锁)理解到硬件的material也是应该的.<br />
为什么这么说? 如果不用关心到logic完整的material, 实际上我们不需要理解什么语言啊, computation model. 设计模式啊, 操作系统啊.<br />
只要脑子想就够了.可是material也是being存在.也是有form的存在.<br />
所以另外的, 很重要的就是, 我们不是理解hardware本身, 我们理解的是hardware背后的form!<br />
form的内容就很少了.所以说学习要特别注意两点, form和completeness.<br />
记住我们关心的不是hardware的material而是hardware的form.<br />
所以说我们是为了完整complete form而不是material.<br />
而实际上, 当我意识到所谓的form的存在的时候, hardware本身就成一种自然的延伸了.自然的被包括进学习的范围目标里面了(FIXME).</p>
<h1 id="os:067ec0f34de866d1b35db70204ef4b7d">os</h1>
<p>所以下面的os, 从一个整体的角度去看待computer, 实质善顺道把os相关, 有助于os理解的hardware的知识<br />
也包含进来. 下面的思考包含常见的GNU Linux/Unix/Windows这些系统, 和distribute system.<br />
在更general 的form下思考他们的form.<br />
我们似乎根本就不在乎是否有hardware参与进来, 我们关注的只是form. 如果form本身是完整的. hardware是不需要的.<br />
为什么hardware对我们是不需要的, 因为我们所构建的cs的真正基础是纯粹逻辑的(FIXME), 可能有部分内容依赖物理如晶振, 电路的delta时间.<br />
所以说, 我几乎不需要hardware.<br />
开始分析os, os包括userspace, application. 睡觉.<br />
from this <a href="https://www.bowdoin.edu/~sbarker/teaching/courses/spring14/slides/lec03.pdf">ppt Last Class: OS and Computer Architecture</a><br />
we know<br />
| OS Service | Hardware Support |<br />
| Protection | Kernel/user mode, protected instructions, base/limit registers |<br />
|————-|————————————-|<br />
| Interrupts | Interrupt vectors |<br />
| System calls | Trap instructions and trap vectors |<br />
| I/O | Interrupts and memory mapping |<br />
| Scheduling, error recovery,accounting | Timer |<br />
| Synchronization | Atomic instructions |<br />
| Virtual memory | Translation look-aside buffers |</p>
<h1 id="architecture-of-cs:067ec0f34de866d1b35db70204ef4b7d">architecture of cs</h1>
<p>Algorithm, TOC, Design Pattern, SICP, Logic, Mathematics<br />
Programming: language, coding style<br />
Compile, link, and load or interpret:<br />
OS<br />
Arch</p>
<ul>
<li><p>Top method<br />
Abstruction<br />
Combination<br />
Virtualization<br />
Exchange time and space<br />
Isolation/Modular</p></li>
<li><p>Top goal<br />
Easy to use<br />
Efficiency<br />
Protection<br />
Reliability<br />
Security<br />
Energy-efficiency</p></li>
</ul>
<h1 id="programming-1:067ec0f34de866d1b35db70204ef4b7d">Programming</h1>
<p>Programming langueage: c, python, shell<br />
Programming tools: vim<br />
Compile Link: ELF<br />
Testing<br />
Debuging<br />
Interface</p>
<h1 id="os-1:067ec0f34de866d1b35db70204ef4b7d">OS</h1>
<p>Batch processing -> Time-sharing<br />
Overlaying<br />
* vm<br />
There are some great historical papers and books we should read before fully understanding virtual memory.<br />
<a href="http://research.microsoft.com/en-us/um/people/gbell/CGB%20Files/Computer%20Structures%20Readings%20and%20Examples%201971.pdf">Computer Structures: Readings and Examples </a><br />
<a href="http://research.microsoft.com/en-us/um/people/gbell/Computer_Structures_Principles_and_Examples/contents.html">Computer Structures: Readings and Examples html version</a><br />
Chapter 10 One-level storage system is the first implemention of virtual memory mind.</p>
<h2 id="process-management:067ec0f34de866d1b35db70204ef4b7d">Process management</h2>
<p>进程的定义和PCB,进程和线程的区别,进程的三个基本状态及它们之间的转换关系,进程的同步,竞争和死锁,进程间通信<br />
###Representation<br />
* Program memory<br />
Stack(User/Kernel)<br />
Heap<br />
Data segment(data/bss)<br />
Code segment<br />
* PCB<br />
Resource<br />
Processor Context<br />
Process state<br />
###daemonize<br />
<a href="http://fixunix.com/unix/84640-daemon-controlling-terminal.html">http://fixunix.com/unix/84640-daemon-controlling-terminal.html</a></p>
<h2 id="memory-managerment:067ec0f34de866d1b35db70204ef4b7d">Memory managerment</h2>
<p>分页式管理,分段式管理,虚拟内存的概念,页面置换算法,内存分配算法</p>
<h3 id="paging:067ec0f34de866d1b35db70204ef4b7d">Paging</h3>
<p>paging is one of the memory management schemes by which<br />
a computer stores and retrieves data from the secondary storage for use in main memory.<br />
* Page fault<br />
###Page replacement algorithm<br />
OPT<br />
FIFO<br />
Second-chance<br />
LRU</p>
<h3 id="x86-memory-segmentation:067ec0f34de866d1b35db70204ef4b7d">x86 memory segmentation</h3>
<p>linux 基本不用<br />
<a href="http://oss.org.cn/kernel-book/ch02/2.3.7.htm">Linux中的段</a><br />
* GDT<br />
* TSS<br />
<a href="https://en.wikipedia.org/wiki/Task_state_segment#Use_of_TSS_in_Linux">Use of TSS in Linux</a><br />
* Linear address</p>
<h3 id="virtual-memory-https-en-wikipedia-org-wiki-virtual-memory-paged-virtual-memory:067ec0f34de866d1b35db70204ef4b7d"><a href="https://en.wikipedia.org/wiki/Virtual_memory#Paged_virtual_memory">Virtual memory</a></h3>
<p>It maps memory addresses used by a program, called virtual addresses, into physical addresses in computer memory.<br />
* Logic/Virtual address<br />
* Page table</p>
<h3 id="memory-allocation:067ec0f34de866d1b35db70204ef4b7d">Memory allocation</h3>
<ul>
<li>Buddy memory allocation.<br /></li>
<li><p>Slab allocation/Memory Pool</p>
<h2 id="device-management:067ec0f34de866d1b35db70204ef4b7d">Device management</h2>
<p>中断的概念,中断处理,I/O控制方式,缓冲区管理,设备驱动,磁盘调度和高速缓存</p>
<h2 id="network-stack:067ec0f34de866d1b35db70204ef4b7d">Network stack</h2>
<p>Protocol</p>
<h2 id="i-o:067ec0f34de866d1b35db70204ef4b7d">I/O</h2>
<p><a href="http://www.cs.uwm.edu/classes/cs458/Lecture/HTML/ch11s02.html">Methods for designing a CPU’s I/O interface generally fall into one of the following categories:</a><br />
Completely separate memory and I/O. buses DMA?<br />
Common buses, separate control lines. Port-I/O<br />
Common buses and control line. Memroy-maped I/O<br />
###Higher level implemention of I/O<br />
device or partion of device/memory -> file<br />
io -> stream<br />
####<a href="https://en.wikipedia.org/wiki/Stream_(computing">stream</a>)</p></li>
<li><p><a href="https://en.wikipedia.org/wiki/Standard_streams">Standard streams</a><br />
interface is stdio library or the kernel version.</p></li>
<li><p>codata</p>
<h3 id="low-i-o-type:067ec0f34de866d1b35db70204ef4b7d">Low I/O type</h3></li>
<li><p>Programmed I/O/Polling</p></li>
<li><p>DMA</p></li>
<li><p>Interrupt I/O</p></li>
<li><p>Channel I/O</p>
<h3 id="i-o-scheduling:067ec0f34de866d1b35db70204ef4b7d">I/O scheduling</h3>
<p>Elevator algorithm<br />
###Asynchronous I/O NEED CLEAN</p></li>
<li><p>synchronous I/O multiplexing and I/O event notification facility<br />
select/poll/epoll<br />
For the ease of use, the select loop is implemented as an <em>event loop</em> with callbacks.<br />
libevent and libev is a well-designed <em>event loop</em>.Check shadowsocks for using of libev.</p>
<h2 id="file-system:067ec0f34de866d1b35db70204ef4b7d">File system</h2>
<p>文件的概念,文件的管理,文件系统</p>
<h2 id="system-calls:067ec0f34de866d1b35db70204ef4b7d">System calls</h2>
<p>系统调用的概念,系统调用的处理,系统调用类型<br />
##CPU-device I/O</p>
<h3 id="memory-mapped-i-o:067ec0f34de866d1b35db70204ef4b7d">Memory-mapped I/O</h3>
<p>ioremap: physical address->logical address, simlar to vmalloc except we need not page.</p>
<h3 id="ported-mapped-i-o:067ec0f34de866d1b35db70204ef4b7d">Ported-mapped I/O</h3>
<p>##Non CPU-device I/O</p>
<h3 id="i-o-channels:067ec0f34de866d1b35db70204ef4b7d">I/O channels</h3>
<h2 id="同步与异步io:067ec0f34de866d1b35db70204ef4b7d">同步与异步IO</h2>
<p>今天我们要辨析一下同步和异步IO. 我们先解释最基础的概念, 之后用生活化的例子<br />
完成认知.<br />
首先是blocking 和 non-blocking这两个概念. 这两个概念实质上是和IO没有关系.<br />
他们是在说, 比如读数据, 如果没有数据我该怎么办. 也就是说, 他是在IO不存的时候,<br />
在语义上才是有效, 如果你要读的数据始终存在, 那么你还会考虑阻塞与不阻塞的问题吗?<br />
那你应该考虑什么? 同步还是异步IO, 倒地什么是同步或者异步呢?<br />
英文synchronous, syn 和chronous构成, syn是在一起的意思而chronous是时间的意思.<br />
也就是说在一个时间点上在一起, 那么是谁和谁在意一起呢?其中一个是IO可以肯定, 另外一个<br />
就是执行IO的发起者, 通常也就是进程. 简单说来这个IO是由进程执行的.<br />
那么异步IO呢, asynchronous是a + synchronous. a表否定, 我们知道在IO进行的过程中我们的<br />
进程是始终存在的, 也就是说IO 和进程共享着相同的时间进度, 但是却不在一起.也就是说,<br />
IO不是由我们的进程完成而是别的进程完成, 是谁呢,是内核线程.<br />
那么我们就知道只有linux上的aio是符合异步IO的标准, 而多路复用, 如epoll返回是我们和IO是在<br />
一起, 我们要调用read之类的完成他.</p>
<h1 id="physical-computation-phenomenon:067ec0f34de866d1b35db70204ef4b7d">Physical computation phenomenon</h1>
<p>A Symbolic Analysis of Relay and Switching Circuits<br />
The Mathematical Theory of Communication<br />
Given a symbol level, the architecture is the description of the system in<br />
whatever system-description scheme exists next below the symbol level. - Newell, 1990, p. 81<br />
<a href="https://news.ycombinator.com/item?id=9844090">Ask HN: How to learn about the history of computing?</a></p></li>
<li><p>Control<br />
Cogwheel control<br />
electromechanical magnet plugging control<br />
control sequence points</p></li>
</ul>
<h1 id="faq:067ec0f34de866d1b35db70204ef4b7d">Faq</h1>
<ul>
<li>How does gcc attribute((aligned)) work?<br />
struct S1 { short f; short f1; short f2;char a; char c;} <strong>attribute</strong> ((aligned ));<br />
sizeof S1 = 16 in 64-bit<br /></li>
<li>In what situation can unaligned accesss make a kernel panic?<br />
may be arch/mips/kernel/unaligned.c<br /></li>
<li>Is the address generated by compiler physical or virtual?<br />
Graphviz + CodeViz<br /></li>
</ul>
</article>
</div>
</section>
<aside id=comments>
<div><h2> Comments </h2></div>
<div id="disqus_thread"></div>
<script type="text/javascript">
var disqus_shortname = 'firoyang';
var disqus_identifier = 'http:\/\/firoyang.org\/cs\/cs\/';
var disqus_title = 'Computer science a kernel programmer\x27s perspective';
var disqus_url = 'http:\/\/firoyang.org\/cs\/cs\/';
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
</aside>
<footer>
<div>
<p>
© 2014 ~ 2016 <span itemprop="author" itemscope itemtype="http://schema.org/Person">
<span itemprop="name">Firo Yang </span></span><a href="http://creativecommons.org/licenses/by/4.0/">Some rights reserved</a>.
Powered by <a href="http://gohugo.io">Hugo</a> and <a href="https://fortawesome.github.io/Font-Awesome/">Font Awesome</a>.
Theme by <a href="http://spf13.com">Steve Francia <a href="http://firoyang.org">Firo Yang</a>.
</p>
</div>
</footer>
<script type="text/javascript">
(function(){var j=function(a,b){return window.getComputedStyle?getComputedStyle(a).getPropertyValue(b):a.currentStyle[b]};var k=function(a,b,c){if(a.addEventListener)a.addEventListener(b,c,false);else a.attachEvent('on'+b,c)};var l=function(a,b){for(key in b)if(b.hasOwnProperty(key))a[key]=b[key];return a};window.fitText=function(d,e,f){var g=l({'minFontSize':-1/0,'maxFontSize':1/0},f);var h=function(a){var b=e||1;var c=function(){a.style.fontSize=Math.max(Math.min(a.clientWidth/(b*10),parseFloat(g.maxFontSize)),parseFloat(g.minFontSize))+'px'};c();k(window,'resize',c)};if(d.length)for(var i=0;i<d.length;i++)h(d[i]);else h(d);return d}})();
fitText(document.getElementById('title'), 1)
</script>
</body>
</html>
<script type="text/javascript"
src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [['$','$'], ['\\(','\\)']],
displayMath: [['$$','$$'], ['\[','\]']],
processEscapes: true,
processEnvironments: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre'],
TeX: { equationNumbers: { autoNumber: "AMS" },
extensions: ["AMSmath.js", "AMSsymbols.js"] }
}
});
</script>
</body>