CSAPP

本文最后更新于:2021年11月19日 晚上

看到第四章才发现看的第二版,偶emo了。。。。
第三版和第二版差别还是挺大的。
我找到的第三版电子书还是彩色的
暂时记录部分笔者看CSAPP的笔记,参考Kipery的笔记。
Kipery,yyds!!!

计算机系统漫游

由于系统中所有信息都是由比特表示,因此区分不同数据对象的唯一方法是上下文.
如对于hello.c,其编译系统的执行如下:


graph TD
  编写hello.c--源程序文本-->x(预处理器)
  x -->|hello.i--被修改的文本| y(编译器)
  y -->|hello.s--汇编程序| z(汇编器)
  z -->|hello.o--可重定位目标程序二进制| m(链接器)
  m-->|hello--可执行目标程序二进制| exe

为了解决处理器与主存之间的速度差距,系统设计者采用了高速缓存存储器,由此形成了具有层次结构的存储设备。为了操控硬件,程序通过操作系统控制硬件。操作系统的两个基本功能是:

  1. 防止硬件被失控的程序滥用
  2. 控制复杂而又广泛不同的低级硬件
    程序运行时,操作系统提供进程的假象,使程序看起来好像在独占硬件。这种进程之间的转移通过上下文(进程运行所需的所有状态信息)切换实现。
    虚拟存储器为每个进程提供假象,虚拟地址空间由:
  • 程序代码和数据,包括全局变量以及只读变量
  • 堆,主要是调用内存时分配或释放函数,运行时相当于动态的扩展和收缩
  • 共享库,地址中间用来存放c的库函数这些共享的数据
  • 栈,位于用户的虚拟地址空间顶部,编译器调用它来实现函数调用
  • 内核虚拟存储器,地址最顶部为内核保留,不允许程序读/写/执行该区域,应用程序只能调用内核来执行这些操作
    从上至下分区。

程序执行和结构

信息的表示和处理

信息存储

机器级程序将存储器视为一个极大的字节数组(虚拟存储器),存储器的每一个字节都由一个唯一的数字标识(地址),所有地址的集合成为虚拟地址空间。

我们以16进制来书写位模式,通过展开每一个16进制数字可以得到2进制,而把二进制高位补0至有4的倍数的位数则可以转为16进制。如:

  • 16 0x173A4C
  • 2 0001 0111 0011 1010 0100 1100
    每台计算机都有一个字长,对一个字长为n位的计算机,其虚拟地址范围为0~2^n-1,32位字长的虚拟地址空间为4GB
    对于一个w位的整数,其最高有效字节包括x w-1 ~ x w-8,最低有效字节包括x 7 ~ x 0。机器在存储器中按最低有效字节到最高有效字节存储则称为小端法,反之为大端法
    字符串以ASCII表示,因此具有更强的平台独立性,而unicode则可以表示包括英语在内的几乎所有语言

整数表示

负数常以二进制补码表示,即将最高有效位设置为1表示负,设置为0表示正。
有符号整数与无符号整数的强制类型转换只是改变了如何解释参数的位。给定一个整数x,类型转换将确定唯一一个整数y.显式类型转换由程序设计者确认,而隐式类型转换则可能导致错误:

1
2
3
4
int x=-1;
unsigned y=0;
if(x<y) cout<<"yes";
else cout<<"no";

上面程序的输出结果是no,原因就在于程序对-1进行了隐式类型转换,表达式等价于4294967295U<0U,因此出错。
当将一个无符号数字转为较大类型(字长增加)时,通常在开头加0即可;而对于有符号整数,我们可以执行符号扩展,即在表示中添加最高有效位的值。若机器字长为1位,则由
$x_{w-1},x_{w-2},…,x_{0}$变为$x_{w-1},x_{w-1},x_{w-2},…,x_{0}$这样由于$-2^{w}+2^{w-1}=-2^{w-1}$,运算后就会保持原有数值

整数运算

无符号整数通过舍弃高位来计算,相当于计算%2^w的和。假设我们一共有四位,如9【1001】+12【1100】=21【10101】,舍弃高位得到5【0101】,即21%16=5(我们共有4位)。有符号整数(或二进制补码)加法则也有类似的问题,具体表现为溢出。
无符号乘法仍定义为低w位表示的值,仍等价于计算%2^w的值。二进制补码乘法相同。
由于整数乘法/除法相当的慢,因此编译器试图通过1个时钟周期+,-,位级运算,移位来代替乘法。而在这种情况下,即使溢出,我们通过移位得到的结果也是正确的。

浮点

采用IEEE标准,即
$$V= \left ( -1 \right ) ^{s} \times M\times 2^{E} $$
来表示一个数:

  • 符号s决定正负
  • 尾数M作为有效数,是一个二进制小数(n位)
  • 阶码E对于浮点数加权(k位)
    需要注意的是,浮点数中的阶码并非真正的
    $$2^{exp} $$
    而是需要减去一个偏移,该偏移为
    $$ offset=2^{n-1}-1 $$
    其中n为阶码位数,真正的阶码为
    $$2^{exp-offset} $$
    单精度表示中,n,k,s分别为23,8,1位,双精度表示中则分别为52,11,1
    浮点数编码的值有4种情况,下面是单精度时的4种对应情况:
  • 规格化:exp!=0&&exp!=255时
  • 非规格化:exp==0
  • 无穷大: exp == 255 && frac == 0
  • NaN(not a number):exp==255&&frac!=0

尽管浮点数可表达的范围较大,但当浮点数越来越大时,其精度会越来越小;当浮点数越来越小时,其精度也会越来越大。不管精度如何变化,这其中始终存在一个范围。
关于舍入,CSAPP提供了四种舍入方式:

通常情况下,任何正常人都应该想到的是浮点运算可以把浮点数看作实数运算进行,但对于浮点运算来讲,存在一些可能致命的威胁:

  • 加法/乘法没有可结合性:
1
2
x=a+b+c;
y=b+c+d;

编译器可能通过下面的优化来减少加法次数:

1
2
3
t=b+c;
x=a+t;
y=t+d;

x很有可能因为加法顺序不同导致舍入结果不同

程序的机器级表示

常用汇编指令:

  1. 三种操作数指示符:
    立即数—$-577
    寄存器
    存储器
  2. 数据传送:
1
2
3
4
5
movl $0x4050,%eax  立即数到寄存器
movl %ebp,%esp 寄存器到寄存器
movl (%edi,%ecx),%eax 存储器到寄存器
movl $-17,(%esp) 立即数到存储器
movl %eax,-12(%ebp) 寄存器到存储器


3. 条件:

1
2
3
jmp .L1  直接跳转到L1
jmp *%eax 将寄存器%eax中的值作为跳转目标
jmp *(%eax) 将%eax中的值作为读地址,从存储器中读出跳转目标

过程

  • 为单个过程分配的那部分栈称为栈帧,其最顶端以%ebp作为帧指针,以%esp作为栈指针,程序执行时栈指针将移动。因此要访问则需要帧指针,有一个形象的程序可以说明这些操作:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int swap_add(int *xp,int *yp){
int x=*xp;
int y=*yp;
*xp=y;
*yp=x;
return x+y;
}
int caller(){
int arg1=534;
int arg2=1057;
int sum=swap_add(&arg1,&arg2);
int diff=arg1-arg2;
return sum*diff;
}

其栈帧如下:

数组

数组A[4][3]被按照行优先的顺序存储,下面的例子拷贝A[i][j]到寄存器%eax:

1
2
3
4
sall $2,%ecx
leal (%edx,%edx,2),%edx
leal (%ecx,%edx,4),%edx
movl (%eax,%edx),%eax

因此当我们使用二维数组时,可以从机器取元素的方式考虑减少程序时间,把数组中频繁用到的数字存取至同行,而不是A[0][0],A[1][0],A[2][0]这样的跳行式存取

错误

由于c对于数组引用不进行边界检查而局部变量和状态信息存储于栈中,所以当两种情况都发生时,数组越界+写操作将破坏栈中的状态信息。
缓冲区溢出:例如在栈中分配某一个字节数组保存字符串而字符串长度超越数组分配的空间。这会导致所有后来的栈引用都是非法的。程序将返回错误地址。另外,输入一个包含可执行代码的字符串,将会使程序执行它不应该执行的函数
第二版补充(来自第三版的知识):

实现条件操作的传统方法是通过使用控制的条件转移,例如各类跳转指令。这种机制十分简单而通用。但在现代处理器上,它可能会非常低效。一种替代策略是使用数据的条件转移。这种方法计算一个条件操作的两种结果,然后根据条件是否满足从中选取一个。如果这种策略在某些情况下可行,则只需用一条简单的条件传送指令来实现.

处理器体系结构

一些“常识”:

  • 一个处理器支持的指令和指令的字节级编码称为他的ISA(instruction-set architecture)
  • ISA模型看上去是顺序执行,实际上为了获得更高性能,人们采用了特殊机制,同时处理多条指令的不同部分
  • HCL(hardware control language),硬件控制语言

Y86

  • 八个程序寄存%eax,%ecx,%edx,%ebx,%esi,%edi,%esp,%ebp;其中%esp被入栈出栈调用和返回指令作为栈指针
  • 条件码:ZF,SF,OF
  • 指令:
1
2
3
4
5
6
7
8
9
10
irmovl,rrmovl,mrmovl,rmmovl   
//源可以是立即数i,寄存器r,存储器m;目的可以是寄存器r,存储器m
addl,subl,andl,xorl
//只对寄存器数据进行操作
jmp,jle,jl,je,jne,jge,jg
//跳转指令
call,ret
//call将返回地址入栈,ret从过程中调用返回
pushl,popl//入栈,出栈
halt//停止指令的执行

鉴于学习任何语言都是要实操的,因此我们直接来程序。
这是c:

1
2
3
4
5
6
7
8
9
int Sum(int *Start,int Count){
int sum=0;
while(Count){
sum+=*Start;
Start++;
Count--;
}
return sum;
}

这是一个c在处理后的变化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Sum:
pushl %ebp
rrmovl %esp,%ebp
mrmovl 8(%ebp),%ecx ecx=Start
mrmovl 12(%ebp),%edx edx=Count
xorl %eax,%eax sum=0
andl %edx,%edx
je End
Loop:
mrmovl (%ecx),%esi get *Start
addl %esi,%eax add to sum
irmovl $4,%ebx
addl %ebx,%ecx Start++
irmovl $-1,%ebx
addl %ebx,%edx Count--
jne Loop Stop when 0
End:
rrmovl %ebp,%esp
popl %ebp
ret

HCL

要实现一个数字系统需要三个主要的组成部分:计算位的函数的组合逻辑、存储位的存储器元素、控制存储器元素更新的时钟信号

  • 逻辑门语法:a&&b,a||b,!a分别对应And,Or,Not.
  • 组合电路满足两个要求:1. 两个及以上的逻辑门的输出不能接在一起 2. 这个网必须无环
  • 例如测试A和B是否相等,只需要测试A和B的每一位是否相等,最后用AND连起来即可
  • 多路复用函数采用case来描述,在最后一个case中为1,如一个找出A、B、C最小值的逻辑电路:
1
2
3
4
5
int Min3={
A<=B&&A<=C :A;
B<=A&&B<=C :B;
1 :C;
};

Y86的ALU:

  • 由于组合电路实际上不存储信息而是对信息作出响应,因此为了产生时序电路(以时间/顺序为状态且在这个状态上进行计算的系统),我们需要时钟寄存器随机访问存储器
    时钟寄存器:被时钟信号控制,如果产生了一个新的寄存器输入,但时钟是低电位,寄存器输出就仍为上个输出,当时钟变为高电位时,输入信号就加载到寄存器
    随机访问存储器:用地址选择该读/写那个字,通常是多端口随机访问存储器

Y86的顺序实现

现代处理器是顺序执行的,为此指令需要组成某个特殊的阶段序列:

  • 取指
  • 解码
  • 执行
  • 访存
  • 写回
  • 更新

SEQ

该部分来自kp
抽象视图
SEQ的阶段实现:

  • 取指:以PC作为第一个字节的地址,指令内存硬件单元会一次从内存读出10个字节,并将第一个字节分隔成两个4位的数来计算指令和功能码,PC增加硬件单元会根据当前PC以及CPU内的信号生成下一条指令的PC。即:
    $$\mathit{newPC} = \mathit{oldPC}+ 1 + r + 8i $$
    其中r为当前指令是否需要寄存器指示字节,i为需要的常数字节数
  • 解码和写回:指令字段解码,产生寄存器文件需要的四个地址的标识符,从寄存器文件中读出的值为valA,valB,写回值为valE和valM
  • 执行:该阶段包括ALU,对输入的aluA/aluB执行特定操作,每次运行时产生三个与条件码相关的信号:0,符号,溢出;同时确定是否进行条件分支或条件数据传送
  • 访存:对主存,寄存器文件进行读写
  • 更新PC:根据指令类型以及是否选择分支来设置新的PC。若没有,则用取指计算新的PC值

优化程序性能

程序员必须编写容易优化的代码,以帮助编译器

编译器的优化能力有限

编译器必须执行的是安全的优化,CSAPP举了一个十分形象的例子来说明:

1
2
3
4
5
6
7
8
void twiddle1(long *xp,long *yp){
*xp+=*yp;
*xp+=*yp;
}

void twiddle2(long *xp,long *yp){
*xp+=2* *yp;
}

我们分析以下这两个函数,他们的行为似乎是相同的。而twiddle1执行了两次对*xp的读,两次对 *yp的读、两次对 *xp的写,twiddle2执行了一次读 xp,一次读 yp,一次写 xp,似乎twiddle2更快。但是CSAPP提出了一个问题:当xp == yp时,是否仍满足上述情况?
显然,xp == yp时,twiddle1将使
xp的值变为之前的4倍,而twiddle2将使 xp的值变为原先的3倍------因此twiddle1不能优化为twiddle2那样
上面的情况叫做
内存别名使用
,如果编译器不确定指针是否指向同一个位置,那就必须假设有这种可能。

表示程序性能

  • CPE(cycles per element)用来度量迭代程序的循环性能
  • 如对于第一个普通代码以及第二个采用了循环展开的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void p1(float a[],float p[],long n){
long i;
p[0]=a[0];
for (i=1;i<n;i++){
p[i]=p[i-1]+a[i];
}
}
void p2(float a[],float p[],long n){
long i;
p[0]=a[0];
for(i=1;i<n-1;i+=2){
float mid=p[i-1]+a[i];
p[i]=mid;
p[i+1]=mid+a[i+1];
}
if(i<n){
p[i]=p[i-1]+a[i];
}
}


其运行时间分别近似于368+9n和368+6n

  • 代码移动:
1
2
3
4
5
6
7
8
9
10
void combine(vec_ptr v,data_t *dest){
long i;
long length=vec_length(v);
*dest=IDENT;
for(i=0;i<length;i++){
data_t val;
get_vec_element(v,i,&val);
*dest=*dest OP val;
}
}

在上述代码中,把for循环中i < vec_length(v)放到外面,写作i < length,将时间缩小了很多,而优化的时间决定于vec_length(v)的执行时间。加入执行时间为length,则运行时间将由o(n^2)减到o(n)

  • 减少过程调用/消除不必要的内存引用

每次迭代时,累积变量的数值都要从内存读出在写入,然而每次迭代开始时读出的值就是上次迭代最后写入的值

我们可以用一些int,long之类的临时变量完成迭代最后赋值给数组,这样就改变了频繁的对数组的读写。在CSAPP给出的例子中,消除不必要的内存引用调用优化的时间甚至相当于未减少前-o2优化后的时间

理解现代处理器

现代处理器同时对多条指令求值(指令级并行),采用了复杂而奇异的结构,同时在代码级上呈现出简单的顺序执行指令的表象

  • 流水线化:一个典型的浮点加法器包含处理指数值、将小数相加、对结果舍入三个阶段,算术运算不需要等待一个操作完成后再开始下一个,而是连续的通过各个阶段。除法不能这样。

存储器层次结构

存储器系统实际上是一个具有不同容量、成本、访问时间的存储设备

  • RAM,随机访问存储器,静态的SRAM比动态的DRAM更快,SRAM用于高速缓存存储器,DRAM用于主存或者图形系统的帧缓冲区
  • SRAM的稳定性:
  • DRAM对干扰十分敏感,但由于计算机运行的时钟周期以纳秒衡量,因此没事,来看图:
  • 由于断电后,SRAM、DRAM会丢失他们的信息,因此他们是易失的,而非易失存储器仍能保留信息。如基于闪存的固态硬盘
  • 数据流通过总线(bus)在处理器和DRAM主存之间来回

局部性

时间局部性/空间局部性:倾向于引用最近引用过的数据项的数据项

通用的高速缓存

  • 一般而言,高速缓存的结构可以用元组(S,E,B,m)来描述,高速缓存的大小C=S* E *B
  • 在缓存中找字类似于哈希表,如图:

直接映射高速缓存

  • 每一个组只有一行的高速缓存被称为直接映射高速缓存
  • 请求数据的流程如下:
  1. 组选择–从主存地址中的特定偏移处抽取s个组索引,这些位被解释成一个对应的无符号整数高速缓存组号。
  2. 行匹配–直接映射高速缓存中每组只有一个高速缓存行。如果当前行的有效位已经设置,并且标记(tag)匹配,则缓存命中。
  3. 字选择–根据后b位的块内偏移来获取所需的字
  4. 行替换:如果缓存不命中,则需要从下一级存储层次结构中取出请求的块,并驱逐并替换高速缓存行。
    优点是唯一映射,命中时间小;缺点是缺失率高,关联度低
  • 抖动—高速缓存反复加载和驱逐相同的高速缓存块的组,方法是在每一个数组的结尾放B字节的填充

组相连高速缓存

  • 他必须检查多个行的标记位和有效位,其中的每一个组都可以看成一个小的相连存储器。高速缓存必须搜索组中的每一行,如果命中,就块偏移选择一个字
  • 未命中则采用LRU策略替换最后一次访问时间最久远的那一行

全相连高速缓存

唯一的一组:

  • 其数据选择:

写策略

  • 写命中
  1. 直写,同时写cache和主存,较慢
  2. 回写,只写cache,缺失/更新时一次写回,控制更复杂
  • 不命中
  1. 写分配:将主存装入cache,然后更新
  2. 直接写进主存单元

在系统上运行程序

链接

链接是将各种代码和数据片段收集并组合为一个单一文件的过程

静态链接示例:
链接器的主要任务:

  • 符号解析
  • 重定位

可重定位目标文件

  • .text 已经编译程序的机器代码
  • .rodata只读数据
  • .data 已初始化的全局和静态变量
  • .bss未初始化的全局和静态变量
  • .symtab 符号表,存放在程序中定义和引用的函数和全局变量的信息
  • .rel.text 一个.text节中位置的列表
  • .rel.data所有全局变量的重定位信息
  • .debug调试符号表
  • .line 源程序中的行号和.text节中机器指令之间的映射
  • .strtab 字符串表

符号和符号表

每一个可重定位模块m都有一个符号表,

  • m定义并被其他模块引用的全局符号
  • 其他模块定义并被m引用的全局符号
  • 只被m定义引用的局部符号

链接器

规则:

  • 不允许多个同名的强符号(main以及初始化的全局变量等)
  • 选择强符号(强符号+多个弱符号)
  • 多个弱符号同名时任意选择一个
    静态库:相关函数被编译为独立的目标模块,然后被封装成为单独的静态库文件

动态链接共享库

共享库可以加载到任意的内存地址,并在和一个内存中的程序链接起来。linux中以.so表示,windows称为dll

此处仅作摘要

  • PIC数据引用:代码段中任何指令和数据段中任何变量之间的距离都是一个运行时常量,通过全局偏移量表实现

库打桩

截获对共享库函数的调用,执行自己的代码。通过欺骗系统来实现。

本节知识似乎并不能很好的应用于实践,笔者打算做lab时在深入学习。

异常控制流

现代系统通过使控制流突变来应对特殊情况。这被称作异常控制流ECF

异常

异常就是控制流中的突变,用来响应处理器状态中的某些变化


系统为每一种的异常都分配了唯一的非负整数的异常号,存在异常表里。

下表来自kipery

类别 原因 异步/同步 返回行为
中断(interrupt) 来自I/O设备的信号 异步 总是返回到下一条指令
陷阱(trap) 有意的异常 同步 总是返回到下一条指令
故障(fault) 潜在可恢复的错误 同步 可能返回到当前指令
终止(abort) 不可恢复的错误 同步 不会返回
  • 中断
  1. 异步发生,一些I/O设备或芯片通过向CPU上的某个引脚发送信号,并将异常号放至系统总线上来触发中断。
  2. 在当前指令执行完成后,CPU注意该引脚上的电压变为高电平,则获取异常号并调用中断处理程序,最后将控制流返回到下一条指令。
  • 陷阱
  1. 先来解释名字,陷阱其实只是一个有意的异常,经常用于用户程序向内核提供接口。当用户想要请求某个服务时,可以通过"syscall n"指令来调用适当的内核程序。即完成系统调用
  • 故障
  1. 可能能被故障处理程序修正
  2. 经典的故障是缺页异常,即程序引用一个不存在于内存的虚拟地址而导致必须从磁盘中取出时。
  • 中止
  1. 不可恢复的致命错误造成的结果

进程

异常是允许操作系统内核提供进程概念的基本构造块,而进程是计算机科学中最深刻、最成功的概念之一。

进程提供给应用程序两个关键抽象:

  • 一个独立的逻辑控制流
  • 一个私有的地址空间
    进程欺骗了每一个程序,让他们以为自己是唯一被爱的那个。然而计算机是博爱的,进程充当了欺骗程序的帮手。
    考虑一个运行着三个进程的系统,处理器的一个物理控制流被分为三个逻辑流。实际的执行过程是交替的,每一个进程执行他的一部分,然后就被抢占。注意处理器并不改变程序内存位置或者寄存器内容。
  • 一个逻辑流的执行在时间上与另一个重叠,称为并发流。需要注意的是,即使两个流运行在同一个处理器上,他们在时间上只要重叠,那他们就是并发流。
  • 如果两个流并发的运行在不同的处理器上,那么他们就是并行流
  • 进程为每一个程序提供它在独占的使用系统地址空间的假象,渣男一般而言,进程提供的地址空间是私有的
  • 处理器设置模式位来提供对于用户模式内核模式的分辨。没有设置时为用户模式,此时不能操作内核,如停止处理器,改变模式位
  • 内核为每一个进程维持一个上下文–内核重新启动一个被抢占的进程所需的状态。内核决定抢占当前进程的决策叫做调度

进程控制

  • 首先获取进程ID,即PID
1
2
3
4
#include <sys/types.h>
#include <unistd.h>
pid_t getpid(void);
pid_t getppid(void);
  • 作为一个程序员,我们可以认为进程总是处于以下三种状态之一:
  1. 运行
  2. 停止,挂起
  3. 终止
    使用fork创建子进程的父进程示例:
1
2
3
4
5
6
7
8
9
10
11
int main(){
pid_t=pid;
int x=1;
pid=Fork();
if(pid==0){
printf("child:x=%d\n",++x);
exit(0);
}
printf("parent: x=%d\n",--x);
exit(0);
}

程序输出:

1
2
parent :x=0;
child:x=2;

即:

  • 调用一次,返回两次,一次父进程,一次新创建的子进程
  • 并发执行,两个逻辑控制流
  • 相同但独立的地址空间
  • 共享文件,当父进程调用fork时,stdout打开,子进程继承了这个文件,因此他的输出并没有打开一个新窗口
  • 当进程终止时,直到其父进程被回收,该进程才被内核清除。在子进程终止但还未被回收时,他被称作僵尸进程
  • 如果父进程未回收其僵尸子进程就终止了,所有进程的祖先–init会去回收那些孤儿进程
  • waitpid,挂起调用进程的执行,直到他的等待集合中的一个子进程终止。如果等待时一个进程已经终止,那waitpid就立即返回
  • sleep,将一个进程挂起一个指定时间;pause,让函数休眠直到该进程收到一个信号
  • execve在当前进程的上下文加载并运行一个新程序

信号

一个信号就是一个消息,他同志进程系统中发生了一个某种类型的事件。下面是linux只是的30种不同类型的信号:

  • 发送信号,两个原因:1.内核检测到一个系统事件2.一个进程调用了kill函数
  • 接受信号:目的进程被内核强迫以某种方式对信号的发送作出反映

发送信号

每一个进程属于一个进程组,进程组由一个正整数ID表示

1
/bin/kill -9 15213

发送信号9给进程15213

1
2
3
#include <sys/types.h>
#include <signal.h>
int kill(pid_t pid,int sig);

进程通过调用kill函数发送信号给包括自己在内的进程

接收信号

每一个信号类型都由一个预定以的默认行为:

  • 进程终止
  • 进程终止并转储内存
  • 进程挂起直到被重启
  • 进程忽略该信号

非本地跳转

他将控制直接从一个函数转移到另一个当前正在执行的函数,不需要经过正常的调用-返回序列。
非本地跳转通过setjmp和longjmp函数来提供实现的

  • setjmp/sigsetjmp
    setjmp函数会在env缓冲区中保存当前的调用环境,以供longjmp使用,同时返回0。
    调用环境包括程序计数器,栈指针和通用目的寄存器等等
    setjmp返回值无法赋值给变量
  • longjmp/siglongjmp
    longjmp函数从env缓冲区中恢复调用环境,然后触发一个从最近一次初始化env的setjmp调用的返回。
    然后setjmp返回,并带有非零的返回值retval。

应用

  • 允许从一个深层嵌套的函数调用中立即返回,检测到错误时可以使用
  • 使一个信号处理程序分支到一个特殊的代码位置。
    大晚上不想写代码了,看书摸鱼

虚拟内存

随着电脑对CPU需求的增长,进程合理的以一种平滑方式慢了下来,为了更有效的管理内存并且少出错,现代系统提供了一个叫虚拟内存的抽象概念

虚拟内存的三个能力:

  1. 将主存看成是一个存储在磁盘上的地址空间的高速缓存,在主存中只保存活动区域,并根据需要在磁盘和主存之间来回传送数据
  2. 为每一个进程提供了一致的地址空间,从而简化了内存管理
  3. 他保护了每一个进程的地址空间不被其他进程破坏
    虚拟内存默默运行,但却存在危险性:带有错误指针的程序可以立即崩溃,也可以默默运行几个小时再崩溃,或者产生不正确的结果
  • 计算机系统的主存被组织成一个由M个连续字节大小的单元组成的数组,每一个字节都有唯一的物理地址
  • 现代小型计算机的CPU生成一个虚拟地址,虚拟地址被动态翻译成为物理地址。如图:
  • 地址空间是一个非负整数地址的有序集合,一个地址空间的大小由表示最大地址所需要的位数来表示,如一个包含N=
    $$2^{n}$$
    个地址的虚拟地址空间就叫做一个n位地址空间
  • 任意时刻,虚拟页面的集合都分为三个不相交的子集:
  1. 未分配的:VM系统未分配的页
  2. 缓存的:当前已经缓存在物理内存中的已分配页
  3. 未缓存的:未缓存在物理内存中的分配页
  • 页表就是一个页表条目的数组。页表条目(PTE)由一个有效位加一个n位地址字段组成,如图所示:
  • 如果工作集的大小超过了物理内存的大小,那么程序将抖动。页面将不断的换进换出
    虚拟简化了链接和加载,代码和数据共享,以及应用程序的内存分配,主要体现在以下方面:
  • 允许每个进程的内存映像使用相同的基本格式
  • 加载器无需从磁盘到内存实际复制数据,而是由虚拟系统自动调入数据页
  • 使每一个进程都有自己私有的代码,数据,堆,栈区域
  • 使操作系统没有必要分配连续的物理内存页面
  • 通过虚拟内存保护实际内存

地址翻译

我们的目的是把一个N元素的虚拟地址空间映射到一个M元素的物理地址空间:
$$ MAP:VAS\longrightarrow PAS\cup \varnothing $$
页面命中:

  1. 处理器生成虚拟地址传给MMU(分页内存管理单元,位于CPU)
  2. MMU生成PTE地址,并从高速缓存/主存请求得到
  3. 高速缓存/主存向MMU返回PTE(页表条目)
  4. MMU构造物理地址,传给高速缓存/主存
  5. 高速缓存/主存返回请求的数据给处理器

    缺页:
  6. 上述的1~3
  7. PTE有效位为0,MMU触发异常,传递CPU中的控制到操作系统内核中的缺页异常处理程序
  8. 缺页处理程序确定物理内存的牺牲页
  9. 缺页处理程序调入新的页面,更新PTE
  10. 再次执行导致缺页的指令,命中
    为了加速地址翻译,可以:
  • 使用高速缓存
  • 使用TLB,即在MMU中包括一个关于PTE的小缓存
  • 多级页表层次:

    9.9节让我深刻意识到了malloc的复杂,还是java适合设计软件
    CSAPP的9.9~9.11分别叙述了动态内存分配的实现、垃圾回收以及其危险性,实在劝退了我,因此暂时不予记录。在做实验的时候学习。

程序间的交流和通信

当学完了这一部分,你将逐渐变成一个很牛的程序员

系统级I/O

这一部分主要讲的是函数。。。。。先鸽了

unix I/O

unix将所有的I/O模型化为文件,使所有输入输出以一种统一的方式来执行:

  • 打开文件,内核返回给应用程序一个非负整数–描述符,应用程序只需记住这个描述符
  • 每个进程开始时都有三个打开的文件:标准输入/输出/错误
  • 内核保存的文件位置k是从文件开头起始的字节偏移量
  • 一个读操作是从当前位置k开始然后将k增加到k+n

文件

常见的linux文件有:

  • 普通文件,包括文本文件和二进制文件
  • 目录,包含一组映射到文件的链接
  • 套接字,即socket,用来与另一个进程进行跨网络通信的文件

RIO包

网络编程

  • 客户端-服务器模型中的基本操作是事务
  • 物理上讲,网络是一个按照地理远近组成的层次系统。最底层是LAN(局域网),而目前最流行的局域网技术是以太网,从3Mb/s演变到10Gb/s,
  • 每一个以太网适配器都有一个全球唯一的48位地址,一台主机发送的帧可以被这个网段内的其他任何主机看到
  • 网桥把多个以太网段连接成较大的局域网
  • 路由器把多个不兼容的局域网连接起来,组成一个互联网络
    互联网采用增加一个运行在每台主机和路由器的协议软件来消除完全不同和不兼容的各种局域网的差异。该软件提供了两种基本能力:
  • 命名机制,每台主机至少被分配一个唯一的互联网络地址
  • 传送机制:定义一种把数据位捆扎成不连续的片-包的方式传送数据

封装就是关键

全球IP因特网

只讨论IPV4

IP地址

一个IP地址就是一个32位无符号整数,IP地址结构如下:

1
2
3
struct in_addr{
uint32_t s_addr;
};

因为因特网主机中可以有不同的主机字节序列,TCP/IP为任意整数数据项定义了一个统一的网络字节顺序(network byte order) —— 大端字节顺序。即使主机字节顺序是小端法。unix提供相应函数实现转换:

1
2
3
4
5
6
7
#include <arpa/inet.h>
uint32_t htonl(uint32_t hostlong);
uint16_t htons(uint16_t hostshort);
//返回:按照网络字节顺序的值
uint32_t ntohl(uint32_t netlong);
uint16_t ntohs(uint16_t netshort);
//返回:按照主机字节顺序的值

IP地址通常用点分十进制来表示,例如128.2.194.242就是地址0x800c2f2。

因特网域名

  • 因特网定义了一组域名(domain name)以及一种将域名映射到IP地址的机制,便于人们记忆。
  • 常见的一级域名有com,edu,gov,org,net,二级域名有cmu.edu等
    下面是因特网域名层次结构的一部分:

因特网连接

  • 连接是点对点、全双工、可靠的
  • 一个套接字是一个端点,对应一个套接字地址,由一个因特网地址和一个16位的整数端口组成,用“地址:端口”表示
  • 当客户端发起连接请求时,客户端套接字地址中的端口是由内核自动分配的,称为临时端口(ephemeral port)。但服务器套接字地址中的端口通常是某个知名端口,与服务相对应。
  • 一个连接是由两端的套接字地址唯一确定。这对套接字地址叫做套接字对(socket pair),由下列元组表示:(cliaddr:cliport, servaddr:servport)

套接字接口

  • 套接字接口(socket interface)是一组函数,它们和Unix I/O 函数结合,用以创建网络应用。
    如图:
  • 套接字地址结构
1
2
3
4
5
6
7
8
9
10
11
12
/* IP socket address structure */
struct sockaddr_in{
uint16_t sin_family; /* Protocol family (always AF_INET) */
uint16_t sin_port; /* Port number in network byte order */
uint16_t sin_addr; /* IP address in network byte order */
unsigned char sin_zero[8]; /* Pad to sizeof(struct sockaddr) */
}
/* Generic socket address structure (for connect, bind, and accept) */
struct sockaddr{
uint16_t sa_family; /* Protocol family */
char sa_data[14]; /* Address data */
}
  • 客户端和服务器使用socket函数创建一个socket:
1
2
3
#include <sys/types.h>
#include <syssocket.h>
int socket(int domain,int type,int protocol);
  • connect函数建立和服务器的连接
  • bind函数告诉内核将addr服务器套接字地址和套接字描述符sockfd联系起来。
  • 服务器调用listen函数告诉内核描述符是被服务器而不是客户端使用的
  • accept函数等待来自客户端的连接请求

并发编程

现代操作系统提供三种基本的构造并发程序的方法:

  1. 进程,使用显式的进程间通信机制(IPC)
  2. I/O多路复用
  3. 线程

基于进程的并发编程

在父进程中接受客户端连接请求,然后创建一个新的子进程来为客户端提供服务
示例:

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
#include "csapp.h"//别问我这是什么头文件
void echo(int connfd);
void sigchld_handler(int sig){
while(waitpid(-1,0,WNOHANG)>0)
;
return;
}
int main(int argc,char **argv){
int listened,connfd;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
if(argc!=2){
fprintf(stderr,"usage:%s <port>\n",argv[0]);
exit(0);
}
Signal(SIGCHLD,sigchld_handler);
listened=Open_listenfd(argv[1]);
while(1){
clientlen=sizeof(struct sockaddr_storage);
connfd=Accept(listenfd,(SA *) &clientaddr,&clientlen);
if(Fork() == 0){
Close(listenfd);
echo(connfd);
Close(connfd);
exit(0);
}
Close(connfd);
}
}
  • 我们需要一个SIGCHLD来回收僵尸子进程
  • 父进程必须关闭他的已连接描述符
  • 所有进程的connfd都关闭后到客户端的连接才终止
    优点是由独立的地址空间,缺点是往往比较慢,开销大

基于I/O多路复用的并发编程

对于每一个新的客户端,基于I/O多路复用的并发服务器会创建一个新的状态机,初始化后服务器调用select函数检测不同类型的输入事件,随之作出反应。可以说,I/O多路复用的抽象模型是状态机,具体实现依赖于select函数。相比于其他两种方式,I/O多路复用具有明显的性能优势,现代处理器也是采用I/O多路复用

基于线程的并发编程

在某一时刻,主线程创建一个对等线程,当主线程执行一个慢速系统调用或被中断,控制就会通过上下文切换传递到对等线程。两个线程并无本质区别。而在任何一个时间点上,线程都是可结合的/分离的。基于线程的并发服务器容易造成内存泄漏,必须小心的释放主线程分配的内存块

一般而言,无法预测操作系统是否为线程选择了一个正确的顺序


Edsger Dijkstra,提出了经典的解决同步不同执行线程问题的方法,信号量s只能由两种操作处理:

  1. P(s),若s!=0,p令s-1,若s == 0,就挂起这个线程
  2. V(s),v将s+1,如果有线程阻塞在p等待s变为!0,那么v会长期这些线程中的一个
    其余暂略

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!