深入理解计算机系统（Computer Systems: A Programmer's Perspective）
学习资料：
https://www.bilibili.com/video/BV1iW411d7hd （字幕）
https://www.bilibili.com/video/BV1a54y1k7YE （无字幕）
深入理解计算机系统书籍pdf : 链接: https://pan.baidu.com/s/1zWGfoxn0os0s9B3A2joM0Q 提取码: t4uc
豆瓣9.5分的书籍，这是一本"入门"级别的书，覆盖面很广，从计算机的基本组成，二进制数据表示方式，到机器级别的指令，CPU工作方式，存储结构和优化，操作系统的虚拟内存管理，程序运行方式，I/O，网络、到程序性能优化和并行程序开发等，实验部分设计的也很精彩。 本视频对应于该书第3版，是原作者Randal E.Bryant的授课内容。 课件下载: https://pan.baidu.com/s/1ZKz5kYs4c1aWdmosEOx0bw 提取码：ru0t
Lecture01 Bits,Bytes,Integers：
这个课程涉及的都是x86-64位机器
位运算：
一个应用（表示集合）：
位移操作：
左移的时候，只是用0填充，
右移分为 逻辑右移和算术右移，其中的算术右移填充是用最高位进行填充的！
有符号整数：
例：
这里假定w=4（4位）,
机器中能表示的所有情况：
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 总共有16中表示方法，
第一种方法（补码）：B2T（现代计算机都是使用这种编码方式表示有符号整数）
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0 1 2 3 4 5 6 7 -8 -7 -6 -5 -4 -3 -2 -1
第二种方法（反码）：B2O
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
+0 1 2 3 4 5 6 7 -7 -6 -5 -4 -3 -2 -1 -0
第三种方法（原码）：B2S
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
+0 1 2 3 4 5 6 7 -0 -1 -2 -3 -4 -5 -6 -7
参考：
有符号数的扩展，在不改变值的情况下扩展比特：
基本的规则是：将符号位复制到左侧来完成，
例如：
0110 -> 0 0110 ，它都是代表6
1110 -> 1 1110 , 它都是代表-2
截断
加法：
例如： w=4 ,
1101 + 0101 = 1 0010
13 5 18%16 = 2
乘法：
除法的右移
求相反数
将所有的比特反转 然后再加1
整数运算总结：
为什么仍要使用无符号整数
无符号整数容易产生的问题：
既然无符号整数和有符号整数这么复杂，那么我们为什么还使用无符号整数，不应该去掉无符号整数吗（Python,Java就只有有符号整数）？
计算机的字长：
Byte Ordering ：
Lecture02 Floating Point：
w = 1 -> 8 所能表示的小数：
import matplotlib.pyplot as plt import copy def PowerSetsRecursive(items): # the power set of the empty set has one element, the empty set result = [[]] for x in items: result.extend([subset + [x] for subset in result]) return result input_arrs = [] temp_arr = [] for i in range(1, 9): temp_arr.append(i) input_arrs.append(copy.deepcopy(temp_arr)) w = 1 for input_arr in input_arrs: subsets = PowerSetsRecursive(input_arr) datas = [0, ] # 要绘制的数据 for arr in subsets: if not arr: continue s = 0 for i in arr: s += (1 / 2) ** i datas.append(s) # 对 datas 排序 datas = sorted(datas) # 绘制datas ids = [] # 横坐标 for i in range(len(datas)): ids.append(i) #print(ids) #print(datas) plt.scatter(ids,datas) plt.title(f"w={w}") plt.savefig(f"w={w}") #plt.show() w += 1
上述表示方法的局限：
它只能表示 形如 ： 这样的小数，
其他的小数只能近似的表示，
例如，1/5 的表示，
用二进制表示，也有一些是循环的，就像10进制中的1/3 表示为0.3333333 [3]
具体计算过程如下：
IEEE 浮点表示：
IEEE 浮点标准使用如下形式来表示一个数：
Note: Most Significant Bit，在二进制数中属于最高有效位，MSB是最高加权位，与十进制数字中最左边的一位类似。
三种浮点数的格式：（前两种，C中的float 和 C中的double ）
01 Normalized 值：
关于范围：
容易知Exp 域 的范围是 [0,255] 0000 0000 -> 1111 1111
又知，Bias = 127,即 0111 1111
所以，实际的E 的范围是 [-127,128]
总结：
frac域 就是 [1,2) 的小数，具体是 1.xxx...x （2进制），注：1.xxx...x的1 是隐含编码（默认就有了1，就不用再占用一个位置了）！
exp域 是unsigned val ，需要E 额外 加上Bias（偏移），这里可以思考个问题，为什么不用补码来表示exp域？，为了更好的做比较
s 域 是0 或 1
※关于为什么不用补码来表示exp域？
It's just another way of doing negative numbers, instead of two's complement. There's no reason for 0 to actually be represented by zeroes.
There are 8 bits of exponent so 127 gives roughly the same positive and negative range.
02 Denormalized 值：
因为使用第一种normalized values 要求M [1,2) ，所以就无法表示0。所以就有了第二种 Denormalized Values。
它的特征是 exp域全为0 ，它的frac 中没有隐含1， 所以frac 的编码和M完全等价，
为什么要用 Denormalized 来表示接近0的浮点数，用范围 换精度 ！
Special 值：
总结：
例子：
假设一个浮点数exp 是4个bits,frac 是3个bits
画图来表示：
假设exp 3bit ,frac 2 bit
完整范围：
-1 ~ 1 附近的视图放大后如下：
IEEE Encoding 的特殊性质：
- 浮点0 被编码为了整数0
- All bits = 0
- 除了NaN之外，可以比较所有的浮点数，具体方法是通过将其视为无符号的整数
- Must first compare sign bits （必须首先比较最高位）
- Must consider -0 = 0 （必须考虑 -0 = 0 ）
舍入：
IEEE 有四种舍入模式：
最后一种模式是：4舍6入，5取偶
二进制数字的舍入：
浮点数乘法：
两个符号位的操作就是异或的操作，可见只有相同的时候，异或才是1 ，不一样就是0 。
两个浮点数相加：
浮点数乘法可以交换，但不具有结合性，
浮点数加法可以交换，但不具有结合性，经常发生在一个很大的数字和一个很小数字的操作上，例如3.14 和 2^10 的操作，
总结： 浮点数是不满足结合律的， 而且一般是发生在两个相差很大的数字之间的情况，所以作为程序员一定要明白数字的变化范围，重新结合或改变运算的顺序结果可能是不相同的。
现在有两种浮点数，有IEEE单精度和IEEE双精度浮点数。
Lecture03 Machine-Level Programming 01:Basics
History of Intel processors and architectures
Intel 系列的处理器俗称 x86 。 这是因为它的第一个芯片被称为8086。
然后跳过了8186，随后推出了8286，8386。
x86有时候又被称作CISC （Complex instruction set computer）。【在80年代早期有件大事，80年代又被称作RISC 和 CISC大战的年代，RISC是精简指令集计算机】
4核心芯片的构成：
8核处理器
顺便提一句的是除了 x86结构，还有ARM ，它们是两个主要的两种设计。
总结：
Intel公司，AMD公司 都是使用x86结构，
ARM 实际是 Acorn RISC Machine ，Acorn 早期是一家公司，它们在早期决定制造自己的个人电脑，它们不打算从Intel购买芯片，最后它破产了，但是它们提出了一个相当不错的指令集（Advanced RISC），非常高效简单。现在ARM是一家总部位于剑桥的公司，它出售设计而不是芯片。
C,assembly,machine code
Assembly Basic:Registers,operands,move
16个寄存器，可以用来保存整数和指针。%r 代表的是64位， %e代表的是32位。
movq 指令
q of movq is quad ,意思是4个字节，64位。
注： 出于 对硬件设计者的方便，不允许从Mem 复制到 Mem, 而且Imm （立即数）也不能作为Dest。
这个例子展示了非常简单的内存引用，
关于why S is 1,2,4,8, 因为如果这是一个数组索引，必须通过数据类型的字节数来缩放索引值，如果它是一个int,就必须缩放4倍，如果是long，就缩放8倍，这也是它们存在的原因。
上面是 汇编代码中内存引用的基本格式，如果不使用某些字段，可以删除其中的一些字段，如下：
Arithmetic & logical operations
lea 指令：
这里是将 3*%rdi 存储到 %rax 中，然后再讲%rax 左移2位，这也是lea 和 mov 的区别，lea 是不使用内存引用！
总之一句话，lea without memory reference, lea 常用于 整数和地址的运算~
这种做法比直接乘12 会好，因为乘法运算会很慢，
注：这里Src在前，Dest在后，
一个例子：
lea 的两种用法（其实是一种）：
01 Computing arithmetic expressions of the form x + k*y
#include01_arthimetic.clong m12(long x){ return x*12; } int main(){ return 0; }
02 Computing addresses
#include02_compute_address.clong* compute_address01(long* arr){ long *p = &arr[0]; return p; } long* compute_address02(long* arr){ long *p = &arr[1]; return p; } long* compute_address03(long* arr){ long *p = &arr[2]; return p; } int main() { long arr[] = {0,0,0,0,0}; compute_address01(arr); compute_address02(arr); compute_address03(arr); return 0; }
使用 gcc xxx.c -Og -S 就可以产生对应的 xxx.s 的汇编代码了。
Lecture04 Machine-Level Programming 02:Control
现在有几个问题，
寄存器（Reg） 是 内存（Mem） 的一部分？ No,
寄存器（Reg） 是缓存（Cache） 的一部分？ No,
寄存器是CPU内部用来存放数据的一些小型存储区域 。
本节主要是表述 如何控制机器级别指令的执行顺序，以及如何使用这些技术来实现基本的条件语句，循环和switch 语句 等。
Control: Condition codes
有一些指令，它们唯一的作用就是设置条件码，
这里需要提醒的是，在机器级编码中的参数顺序通常与高级语言中的顺序相反，例如：cmpq Src2,Src1, 我们在高级语言中一般是 cmp Src1,Src2。
test 指令的唯一目的也是设置条件标志，
movzbl 指令，是从%al 扩展到 %eax ，eax 虽然是只有32位，但是在x86的世界里，如果对低32位做了操作，那么也相当于对高32位做了操作，
Conditional branches
由于条件分支的汇编代码 和 C的goto 语句 很类似，由因为汇编代码可读性较差，所以下面都是用goto 形式来表述 条件分支的汇编代码。 注：（C中不建议使用goto语句）
为什么不能一直使用Conditional Move?
1,进行两种情况的计算可能是一个非常非常糟糕的主意，
2，有时候确实不能这样做，例如要保证p非空指针，
3， 执行程序会影响其他分支的结果 ，例如第三种情况
Loops
两种方式，生成While 循环的汇编代码：
第三种循环时for 循环：
Switch Statements
switch 语句的汇编形式，
switch 的简单用法：
我们知道可以用if-else 代替 switch,所以，你可能觉得switch 的汇编代码也是 if-else 类似的汇编代码，实际上不是的！
注： ja : Jump above ,这里使用ja 而不是使用jg（jump greater），是因为如果x是负数，进行无符号的比较也会变为很大的正数。 总之，如果x 大于6，或者小于0都会直接跳到 default！
问题：
如果x是负数，通常会加上一个偏置Bias 变为正数
如果只有两个case ,case 0 和 case 10000 ,难道要建立 10000个项的表吗？ 的确是的，所以编译器会优化成为if-else 的汇编代码形式，
虽然有时switch用到不多，但是有时候也是可以带来性能的提升，因为switch表是O(1) 的时间复杂度，if-else 是线性的复杂度O(n） ，
而且，如果case是稀疏的话，它会设置一个条件树，进行二分搜索，可以达到时间复杂度为： O(logn)的级别。
不管哪种都是优于if -else 的，
总结：
基本上有三个条件控制，
1，使用条件跳转到代码的不同位置
2，是使用Condition moves (先把所有情况都计算出来，再决定跳到哪个)
3, 是使用Jump table
Lecture05 Machine-Level Programming 03:Procedures（过程）
一个Procedure(P) 调用另一个Procedure (Q) ,
Stack Structure
一个很关键的问题， how do we pass control to a function ?
说这个之前，我们必须要提到 Stack（栈），它不是什么special memory ,it's just a region of the normal memory. 正如之前说的那样，对于汇编层面的程序员而言，内存只是一个巨大的字节数组。
在这个巨大的数组的某个地方，我们将其称为栈。
程序用 栈 来管理 过程调用 和 过程返回 的状态。
在栈中，程序传递 潜在信息，控制信息和数据，并分配本地数据。
之所以用栈来 管理 过程调用和过程返回， 是因为栈的 后进先出 和 调用和返回 思想十分一致 !
在 x86-64 Stack 中，栈从一个很高的地址开始， 栈Grow 通过递减栈指针操作 来完成。
栈指针是当前栈顶部的地址，它存储在 %rsp 中，
具体来说，有push 和 pop 两种指令来对栈进行操作，
这就是栈的思想，
Calling Conventions （Calling 规范）
主要三部分： control ， passing data, managing local data
我们将栈的思想用在了 call 和 return 上，
1 Passing control
之所以用反汇编代码是因为它有地址，容易看
Procedure Control Flow:
要调用一个函数，只需要 call 这个函数的标签，
需要返回的时候，只需要调用 ret 指令，
请记住： 这两个指令并没有完成 过程调用和 过程返回 的 全部任务！ 它只是完成了 Procedure Contorl 的部分， 这只是 Procedure的三分之一 !
假设我们的栈顶元素在0x120（注，现实中是不可能的事情）
%rip 表示当前指令的地址位于 0x400544 , 即 call 指令，
那么这个call 指令会发生什么事情呢？
1，它会减少栈指针（120 -> 118 十六进制）
2，它会将 接下来（下一行）调用的指令地址（400549） 写入栈顶
3，它会%rip 变为400550。（其实是一个 push 和 一个jump 指令 ）如下：
继续，此时%rip 是400550 ， 它一直执行到400557, 如下图：
注： retq 和 rep 是相同的指令
ret 指令的目的是逆转 call 的效果， 所以ret 如下两件事：
1，它会%rip 变为当前栈顶 400549。
2，它会增加栈指针（118 -> 120 十六进制）。值并并没有从内存中消失，只是移动了一下指针，不再视之为栈的一部分了。 如下：
我们从中能感受到call 的时候，push 下一个指令的明智之举，它为ret 恢复做了前期准备。
2 Passing data
前面我们知道使用了一些寄存器来传递函数的参数，
例如这里的反汇编代码中的寄存器%rax 就是用于函数的返回值的，
ABI（Application Binary Interface）【A common aspect of an ABI is the calling convention, which determines how data is provided as input to, or read as output from, computational routines. Examples of this are the x86 calling conventions.】
这些规则要求要求前六个参数要通过指定的寄存器来传递，如下图：(注： IA-32 Intel Architecture 32-bit 时期，所有的参数都是在栈中传递)
如果函数的参数超过了6个，它会放在栈内存上
注：这里的参数要求是整型或者是指针类型。 对于浮点类型的参数是由另外一组单独的寄存器来传递的！
3 Managing local data
每当我们调用一个函数，入栈就行了，一直这样...,
我们把栈上用于特定call 的每个内存块，称之为 stack frame,
我们所需要的只是在栈中为每个被调用且未返回的 procedure 保留一个 frame（stack frame）。
当Caller Frame 调用下面的新Frame 时，Return Addr会被放到 Caller Frame 中，如果Caller Frame 调用新的Frame需要6个以上的参数，多余的参数也会被放到Caller Frame 中。 在我们调用的函数开始之前，所有的这些信息都已经在栈中了，
如果有一些局部状态，例如一些需要保存的寄存器 或者 要在局部分配一个新的空间 ，那么这些会被存储在 Current Stack Frame 中，
上图的红色代码，生成了两条汇编指令，它做了两件事情：
1，在栈中分配16字节的空间，即%rsp = %rsp + 16字节 。
2，在%rsp + 8 这个偏移量的地方存储常数 15213，（这里我们可以看到，编译器经常在栈上分配比实际需求还要多的空间，这里是多了8个字节，这是因为有一些约束要求内存地址保持对齐，对齐方式有很多种） 。
上图开始执行后，%rdi 会得到&v1, %rsi会被赋值3000 （注，这里是movl 不是movq, 因为3000 足够小 32bit 已经够了，所以是%esi ）。 （当一个寄存器是以 e 开头时，它的高32位会被设置为0）。
这里的 8(%rsp） 看起来是 引用，但是这里是leaq ，所以它将计算后的地址直接复制给 %rdi ，而不是像mov 等那样使用引用！
继续，会call incr, 之前已经看了 incr 是将val 加到 指针（所对应的值）上， 所以这里的实际作用是， 15213 变为了 18213，而且它也将15213 放在了%rax （返回值）！
继续执行 最后一行 return v1 + v2; 它将%rsp + 8 的值 放到了 %rax 中， 然后将%rsp 又增加了 16个字节，即出栈，释放空间返回到了原先的状态。
上图， ret 指令始终 ret 的是 %rsp, 执行完之后，rtn address 也会被释放了。
关于 寄存器 保存时的一些约定：
如上图，当yoo call who 后， %rdx寄存器还会保存15213 ?
一般的答案是NO, 因为 who 中已经使用18213 覆盖了 %rdx, 所以我们要提出一些约定（conventions），以便于寄存器保存值的时候不会被覆盖掉!
首先是一些术语：
如果想要一个寄存器的值不被覆盖掉，有如下两种途径：
1， Caller做工作：即Caller 在call 之前保存临时的值在它自己的stack frame ,
2， Callee做工作：.即Callee 在使用寄存器的值之前先保存，然后在返回Caller之前再将寄存器的值 给恢复了 ！
所以，%r10 ,%r11 也通常被用作临时存储（temporary storeage）， %rax 会被多次覆盖（返回值）。
上图：如前面stack frame 中所示，如果你使用frame pointer（它是可选的），%rbp 是很特殊的， 如果不使用的话，那么它其实是作为Callee-Saved 来使用的寄存器。 同样%rsp 也是很特别的，（一般不要乱用）
下图是 Callee-Saved 的示例：
这里的call_incr2 有一个参数x, 它会被存储在 %rdi 寄存器中， 而后面我们调用incr()的时候，又使用了寄存器%rdi， 所以为了避免覆盖，我们应该为x 做些事情，具体是Callee frame 暂时将%rdi 的值存到了 %rbx中。
上图中我们可以看到callee frame 中
1，首先将%rbx 的值 push 到了栈中（暂存%rbx 的值 ），
2，后面又将%rdi 的值 移到了 %rbx
3，将%rbx 现有的值（x）加到了 返回值 %rax 中，
4，最后又将栈顶元素pop 到%rbx中（恢复%rbx 原先的值），
这就是Callee-Saved !
ILLustration of Recursion
这个递归函数用来统计 一个无符号整数的二进制形式中1的个数，
最后恢复 %rbx 的值，
Observations About Recursion:
Summary:
Lecture06 Machine-Level Programming 04:Data
数据表示，上面所有的内容都只是操作整数和指针，
现在我们进一步介绍两种聚合数据的方式：
1，数组 Array
2，结构体Struct
我们将要看到的是它们在机器中的表现方式，主要看到的是在机器级代码里是没有数组这一高级概念的，而是将它视之为一些字节的集合（collection of bytes）。
Arrays
One-dimensional
一些基本常识：
问题：
可以用负数做为数组的下标吗？
C中没有什么东西会阻止它，它会给一个随机的垃圾数出来， C语言没有边界检查！
可以两个指针做运算吗？
No, 指针运算都是 一个指针参与运算，另一个必须是常规的整数（编译器会适当的缩放它，int 是4，char 是1），
Array Accessing Example：
Array Loop Example：
如何理解Pointers 和 Arrays:
当声明的是一个数组时，它做了两件事：1，为数组名（指针本身）分配空间，并初始化， 2 也为数组中的元素分配空间并初始化。
当声明的是一个指针时，它仅仅是为指针本身分配了空间，没有初始化。
上图中，首先A1 A2 A4 都是个数组， A3 是个指针
对于下面两个 int(*A3)[3] 和 int(*A4[3] ) 的如何读？
按优先级来读，
A3是一个指针，它指向一个int [3] 的数组
A4，要想读懂A4,首先要知道C语言中的优先级，可以知道 [ ] 的优先级 是大于 * 的，所以A4是个数组，数组中存放了3个int *
关于优先级
参考：
https://overiq.com/c-programming-101/operator-precedence-and-associativity-in-c/
Operator precedence: It dictates the order of evaluation of operators in an expression.
Associativity: It defines the order in which operators of the same precedence are evaluated in an expression. Associativity can be either from left to right or right to left.（相同优先级下使用，结合方向）
C 中的优先级：
例子：
int(*A3)[3] 和 int(*A4[3] )
C/C++ 的优先级：
Multi-dimensional(nested)
Nested Array Row Access:
Nested Array Element Access:
Nested Array Element Access Code:
Multi-level 多层引用的数组
对比：
第一种发生了一次内存引用， 第二种发生了两次内存引用，
这就很有趣，看起来两个C代码是一样的，但是它的底层汇编代码是不同的， 所以发生内存引用的次数也是不同的，
下面是三个例子：
上图是一个二维数组地址计算的例子：
C是16，K是4个字节，
上图的n 是一个传递给函数的参数，（可变数组），
它一开始不知道具体C ,所以，它必须要使用imulq 乘法（开销比较大）
Structures
Structures & Alignment：
实际上，为了保持对齐，当一个结构体被分配的时候，编译器实际上会插入一些空白不被使用的字节，
最重要的就是上面两句话：
Primitive data type requires K bytess
Address must be multiple of K
还有两句话：
For largest alignment requirement K（最大对齐要求）
Overall structure must be multiple of K （边界必须满足最大的K）
至于为什么要这样做：
这实际是个硬件问题，即内存系统，实际的硬件内存一次不取一个字节，（对于现在的大多数机器，一次取64个字节，它取决于硬件中的宽度 ）。所以，如果因为没有对齐地址，某个数据跨越了两个块的边界，这将导致硬件甚至有可能操作系统来采取一些额外的步骤来处理。
总结一句话，只是出于效率。trust me ,进行数据对齐吧！
在声明一个结构体的时候，如何节省空间？
上图中，显然第二种方式是比较节省空间的，
其实，我们先把最大的东西放在开头，再依次放更小的元素，这种贪心的算法总是有效的。
这样，我们能够最大限度的减少空间的浪费！
Note： 对齐仅仅是指原始的数据类型，不包含聚合数据类型，例如数组。
Floating Point
具体关于浮点数的要看课本了，
Summary:
Lecture07 Machine-Level Programming 05:Advanced Topics
这部分主要是关于几个重要的话题，
一个是当运行x86-64程序的时候，内存是如何组织的？
一个是关于安全漏洞相关的，即缓冲区溢出
最后会了解下 Union 这种的数据结构，
Memory Layout
在机器级编程的程序员眼中，内存就是一个大的字节数组，
正如你所了解的，x86-64 机器的地址在名义上有64位，即有2^64 个地址，但是，其实现在的64位机器会限制，只使用47位，即2^47 Byte 大概是 128TB。
但是，随着技术的进步，内存的价格会进一步的下降，47位的限制也会随着处理器的发展而进行增加，地址的范围也会越来越大。
从上图可以看出，最高地址是0000 7fff ffff ffff ，它就是 2^47 !
7 就是3 个1
F 就是4个1
所以 1个7 ，11 个F 就是47个1。就是2^47 个地址，
相关估计：
2 ^ 10 约等于 10^3
2^64 = (2^10)^6 * 2^4 约等于 16 * 10^18
2^47 = (2^10)^4 * 2^7 约等于 128 * 10^12 = 128 TB
10^12 （字节）是 TB
10^15 是 PB
10^18 是 EB
10^21 是 ZB
1024 b = 1B
1024 B = 1 K
1024 K = 1M
1024 M = 1G
1024 G = 1TB
1024 TB = 1PB （谷歌每天都会产生几个PB，谷歌的数据是以EB为单位的）
1024 PB = 1EB
继续上图，
在常用的系统上，栈的大小是8MB，（Linux系统上，可以通过 limit 指令查看）。
它意味着，如果试图去访问一个超过8MB范围的地址的时候，将会产生一个段错误（segmentation fault ）!
继续上图，
最下方的地址是存放代码的位置，它来自于可执行文件，后面学习 linking 的时候会详细介绍。
由于一些特殊的原因，这个存放可执行程序的区域被称为 text segment（文本段）。
继续上图，
看 Data 段，
Data段是用来存放程序开始时分配的数据，所以你声明的全局变量，静态变量，字符串常量都在这，
继续上图，
看 Heap 段，
堆 用来存放 通过malloc 或相关函数 申请的 变量， 这些变量在程序运行的时候会动态变化，
如果你不及时free 内存，那么heap 会一直往高地址走。
继续上图，
从 Heap 往上的地方 Shared Libraries, 它也是存放代码的地方，不过它存储的是类似于printf 和 malloc 这样的库函数，
库代码被存储在硬盘上，当程序开始执行的时候，会将它们加载到程序中，被称为动态加载（dynamic linking）。
总体来说，我们可以发现，程序运行时有时会分配低地址的空间（Stack），有时会分配高地址的空间(Heap)，
内存分配例子：
通过它们被分配的地方就可以看出它们的不同，
我们从上图可以看出，local 变量被分配到了 Stack中，
main 函数和useless 函数被分配到了 Text 中，
预定义的数组（不是通过malloc分配），被分配到了 Data中，有趣的是较小的数组在Data 的较下方，
对于Heap，类似Data，小的被分配在了Heap 较低的位置，而大的被分配到了Heap较搞的位置，（理论上说，持续的申请内存，malloc 会返回0，上下两块会相遇，两边的地址会朝着中间靠近）
通过GDB调试，可以在运行时看到反汇编代码，
看到7 和 几个 f 就知道是栈的地址，
看到很多 0 和 几个4 就知道是Text 的地方，
使用GDB调试工具去观察程序运行时的各种地址真的很有用，
GDB调试快速学习：https://u.osu.edu/cstutorials/2018/09/28/how-to-debug-c-program-using-gdb-in-6-simple-steps/
Buffer Overflow
在C程序中，如果有途径可以让外界使程序的缓冲区溢出，这将会产生安全问题， 例如上图例子中的 i 可以随意赋值，它就很容易导致缓冲区溢出！ 因此当你编写代码的时候应该考虑，我能否信任这个值， 考虑它是否会在我们预期的范围内，
在用户输入一个字符串时，将会出现很多缓冲区溢出的问题，它是因为无法提前知道字符串的大小，
对于已经分配的缓冲区来说，这个字符串可能会过大，
引发这个问题的原因之一是那些存储字符串却不进行边界检查的库函数， 例如gets() 【现在已经被弃用】 ,
gets 的目的是从终端的输入中读取字符串，直到遇到结束符\n ( 0x0a )，
gets从标准输入设备读字符串函数，其可以无限读取，不会判断上限，以回车结束读取，所以程序员应该确保buffer的空间足够大，以便在执行读操作时不发生溢出。
同样的问题也出现在strcpy ,strcpy 没有办法知道 目标地址的 缓冲区大小， strcat 也是如此，
scanf 在获取输入的字符串的时候也会有缓冲区溢出的可能， 给它传递%s ,它会读取一个字符串，将它存储在某个地方， 它既不知道字符串的大小也不知道目标地址的缓冲区大小，
这些都是真实的安全问题，下面要讨论的是作为一个程序员，我们应该如何处理这些问题，
先看个例子：
按道理来说，它最多是4个字节，
现在看汇编代码，
上图中的 sub 0x18 ,%rsp , 0x18 就是24 ，所以最多可以接受24个字节，即使最开始的时候只声明了4个字节的缓冲区，
上图中，还有20个字节没有被使用，
如果我们输入23个字符，这将会用光整个缓冲区，因为字符串是以00结束的， 如下图：
如果我们输入25个字符， 如下图：
如果我们输入24个字符， 如下图：
上图，最后的空字符 占了 返回地址的一个字节， 执行完echo 的程序原本应该返回到 00 40 06 cf ,但是现在却返回到了 00 40 06 00 ，如下：
它仍然使得程序错误的运行着，并没有使程序崩溃掉，
我们经常会遇到有些bug 使程序错误地运行，但是我们却不知道， 就是上面这种情况，
我们从键盘输入的字符串会默认加一个 \0 （0x0）的 !
Q 执行完本来应该返回A，现在A被改为了B， 这将会执行插入的代码（exploit code ）
如何使我们的机器免受这样的攻击：
1，编写代码的时候可以写的更安全，
2，栈随机化，ASLR（Address Space Layout Randomization ）
每次程序运行的时候，它的地址都是变化的， 所以基本不知道代码运行在什么地方，
3， gcc 默认的栈保护 ，这种行为称为canary
Unions
如果我们知道自己只会使用其中的一个值， 我们就可以使用 Union。
这和 强制转换 是完全不一样的，
Byte Ordering
Big Endian :
MSB 放在 lowest address
Little Endian:
LSB 放在 lowest address
Byte Ordering Example:
#includeint main(){ int a = 0x12345678; char *p = (char*)&a; printf("%x %x %x %x\n",*p,*(p+1),*(p+2),*(p+3)); // 输出是: 78 56 34 12 说明是小端 系统 return 0; }
Lecture08 Program Optimization
注意：这里如何运行的更快指的是 算法已经确定了，并且程序可以正确的运行。
要编写出编译器友好的代码，必须明白什么代码编译器能优化，什么代码编译器不能优化，从而养成一个习惯：尽量编写编译器会优化的代码。
Generally Useful Optimization
如果你希望程序快速运行，那么你必须写汇编代码，这显然是不对的，除非程序运行在资源非常小的机器上（例如计算力不足的嵌入式系统上）。
一般来说，编译器有一套优化策略，但总的来说，如果编译器对代码的某些优化不够确定，那么就不优化。
1,Reduce Frequency 减少代码执行的频率：
- 如果它总是产生同样的结果
- 尤其是将代码移出循环
例如：
2, Reduction in Strength 降低强度
用简单的操作代替昂贵的操作
移位，加法 代替 乘法或除法
在Intel Nehalem上，整数乘法需要3个CPU周期
例子：
3, Share Common Subexpressions
Optimization Blockers
第一个例子： 转换大写字符 到 小写字符：
上面这个例子的性能：
这是因为for 循环中， strlen 每次都会被执行，所以 strlen 的执行次数 等于循环的次数，
strlen 的原理是： 从第一个字符一直往后走，直到空字符，所以 strlen 本身的性能是 线性的，
上述例子对一个线性的调用了n次，所以基本上就变为了 n ^2 。
所以优化如下：
从上图可以看出 lower2 基本上是个平线，
所以，为什么编译器不能聪明一些，将strlen 移除循环？
编译器必须假设 strlen 是个黑盒，而且假设它可能会做任何事情，
第二个例子： 计算二维数组的每行总和 存储到 一维数组中：
这里主要是 每次内循环都 从内存读取 b[i] 然后 加上个值 再将b[i] 写入，所以一遍又一遍的在内存和寄存器之间传递数据造成很大浪费。
而且这种Alias 也可能会导致程序出错：
例如：
B的初始值是 A中的第二行，此时，B[0] 和 A[3] 都引用着4 ，等等。
当i = 0 时， b[i] = 0,其实也将 A[3] 从4 变为了0，最终导致了错误！！！
所以要移除 Alias ,如下：
改善后的只是 读取一个 浮点数（a[i*n +j] ），然后加到 寄存器中就可以了！
当然，i*n 也可以优化先计算出来，（不过这个gcc会自动优化）
Expoiting Instruction-Level Parallelism（利用 指令级别 并行）
需要对现代处理器设计有全面的了解
- 硬件可以并行执行多条指令
受数据依赖性限制的性能
简单的转换可以显著提高性能
- 编译器通常无法进行这些转换
- 浮点运算中缺少结合性和分配性
我们可以 定义 data_t 为 int long float double ，这样就可以看到性能随着不同数据类型发生的变化了。
上图：
CPE 它代表 处理一个元素用了几个时间周期 ，我们不去关心具体花费了多长时间，
去关注处理器内部的时钟周期更有用！
因为CPU是2.3Ghz 还是 2.6GHz ，一个程序员是无法控制它的。 但是我们可以控制程序中的不同部分使用多少个时钟周期，
上图的优化：
将vec_length 移出循环，
避免每次都做边界检查，【get_vec_element() 每次都会做边界检查的】
引入临时变量，用于累加值
优化后的结果：
一个时钟周期执行多条指令，功能单元会设计的更复杂， 它使用了流水线技术，
上图：
流水线技术的基本思想是 将计算分解为一系列不同的阶段，（注： a*b 和 a*c 是互不影响的 ）
我们假设每个Stage 都有一个专门的硬件来工作，假设每个乘法都需要经过3个Stage .
Time1 的时候，只有一个Stage1,所以先算a*b 的第一阶段，
Time2 的时候， a*b 进入Stage2,这时候可以同时进行 a*c 的Stage1 ...
最后，在a*c 的第三个阶段之前，不能进行p1*p2 的乘法，
所以，整体下来需要7 cycles ，比 9 cycles 剩下了2个！
它有点像并行性，但是这种并行性不是说你拥有了多份资源（多个乘法器）。
What about Branches?
如果条件 满足，就会跳转执行，如果条件不满足 它会继续执行后面的代码，
而且我们事先没有办法知道哪个会被执行，因为这和数据有关！
所以，现代的处理器是采用分支预测（本质上只是猜测）来处理这种情况的！
猜测哪一个分支会被执行，
先执行猜测的分支，然后在后面验证猜测是否正确！
注： 所有的指令都只是修改寄存器，对于每个寄存器，通常有几百个虚拟寄存器（副本）所以有足够的备份可以返回之前的状态。
Summary
关于 分支预测： https://stackoverflow.com/a/11227902
Lecture 09 The Memory Hierarchy（内存 层次结构）
到目前为止，我们只是把内存当做是一个巨大的字节数组，可以通过下标来访问。
但实际上，内存系统是一个非常复杂的层次结构，它提供了一个抽象，把内存结构抽象成一个大的线性数组。
所以，这个lecture 就是探寻内存层次结构是如何构建的，
Storage technologies and trends(存储技术和趋势）
注意这里是以一个很高的视角来快速浏览，不会陷入一大堆深奥的细节。
1,RAM:
上图：
现在大多数人所熟悉的内存其实是叫做 随机访问存储器（RAM），
SRAM 和 DRAM 是根据 存储单元 的实现方式来区分的，
EDC：error detection and correction
DRAM 只需要一个晶体管去存储一个比特， 而SRAM更复杂，需要4 or 6 个晶体管来存储一个比特。
虽然SRAM成本更高，但是速度也是比DRAM快一个数量级，
虽然SRAM成本高，但是它也不需要刷新，而且也稳定不是很需要EDC，
所以，我们将SRAM用于 容量小 但速度非常快的芯片中，叫做高速缓存。
将DRAM用于主存，以及图形显卡的帧缓存中，
注：SRAM 和 DRAM 都是易失的（volatile）,如果断电，就会丢失它们所保存的信息。
2,Nonvolatile Memories 非易失性存储器:
这些非易失性存储器的通用名称是 ROM， ROM是一种非易失性存储器，旨在不经常重写或永不重写!
现在的Flash memory（闪存）擦除后，可以被重新编码10 0000次，之后就损坏了。
ROM 被使用在BIOS中，在开机后最初执行的指令都是存储在ROM（被硬编码进去的）。
SSD solid state disks（固态硬盘），系统仍然把它们当做旋转的硬盘，实际上它们是由闪存组成的（可以被擦写100000次，我电脑500G固态，就是可以累积被擦写各 500*100 000 =50 000 000G的数据，5w T ）,所以固态硬盘是比传统硬盘（磁盘）快。
U盘也是一样，一个64G U盘，累积可以被擦写 64 *100 000 G = 640 T的数据。
3, Traditional Bus Structure Connecting CPU and Memory
上图只是一种抽象，不用太较真字面的意义，目的是去了解信息如何在系统中流动，
现代系统的使用的总线设计是非常神秘，而且越来越复杂！
例子01：
（之所以是 load 是因为这是以CPU的角度看的，将A从memory加载到 CPU的rax 寄存器上）
CPU 首先将A的地址放到 bus 上，如下：
然后main memory 感知到这个信号后，读取A地址的 8个字节内容，然后放回 bus ,如下：
然后CPU会从总线数据中读取内容，最后放到 %rax 中，如下：
例子02：
4，Disk 硬盘（磁盘）：
硬盘其实是一系列的盘片，每个盘片上都涂有磁性材料，
里面有很多传动臂，齿轮等机械设备，所以硬盘（旋转磁盘）比SRAM 和 DRAM 都慢，
上图：
我们可以认为硬盘是有盘片组成的，每个盘片有两个表面，
每个表面都有一系列的同心圆，称之为磁道（Track），
每个磁道包含很多个扇区（Sector）,扇区存储着数据， 每个扇区存储512个字节，
扇区之间的 Gap 是不存储数据的，
上图：
盘片在主轴上是彼此对齐的，
在不同表面上，磁道也是对齐的，
上图中的磁道的集合，我们称之为一个圆柱面（Cylinder ）。
注意：所有的厂商是用公式是： 1GB = 10^9 Bytes, 而不是 2 ^ 20 Bytes（1024 * 1024） ，所以我们买电脑的时候，商家说我们电脑是 500GB 的，实际上真实的大小是 没有500G的！！！
磁盘容量是有两个因素决定的：
1，记录密度（Recording density），决定单独的一个扇区可以存储多少比特，
2，磁道密度（Track density），相邻的磁道可以放置得有多近，
它们两个的乘积称之为 面密度 Areal desity ，决定了整个磁盘的存储容量。
磁盘的面密度越高，存储的比特就越多。
硬盘是如何工作的？
上图：
每个盘片都有磁臂，每个表面都有一个读写头，
访问数据：
上图：
SRAM 读取一个 double 需要 4ns
DRAM 读取大约是 60 ns (DRAM 比 SRAM 慢一个数量级)
但是，硬盘（旋转磁盘）比SRAM 慢了 40，000倍，比DRAM慢了2，500倍。
5 , I/O Bus
现在将硬盘（旋转磁盘）这样的设备 连接到CPU 和 内存，如下：
【硬盘（旋转磁盘）是外存储器，注：固态硬盘是ROM，所以是内存储器】
例子：
从硬盘的一个扇区读取数据，
CPU 写 一个三元组 到disk controller， (command, logical block number , memory address )
上图：
disk controller 读取 logical block number 对应的扇区（假设一个 logical block 对应一个扇区），
然后，disk controller 获得bus 控制权，通过IO bridge 将数据复制到Main memory,而无需通知CPU！
上图：
当DMA传输完成后，disk controller 通过中断的机制 来通知 CPU，（通过设置CPU上的一个引脚）。
这样做的目的是因为，CPU执行速度太快，磁盘的速度太慢，所以如果让CPU停下来等待磁盘传输，肯定是不行的。
6, Solid State Disks （SSDs）
ssd 大概是介于 DRAM 和 硬盘（旋转磁盘）之间的存储器，本质上是ROM。
在CPU看来，它和硬盘完全相同， 但是它没有像硬盘那样的机械装置，而是完全由闪存构建。
现在的Flash translation layer 中实现了各种花里胡哨的算法，以延长SSD的使用寿命，例如缓存技术等。
上图：
Intel 保证在磨损之前，你可以使用 128 PB 的数据，
所以硬盘（旋转磁盘）容量更大，但是速度更慢，
固态硬盘容量较小，但是速度更快。
上图：
Y轴，每个间距都是一个数量级的变化，
我们可以看到 CPU 和 DRAM ，SSD Disk 都存在巨大的差距，这是个问题，
因为程序都需要数据，而数据存储在内存和磁盘中，所以如果CPU性能一直增加，而存储性能增加缓慢（差距相对变大），实际上整体计算机性能实际不会增加。
Locality:
作为一个程序员，我们要知道一个程序是有一个好的 Locality 还是一个坏的 Locality ,
例子01：
例子02：
上图：一直在内存中跳跃，所以对于a,这是一个很糟糕的 spatial locality,
存储器设计整体结构图：
Caching in the memeory hierarchy
上图，重要的一点是，上层的存储器有一部分区域用于保存下面一层的数据。这就是缓存。
Caches
层次结构创建了一个大型存储池，它的存储容量大约是最底层的存储设备的大小，其访问速度却是最高层的存储设置的访问速度，
缓存的一般工作方式
下面的lecture 是其中的细节，
缓存是一个非常通用的概念，可以应用于存储器层次结构中的所有层。
假设现在CPU需要Memory中的 4， 和 10 （Cache中没有），
再如：
缓存很好，但是如果缓存没有命中，就会很慢了，
不同的缓存不命中：
Summary
Lecture 10 Cache Memories (高速缓存器)
接着上个Leture ,说了很多的Cache,
现在有一种很重要的Cache，即Cache memoriey （高速缓存器），它包含在CPU芯片中，它们是使用SRAM来实现的，
高速缓存完全由硬件来管理
上图：
line 中的 tag 帮助我们搜寻 block（line），
缓存硬件如何实现读取到CPU：
例子：
如果匹配不上的话，就要从内存中加载进来了，然后会覆盖缓存中的数据，
例子2：
假设一个简单的内存系统，4-bit地址，由16 字节组成，
分为 4 个 set , 每个 set 有 1个block（line）, 每个block 存2个字节，
S E B
开始时，缓存是空的，valid bit 被设置为0 ，
可以看出最后两次，每次都不会命中，它们之间产生了冲突，每次都要从内存中加载进来， 这是个缺点，它的原因是每个set 只有一个 line(block) ,
下面看E= 2时，（每个set有2个 block ）
我们看到E = 2 时，最后一个就不会再次 miss 了，
注： E越大，电路设计起来也就越复杂，但是为了不冲突，E也要适当的大一点，
总结：
例子：
缓存硬件如何实现写到内存：
上图：
d-cache 是 data cache
i-cache 是 instruction cache
一般miss 的惩罚都会比较大， 所以尽量降低 miss rate
Writing Cache Friendly Code
前面已经提到，缓存是由硬件控制的，是自动执行的，虽然我们不能直接去操纵它，但是了解缓存有助于我们编写cache friendly 的代码，
尽量减少内循环中的未命中率， 重复引用变量是好的，特别是对于局部变量，
如果声明一个局部变量，编译器可能把它放到寄存器中，
如果你正在引用全局变量，编译器无法将它放到寄存器中缓存，所以重复引用栈中的局部变量是好的！
缓存对代码性能的影响
1，The Memory Mountain
它描述了 吞吐量（read throughput），也就是每秒从内存中读取的字节数！
我们写程序尽量要使得 程序在山的顶端， 即 14000 MB /s
2，Rearraging loops to improve spatial locality
另：在任何类型的存储系统中，写操作比读操作更为灵活，为什么？
是因为写操作，你可以推迟写。但是读操作时，在获得该数据之前，无法干其他的事情！
3，Using blocking to improve temproal locality
当我们重新排列循环的时候，我们改善的是我们的空间局部性， 并没有对时间局部性作出改善。
要想改善时间局部性，可以使用blocking（分块）的技术！
没有使用分块时候的总的Miss 分析
我们现在做的不是一次更新一个元素， 一次加载一个块进缓存！
Cache Summary：
Lecture 11 Linking
这个lecture，内容是：程序如何与硬件交互，以及程序如何与特定系统中的软件交互！
通过学习Linking 去弄清楚系统是如何构建程序的！后面也会学习下Library interpositioning（库打桩）。
在Translators 中有三个翻译器，
首先是调用C预处理器cpp（它将main.c 翻译成中间文件main.i ）
然后是调用cc1（它将main.i 翻译成汇编文件main.s）
最后调用汇编器as （将 main.s 翻译为 main.o ）
得到main.o 和 sum.o 之后，链接器（Linker） 会加上一些必要的系统目标文件，然后将它们链接在一起，得到一个可执行文件prog !
为什么要分离编译，而不是一个大文件包含所有的代码？
链接器做的事情
链接器主要的两个任务：
1，Symbol resolution（符号解析）
现在这里说的Symbol resulution 是在链接器的链接过程中， 链接器将每个符号引用与一个符号定义相关联。
2，Relocation（重定位）
此时，每个符号引用都有唯一一个符号定义，此时进行重定位，
Three Kinds of Object Files （Modules）
ELF 格式：
它是 .o , a.out .so 文件的统一格式。
exclusively :唯一地， 第三个的Local symbols 只能从该模块中引用它，如果我们想一模块中的函数能够被别的模块引用就不加static ，如果只希望模块中的函数在模块中使用就加上static 。
上图，
链接器在符号解析的时候，会将每个符号引用来唯一的符号定义关联起来，
例子：
一旦链接器生成目标文件，目标文件就可以直接加载到内存，
Packing Commonly Used Functions
链接 的一个优势是允许我们创建库，我们将常用的函数打包提供给其他的程序员，
静态库：
上图 ：
例如printf.c 发生变化时，我们只需要重新编译printf ，然后重新打包所有的 .o 文件即可！
上图：这些静态库的规范是，以lib 为前缀
例子：
上图：
libtest.o 中调用了 libmine.a 中的函数，
由于链接器是从做往右scan,所以 如果把 libmine.a 放在了前面，这样最后就会有 unresolved 的entries 存在在list 中，
编写头文件和生成静态库：
头文件
// vector.h
void addvec(int* x,int* y,int* z,int n);
void mulvec(int* x,int* y,int* z,int n);
生成静态库
gcc addvec.c -c # 生成 addvec.o
gcc mulvec.c -c # 生成 mulvec.o
#生成静态库
ar rs -o libvector.a \
addvec.o mulvec.o
之后，我们将头文件和静态库分享给别人就行了，
别人使用上面的静态库：
//main.c
#include#include "vector.h" int main() { int a[3] = {1,2,3}; int b[3] = {4,5,6}; int c[3] = {0}; addvec(a,b,c,3); for (int i = 0; i < 3; ++i) { printf("%d ",c[i]); } mulvec(a,b,c,3); for (int i = 0; i < 3; ++i) { printf("%d ",c[i]); } return 0; }
gcc main.c -c # 生成 main.o 只编译未链接
gcc main.o -L. libvector.a # 库要放在最后！ 或 gcc main.o -L. -lvector
# 或者下面一行命令
gcc main.c -L. libvector.a # 或 gcc main.c -L. -lvector
动态库(共享库)：
编写头文件和生成动态库：
头文件
// vector.h
void addvec(int* x,int* y,int* z,int n);
void mulvec(int* x,int* y,int* z,int n);
生成动态库
#生成动态库
gcc -shared -fpic -o libvector.so \
addvec.c mulvec.c
# 直接从 *.c 生成 .so
之后，我们将头文件和动态库分享给别人就行了，
别人使用上面的动态库：
//main.c
#include#include "vector.h" int main() { int a[3] = {1,2,3}; int b[3] = {4,5,6}; int c[3] = {0}; addvec(a,b,c,3); for (int i = 0; i < 3; ++i) { printf("%d ",c[i]); } mulvec(a,b,c,3); for (int i = 0; i < 3; ++i) { printf("%d ",c[i]); } return 0; }
gcc main.c ./libvector.so
linking summary
Library interpositioning（库打桩）
例子：
Lecture 12 Exceptional Control Flow: Exceptions and Processes(异常控制流)
异常控制流是现代系统的一个重要组成部分，它存在于计算机系统的各个层次，从最低层的硬件一直到上层的软件。
当你打开一个计算机，它会一个接一个的执行指令，直到关机。 如果你的计算机有多个核心，那么这些核心会交替执行指令.
Exceptional Control Flow
Exceptions
异常是将控制权转移到操作系统内核（内核是操作系统始终驻留在内存的一部分），
异常由硬件和软件共同完成（例如，%rip 等的改变是由硬件完成的），
上图：
由该异常而去执行的代码是要由操作系统内核来设置和决定的，
因此每种类型的事件都有一个唯一的【异常编码（Exception numbers）】，它作为异常表的索引，
例如当异常k 发生的时候，硬件使用k 作为索引获取到 该异常处理程序的地址，
Exception 的分类：
上图：
异步异常是由处理器外部发生的状态变化导致的， 这些称为（Interrupts）中断， 那些状态变化是通过处理器的引脚向处理器通知这些状态变化的！ An external pin called the interrupt pin（外部引脚也叫中断引脚）。
最常见的例子：
定时器中断，所有系统都有一个内置计时器，每隔几毫秒就会关闭一次。当关闭的时候，它将中断引脚设置为高电平，并且有一个特殊的异常编码用于定时器中断，
同步异常分为三类：
Traps ，它是故意（操作系统故意）的异常， 例如，程序进行系统调用，并从内核请求各种功能， 内核对请求做出响应之后，最后将控制权返回给调用程序那里。 可以这么看待系统调用：它看起来像是函数调用，实际是将控制权转移到内核中！
Faults, 它不是故意的异常，但是，可能是可以恢复的，
Aborts ,它不是故意的异常，也是不可恢复的， 永远没有办法回到该程序，
上图：
这个唯一的编号是由Linux分配的，
例子：
Processes
上图：
第一个抽象：独占CPU和寄存器
exclusive use of the CPU : 独占使用CPU 和寄存器，当运行一个进程的时候，你永远不用担心其他程序修改你的寄存器， 甚至你无法感知到系统上还有其他的程序在运行，
第二个抽象：感觉拥有自己的地址空间
这是由一种虚拟内存的机制提供的，每个运行的程序都有自己的代码，数据，堆栈，
上图：
系统中运行了多个进程，即使是在单核的机器上，这些进程中的许多个实际上是在同一时间并发运行的，
上图：
看起来，一个进程对系统有 独有的访问权限（独占CPU，寄存器 ，独自的地址空间），但是实际上是我们共用CPU，操作系统这里做的工作就是管理共享，
单核的系统（一个CPU）：
多核系统（多个CPU）：
上图：
一般认为每一个进程代表一个【逻辑控制流】，它是该进程的所有指令
因为在时间上，A进程和B进程 ， A进程和C进程 有重叠，所以是【并发】
因为在时间上，B进程和C进程没有重叠，所以是【串行】
无论核心的多少，这种并发性的定义都是成立的，
上图：
我们可以认为三个进程是 【并行】 的，
上图：
上下文切换， 它被内核所管理着！
重要的一点是，内核不是一个单独的进程，而是作为某些现有进程的一部分运行的 ! 它是位于地址空间顶部的代码，
Process Control
Linux提供了很多函数，你可以轻松来操作进程，我们称之为【进程控制】，
上图：
硬性规则：
1，当调用系统级别的函数时，必须要检查返回值，
2，唯一的例外是，有些函数返回void ,例如 exit() 或者 free()
使用unix_error() 简化代码，
进一步简化：
上图：
我们这里做的是，形成一个包装器，它与原来的函数具有相同的接口，
上图：
Running，该进程正在运行并执行指令， 或 它可以被调度（虽然此刻没有运行，但稍后会被执行），
Stopped, 该进程被停止，并且在进一步通知（signals）前不会被调度，通常一个进程会停止，是因为它收到了某种信号，
Terminated, 该进程被终止（永久停止），
上图：
终止进程有三个原因：1，收到了终止信号 2 程序从main函数返回 3 调用了 exit() 函数，
上图：
child 拥有一个独立的拷贝的地址空间（child和父进程在栈上，堆等拥有相同的值），拥有一个父进程已打开的文件描述符拷贝（child可以访问任何已打开的文件，包括父进程拥有的标准输入和标准输出），唯一的区别是子进程获得的进程ID和父进程不同，
fork 是非常有特殊，因为它被调用一次，但返回两次，在父进程中返回一次，在子进程中返回一次，
上图：
我们不能对不同进程的运行顺序作出预测，但是我们可以使用【Process Graphs进程图】来了解事件的次序，
我们要做的是：
每个顶点对应一个语句的执行，使用当前变量值 标记边（edge），等等...
上图：
当一个进程因任何原因而终止时，系统实际上一直保持它，直到它被【回收Reap】,被父进程回收，这样做的目的是父进程可能想要直到子进程的退出状态。如果父进程创建一个进程，它可能希望等待该子进程完成并检查其退出状态， 所以当一个子进程结束后，系统不会完全删除它，它会保留一些状态信息，
如果父进程不回收它的子进程，那么系统会安排系统中存在的第一个进程（pid = 1 ，init process）来回收， init 进程总是回收这样的孤儿进程（orphaned process）
我们只需要关心回收僵尸进程，例如长期运行的父进程（shell 或者 servers），在这种情况下，服务器可能创建数百万个子进程，每个子进程都会成为僵尸进程，它们有它们的状态信息（这占用了内核空间，这可以理解为一种内存泄漏【memeory leak】的形式）， 如果你没有回收这些僵尸进程，最终会使得内核崩溃~
对于长期运行的程序，我们必须使用 wait 和 waitpid 来回收子进程
// prevent_zombile.c #include#include #include int main() { if (fork() == 0){ // child printf("I'm child,pid=%d\n",getpid()); }else{ // parent int status_for_child; wait(&status_for_child); // 如果没有这个的话，child 就成了zombie process 了 printf("child status : %d\n",status_for_child); printf("==========\n"); while(1){ printf("running [parent],pid=%d\n",getpid()); sleep(1); } } return 0; }
孤儿进程，
上图，
wait 是同步的， 它会等待其中的一个子进程终止，
上图：
WIFEXITED ： wait if exited ,它针对的是 子进程 使用 exit 的情况， 这时候可以用WEXITSTATUS 来查看status
上图：
我们使用类似于wait的 waitpid, 它等待特定的子进程，注：waitpid 非常复杂~
上图：
我们已经学会了如何创建子进程，
我们创建了子进程只是创建了一个与父进程完全一样的副本， 它们运行相同的代码，相同的程序，相同的变量，
要想在进程中运行不同的程序，我们需要使用 execve() 函数，
一旦在一个进程中调用execve ，它将会覆盖code,data,stack虚拟地址空间，当破了当前的程序，但是，保留了PID，已经打开的文件，信号上下文
// main 函数中的 argc argv envp 三个参数 #include#include // for getenv() void printString(char** s,int len){ for (int i = 0; i < len; ++i) { printf("%s |",s[i]); } printf("\n===\n"); } int main(int argc, char *argv[],char* envp[]) { // argc printf("argc: %d \n===\n",argc); // argv printString(argv,argc); // envp for(int i =0;envp[i]!=NULL;++i){ printf("%s |",envp[i]); } char* ret = getenv("HOME"); printf("\n===\nenv var:HOME=%s\n",ret); return 0; }
// 使用 fork 和 execve 来模拟 shell
#include#include // for fork() #include // for wait() #include <string.h> // 模拟shell 来 执行 命令行 命令 [例如：ls 路径: /bin/ls] int main(int argc, char *argv[],char* envp[]) { pid_t pid = fork();// 返回两次，child pid 返回到parent. 0 返回到 child if(pid == 0){ // child printf("child %d\n[execve]:\n",getpid()); argv = &argv[1]; // 剔除 argv[0] int ret = execve(argv[0],argv,envp);// 执行成功的话，不返回(但是父进程还是回收的)，下面代码也不执行了 ,执行不成功（例如文件名错误) 返回-1 printf("%d\n",ret); }else{ // parent printf("child %d\n",pid); printf("parent %d\n",getpid()); int status; int ret1 = wait(&status); printf("status: %d | wait's ret is :%d\n",status,ret1); } return 0; } /* root@zcb-virtual-machine:/home/zcb/test/csapp_project/lecture14# ./a.out /bin/ls child 10944 parent 10943 child 10944 [execve]: a.out execve_example.c prevent_zombie.c README status: 0 | wait's ret is :10944 root@zcb-virtual-machine:/home/zcb/test/csapp_project/lecture14# ./a.out /bin/ls -l child 10946 parent 10945 child 10946 [execve]: 总用量 24 -rwxr-xr-x 1 zcb zcb 8536 2月 19 14:08 a.out -rw-r--r-- 1 zcb zcb 905 2月 19 14:12 execve_example.c -rw-r--r-- 1 zcb zcb 545 2月 18 17:08 prevent_zombie.c -rw-r--r-- 1 zcb zcb 41 2月 18 14:38 README status: 0 | wait's ret is :10946 root@zcb-virtual-machine:/home/zcb/test/csapp_project/lecture14# ./a.out /usr/bin/find / -name stdio.h child 10950 parent 10949 child 10950 [execve]: /usr/bin/find: ‘/run/user/1000/gvfs’: 权限不够 /usr/include/c++/7/tr1/stdio.h /usr/include/x86_64-linux-gnu/bits/stdio.h /usr/include/stdio.h /snap/gnome-3-34-1804/36/usr/include/c++/6/tr1/stdio.h /snap/gnome-3-34-1804/36/usr/include/stdio.h /snap/gnome-3-34-1804/36/usr/include/x86_64-linux-gnu/bits/stdio.h status: 256 | wait's ret is :10950 */
fork 和 exec 有些奇怪，为什么不能是 一个命令【创建一个新进程，并运行】？
为什么分开为两个独立的函数，fork 和 exec ?
因为很多的时候，我们仅仅只是需要fork一下就行了，仅仅是需要一个进程的副本，
但也有的时候，我们是需要一个新的进程去执行不同于父进程的任务的，
上图：
execve 它将创建一个新的 栈，堆，等等， 栈的形式，如上图，
// environ 的使用 #includeextern char** environ; // 实际还是 envp int main(int argc, char *argv[],char* envp[]) { for(int i =0;environ[i]!=NULL;++i){ printf("%s |",environ[i]); } return 0; }
Summary：
Lecture13 Exceptional Control Flow： Signals and Nonlocal Jumps
本lecture主要是看看一些高层次的机制，比如说Linux信号机制和C中的非本地跳转，会将主要的时间放在信号上，它有一些技巧可能会迷惑你，
Shells
上图：
在Linux下，我们只有一种方法创建进程，即使用fork,
当启动系统时第一个创建的进程是init 进程（它的process id is 1），系统上其他所有的进程都是 init 进程的子进程，init进程启动时会自动创建守护进程（Daemon） ， 【守护进程一般是一个长期运行的程序，通常用来提供服务】
init进程最后会创建Login shell 进程，【它为用户提供了命令行接口】
上图：
所以其实shell 这个程序和其他的程序没区别，
在Linux下，默认的shell 叫做 bash ,
上图：
注意，bg 后台程序是没有进行wait回收的, 如果有大量的后台程序就会导致僵尸进程【内存泄漏】，
Signals
上图：
信号机制与上个lecture的异常很像，（不过信号完全是由软件实现的，）
内核信号是由内核发出到进程，但是有时是在某些进程请求内核发出另一个进程，
SIGINT：对一个前台程序按下 ctrl-c 就会终止程序，
SIGKILL和SIGINT的效果是一样的，区别是SIGKILL不能被覆盖或者忽略【待会儿可以看到一些方法可以捕获并忽略SIGINT这类的信号】，
SIGSEGV，如果一个进程访问不合法的内存，就会出现段错误【内核会向这个进程发送SIGSEGV信号】，
SIGALRM，是一个可以自行安排的信号，我们可以在程序里每隔3秒给自己发送一个SIGALRM信号， （可以用来设置定时器，例如为了防止一项工作超过10s,我们可以在10s后向该程序发送SIGALRM）
SIGCHLD，每当子进程被终止或结束时，内核就会通知它们的父进程，
处理信号时，要十分小心处理术语【Signal Concepts】
上图：
内核强制目标进程以某种方式作出反应，
这里的处理方式，很像上个lecture的异常处理，它们的区别是异常处理是在内核层次，而信号处理是在C代码里，
上图：
我们说一个信号是pending（待处理）【内核已发出，但是进程还未收到】，对于每种类型的信号，最多只能有一个处于pending的信号，【这里不存在排队，如果已经有一个处于pending的SIGINT，再来一个新的会被直接丢弃】。
在进程中也可以阻塞某些信号的接收， 【它没办法阻止信号的传递， 但是，信号不会被接收直到阻塞解除】
处于 pending 的信号只能被接收一次，
上图：
每个进程都会维护一个 pending 位向量（32位的int），里面是待处理信号的集合，这也是为什么没有排队一说的原因，
也会维护一个blocked 位向量，可以使用sigprocmask 函数 置位或清零它，
blocked 位向量 也被称为 【信号掩码signal mask】
上面就是重要的一些概念，下面看发送和接收信号的细节：
上图：进程组的概念，每个进程都属于某个进程组，
第一种发送信号的方法--通过kill , 可以同时给一组进程发送信号
上图：
kill 加上 - 意思是发送信号给进程组中的每个进程，
第二种发送信号的方法是在通过键盘，
Ctrl + c 时，内核会向前台进程组下的所有进程发送SIGINT ，
Ctrl + z 时，内核会向前台进程组下的所有进程发送SIGTSTP【to stop 默认行为是挂起进程,直到进程收到SIGCONT】 ，
第三种发送信号的方法 使用系统调用kill 函数
下面是进程如何接受信号
上图：
现在的假设是，内核进行异常处理完毕，马上要进入Process B的时刻【目前内核拥有控制权】，会做判断：
如果pnb 是0 ，也就是没有需要被处理的信号， 直接给控制权到B进程
如果pnb 不是0，它会选择最小的非0位，强制让进程B 接收相应的信号，进程B会进行一定的action，然后会继续遍历pnb中所有的nonzero ，让进程B都作出相应的action， 当处理完所有的非0位，就会将控制权转移给B进程。
进程对于每种信号都有一个默认的action，它们包含于上面3种，我们可以使用signal() 来修改默认的action，
上图：
注：这里的signal 和 kill 函数一样都有一定的误导性，kill 是发送信号的，signal() 来修改默认的action，
// signal_handle.c
#include// for printf() fprintf() #include // for exit() #include // for signal() SIGINT, SIG_ERR #include <string.h> // strerror() #include // for errno #include // for pause() void signal_handler(int sig){ printf(" ctrl + c 哈哈哈哈哈哈!\n"); exit(0); } int main() { if(signal(SIGINT,signal_handler) == SIG_ERR){ fprintf(stderr,"%s:%s\n","signal_error",strerror(errno)); exit(0); } // pause pause(); // 暂定，直到收到 一个 信号 return 0; }
什么时候会出现 SIG_ERR？
https://www.quora.com/What-is-the-case-where-the-SIG_ERR-of-Linux-signal-function-can-occur-C-C-Linux-development
#include// for printf() fprintf() #include // for exit() #include // for signal() SIGINT, SIG_ERR #include <string.h> // strerror() #include // for errno #include // for pause() void signal_handler(int sig){ printf(" ctrl + c 哈哈哈哈哈哈!\n"); exit(0); } int main() { //if(signal(SIGINT,signal_handler) == SIG_ERR){ // [1,64] 信号才是正确的范围 if(signal(65,signal_handler) == SIG_ERR){ fprintf(stderr,"%s:%s\n","signal_error",strerror(errno)); //errno is 22 EINVAL: invalid argument exit(0); } // pause pause(); // 暂定，直到收到 一个 信号 return 0; }
#include#include #include <string.h> #include int main(int C, char**V) { printf("SIG_DFL=%p SIG_IGN=%p SIG_ERR=%p\n", (void*)SIG_IGN, (void*)SIG_DFL, (void*)SIG_ERR); //Linux signals: [1,64] but try going outside this range, just for the lols for(int i=-1; i<=66; i++) if(SIG_ERR==signal(i,SIG_DFL)) printf("%d: %s\n",i, strerror(errno)); //EINVAL for: SIGKILL,SIGSTOP,32,36 + anything outside of [1,64] if(SIG_ERR==signal(1,(void*)42)) printf("%d: %s\n",1, strerror(errno)); //Linux doesn't check the handler argument }
信号处理也是并发的
上图：
内核总会阻塞 正在被处理信号类型 的signal。 例如SIGINT handler 不能被其他的SIGINT中断！ 【隐式阻塞】
内核也提供sigprocmask 函数去显式设置阻塞和解除阻塞。 【显式阻塞】
// block_signal.c #include#include #include int main() { // sigset_t 实际是 struct { unsigned long sig[64/bit of long]}; 但是 sizeof(sigset_t) = 128byte sigset_t mask,prev_mask; // 理解为 一个 bit vector 就可以 sigemptyset(&mask); sigaddset(&mask,SIGINT); // add SIGINT //sigprocmask(); 阻塞 SIGINT ,并保存 前一个blocked set 至 prev_mask sigprocmask(SIG_BLOCK,&mask,&prev_mask); /* * code region that will not be interrupted by SIGINT * */ printf("你以为 ctrl+ c 能干死我吗？【5s后自己就停了】\n"); sleep(5); // restore previous blocked set,unblocking SIGINT sigprocmask(SIG_SETMASK,&prev_mask,NULL); return 0; }
关于sigset_t
上图是 32-bit 机器，
/* Note on the size of sigset_t: * * In glibc, sigset_t is an array with space for 1024 bits (!), * even though all arches supported by Linux have only 64 signals * except MIPS, which has 128. IOW, it is 128 bytes long. * * In-kernel sigset_t is sized correctly (it is either 64 or 128 bit long). * However, some old syscall return only 32 lower bits (one word). * Example: sys_sigpending vs sys_rt_sigpending. * * Be aware of this fact when you try to * memcpy(&tcp->u_arg[1], &something, sizeof(sigset_t)) * - sizeof(sigset_t) is much bigger than you think, * it may overflow tcp->u_arg[] array, and it may try to copy more data * than is really available in. * Similarly, * umoven(tcp, addr, sizeof(sigset_t), &sigset) * may be a bad idea: it'll try to read much more data than needed * to fetch a sigset_t. * Use NSIG_BYTES as a size instead. */
保证 Signal Handling 安全
上图：
G2 : errno 是个全局变量，它是系统级函数出现错误的时候才会被赋值，
G3: 当访问某些共享数据时，要阻断所有的信号 ，（main 访问signal handler 或者 signal handler 访问main都要这样），原因是：例如如果main 程序更新了一个全局变量，然后被中断进入了signal handler，它就会发现这个全局变量的状态不一致了。
G4: volatile 可以防止编译器将它的值放入寄存器中， 它会始终通过内存读写。例子：假设signla handler 更新一个全局变量，此时main 正在等待这个全局变量的改变，如果这个全局变量被更新到了寄存器，那么main就永远也接收不到改变。
G5: 特殊的全局变量 flag ，它仅读写，不能被增加或更新， 原子操作意味着 这个flag 变量的操作只能发生在一个禁止中断的过程中！
上图：
printf 是不安全的， 例子：我们在main 中密集printf , 假设main 中的一个prinf获得了终端的lock ,然后signal handler 它调用了一个printf (它一直无法获得lock), 这就会一直阻塞，这就是死锁现象！
上图：
csapp.c 见课程网站，
Lecture 14 System-Level I/O
Unix I/O
上图：
Unix中的一个设计优点是 用文件来描述很多抽象的事物， 文件是由一些字节序列组成的。
与Windows不同，Unix中文件不区分类型，只是把文件看做字节，操作系统基本上不了解文件内部的详细结构，。
上图：
对于文本处理，Windows 和 Linux 对文本行结尾的处理不一样，
上图：
文件描述符是一个小的整数，它标识了当前进程正在操作的某个文件。基本上系统允许同时打开的文件描述符数量是有限的， Linux中是 1024 。每个进程都有三个特殊的文件描述符，stdin stdout stderr
强调一点：每次进行系统调用时 务必要检查返回值！！！
上图：
你可能会想 难道关闭打开的文件还会报错吗？
YES. 在多线程程序中， 可能有两个程序同时运行，共享同一个文件，所以可能出现关闭一个已经被关闭的文件。
所以，还是强调，在使用系统函数时一定要检查返回值，即使是像close() 这样的函数。
上图：
这是一段非常糟糕的代码，因为系统级调用的开销是比较大的，
上图：
当字符的数量大于0 小于buf size 的时候，我们称之为 short counts ,
假设此时的位置距离EOF还有100字节，但是你要指定读入200字节，read 第一次将读入100 并返回100.然后第二次读EOF，返回0！
总之，写代码时要考虑到可能出现的short counts。
RIO(robust I/O) package
上图：
buffer 的好处就是先调用一次系统的函数将数据缓存起来，然后用户需要读取的时候，先检查buffer是否读完，如果全部读完就再次调用系统的函数重新填满buffer 。
Metadata ,sharing ,and redirection
上图：
每个进程都会有一个 desc table，一般是1024个。
总之，每个打开的文件在文件表中都会有一个对应的条目， 这个文件表是整个操作系统共享的， 此外，文件表中的每个条目也对应一个相关的v-node(virtual node 虚拟节点) 。
实际上，系统上的文件无论是否打开，都会对应一个v-node,
上图：
同一个进程中两次调用open() 会得到两个fd,会对应两个 open file table item , 对应一个v-node table item 。
此时，如果父进程读文件，File pos 就会往前走，此时Child 再读文件就会从新的位置读取。
上图：
dup2 是duplicate，复制的意思。 它复制一个fd table item 去覆盖一个 fd table item , 它最常见的用途是IO重定向。 这个item 可以理解为open file table 的地址。
上图：
close () 函数关闭文件，它只会减少 refcnt ，
本来 ls 是输出到 stdout 的，现在dup(4,1) ,所以现在再ls 就会输出到 4 文件描述符对应的文件了！
// io_redirection.c
#include#include // for open() #include // for sleep() // command 格式: ./a.out to a.txt int main(int argc, char *argv[]) { if (argc >= 3 ){ write(1,"before\n",6); // 输出到 stdout // 备份 stdout int bak_stdout = dup(1); // 此时 stdout 1 的地址被 复制到了 bak_stdout 的item , bak_stdout 为 最小的文件描述符 // 下面 使用 dup2 来重定向输出到 argv[2] 这个文件 int fd = open(argv[2],O_WRONLY); dup2(fd,1); // 这时的 stdout 都会到 argv[2] 这个文件了 write(1,"hello i enter file\n",6); // 输出到 argv[2] 这个文件 // 恢复 stdout dup2(bak_stdout,1); write(1,"after\n",6); // 输出到 stdout // close bak fd close(bak_stdout); // close fd close(fd); int lowest_fd = dup(1); printf("Now: lowest_fd is %d\n",lowest_fd); close(lowest_fd); } return 0; }
Standard I / O
上图：
标准IO是C的一部分，标准IO函数都带有缓冲功能，所以避免了很多系统级别的调用，使用起来也变得简单了 ！
上图：
如果碰到 \n ， 它将自动 flush ，
Closing remarks
可能会问，已经有了stdio ,为何还要自己写RIO？
这是因为stdio 虽然非常适合对终端和文件执行IO操作， 但是不太适用于network , RIO 主要是用于网络的
而且stdio 和 RIO 都带有缓冲区，而且缓冲区不一样，所以不要混着用！
注意：不能对没有行概念的文件进行基于行的IO操作，例如jpeg ,mp4,因为这些函数在处理 0xa（\n） 这个特殊字符会停止读入 ！
Lecture 15 Virtual Memory :Concepts
Address spaces
上图：
对资源的虚拟化，一般是通过拦截请求过程来实现， 通过磁盘控制器拦截请求实现磁盘虚拟化。
对于main memory , CPU发出的请求实际上是由MMU（memory management unit）来处理的， 上图中，它MMU将虚拟地址4100 转为 实际物理地址 4 ， 这个过程称之为 address translation （地址转换）！
为什么要虚拟化地址呢？
先看术语：
上图：
通常Virtual address space 比 Physical address space 大得多，
Physical address space 对应于系统中实际拥有的DRAM，
VM as a tool for caching
上图：
VM中的内容 被 缓存在 DRAM中，
VM中的blocks 被称为 pages ,它比一般的cache block 大得多， page通常是4096byte，block通常是64byte。
上图：
DRAM 这里可以理解为是个cache，但是和之前所学的缓存非常不同，
VM 不会直接写回disk，而是延迟写回disk
上图：
page table 是内存中的一个数据结构，是每个进程上下文的一部分， 由内核维护，每个进程都有自己的page table。
PTE 1 对应 VP1，这表明disk 中的VP1被映射到PP0，
VP3 和 VP6 是已经被allocate，但是不在内存中的page , 它们存储在磁盘上，
上图：
CPU在执行指令时，生成一个虚拟地址，MMU在page table 查找，
上图：
刚开始VP5 不会被缓存进DRAM，知道实际访问的时候，它才会被放入缓存！
VM as a tool for memory management
上图：
VM极大地简化了内核进行内存管理的工作，
每个进程都对应一个page table(DRAM), page table 都对应Virtual Memory（disk）, 使用的时候从disk加载到Physical Memory(DRAM)。
Process 1 的 VP1 被map 到了 PP2 ，Process2 的VP1 被map 到了 PP8.
Process 1 的VP 2 和 Process2 的VP2 被map到了 PP8
程序员的视角可以认为每个进程都有一个非常相似的虚拟地址空间，代码和数据都是从同一个地址开始的，但其实进程实际使用的page 可能分散在内存中。
VM as a tool for memory protection
Address translation
上图：
当CPU传递一个虚拟地址给MMU， MMU得到VPN（VP number），并将其做为page table的索引 在当前进程中的page table 中进行查找。
地址转换的作用是给定一个虚拟地址，得到相应的物理地址。
VPO 和 PPO 是相同的，
上图：
PTE 也参与L1 cache,
Lecture 16 Virtual Memory :Systems
Simple memory system example
Case study:Core i7 /Linux memory system
Memory mapping
Lecture 17 Dynamic Memory Allocation:Basic Concepts
Basic concept
Implicit free lists
Lecture 18 Dynamic Memory Allocation:Advanced Concepts
Lecture 19 Network Programming: Part I
上图：
从硬件角度思考
Internet 指的是最大的 network， 小写的internet 指的是network这一总体概念。
上图：
大部分low level network 是由 以太网支持的，
上图：
世界各地的主机通过router进行通信，
上图：
这些协议一般包含命名规则（name scheme）,和一些 发送机制（delivery mechanism）。
上图：
这些（和其他）问题是由被称为计算机网络的系统领域来解决的
上图：
IP 定义了命名主机的方法，发送包的方法，底层的IP协议并不能保证包被成功发送。
作为一个程序员，要利用所有网络层次，
我们可以把它想象成文件IO，一端持续向文件写入数据，数据不断通过网络发送到另一端。
注：
网络编程中的字节序是大端模式，
IPv4, 32bit ,所以最多是 2^32 约等于 40 亿个节点，
所以，IPv6 从 32 bit 扩展到了 128 bit , 它已经是一个20年（2021）的老技术了，但是知道今天它的采纳率仍然很低，
IPv4 32bit, 点分十进制，例如 192.168.137.1 (记忆：32/8)
IPv6 128bit, 冒号分十六进制， 例如，abcd:0000:0000:0000:0000:0000:0000:0000 (记忆：128/16)
上图：
现在大部分机器都是 小端字节序，但是网络中仍然使用的是大端字节序，
上面的四个函数可以保证host(无论是大端还是小端的host) 都能和network进行正确的转换，
需要注意的是，这些函数没有用于转化64bit(8个字节） 的函数， 这就要我们自己编写一个函数来实现这一功能了！！！
问题：如何从域名映射到IP地址？
可以有多个域名对应同一个IP，而且一个域名也可能对应多个IP， 也可以是多对多，
上图：端口是一个 16bit的整数， 客户端上端口分配是动态分配的， 称之为临时端口，
上图：
sockaddr 这个结构体本质上是一个16个字节长的东西，特殊的地方是就是头两个字节，头两个字节指明了这个socket 是什么类型的， 例如：TCP socket，UDP socket，等
上图：
sockaddr_in 用于IPv4 ,不是IPv6,因为sin_addr 是4个字节，我们可以把sockaddr_in 看成是sockaddr 的一个子类，
上图：
getaddrinfo() 它是C语言中的一个新函数，它同时适用于IPv4 和 IPv6 ,
上图：
getaddrinfo() : host ,service ,hints 输入之后，它会返回一个result 。实际上host 或 service（port） 至少提供一个就行了
freeaddrinfo（）用于释放result所占用的空间，
上图：
getaddrinfo 返回的是一个链表，
例如，传入twitter.com , 它会返回几个不同的address,
总结：可以把它们看做是 nslookup 的简易版！
上图：
socket() 返回了一个int , 它实际是一个文件描述符，
上图：
bind 会 将socket 函数返回的文件描述符 和 server sock address 绑定在一起，
bind() 是一个 kernel call ,
上图：
listen() 将socket 转换成监听状态，
上图：
accept（）在服务端会返回另一个文件描述符， server 通过这个fd 与client通信，
上图：
之所以server要有listenfd 和 connfd 是因为server想要和多个client通信，
Lecture 20 Network Programming: Part II
先看简单的部分（client），
上图中的connect() 会挂起等待是否连接到服务端，可以设置timeout，
上图：
accept会一直阻塞，无限期等待直到客户端来连接，
总结：network programming中 重要的几个结构体 和 一些函数
1，in_addr (4个字节长度)
in_addr 用于IPv4
2,sockaddr和 sockaddr_in（它们都是16个字节长度）
sockaddr 是更一般性的 socket addr 它的前两个字节为Protocol family
sockaddr_in（用于IPv4） 可以理解为sockaddr 的子类，它的前两个字节为protocol family,接着两个字节为 port number（big endian） , 接着是4个字节的 in_addr(真实的 binary form ip 地址)， 最后是8个字节的 0（它为的是和sockaddr 长度一致）。
那个时候，C语言还没有void *, 所以connect ,bind ,accept 函数的需要的参数类型都是更为通用的sockaddr，在具体使用的时候，我们将自己的参数强转为sockaddr ，例如：我们用的是IPv4的sockaddr_in ，传入connect，bind，accept的时候，需要强制转为更为一般的sockaddr.
3，getaddrinfo() 和 getnameinfo()
这两个函数是为 下面socket() accept() connect() 等更方便提供参数的，有了它们，我们就可以编写出适用于IPv4和IPv6 的通用代码了。
它提供了 sockaddr 和 host/service（text form） 的相互转换，
对于 getaddrinfo() 提供好host，service（port）至少一个， 提供好 hints条件，然后就会得到 result（链表）。
对于 getnameinfo() 提供好sockaddr ,提供好 host，service（port） 的buf，然后就会将host 和 port 的结果就会放到 对应的buf 中。
#include#include // for getaddrinfo() getnameinfo() #include // for exit() #include <string.h> // for memset() #include // for ntohs() net to host uint16 int main(int argc, char *argv[]) { struct addrinfo hints,* listp; //hints 为限制条件 listp 为result memset(&hints,0,sizeof(struct addrinfo)); // 先将 hints 要 set to 0 hints.ai_family = AF_INET; // ip4 only hints.ai_socktype = SOCK_STREAM; // TCP only int rc; // return code if( (rc = getaddrinfo(argv[1],argv[2],&hints,&listp) != 0) ){ fprintf(stderr,"getaddrinfo error:%s\n",gai_strerror(rc)); exit(1); } // 遍历 listp struct addrinfo *p; char host[256]; char port[256]; for(p=listp;p;p=p->ai_next){ getnameinfo(p->ai_addr,p->ai_addrlen,host,sizeof(host),port,sizeof(port),NI_NUMERICHOST); printf("host: %s\n",host); printf("port: %s\n",port); printf("===addrinfo===\n"); printf("flags:%d\n",p->ai_flags); printf("family:%d\n",p->ai_family); printf("socktype:%d\n",p->ai_socktype); printf("protocol:%d\n",p->ai_protocol); printf("ai_canonname:%s\n",p->ai_canonname); printf("addrlen:%d\n",p->ai_addrlen); printf("sockaddr.sa_family:%d\n",p->ai_addr->sa_family); struct sockaddr_in* ip4_addr = (struct sockaddr_in*)p->ai_addr; printf("port:%d\n", ntohs(ip4_addr->sin_port)); // 注意： big endian -> small endian } return 0; } /* OUTPUT： zcb@zcb-virtual-machine:~/test/csapp_project/lecture17$ ./a.out localhost 80 host: 127.0.0.1 port: http ===addrinfo=== flags:0 family:2 socktype:1 protocol:6 ai_canonname:(null) addrlen:16 sockaddr.sa_family:2 port:80 zcb@zcb-virtual-machine:~/test/csapp_project/lecture17$ ./a.out localhost 8888 host: 127.0.0.1 port: 8888 ===addrinfo=== flags:0 family:2 socktype:1 protocol:6 ai_canonname:(null) addrlen:16 sockaddr.sa_family:2 port:8888 zcb@zcb-virtual-machine:~/test/csapp_project/lecture17$ ./a.out localhost 443 host: 127.0.0.1 port: https ===addrinfo=== flags:0 family:2 socktype:1 protocol:6 ai_canonname:(null) addrlen:16 sockaddr.sa_family:2 port:443 zcb@zcb-virtual-machine:~/test/csapp_project/lecture17$ ./a.out baidu.com 7777 host: 39.156.69.79 port: 7777 ===addrinfo=== flags:0 family:2 socktype:1 protocol:6 ai_canonname:(null) addrlen:16 sockaddr.sa_family:2 port:7777 host: 220.181.38.148 port: 7777 ===addrinfo=== flags:0 family:2 socktype:1 protocol:6 ai_canonname:(null) addrlen:16 sockaddr.sa_family:2 port:7777 */
Web Server Basics
上图：
HTTP和TCP协议都是基于IP协议（internet protocol）的，
Lecture 21 Concurrent Programming
Lecture 22 Synchronization Basics
Lecture 23 Synchronization Advanced
Lecture 24 Thread Level Parallelism
最后编辑于 2021-02-27 14:49