• 第1章 计算机系统漫游
• 第2章 信息的表示和处理
• 第3章 程序的机器级表示
  • 程序编码
  • 访问信息
  • 算术和逻辑操作
  • 控制
  • 条件传送指令
  • 过程
• 第4章 处理器体系结构
  • Y86指令集体系结构
  • 逻辑设计和硬件控制语言HCL
  • Y86的顺序实现
  • 流水线的通用原理
  • Y86的流水线实现
• 第5章 优化程序性能
  • 编译器的能力和局限性
  • 表示程序性能
  • 程序示例
  • 消除循环的低效率
  • 减少过程调用
  • 消除不必要的存储器引用
  • 理解现代处理器*
  • 循环展开
  • 提高并行性
  • 限制因素
  • 理解存储器性能
  • 确认和消除性能瓶颈
• 第6章 存储器层次结构
  • 存储技术
  • 局部性
  • 存储器层次结构
  • 编写高速缓存友好的代码
  • 高速缓存对程序性能的影响
• 第7章 链接
  • 静态链接
  • 目标文件
  • 可重定位目标文件
  • 符号和符号表
  • 符号解析
  • 静态库
  • 重定位
  • 可执行目标文件
  • 共享库
  • 运行时加载和链接共享库
• 第8章 异常控制流
  • 异常
  • 进程
  • 进程控制
  • 信号
  • 非本地跳转
• 第9章 虚拟存储器
  • 物理寻址与虚拟寻址
  • 虚拟存储器作为缓存的工具
  • 虚拟存储器作为存储器管理的工具
  • 虚拟存储器作为存储器保护的工具
  • 地址翻译
  • 存储器映射
  • 动态存储器分配
  • 垃圾收集
  • 第10章 系统级I/O
    • Unix I/O
    • 打开和关闭文件
    • 读和写文件
    • 健壮地读写
    • 读取文件元数据
    • 共享文件
    • I/O重定向
    • I/O函数选择
  • 第11章 网络编程
    • 网络基础
    • 套接字接口
  • 第12章 并发编程
    • 基于进程的并发编程
    • 基于I/O多路复用的并发编程
    • 基于线程的并发编程
    • Posix线程
    • 多线程程序中的共享变量
• AT LAST ! Tiny Web Server

第1章 计算机系统漫游

执行gcc -o hello hello.c，完成从C语言代码到可执行文件的整个过程分为以下4个阶段：

hello.c源程序（文本）  
    ->  预处理器（cpp）  ->  hello.i被修改的源程序（文本）
    ->  编译器（ccl）    ->  hello.s汇编程序（文本）
    ->  汇编器（as）     ->  hello.o可重定位目标程序（二进制）
    ->  链接器（ld）     ->  hello可执行目标程序（二进制）

（基础内容，略）

第2章 信息的表示和处理

计算机使用字节（8位的块）作为最小的可寻址的存储单位，而不是在存储器中访问单独的位。存储器的每个字节都由一个唯一的数字来标识，称为它的地址。

对于跨越多字节的程序对象必须建立两个规则：这个对象的地址是什么，以及在存储器中如何排列这些字节。最低有效字节在最前面的方式称为小端法，最高有效字节在最前面的方式称为大端法。假设变量x的类型为int，位于地址0x100处，它的16进制值为0x01234567，地址范围为0x100~0x103字节，其排列顺序可能如下：

0x100  0x101  0x102  0x103
  01     23     45     67        大端法
  67     45     23     01        小端法

在不同类型的机器之间传送数据时，字节的顺序会称为问题。

（二进制编码表示及运算，比较基础，略）

第3章 程序的机器级表示

gcc编译器以汇编代码形式产生输出，汇编代码是机器代码的文本表示，给出了程序中的每一条指令。然后gcc调用汇编器和链接器，根据汇编代码生成可执行的机器代码。 Linux使用了平坦寻址方式，因此可以将整个存储空间（包括栈、堆等）看做一个大的字节数组。

程序编码

执行： gcc -O1 -o p p1.c p2.c 其中-O1指使用第一级优化。gcc会调用一系列程序来将源代码转化为可执行代码： 首先C预处理器扩展源代码，插入所有用#include指定的文件，并扩展所有用#define定义的宏； 然后编译器产生两个源代码的汇编代码:p1.s和p2.s； 接着汇编器将汇编代码转化为二进制目标代码：p1.o和p2.o，目标代码是机器代码的一种形式，它包含所有指令的二进制表示，但是还没有填入地址的全局值； 最后，链接器将两个目标代码文件与实现库函数的代码合并，并产生最终的可执行文件p。

对于机器级编程来说，有两种抽象尤为重要： 第一种是机器级程序的格式和行为，定义为指令集体系结构（Instruction set architecture），它定义了处理器状态、指令的格式，以及每条指令对状态的影响。大多数ISA把程序的行为描述成好像每条指令是按顺序执行的，实际处理器硬件远比描述的精细复杂，它们并发地执行许多指令，但是可以采取措施保证整体行为与ISA指定的顺序执行完全一致。 第二种是机器级程序使用的存储器地址是虚拟地址，提供的存储器模型看上去是一个非常大的字节数组，存储器系统的实际实现是将多个硬件存储器和操作系统软件组合起来。

编译器会将C语言提供的相对比较抽象的执行模型表示的程序转化为处理器执行的非常基本的指令，即汇编代码。汇编代码的表示非常接近于机器代码，如下C语言代码：

int accum = 0 ;
int sum(int x, int y){
	int t = x + y;
	accum += t;
	return t;
}

执行gcc -O1 -S code.c将产生一个如下内容的code.s文件：

sum:
  pushl %ebp
  movl  %esp,%ebp
  movl  12(%ebp),%eax
  addl  8(%ebp),%eax
  addl  %eax,accum
  popl  %ebp
  ret

这段代码中已经去除了所有关于局部变量名或数据类型的信息，且代码中有一个对全局变量accum的引用，这是因为编译器还不能确定这个变量会放在存储器中的哪个位置。 如果使用gcc -O1 -c code.c，将生产一个目标文件code.o，它是一个二进制文件，在文件中可以找到一段字节序列：

55 89 e5 8b 45 0c 03 45 08 01 05 00 00 00 00 5d c3

这段字节序列就是上面汇编代码对应的目标代码，由此可见机器实际执行的程序只是对一系列指令进行编码的字节序列。 在Linux上可以使用反汇编器objdump来生成目标代码对应的字节序列：

objdump -d code.o

生成结果如下：

00000000 <sum>:
 0:55                     pushl %ebp
 1:89 e5                  movl  %esp,%ebp
 3:8b 45 0c               movl  12(%ebp),%eax
 6:03 45 08               addl  8(%ebp),%eax
 9:01 05 00 00 00 00      addl  %eax,accum
 f:5d                     popl  %ebp
10:c3                     ret

生成实际可执行的代码需要对一组目标代码文件运行链接器，这一组目标代码文件中必须含有一个main函数。链接器将代码的地址移到一段地址范围中，且会确定全局变量的地址：

08048394 <sum>:
 8048394:55                     pushl %ebp
 8048395:89 e5                  movl  %esp,%ebp
 8048397:8b 45 0c               movl  12(%ebp),%eax
 804839a:03 45 08               addl  8(%ebp),%eax
 804839d:01 05 00 00 00 00      addl  %eax,0x804a018
 80483a3:5d                     popl  %ebp
 80483a4:c3                     ret

最终链接后生成的文件会比较大，是因为它不仅包含了多个文件的代码，还包含了用来启动和终止程序的信息，以及用来与操作系统交互的信息。

访问信息

IA32 CPU包含一组8个存储32位值的寄存器，这些寄存器用来存储整数数据和指针。大多数指令有一个或多个操作数用于指出执行一个操作中要引用的源数据值，以及放置结果的目标位置。源数据值可以以常数形式（如$12）给出，或者是从寄存器（如%eax）、存储器（如0x804a018）中读出。结果可以存放在寄存器或者存储器中。

算术和逻辑操作

（算术和逻辑运算指令的介绍，略）

控制

C语言中的某些结构，比如条件语句、循环语句、分支语句，要求有条件地执行。机器代码提供两种基本的低级机制来实现有条件的行为。除了整数寄存器，CPU还维护着一组单个位的条件码寄存器用于描述最近的算术或逻辑操作的结果。可以检测这些寄存器来执行条件分支指令。常用的条件码有： CF:进位标志，最近的操作使最高位产生了进位，可以用来检查无符号操作数的溢出； ZF:零标志，最近的操作得出的结果为0； SF:符号标志，最近的操作得到的结果为负数； OF:溢出标志，最近的操作导致一个补码溢出（正溢出或负溢出）

跳转指令会导致执行切换到程序中一个全新的位置，在汇编代码中，跳转的目的地通常用一个label表示。 如：

int absdiff(int x, int y){
	if(x < y){
		return y - x;
	}
	else{
		return x - y;
	}
} 

以上C语言代码将被编译为如下汇编代码：x在%ebp+8中，y在%ebp+12中

  movl 8(%ebp),%edx          获取x
  movl 12(%ebp),%eax         获取y
  cmpl %eax,%edx             比较x和y
  jge  .L2                   如果>=，则跳转.L2
  subl %edx,%eax             计算y-x
  jmp  .L3                   无条件跳转.L3
.L2:
  subl  %eax,%edx            计算x-y
  movl  %edx,%eax            两种情况下返回值都放在%eax中
.L3:                         结束

C语言中提供了多种循环结构，do-while、while、for等。可以使用条件测试和跳转组合起来实现循环的效果。大多数汇编器会根据一个循环的do-while形式来产生循环代码，其他的循环会首先转换成do-while形式，再编译成机器代码。

条件传送指令

实现条件操作的传统方法是利用控制的条件转移，当条件满足时程序沿着一条执行路径进行，而当条件不满足时，就走另一条路径。这种机制比较简单，但在现代处理器上可能会非常低效。条件转移是一种替代策略：先计算一个条件操作的两种结果，然后再根据条件是否满足从而选取一个，只有在一些受限的情况下这种策略才可行，但是如果可行，就可以用一条简单的条件传送指令来实现它。条件传送指令更好地匹配了现代处理器的性能特性。

使用条件表达式实现absdiff函数：

int absdiff(int x,int y){
	return x < y ? y-x :x-y;
}

生成的汇编代码如下：

  movl 8(%ebp),%ecx          获取x
  movl 12(%ebp),%edx         获取y
  movl %edx,%ebx             复制y
  subl %ecx,%ebx             计算y-x
  movl %ecx,%eax             复制x
  subl %edx,%eax             计算x-y，并设置为返回值
  cmpl %edx,%ecx             比较x，y
  cmovl %ebx,%eax            如果<，则将返回值替换为y-x    !!! 仅需一条指令图（条件传送指令）

以上汇编代码类似于如下的C语言代码：

  int tval = y-x;
  int rval = x-y;
  int test = x<y;

  // 只需一条指令
  if(test) {
    rval = tval;
  }

  return rval;

基于条件数据传送的代码比基于条件控制转移的代码性能好，原因在于：现代处理器使用流水线方式来执行指令，这种方式通过重叠连续指令的步骤来获得高性能，例如正在取一条指令的时候执行它前面一条指令的算术运算。要做到这一点，要求能够事先确定要执行指令的序列，这样才能够保持流水线中充满了待执行的指令。当机器遇到条件跳转时，它常常还不能确定是否会进行跳转，处理器使用非常精密的分支预测逻辑来猜测每条跳转指令是否会执行，如果它的猜测比较可靠，指令流水线中就会充满着指令，但是如果猜测错误，则处理器要丢掉它为该跳转指令后所有指令已经做了的工作，然后再开始从正确位置处起始的指令去填充流水线。这样一个错误的预测会导致大约20~40个时钟周期的浪费。 与条件跳转不同，处理器可以执行条件传送而无需预测测试的结果，处理器只是读源值，检查条件码，然后要么更新目的寄存器，要么保持不变。 使用条件传送也不是总会改进代码的效率，如果条件求值需要大量的计算，那么当相应的条件不满足时，这些工作就白费了。对gcc的实验表明，只有当两个表达式都很容易计算时（即所谓的受限情况）它才会使用条件传送。

过程

一个过程调用包括将数据（参数、返回值）和控制从代码的一部分传递到另一部分，在进入过程时为过程的局部变量分配空间，在退出时释放这些空间。大多数机器只提供转移控制到过程和从过程中转移出控制等简单的指令，数据传递、局部变量的分配和释放通过程序栈来操作。

机器用栈来传递参数、存储返回信息、保存寄存器用于以后恢复以及本地存储等。为单个过程分配的那部分栈称为栈帧（stack frame）。栈帧以两个指针界定，寄存器%ebp为帧指针，寄存器%esp为栈指针，当程序执行时，栈指针可以移动，因此大多数信息的访问都是相对于帧指针（即帧指针为当前栈帧的固定起点）的。

     [栈底]
+================+
-                -
-      ...       -     [较早的帧]
-                -
+================+
-       ...      -    
-     参数n      -     [调用者的帧]
-     参数1      -
-    返回地址    -
+================+
-      %ebp      -
-       ...      -
-    临时变量    -     [当前帧]
-                -  
+================+  <-- %esp
      [栈顶]

假设过程P调用过程Q，则Q的参数放在P的栈帧中，P中的返回地址被压入栈中，形成P的栈帧的末尾。返回地址就是当程序从Q返回时应该继续执行的地方。过程Q也用栈来保存其他不能存放在寄存器中的局部变量，以及Q调用的其他过程的参数。

栈向低地址方向增长，而栈指针%esp指向栈顶元素，可以用pushl将数据存入栈中并利用popl指令从栈中取出。将栈指针的值减小一定的值可以分配没有指定初始值的数据空间，也可以通过增加栈指针来释放空间。

CPU支持以下过程调用和返回的指令：

  call Label       过程调用
  call *Operand    过程调用
  leave            为返回准备栈
  ret              从过程调用中返回

call指令的效果是将返回地址入栈，并跳转到被调用的过程的起始处。返回地址是在程序中紧跟在call后面的那条指令的地址，当被调用的过程返回时，执行会从此处继续。ret指令从栈中弹出地址，并跳转到这个位置。

（数组、组合类型等，略）

第4章 处理器体系结构

CPU能够执行的指令被编码为一个或多个字节序列组成的二进制格式，一个CPU能够执行的所有指令和指令的字节级编码被称为它的指令集体系结构（ISA Instruction-Set Architecture）。 ISA模型看上去应该是顺序执行指令，但是现代处理器的实际工作方式并非如此：通过同时处理多条指令的不同部分，处理器可以获得较高的性能（流水线化处理器）。为了保证处理器能达到同顺序执行相同的结果，处理器又采取了一些特殊的机制。

Y86指令集体系结构

每条指令都会读取或修改处理器状态的某些部分。 Y86有8个寄存器%eax、%ecx、%edx、%ebx、%esi、%edi、%esp、%ebp。每个寄存器存储一个字，%esp被入栈、出栈、调用和返回指令作为栈指针，在其他情况下寄存器没有固定的含义或固定值。 有3个1位的条件码：ZF（零）、SF（符号）、OF（溢出），它们保存最近的算术或逻辑指令所造成影响的有关信息。 程序计数器PC存放当前正在执行指令的地址。 存储器从概念上讲是一个很大的字节数组，保存程序和数据，Y86程序用虚拟地址来引用存储器位置，硬件和操作系统一起将虚拟地址翻译成实际物理地址。 状态码Stat表明程序执行的总体状态，如正常运行还是出现了某种异常。

Y86指令集只包括四字节整数操作，寻址方式和操作也比较少，以下是Y86支持的所有指令的表述：

汇编码                字节编码
halt                  0  0
nop                   1  0
rrmovl rA,rB          2  0  rA  rB       r->r  从寄存器移往寄存器
irmovl V,rB           3  0  F   rB  V    i->r  从立即数移往寄存器
rmmovl rA,D(rB)       4  0  rA  rB  D    r->m  从寄存器移往存储器
mrmovl D(rB),rA       5  0  rA  rB  D    m->r  从存储器移往寄存器

注：不允许直接从存储器地址传送到另一个存储器地址，也不允许将立即数传送到存储器。

OPl  rA,rB            6  fn rA  rB  D    

OP代表4种整数操作指令：addl、subl、andl、xorl，这些指令会设置3个条件码ZF、SF、OF

jXX  Dest             7  fn Dest

jXX代表7个跳转指令：jmp、jle、jl、je、jne、jge、jg。

cmovXX rA,rB          2  fn rA  rB

cmovXX代表6个传送指令：cmovle、cmovl、cmove、cmovne、cmovge、cmovg;只有当条件码满足所需要的约束时，才会更新目的寄存器的值。

call Dest             8  0  Dest

将返回地址入栈，然后跳到目的地址，ret指令用于从这样的过程中返回。

ret                   9  0
pushl rA              A  0  rA  F       入栈
popl rA               B  0  rA  F       出栈

其指令编码长度从1个字节到6个字节不等。一条指令含有一个单字节的指令指示符，可能含有一个单字节的寄存器指示符，还可能含有一个4字节的常数字。字段fn指明是某个整数操作OPl、数据移动条件cmovXX或者分支条件jXX。

程序寄存器存在CPU中的一个寄存器文件中，这个寄存器文件就是一个小的、以寄存器ID作为地址的随机访问存储器。

指令集的字节编码必须具有唯一的解释，任意一个字节序列要么是一个唯一的指令序列的编码，要么就不是一个合法的字节序列。（具体指令编码，略）

对于以下函数：

int Sum(int *Start, int Count){
	int sum = 0;
	while(Count){
		sum += *Start;
		Start++;
		Count--;
	}
	return sum;
}

使用Y86得到的汇编代码如下：

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        Set condition codes
  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
End:
   rrmovl %ebp,%esp
   popl %ebp
   ret

逻辑设计和硬件控制语言HCL

在硬件设计中用电子电路来计算和存储位，大多数现代电路技术都是用信号线上的高低电压来表示不同的值，如逻辑1用1v左右的高电压表示，而逻辑0用0v左右低电压表示。要实现一个数字系统需要三个主要的组成部分：对位进行操作的组合逻辑、存储位的存储器元素、控制存储器元素更新的时钟信号。

硬件控制语言HCL用来描述不同处理器设计的控制逻辑。HCL表达式可以清楚地表明组合逻辑电路和C语言中逻辑表达式（&&、||、!等）的对应之处。 逻辑门是数字电路的基本计算元素，它们产生的输出等于它们输入位值的某个布尔函数。（图略） 很多逻辑门组合成一个网，就能构建计算块，称为组合电路。 通过将逻辑门组合成更大的网，可以构造出能计算更加复杂逻辑的组合电路，比如设计对字进行操作的电路，而不仅仅是对位进行操作。组合逻辑电路可以设计成在字级数据上执行许多不同类型的操作。算术逻辑单元ALU是一种组合电路，这个电路有3个输入：两个数据输入和一个控制输入，根据控制输入的设置，电路会对数字输入执行不同的算术或逻辑操作。组合电路可以实现将一个信号与多个可能匹配信号的比较，以此来检测正在处理的某个指令代码是否属于某一类指令代码。

组合电路不存储任何信息，为了产生时序电路，即有状态且在这个状态上进行计算的系统，必须引入按位存储信息的设备。存储设备都是由同一个时钟控制，时钟周期性发出信号决定什么时候要把新值加载到设备中。

寄存器文件有两个读端口和一个写端口，这样一个多端口随机访问存储器允许同时进行多个读和写操作，比如可以读两个程序寄存器的值，同时更新第三个寄存器的状态。

Y86的顺序实现

顺序的处理器即在每个时钟周期上顺序地处理一条完整指令所需的所有步骤。虽然不同指令的动作差异很大，但是所有的指令都遵循统一的执行序列： 取指：从存储器读取指令字节，地址为程序计数器PC的值。取出的长度取决于具体指令的字节编码，然后按顺序方式计算当前指令的下一条指令的地址（等于PC的值加上已取出指令的长度）。 译码：从寄存器文件读入最多两个操作数，通常读入rA和rB字段指明的寄存器，不过有些指令是读寄存器%esp的。 执行：ALU要么执行指令指明的操作（根据ifun值），计算存储器引用的有效地址，要么增加或者减少栈指针。在此，也可能设置条件码。对于跳转指令，这个阶段会验证条件码和（ifun给出的）分支条件，看是不是应该选择分支。 访存：将数据写入存储器或者从存储器中读出。 写回：最多可以写两个结果到寄存器文件。 更新PC：将PC设置为下一条指令的地址。 发生任何异常时，处理器就会停止：执行halt指令或非法指令。

一个时钟变化会引发一个经过组合逻辑的流来执行整个指令。

（硬件实现，略）

顺序处理器的问题在于太慢了，时钟必须非常慢，以使信号能在一个周期内传播所有的阶段（对应不同的硬件单元）。这种实现方式不能充分利用硬件单元。

流水线的通用原理

流水线化可以增加系统的吞吐量，即单位时间内服务的总用户数。但是对单个用户而言，则会轻微地增加延迟（从头到尾执行一条指令所需要的时间称为延迟）。 相邻指令之间很可能是相关的，可以通过引入含有反馈路径的流水线系统来解决。（详略）

Y86的流水线实现

调整顺序处理器中5个阶段的顺序，使得更新PC阶段在一个时钟周期开始时执行，而不是结束时才执行。 （详略）

第5章 优化程序性能

编写高性能的程序通常需要以下3类活动：

1. 选择合适的算法和数据结构；
2. 编写出编译器能够有效优化以转换成高效可执行代码的源代码；
3. 将任务分成多个部分，并让它们并行地执行；

本章主要讨论的是其中第2种情况。

编译器的能力和局限性

编译器使用复杂的算法来优化程序，大多数编译器都提供了对优化的控制，比如gcc -O1将使用一组基本的优化，而gcc -O3则会进行更全面的优化。更高级别的优化可以进一步提高程序的性能，但是也可能增加程序的规模，并使得程序难以调试。 编译器必须只使用安全的的优化，即优化后的程序和未优化的版本应该具有一样的行为。

void func1(int *xp, int *yp){
	*xp += *yp;
	*xp += *yp;
}

void func2(int *xp, int *yp){
	*xp += 2* *yp;
}

func1需要6次存储引用（2次读xp、2次读yp、2次写xp），而func2只需要3次存储器引用（读xp、读yp、写xp），因此func2的效率更高，但是当xp等于yp时，fun1将使xp的值变为原来的4倍，而fun2只会将xp增加为原来的3倍，因为编译器只进行安全的优化，如果编译器不能确定两个指针是否指向同一个位置，就必须假设什么情况都有可能，所以不会将func1优化为func2的形式。

再比如：

x = 1000;
y = 3000;
*q = y;
*p = x;
v = *q;

v的值依赖于指针p和q是否指向存储器中的同一个位置，如果不是，v的值等于3000，如果是，则v的值就是1000。

函数调用也可能成为妨碍优化的因素，如：

int counter = 0;
int f(){
	return counter ++;
}

int func1(){
	return f() + f() + f() + f();
}

int func2(){
	return 4*f();
}

f()函数有一个副作用，即它修改了全局程序状态的一部分，改变它的调用次数会改变程序的行为，因此不能被优化为func2的形式。

表示程序性能

使用CPE (Cycles Per Element)，来作为度量程序性能的标准。 以计算向量的前置和函数为例，对于长度相同的向量p和a：

p[0] = a[0];
p[i] = p[i-1] + a[i]; 

// 函数psum1每次迭代计算一个元素
void psum1(float a[], float p[], long int n){
	long int i;
	p[0] = a[0];
	for(i=1; i<n; i++){
		p[i] = p[i-1] + a[i]; 
	}
}

// 函数psum2使用循环展开的技术，每次迭代计算两个元素，以此减少迭代的次数
void psum2(float a[], float p[], long int n){
	long int i;
	p[0] = a[0];
	for(i=1; i<n-1; i+=2){
		float mid_val = p[i-1] + a[i];
		p[i] = mid_val; 
		p[i+1] = mid_val + a[i+1];
	}

	if(i<n){
		p[i] = p[i-1] + a[i]; 
	}
}

psum1和psum2的运行时间（以时钟周期为单位）分别近似于496+10.0n和500+6.5n（使用最小二乘法拟合方法得到），对于较大的n值，运行时间就会主要由n来决定，其中n的系数（10.0和6.5）就称为CPE有效数。以CPE为度量标准，psum2的CPE为6.5，优于CPE为10.0的psum1。

程序示例

#define IDENT 0
#define OP +

typedef int data_t;

typedef struct{
	long int len;
	data_t *data;
} vec_rec,*vec_ptr;

vec_ptr new_vec(long int len){
	vec_ptr result = (vec_ptr)malloc(sizeof(vec_rec));
	if(!result){
		return NULL;
	}
	result->len = len;
	if(len>0){
		data_t *data = (data_t *)calloc(len, sizeof(data_t));
		if(!data){
			free((void *) result);
			return NULL;
		}
		result->data = data;
	}
	else{
		result->data = NULL;
	}
	return result;
}

// 将向量中索引为index的元素赋值到dest位置，成功返回1，失败返回0
int get_vec_element(vec_ptr v,long int index,data_t *dest){
	if(index<0 || index>=v->len){
		return 0;
	}
	*dest = v->data[index];
	return 1;
}

long int vec_length(vec_ptr v){
	return v->len;
}

// 向量合并运算的初步实现
void combine1(vec_ptr v,data_t *dest){
	long int i;

	*dest = IDENT;
	for(i = 0; i < vec_length(v); i++){
		data_t val;
		get_vec_element(v,i,&val);
		*dest = *dest OP val;
	}
}

combine1函数的CPE如下： + * + F* D* 未优化 20.02 29.21 27.40 27.90 27.36 -O1优化 12.00 12.00 12.00 12.01 13.00

消除循环的低效率

void combine2(vec_ptr v,data_t *dest){
	long int i;
	long int 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;
	}
}

combine2函数的CPE如下： + * + F* D* -O1优化 12.00 12.00 12.00 12.01 13.00 combine2 8.03 8.09 10.09 11.09 12.08

减少过程调用

过程调用会带来相当大的开销，而且妨碍大多数形式的程序优化。

data_t *get_vec_start(vec_ptr v){
	return v->data;
}

void combine3(vec_ptr v,data_t *dest){
	long int i;
	long int length = vec_length(v);
	data_t *data = get_vec_start(v); // 将过程调用从循环中移出

	*dest = IDENT;
	for(i = 0; i < length; i++){
		*dest = *dest OP data[i];
	}
}

             +         *         +        F*         D*
combine2    8.03      8.09     10.09     11.09     12.08
combine3    6.01      8.01     10.01     11.01     12.02

消除不必要的存储器引用

combine3中将合并运算计算的值累积在指针dest中，在第i次迭代中，程序读出这个位置处的值，计算后再将其存回到dest，这样的读写很浪费，因为每次迭代开始时从dest中读出的值就是上次迭代最后写入的值。

void combine4(vec_ptr v,data_t *dest){
	long int i;
	long int length = vec_length(v);
	data_t *data = get_vec_start(v); 
	data_t acc =IDENT; // 在临时变量中存放结果

	for(i = 0; i < length; i++){
		acc = acc OP data[i];
	}
	*dest = acc;
}
             +         *         +        F*         D*
combine3    6.01      8.01     10.01     11.01     12.02
combine4    2.00      3.00      3.00      4.00      5.00

理解现代处理器*

典型的现代处理器可以在每个时钟周期执行多个操作，而且是乱序的，可以达到更高的指令级并行（基于指令高速缓存、分支预测等实现）。 详略。

循环展开

循环展开通过增加每次迭代计算的元素的数量，减少循环的迭代次数。 对于整数加法和乘法，循环展开使CPE有所改进，但是对于浮点数运算却没有，即循环展开不能改进浮点数运算（与CPU进行浮点数计算的方式有关）。

void combine5(vec_ptr v,data_t *dest){
	long int i;
	long int length = vec_length(v);
	long int limit = length - 1;
	data_t *data = get_vec_start(v); 
	data_t acc =IDENT;

	// 循环展开2次
	for(i = 0; i < limit; i+=2){
		acc = (acc OP data[i]) OP data[i+1];
	}

	for(; i<length; i++){
		acc = acc OP data[i];
	}

	*dest = acc;
}

             +         *         +        F*         D*
combine4    2.00      3.00      3.00      4.00      5.00
combine5    2.00      1.50      3.00      4.00      5.00

编译器可以很容易地执行循环展开，如gcc可以使用-funroll-loops选项来执行循环展开。

提高并行性

void combine6(vec_ptr v,data_t *dest){
	long int i;
	long int length = vec_length(v);
	long int limit = length - 1;
	data_t *data = get_vec_start(v); 
	data_t acc0 =IDENT;
	data_t acc1 =IDENT;

	// 循环展开2次，并且使用2路并行（因而有两条关键路径）
	for(i = 0; i < limit; i+=2){
		acc0 = acc0 OP data[i];
		acc1 = acc1 OP data[i+1];
	}

	for(; i<length; i++){
		acc0 = acc0 OP data[i];
	}

	*dest = acc0 OP acc1;
}

             +         *         +        F*         D*
combine5    2.00      1.50      3.00      4.00      5.00
combine6    1.50      1.50      1.50      2.00      2.50

编译器能够将combine4中的代码转换为combine5中的二路循环展开变种，再引入并行性，将其转换成combine6的一个变种。

改变内循环中元素合并的方式：

void combine7(vec_ptr v,data_t *dest){
	long int i;
	long int length = vec_length(v);
	long int limit = length - 1;
	data_t *data = get_vec_start(v); 
	data_t acc =IDENT;

	// 循环展开2次
	for(i = 0; i < limit; i+=2){
		acc = acc OP (data[i] OP data[i+1]);  // 重新结合变换
	}

	for(; i<length; i++){
		acc = acc OP data[i];
	}

	*dest = acc;
}

             +         *         +        F*         D*
combine6    1.50      1.50      1.50      2.00      2.50
combine7    2.00      1.51      1.50      2.00      2.97

可以看到该优化对浮点数的计算也是有效的。 重新结合变换能够减少计算中关键路径上的操作的数量，通过更好地利用CPU功能单元的流水线能力得到更好的性能。

如果对循环展开多次，同时使用多路并行，可以使CPE趋近于1：

                     +         *         +        F*         D*
展开5次，5路并行    1.01      1.00      1.00      1.00      1.00

能够利用GCC对SIMD（单指令多数据）向量指令的支持更进一步地提高性能，对于整数和单精度数据，处理器可以支持每个周期4个合并操作，而对于双精度数据，每个周期2个。

                +         *         +        F*         D*
SIMD+8次展开   0.25      0.50      0.25      0.25      0.50

限制因素

在一个程序的数据流图表示中，关键路径指明了该程序所需时间的一个基本下界，即如果程序中有某条数据相关链，这条链上所有延迟之和等于T，那么这个程序至少需要T个周期才能执行完。

功能单元的吞吐量界限也是程序执行时间的一个下界，即如果一个程序一共需要N个某种运算的计算，而微处理器只有m个能执行这个操作的功能单元，并且这些单元的发射时间为i，那么这个程序的执行时间至少需要N*i/m个周期。

如果并行度超过了可用的寄存器的数量，那么编译器会使用寄存器溢出，即把某些临时值存放到栈中，在这种情况下性能会急剧下降。

当分支预测逻辑不能正确预测一个分支是否需要跳转的时候，条件分支可能会导致严重的预测错误处罚。处理器的工作超前于正在执行的指令，如果指令遵循的是一种简单的顺序，那么这种指令流水线化就能很好地工作，当遇到分支的时候，处理器必须猜测分支该往哪个方向走。对于条件转移的情况，这意味着要预测是否会选择分支，对于间接跳转或过程返回这样的指令，这意味着预测目标地址。 如果预测是正确的，那么处理器就会提交投机执行的指令的结果，把它们存储到寄存器或存储器中，如果预测结果是错误的，处理器必须丢弃掉所有投机执行的结果，在正确的位置重新开始取指令的过程。对于i7来说，预测错误处罚是44个时钟周期。

最新的x86处理器有条件传送指令，在编译条件语句和表达式时，gcc能够产生使用这些指令的代码，而不是更传统的基于控制的条件转移的实现。翻译成条件传送的基本思想是计算出一个条件表达式或语句两个方向上的值，然后用条件传送选择期望的值。条件传送指令可以被实现为普通指令流水线化处理的一部分，没有必要猜测条件是否满足，因此猜测错误也没有处罚。

现代处理器中的分支预测逻辑非常善于辨别不同的分支指令有规律的模式和长期的趋势，因此不要过分关心可预测的分支。对于无法预测的情况，如果编译器能够产生使用条件数据传送而不是使用条件控制转移的代码，可以极大地提高程序的性能，这不是C语言程序可以直接控制的，但是有些表达条件行为的方法能够更直接地被翻译成条件传送，而不是其他操作。如下两个函数实现同样的功能：将a[i]设置为a[i]和b[i]中较小的那一个，将b[i]设置为较大的那一个。

void minmax1(int a[], int b[], int n){
	int i;
	for(i=0; i<n; i++){
		if(a[i] > b[i]){
			int t =  a[i];
			a[i] = b[i];
			b[i] = t;
		}
	}
}

void minmax2(int a[], int b[], int n){
	int i;
	for(i=0; i<n; i++){
		if(a[i] > b[i]){
			int min = a[i] < b[i] ? a[i] : b[i];
			int max = a[i] < b[i] ? b[i] : a[i];
			a[i] = min;
			b[i] = max;
		}
	}
}

使用随机数据测试minmax1，CPE大约为14.50，使用可预测的数据，CPE大约为3.00~4.00。 对于minmax2，无论哪种类型的数据，CPE大约都为5.0

理解存储器性能

现代处理器有专门的功能单元来执行加载和存储操作，这些单元有内部的缓冲区来保存未完成的存储器操作请求集合，例如i7的加载单元的缓冲区可以保存最多48个读请求，而存储单元的缓冲区可以保存最多32个写请求。每个这样的单元通常可以每个时钟周期开始一个操作。

合并运算的测试表明，当不使用SIMD时CPE从没有低于1.00，其中一个制约因素是：对于每一个被计算的元素，都需要从存储器中读一个值，由于加载单元每个时钟周期只能启动一条加载操作，所以CPE不可能低于1.00。对于每个被计算的元素必须加载k个值的应用，不可能获得低于k的CPE。

在大多数情况下存储操作与加载操作一样，能够在完全流水线化的模式中工作，每个周期开始一条新的存储。但是与加载操作不同的是，存储操作并不影响任何寄存器值，因此通常一系列存储操作不会产生数据关联，但是当加载操作是受存储操作的结果影响时会有一些问题。如下函数：

void write_read(int *src, int *dest, int n){
	int cnt = n;
	int val = 0;
	while(cnt--){
		*dest = val;
		val = (*src)+1;
	}
}

a的值为[-10,17]; 当执行write_read(&a[0],&a[1],3)时，指针引用src的每次加载都会得到值-10，因此在两次迭代之后，数组的元素就会分别保持固定的-10和-9.从src读出的结果不受对dest写的影响，测试得到这种情况下的CPE为2.00 当执行write_read(&a[0],&a[0],3)时，src的每次加载都会得到*dest的前次执行存储的值，因而一系列不断增加的值会被存储在这个位置，这就产生了写读相关：一个存储器读的结果依赖于一个最近的存储器写，性能测试发现CPE为6.00 写读相关现象产生性能差异的本质在于加载、存储单元的执行方式。存储单元包含一个存储缓冲区，它包含已经被发射到存储单元但还没有完成的存储操作的地址和数据，这里的完成包括更新数据高速缓存。提供这样一个缓冲区使得一系列存储操作不必等待每个操作都更新高速缓存就能够执行。当一条加载操作发生时，它必须检查存储缓冲区中的条目，如果有地址相匹配，它就取出相应的数据条目作为加载操作的结果。当存在写读相关时，读操作必须等写操作将其结果放到存储缓冲区中后才能执行，而如果没有写读相关，则两个操作可以独立地进行。 对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响其他哪些指令。对于存储器操作，只有计算出加载和存储的地址被计算出来以后，处理器才能确定哪些指令会影响其他的哪些。

确认和消除性能瓶颈

（实验，略）

第6章 存储器层次结构

如果程序需要的数据是存储在CPU寄存器中的，那么在指令的执行期间，在零个周期内就能访问到它们；如果存储在高速缓存中，需要1~30个周期；如果存储在主存中，需要50~200个周期；如果存储在磁盘上，需要大约几千万个周期。

存储技术

随机访问存储器（Random Access Memory）分为两类：静态的和动态的。静态的（SRAM）比动态的（DRAM)更快，也更贵。SRAM用来做高速缓存，DRAM用来做主存及图形系统的帧缓冲区。

SRAM将每个位存储在一个双稳态的存储器单元里，每个单元是一个六晶体管电路，这个电路有这样一个属性：它可以无限期地保持在两个不同的电压状态之一，其他任何状态都是不稳定的。只要有电，它就会永远地保持它的值。

DRAM将每一位存储为一个电容，与SRAM不同的是，DRAM存储器单元对干扰非常敏感，暴露在光线下也会导致电容电压改变，当电容电压被扰乱后，它就永远不会恢复了。存储器系统必须周期性地通过读出，然后重写来刷新存储器的每一位。

SRAM与DRAM的比较：

      每位晶体管数  相对访问时间  是否持续  是否敏感  相对花费
SRAM       6              1          是        否        100    
DRAM       1             10          否        是         1    

SRAM和DRAM在断电后都会丢失信息，因此它们都属于易失的。非易失性存储器即使在断电后也仍然能够保存它们的信息，通常指ROM。由于历史原因，虽然ROM中有的类型既可以读也可以写，但是它们整体上都称为只读存储器ROM。

PROM指可以进行一次编程的ROM，PROM的每个存储器单元有一种熔丝，它只能用高电流熔断一次。

EPROM指可擦写可编程ROM，有一个透明的石英窗口，允许光到达存储单元，紫外线照射后，EPROM单元就被清除为0.对其写入1需要使用特殊的设备来完成。EPROM能够被擦除和重编程的次数大概为1000次。

EEPROM指电子可擦除PROM，类似于EPROM，但是它不需要一个物理上独立的编程设备，且可编程次数超过10万次。

闪存基于EEPROM。

固件（firmware）指存储在ROM中的程序，当计算机通电后，会运行存储在ROM中的固件，如BIOS。复杂的设备，如显卡、磁盘控制器也依赖固件翻译来自CPU的I/O请求。

总线是一种共享电子电路，数据流通过总线在处理器和DRAM之间来回传送。如：

磁盘（略）

固态硬盘（Solid State Disk）是一种基于闪存的存储技术。

局部性

一个编写良好的计算机程序应该具有良好的局部性（locality），即它倾向于引用邻近于其最近引用过的数据项或者最近引用过的数据项本身。局部性有两种形式：时间局部性、空间局部性。

存储器层次结构

寄存器 -> L1高速缓存 -> L2高速缓存 -> L3高速缓存 -> 主存 -> 本地磁盘 -> 远程存储

编写高速缓存友好的代码

局部性比较好的程序更容易有较低的不命中率，因而往往运行的更快。应该试着去编写高速缓存友好的代码。包括以下方法： 1.让最常见的情况运行得快：程序通常把大部分时间花在少量核心的函数上，而这些函数通常把大部分时间花在少量的循环上，因此应该把注意力集中在核心函数的循环上，而忽略其他部分。 2.在每个循环内部缓存不命中数量最小：对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器文件中。步长为1的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块。

高速缓存对程序性能的影响

存储器系统的性能不是一个数字就能描述的，它是一座时间和空间局部性的存储器山（一个变化很大的程序局部性的函数）。

考虑一对nn的矩阵相乘问题，矩阵乘法通常由三个嵌套循环实现，分别用索引i、j、k表示，改变循环次序可以得到矩阵乘法的6个在功能上等价的版本。从高层来看，这6个版本的功能是一样的，总共都执行O(n^3)个操作，且加法和乘法的数量相同。但是分析最里层循环迭代的行为可以发现在访问数量和局部性上是有区别的。 假设： C = AB，AB为nn的数组。只有一个高速缓存，其块大小为32字节，数组n很大，以至于矩阵的一行都不能完全装进L1高速缓存中。

// ijk版本
for(i=0; i<n; i++){
	for(j=0; j<n; j++){
		sum = 0.0;
		for(k=0; k<n; k++){
			sum += A[i][k] * B[k][j];
		}
		C[i][j] += sum;
	}
}

// jki版本
for(j=0; j<n; j++){
	for(k=0; k<n; k++){
		r = B[k][j];
		for(i=0; i<n; i++){
			C[i][j] += A[i][k]*r;
		}
	}
}

// kij版本
for(k=0; k<n; k++){
	for(i=0; i<n; i++){
		r = A[i][k];
		for(j=0; j<n; j++){
			C[i][j] += B[k][j]*r;
		}
	}
}

其他版本略，性能测试结果如下：

                      ijk&jik   jki&kji   kij&ikj
每次迭代加载次数：       2         2         2
每次迭代存储次数：       0         1         1
每次迭代A不命中次数：   0.25      1.00      0.00
每次迭代B不命中次数：   1.00      0.00      0.25
每次迭代C不命中次数：   0.00      1.00      0.25
每次迭代总不命中次数：  1.25      2.00      0.50

对于大的n值，即使每个版本都执行相同数量的浮点数算术操作，最快的版本（不命中次数最小）比最慢的版本运行得几乎快20倍。

第7章 链接

链接是将各种代码和数据收集起来并组合成一个单一文件的过程，这个文件可被加载到存储器并执行。链接可以执行于编译时，也可以执行于加载时，甚至可以执行于运行时。链接器使得分离编译成为可能：不用将一个大型的应用程序组织为一个巨大的源文件，而是可以将它分解为更小、更好管理的模块，并可以独立地修改和编译这些模块。

静态链接

静态链接器（比如ld）以一组可重定位目标文件和命令行参数为输入，生成一个完全链接的、可以加载和运行的可执行目标文件。 为了构造可执行文件，链接器必须完成两个主要任务：符号解析和重定位。

目标文件

目标文件有3种形式： 1.可重定位目标文件：可以在编译时与其他可重定位目标文件合并以创建一个可执行目标文件。 2.可执行目标文件：可以被直接拷贝到存储器并执行。 3.共享目标文件：一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态地加载到存储器并链接。 可重定位目标文件（包括共享目标文件）由编译器和汇编器生成，可执行目标文件由链接器生成。

可重定位目标文件

一个目标文件就是一个字节序列，不同系统上的目标文件格式不同，以下是ELF（Unix可执行和可链接）格式的目标文件的结构：

+-------------+
-   ELF头     - 
+-------------+
-   .text     -
+-------------+
-   .rodata   -
+-------------+
-   .data     -
+-------------+
-   .bss      -
+-------------+
-   .symtab   -
+-------------+
-   .rel.text -
+-------------+
-   .rel.data -
+-------------+
-   .debug    -
+-------------+
-   .line     -
+-------------+
-   .strtab   -
+-------------+

ELF头：描述了生成该文件的系统的字的大小和字节顺序，以及帮助链接器语法分析和解释目标文件的信息；

• .text：已编译程序的机器代码；
• .rodata：只读数据；
• .data：已初始化的全局C变量（不含静态变量和局部变量）；
• .bss：未初始化的全局C变量，不占据实际的磁盘空间，仅仅是一个占位符；
• .symtab：符号表，存放在程序中定义和引用的函数和全局变量的信息；
• .rel.text：.text节中位置的列表，当和其他目标文件结合时，链接器需要修改这些位置。任何调用外部函数或者引用全局变量的指令都需要修改，调用本地函数的指令则不需要修改。可执行目标文件中并不需要重定位信息，因此通常省略。
• .rel.data：被模块引用或定义的任何全局变量的重定位信息，任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改；
• .debug：调试符号表，只有以-g选项编译时才会生成。其条目是程序中定义的局部变量和类型定义、程序中定义和引用的全局变量以及原始的C源文件；
• .line：原始C程序中的行号和.text节中机器指令之间的映射，只有以-g选项编译时才会生成。
• .strtab：一个字符串表，包括.symtab和.debug节中的符号表，以及节头部中的节名字；

符号和符号表

对于任意一个目标模块m，在链接器的上下文中有3种不同的符号：

1. 由模块m定义并能被其他模块引用的全局符号，对应非静态的C函数和被定义为不带C static属性的全局变量；
2. 由其他模块定义并被模块m引用的全局符号，这些符号称为外部符号，对应定义在其他模块中的C函数和变量；
3. 只被模块m定义和引用的本地符号。对应带static属性的C函数和全局变量（不含本地非静态程序变量的任何符号，因为它们在运行时由栈管理）。

注：C源代码文件扮演模块的角色，任何声明带有static属性的全局变量或者函数都是模块私有的，类似地，任何声明为不带static属性的全局变量和函数都是公有的，可以被其他模块访问。定义为带有C static属性的本地过程变量不是在栈中管理，编译器在.data和.bss中为每一个定义分配空间，并在符号表中创建一个有唯一名字的本地链接器符号。

.symtab节中包含符号表，其条目的结构为Elf_Symbol。（详略）

如下程序main.c程序：

void swap();
int buf[2] = {1,2};

int main(){
	swap();
	return 0;
}

编译得到的main.o的符号表的最后3个条目（开始的8个条目是链接器内部使用的本地符号，没有显示出来）如下：

Num   Value   Size   Type        Bind     Ot   Ndx   Name
8       0      8     Object      GLOBAL   0     3     buf
9       0      17    FUNC        GLOBAL   0     1     main
10      0      0     NOTYPE      GLOBAL   0    UND    swap  <- 对外部符号的引用

符号解析

符号解析即将每个符号引用与输入的可重定位目标文件的符号表中的一个确定的符号定义联系起来。 对于引用和定义处于相同模块中的本地符号的引用，符号解析是非常简单明了的：编译器只允许每个模块中的每个本地符号仅有一个定义。此外编译器还保存静态本地变量，它们也会有本地链接器符号，且拥有唯一的名字。

对于全局符号，在编译时编译器向汇编器输出每个全局符号，或者是强（strong）或者是弱（weak），而汇编器把这个信息隐含地编码在可重定位目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。据此，Unix链接器使用如下规则来处理多重定义的符号：

1. 不允许有多个强符号；
2. 如果有一个强符号和多个弱符号，那么选择强符号；
3. 如果有多个弱符号，那么从这些弱符号中任意选择一个；

如：

// foo1.c
int main(){
	return 0;
}

// bar1.c
int main(){
	return 0;
}

当试图编译和链接如上两个C模块时，链接器将生成一条错误信息，因为强符号main被定义了多次。

再比如：

// foo2.c
#include <stdio.h>
void f(void);

int x = 15213;

int main(){
   f();
   printf("x = %d\n",x);
   return 0;
}

// bar2.c
int x;

void f(){
	x = 15212;
}

当编译和链接以上两个文件时，因为bar2中的x未被初始化，链接器将选择定义在foo2中的强符号x，函数f会将x的值由15213改成15212，由此可能会造成一些不易察觉的运行时错误（链接器通常不会表明它检测到了多个x的定义）。

静态库

所有的编译系统都提供一种机制：将所有相关的目标模块打包成一个单独的文件，称为静态库，它可以用作链接器的输入，当链接器构造一个可执行文件时，它只拷贝静态库里被应用程序引用的目标模块。在Unix系统中静态库以存档（archive）格式存放在磁盘中，存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个成员目标文件的大小和位置，后缀为.a。 如：

// addvec.c
void addvec(int *x, int *y, int *z, int n){
    int i;
    for(i=0; i<n; i++){
        z[i] = x[i] + y[i];
    }
}

// multvec.c
void addvec(int *x, int *y, int *z, int n){
    int i;
    for(i=0; i<n; i++){
        z[i] = x[i] * y[i];
    }
}

使用ar工具基于以上两个文件创建一个名为libvector.a的静态库：

gcc -c addvec.c multvec.c
ar rcs libvector.a addvec.o multvec.o

假设该库的头文件为vector.h（定义了库中的函数的原型），则可以如下使用该库：

// main.c
#include <stdio.h>
#include "vector.h"

int x[2] = {1,2};
int y[2] = {3,4};
int z[2];

int main(){
	addvec(x,y,z,2);
	printf("z = [%d %d]\n",z[0],z[1]);
	return 0;
}

为了创建可执行文件，需要编译和链接输入文件main.o和libvector.a：

gcc -O2 -c main.c
gcc -static -o p main.o ./libvector.a

-static指明链接器应该构建一个完全链接的可执行目标文件，即它可以加载到存储器并运行，在加载时无需更进一步的链接。当链接时，它判定addvec.o定义的addvec符号是被main.o引用的，所以会拷贝addvec.o到可执行文件。因为程序不引用任何由multvec.o定义的符号，所以链接器就不会拷贝这个模块到可执行文件。 此外，链接器还会拷贝libc.a中的printf.o模块，以及许多C运行时系统中的其他模块。

在符号解析阶段链接器从左到右扫描可重定位目标文件和存档文件，因此命令行上的库和目标文件的顺序非常重要。（具体解析过程略）

重定位

符号解析完成后，代码中的每个符号引用就和一个符号定义联系起来，因此链接器就知道了输入目标模块中的代码节和数据节的确切大小，因而可以进行重定位操作：合并输入模块，并为每个符号分配运行时地址。重定位具体分为两步：

1. 重定位节和符号定义：将所有相同类型的节点合并为同一个类型的新的聚合节，然后将运行时存储器地址赋给新的聚合节，从而赋给输入模块定义的每个节、每个符号。当这一步完成时，程序中每个指令和全局变量都有唯一的运行时存储器地址了。
2. 重定位节中的符号引用：修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。这一步的执行依赖于可重定位目标模块中名为重定位条目的数据结构。当汇编器生成目标模块时，因为它并不知道数据和代码最终将存放在存储器中的什么位置，也不知道这个模块引用的任何外部定义的函数或者全局变量的位置，所以当汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，以告诉链接器将目标文件合并成可执行文件时如何修改这个引用。代码的重定位条目放在.rel.text中，已初始化数据的重定位条目放在.rel.data中。（ELF定义了11种不同的重定位类型，详略）

可执行目标文件

可执行目标文件包含加载程序到存储器并运行它所需的所有信息，ELF可执行文件结构如下：

+-------------+  ---------------
-   ELF头     - 
+-------------+
-   段头部表  -
+-------------+
-   .init     -   代码段（只读）
+-------------+
-   .text     -
+-------------+
-   .rodata   -
+-------------+  ---------------
-   .data     -
+-------------+   数据段（读写）
-   .bss      -
+-------------+  ---------------
-   .symtab   -
+-------------+
-   .debug    -
+-------------+
-   .line     -  不加载到存储器
+-------------+
-   .strtab   -
+-------------+
-   节头表    -
+-------------+  ---------------

.init节定义了一个名为_init的函数，程序的初始化代码会调用它。 因为可执行文件是完全链接的，即已经被重定位了，所以它不再需要.rel节。 段头部表用来将连续的文件节映射到运行时存储器段。 节头表描述目标文件的节信息。

执行可执行目标文件是通过调用驻留在存储器中的称为加载器的操作系统代码来运行的。加载器将可执行目标文件中的代码和数据从磁盘拷贝到存储器中，然后通过跳转到程序的第一条指令或入口点来运行该程序。

共享库

共享库是一个目标模块，在运行时可以加载到任意的存储器地址，并和一个在存储器中的程序链接起来，这个过程称为动态链接，由动态链接器来执行。在Unix中，共享库的后缀通常为.so。共享库以两种不同的形式来共享，首先在给定的文件系统中对于一个库只有一个.so文件的情况，所有引用该库的可执行目标文件都共享这个.so文件中的代码和数据，而不是像静态库的内容那样被拷贝和嵌入到引用它们的可执行的文件中。其次，在存储器中，一个共享库的.text节的一个副本可以被不同的正在运行的进程共享。

创建共享库形式的libvector.a，并使用：

gcc -shared -fPIC -o libvector.so addvec.c multvec.c
gcc -o p main.c ./libvector.so

-fPIC指示编译器生成与位置无关的代码，-shared指示链接器创建一个共享的目标文件。 如上创建的可执行目标文件p的形式使得它在运行时可以和libvector.so链接。链接器拷贝了一些重定位和符号信息，它们使得运行时可以解析对libvector.so中代码和数据的引用。当加载器加载已部分链接的可执行文件p时，它发现p中包含的.interp节，这个节包含动态链接器的路径名，动态链接器本身就是一个共享目标，加载器不再像通常那样将控制传递给应用，而是加载和运行这个动态链接器。然后动态链接器通过执行以下重定位来完成链接：

1. 重定位libc.so的文本和数据到某个存储器段；
2. 重定位libvector.so的文本和数据到另一个存储器段；
3. 重定位p中所有对由libc.so和libvector.so定义的符号的引用；

运行时加载和链接共享库

应用程序可以在它运行时要求动态链接器加载和链接任意共享库，而无需在编译时链接那些库到应用中。 现代高性能的Web服务器可以使用基于动态链接的方式来生成动态内容，其思路是将生成动态内容的每个函数打包在共享库中，当一个来自Web浏览器的请求到达时，服务器动态地加载和链接适当的函数，然后直接调用它，而不是使用fork和execve在子进程的上下文中运行函数。函数会一直缓存在服务器的地址空间中，所以只要一个简单的函数调用的开销就可以处理随后的请求了。 Linux系统为动态链接器提供了一个简单的接口，允许应用程序在运行时加载和链接共享库：

#include <dlfcn.h>
void *dlopen(const char *filename, int flag);

（详略）

第8章 异常控制流

程序除了应该对由程序变量表示的内部程序状态中的变化做出反应，还必须对系统状态的变化做出反应。比如一个硬件定时器产生的信号、新的包到达网络适配器、子进程终止等等。系统使用异常控制流（EFC）来处理，异常控制流发生在计算机系统的各个层次： 在硬件层，硬件检测到的事件会触发控制突然转移到异常处理程序； 在操作系统层，内核通过上下文切换将控制从一个用户进程转移到另一个用户进程； 在应用层，一个进程可以发出信号到另一个进程，而接收者会将控制转移到它的一个信号处理程序； 一个程序可以通过回避通常的栈规则，并执行到其他函数中任意位置的非本地跳转来对错误做出反应。

EFC是操作系统用来实现I/O、进程和虚拟存储器的基本机制。 应用程序通过陷阱（trap）或者系统调用（system call）的EFC形式向操作系统请求服务，操作系统为应用程序提供了强大的EFC机制。 EFC是计算机系统中实现并发的基本机制。 有些高级编程语言中提供try、catch、throw语句来实现软件异常机制，允许程序进行非本地跳转，即违反通常的调用/返回栈规则的跳转来响应错误情况，这其实属于一种应用层ECF，在C中是通过setjmp和longjmp函数提供的。

异常

在处理器中状态被编码为不同的位和信号，状态变化称为事件。事件可能和当前指令的执行直接相关，也可能无关。在任何情况下，当处理器检测到有事件发生时，就会通过一张名为异常表的跳转表进行一个间接的过程调用，即调用一个专门设计用来处理这类事件的操作系统子程序（异常处理程序）。

根据异常事件的类型，当异常处理程序完成处理后会发生以下三种情况中的一种：

1. 处理程序将控制返回给当前指令；
2. 处理程序将控制返回给当前指令的下一条指令；
3. 处理程序终止被中断的程序；

系统中给可能的每种类型的异常都分配了一个异常号，其中一些是由处理器分配的（除零、存储器访问违例、断点），其他的是由操作系统内核分配的。当系统启动时，操作系统分配和初始化异常表，其中每个条目包含指定异常的处理程序的地址。异常表的起始地址放在异常表基址寄存器（CPU中的特殊寄存器）中。

异常处理类似于过程调用，但又有一些不同之处：

1. 过程调用在跳转到处理程序之前，处理器会将返回地址压入栈中，而异常的返回地址则会根据类型可能是当前指令，也可能是下一条指令。
2. 处理器会把处理器状态压到用户栈里以便在处理程序返回时重新开始被中断的程序。如果异常控制从一个用户程序转移到内核，那么所有这些项目都被压到内核栈中，而不是压到用户栈中。
3. 异常处理程序运行在内核模式下，因此它们对所有的系统资源都有完全的访问权限。

一旦硬件触发了异常，剩下的工作就由异常处理程序在软件中完成，在处理程序处理完事件之后，它通过执行一条特殊的“从中断返回”指令，可选地返回到被中断的程序，该指令将适当的状态弹回到处理器的控制和数据寄存器中，如果异常中断的是一个用户程序，就将状态恢复为用户模式，然后将控制返回给被中断的程序。

异常有4种类别：

1. 中断：异步发生，是来自处理器外部的I/O设备的信号的结果，不是由任何专门的指令造成的。总是返回到下一条指令。I/O设备通过向处理器芯片上的一个引脚发信号，并将异常号（标识了引起中断的设备）放到系统总线上来触发中断。
2. 陷阱：同步发生，属于有意的异常，是执行一条指令的结果，返回到下一条指令。主要用来提供系统调用。
3. 故障：同步发生，由错误情况引起（比如缺页异常），如果处理程序能够修正这个错误情况，它就将控制返回到引起故障的指令，从而重新执行它，否则处理程序返回到内核中的abort例程，进而终止引起故障的应用程序。
4. 终止：同步发生，不可恢复的致命错误造成的结果，通常是一些硬件错误。处理程序会将控制返回给一个abort例程，进而终止引起故障的应用程序。

IA32系统提供了256种不同的异常和上百种系统调用，详略。

进程

进程的经典定义就是一个执行中的程序的实例。系统中的每个程序都是运行在某个进程的上下文中，上下文是由程序正确运行所需的状态组成的，包括存放在存储器中的程序的代码和数据，它的栈、通用目的存储器的内容、程序计数器、环境变量以及打开的文件描述符的集合。进程也能够创建新进程，且在这个新进程的上下文中运行它们自己的代码。

进程为程序提供了两个关键的抽象：

1. 一个独立的逻辑控制流：造成程序独占地使用处理器的假象；
2. 一个私有的地址空间：造成程序独占地使用存储器系统的假象；

进程是轮流使用处理器的，每个进程执行它的流的一部分，然后被抢占（挂起），然后轮到其他进程。一个逻辑流的全部执行时间与另一个流重叠，称为并发（即使它们运行在同一个处理器上）。一个进程和其他进程轮流执行称为多任务。一个进程执行它的控制流的一部分的每一时间段叫做时间片。

操作系统内核使用上下文切换（一种较高形式的异常控制流）来实现多任务：上下文就是内核重启一个被抢占的进程所需的状态，它由一些对象的值组成，包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构，比如页表、进程表、文件表等。内核为每个进程维持一个上下文，在程序执行的某些时刻（比如发生系统调用、中断等），内核可以决定抢占当前进程，并重新开始一个之前被抢占的进程，这被称为调度，由内核中的调度器执行。总之上下文切换执行3步操作：

1. 保存当前进程的上下文；
2. 恢复某个之前被抢占的进程被保存的上下文；
3. 将控制传递给这个新恢复的进程；

进程控制

描述了Unix中通过C操作进程的系统调用，即一些C函数，略。

通过fork()创建的子进程会得到与父进程用户级虚拟地址空间相同的一份拷贝，包括文本、数据和bss段、堆以及用户栈。子进程还会获得与父进程任何打开的文件描述符相同的拷贝，即子进程可以读写父进程中打开的任何文件。父进程与子进程之间最大的区别是它们的PID不同。

信号

Unix信号允许进程中断其他进程。信号是一条消息，通知进程系统中发生了一个某种类型的系统事件。低层的硬件异常是由内核异常处理程序处理的，正常情况下对用户进程而言是不可见的，信号则提供了一种机制通知用户进程发生了这些异常。

一个只发出而没有被接收的信号称为待处理信号，一种类型至多只会有一个待处理信号。如果一个进程已经有了一个特定类型的待处理信号，那么任何接下来发送到这个进程的同样类型的信号都不会排队等待，而是被直接丢弃。

内核通过更新目的进程上下文中的某个状态来发送一个信号给目的进程。发送信号可能有2个原因：

1. 内核检测到一个系统事件，比如除零或者子进程终止；
2. 一个进程调用了kill函数显示地要求内核发送一个信号给目的进程（也可以发送给自己）； 当目的进程被内核强迫以某种方式对信号的发送做出反应时，目的进程就接收了信号。进程可以忽略信号，也可以通过执行信号处理程序来捕获这个信号（有些信号，比如SIGKILL既不能被捕获，也不能忽略）。

kill程序可以向另外的进程发送任意的信号，比如向PID为15213的进程发送SIGKILL（编号为9）信号： kill -9 15213 键盘输入ctrl+c会发送一个SIGINT信号到shell，shell捕获到该信号后会发送SIGINT到这个前台进程组中的每个进程，在默认情况下会终止前台作业。

非本地跳转

C语言通过setjmp和longjmp函数提供了一种称为非本地跳转的用户级异常控制流，实现直接从一个函数转移到另一个当前正在执行的函数，而不需要经过正常的调用-返回序列。非本地跳转的一个重要应用是允许从一个深层嵌套的函数调用中立即返回。另一个重要应用是使一个信号处理程序分支到一个特殊的代码位置，而不是返回到被信号中断了的指令的位置。

（示例太长，略）

第9章 虚拟存储器

虚拟存储器是系统提供的一种对主存的抽象，为每个进程提供了一个大的、一致的、私有的地址空间。 注意：这里“私有”指的是每个进程的虚拟内存空间是私有的，但是不同进程的虚拟内存空间中的地址可能指向相同的物理地址。

物理寻址与虚拟寻址

物理主存被组织成一个由连续字节组成的数组，每个字节都有一个唯一的物理地址。早期的CPU使用物理寻址，即CPU通过存储器总线直接读取主存上特定物理地址的内容到寄存器中。现代处理器使用虚拟寻址方式，通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址（地址翻译）。CPU上的存储器管理单元（MMU）利用存放在主存中的查询表（页表）来动态地翻译虚拟地址，该表的内容由操作系统管理。

虚拟存储器提供3个重要的功能：

1. 在主存中自动缓存最近使用的存放在磁盘上的虚拟地址空间的内容。
2. 虚拟存储器简化了存储器管理，进而简化了链接、在进程间共享数据、进程的存储器分配以及程序加载。
3. 虚拟存储器通过在每条页表条目中加入保护位，从而简化了存储器保护。

虚拟存储器作为缓存的工具

（略）

虚拟存储器作为存储器管理的工具

（略）

虚拟存储器作为存储器保护的工具

每个PTE（页表条目，Page table entity）中有3个位用于实现存储器保护：

1. SUP位表示进程是否必须运行在内核模式下才能访问该页，运行在用户模式中的进程只能访问那些SUP为0的页面；
2. READ位控制对页面的读；
3. WRITE位控制对页面的写； 如果一条指令违反了这些许可条件，那么CPU将触发一个保护故障（段错误 segmentation fault），将控制传递给一个内核中的异常处理程序。

地址翻译

当页命中时，CPU硬件的执行步骤如下：

1. 处理器生成一个虚拟地址，并把它传送给MMU；
2. MMU生成PTE地址，并从高速缓存/主存中请求得到它；
3. 高速缓存/主存向MMU返回PTE；
4. MMU构造物理地址，并把它传送给高速缓存/主存；
5. 高速缓存/主存返回所请求的数据字给处理器； 可见页命中完全是由硬件处理的。

当缺页时，需要硬件和操作系统内核协作完成，步骤如下：

1. 处理器生成一个虚拟地址，并把它传送给MMU；
2. MMU生成PTE地址，并从高速缓存/主存中请求得到它’
3. 高速缓存/主存向MMU返回PTE；
4. PTE中的有效位为零，所以MMU触发一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序；
5. 缺页处理程序确定出物理存储器中的牺牲页，如果这个页已经被修改了，则把它换出到磁盘；
6. 缺页处理程序调入新的页，并更新存储器中的PTE；
7. 缺页处理程序返回到原来的进程，再次执行导致缺页的指令，CPU将引起缺页的虚拟地址重新发送给MMU。因为虚拟页面现在缓存在物理存储器中，所以就会被命中，主存会将所请求的字返回给处理器。

在MMU中包括了一个关于PTE的小的缓存，称为TLB（翻译后备缓冲器）。在有TLB，且TLB命中的情况下，CPU的执行步骤如下：

1. 处理器生成一个虚拟地址，并把它传送给MMU；
2. MMU从TLB中取出相应的PTE；
3. MMU构造物理地址，并把它传送给高速缓存/主存；
4. 高速缓存/主存返回所请求的数据字给处理器；

存储器映射

现代系统通过将虚拟存储器片和磁盘上的文件片关联起来，以初始化虚拟存储器片，这个过程称为存储器映射，这为共享数据、创建新的进程以及加载程序提供了一种高效的机制。 （略）

动态存储器分配

动态存储器分配器维护着一个进程的虚拟存储器区域，称为堆。堆是一组不同大小的块的集合，每个块就是一个连续的虚拟存储器片，要么是已分配的，要么是空闲的。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式地执行，要么是存储器分配器自身隐式地执行，对应的分配器有两种风格：

1. 显式分配器：要求应用显式地释放任何已分配的块，例如C中的malloc，free，C++中的new，delete；
2. 隐式分配器：例如Java的垃圾回收机制；

碎片是造成堆利用率低的主要原因。有两种形式的碎片：

1. 内部碎片：在一个已分配块比有效负荷大时发生，如为了满足字节对齐而额外分配的空间。
2. 外部碎片：当空闲存储器空间合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生。

垃圾收集

垃圾收集器将存储器视为一张有向图，由堆节点组成，每个堆节点对应堆中一个已分配的块，当存在一条从任意根节点（根节点是一些不在堆中的位置，但是它们包含指向堆中的指针）出发并达到p节点的有向路径时，就说节点p是可达的，而不可达的节点就是垃圾，是不能被应用再次使用的。垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点来定期地回收它们。

第10章 系统级I/O

I/O是在主存和外设（磁盘驱动器、终端、网络等）之间拷贝数据的过程。编程语言都提供了执行I/O的库，如C标准库中的I/O库（包含printf和scanf等），C++中的«和»。在Unix系统上它们都是通过由内核提供的系统级Unix I/O函数来实现这些较高级别的I/O函数的，大多数情况下没有必要直接使用Unix I/O），但是在某些重要的情况下使用高级I/O函数不太可能，或者不太合适，比如标准I/O库没有提供读取文件元数据的方式（文件大小、创建时间等），此外I/O库也存在一些问题使得用它来进行网络编程非常冒险。

Unix I/O

所有的I/O设备都被模型化为文件，所有的输入、输出操作都被当做对相应文件的读和写来执行。一个Unix文件就是一个字节的序列，Unix使用Unix I/O来使得所有的输入、输出都能以一种统一且一致的方式执行，Unix I/O的操作包括：

1. 打开文件：内核返回一个非负整数，叫做文件描述符，后续对此文件的所有操作都通过这个文件描述符进行（应用程序只要记住这个描述符，内核记录有关这个已打开文件的所有信息）；Unix Shell创建的每个进程开始时都有3个打开的文件：标准输入（0）、标准输出（1）、标准错误（2）；
2. 改变当前的文件位置：对于每个打开的文件内核都维持了一个当前位置，记录了从文件开头起始的字节偏移量，初始为0。应用程序能够通过执行seek操作显式地设置文件的当前位置；
3. 读写文件：一个读操作就是从文件拷贝若干字节到存储器，当当前位置超过文件大小时，会触发一个EOF事件。写操作就是从存储器拷贝若干字节到一个文件；
4. 关闭文件：内核会释放文件打开时创建的数据结构，并将文件描述符恢复到可用的描述符池中。无论一个进程因为何种原因终止，内核都会关闭所有打开的文件并释放它们的存储器资源；

打开和关闭文件

/* 打开文件
filename 文件名
flags 打开方式：只读、只写、读写
mode 指定新文件的访问权限位（umask）
*/
int open(char *filename, int flags, mode_t mode);

如：

umask(DEF_UMASK);
fd = open('foo.txt', O_CREAT|O_TRUNC|O_WRONLY, DEF_MODE);
...

// 关闭文件
int close(int fd);
关闭一个已关闭的描述符会出错（返回-1）。

读和写文件

ssize_t read(int fd, void *buf, size_t n);
ssize_t write(int fd, const void *buf, size_t n);

如：

char c;
while( read(STDIN_FILENO, &c, 1) != 0 ){
	write(STDOUT_FILENNO, &c, 1);
}
exit(0);

在某些情况下read和write传送的字节比应用程序要求的要少，这些不足值不表示有错误，可能由如下原因引起：

1. 读文件时遇到EOF；
2. 从终端读文本行，这种情况下read函数将一次传送一个文本行；
3. 读和写网络套接字时，内部的缓冲约束和较长的网络延迟都会引起read和write返回不足值；
4. 对Unix管道调用read和write时也有可能出现不足值；

健壮地读写

RIO包（Robust I/O）会自动处理不足值的情况，实现方便、健壮和高效的I/O。

// 无缓冲的输入函数
ssize_t rio_readn( int fd, void *usrbuf, size_t n ){
    size_t nleft = n;
    ssize_t nread;
    char *bufp = usrbuf;

    while( nleft > 0 ){
        if( (nread = read(fd,bufp,nleft)) < 0 ){
        	if(errno == EINTR){  // 被信号打断（Interrupted）
        		nread = 0; // 再次调用read()
        	}
        	else{
        		return -1;
        	}
        }
        else if(nread == 0){ // EOF（已无可读数据，比如n大于文件的实际长度）
        	break;
        }
        nleft -= nread;
        bufp += nread;
    }
    return ( n - nleft );  // return >= 0
}

// 无缓冲输出函数
ssize_t rio_writen( int fd, void *usrbuf, size_t n ){
	size_t nleft = n;
    ssize_t nwritten;
    char *bufp = usrbuf;

    while( nleft > 0 ){
    	if( (nwritten = write(fd,bufp,nleft)) <= 0 ){
    		if(errno == EINTR){  // 被信号打断（Interrupted）
        		nwritten = 0; // 再次调用write()
        	}
        	else{
        		return -1;
        	}
    	}
    	nleft -= nwritten;
        bufp += nwritten;
    }
    return n;
}

// 缓冲区格式
\#define RIO_BUFSIZE 8192
typedef struct {
	int rio_fd;        // 缓冲区描述符
	int rio_cnt;       // 缓冲区中未被读取字节数
	char *rio_bufptr;  // 下一个未读取字节的起始位置 
	char rio_buf[RIO_BUFSIZE];   // 缓冲区
} rio_t;

// 初始化缓冲区的函数（将一个已打开的文件描述符与一个缓冲区联系起来）
void rio_readinitb(rio_t *rp, int fd){
	rp->rio_fd = fd;
	rp->rio_cnt = 0;
	rp->rio_bufptr = rp->rio_buf;
}

// 带缓冲区的read函数
static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n){
	int cnt;
	while( rp->rio_cnt <= 0 ){ // 当缓冲区为空时，则填充缓冲区
		rp->rio_cnt = read( rp->rio_fd, rp->rio_buf, sizeof(rp->rio_buf));
		if(rp->rio_cnt < 0){
			if(errno != EINTR){
				return -1;
			}
		}
		else if(rp->rio_cnt == 0){
			return 0;
		}
		else{
			rp->rio_bufptr = rp->rio_buf;
		}
	}

	cnt = n;
	if( rp->rio_cnt < n ){
		cnt = rp->rio_cnt;
	}
	memcpy(usrbuf,rp->rio_bufptr,cnt);
	rp->rio_bufptr += cnt;
	rp->rio_cnt -= cnt;
	return cnt;
}

一个文本行就是一个由\n结尾的ASCII码字符序列。假设要编写一个计算文本文件中文本行数的函数，如果使用read一次一个字节地从文件传送到用户存储器，通过检查每个字节来查找换行符，这种方式的缺点是效率太低，因为每读取文件中一个字节都要陷入内核。

// 带缓冲区的输入函数（读文本行）
// 最多读maxlen-1个字节，余下的一个字节留给结尾的空字符
ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen){
	int n,rc;
	char c,*bufp = usrbuf;

	for( n = 1; n < maxlen; n++){
		if((rc = rio_read(rp, &c, 1)) == 1){
			*bufp++ = c;
			if(c == '\n'){
				break;
			}
		}else if( rc == 0 ){
			if( n == 1 ){
				return 0;  // EOF no data
			}
			else{
				break;  // EOF some data was read
			}
		}
		else{
			return -1;  // Error
		}
	}
	*bufp = 0;
	return n;
}

// 带缓冲区的输入函数（读字节）
ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n){
	size_t nleft = n;
	ssize_t nread;
	char *bufp = usrbuf;

	while( nleft > 0 ){
		if( (nread = rio_read(rp,bufp,nleft)) < 0 ){
			if( errno == EINTR){
				nread = 0;
			}
			else{
				return -1;
			}
		}
		else if(nread == 0){
			break;
		}
		nleft -= nread;
		bufp += nread;
	}
	return ( n-nleft );
}

读取文件元数据

应用程序可以通过调用stat或fstat函数来检索文件信息，具体的信息通过结构体stat描述。

struct stat{
	dev_t         st_dev;      // device
	ino_t         st_ino;      // inode
	mode_t        st_mode;     // 文件访问许可位和文件类型
	nlink_t       st_nlink;    // 硬链接数
	uid_t         st_uid;      // user id
	gid_t         st_gid;      // group id
	dev_t         st_rdev;     // device type
	off_t         st_size;     // 文件大小（字节数）
	unsigned long st_blksize;  // blocksize for filesystem I/O
	unsigned long st_blocks;   // 已分配的block的数量
	time_t        st_atime;    // 最后访问时间
	time_t        st_mtime;    // 最后修改内容时间
	time_t        st_ctime;    // 最后修改属性（inode）时间
};

int stat( const char *filename, struct stat *buf );
int fstat( int fd, struct stat *buf );

例如输入文件名，解析其类型：

int main( int argc, char **argv ){
	struct stat stat;
	char *type,*readok;

	stat(argv[1],$stat);
	if( S_ISREG(stat.st_mode) ){  // 普通文件
		type = "regular";
	}
	else if( S_ISDIR(stat.st_mode) ){ // 目录
		type = "directory";
	}
	else{
		type = "other";
	}

	if((stat.st_mode & S_IRUSR)){
		readok = "yes";
	}
	else{
		readok = "no";
	}

	printf("type:%s,read:%s\n",type,readok);
	exit(0);
}

共享文件

内核用3个相关的数据来表示打开的文件：

1. 文件描述符表：每个进程都有自己的文件描述符表，表项为进程打开的文件描述符，每个文件描述符指向文件表中的一项；
2. 文件表：打开文件的集合用文件表描述，所有进程共享这张表。每个文件表项包括有文件当前位置、引用计数、一个指向v-node表中对应表项的指针。关闭一个文件描述符会减少相应的文件表表项中的引用计数，内核会在引用计数为0时删除这个表项；
3. v-node表：每个表项包含stat结构中的大多数信息，包括st_mode、st_size等，所有进程共享这张表；

多个描述符可以通过不同的文件表表项来引用同一个文件，如以同一个filename来调用open两次。每个描述符都有它自己的当前位置，所以对不同描述符的读操作可以从文件的不同位置获取数据。 在调用了fork之后，子进程有一个父进程描述符表的副本，因此父子进程共享相同的文件表集合，从而共享相同的文件位置。

I/O重定向

可以使用dup2函数实现重定向： int dup2( int oldfd, int newfd ); 基本原理是拷贝文件描述符表中oldfd的内容到newfd，使得两个描述符都指向相同的文件表项，从而实现输出数据的重定向。

I/O函数选择

标准的I/O函数是磁盘和终端设备I/O之选，大多数情况下不会涉及低级的Unix I/O函数。但是当试图对网络输入输出使用标准I/O时会有问题，Unix对网络的抽象是套接字文件类型，也使用文件描述符来引用，称为套接字描述符。标准I/O流是全双工的，因为程序能够在同一个流上进行输入和输出，但是对于套接字流会有限制：

1. 如果中间没有插入对fflush、fseek、fsetpos或者rewind的调用，输入函数不能跟在输出函数之后；
2. 如果中间没有插入对fseek、fsetpos或者rewind的调用，输出函数不能跟在输入函数之后，除非该输入函数遇到了一个EOF； 但是对套接字使用fseek、fsetpos、rewind等函数是非法的。限制1可以通过采用在每个输入操作前刷新缓冲区来满足，如果使用标准I/O解决限制2的唯一办法是：对同一个打开的套接字描述符打开两个流，一个用来读，一个用来写。但是这样会带来另一个问题，因为程序必须在两个流上都调用fclose才能释放与每个流相关联的存储器资源，避免存储器泄露，但是当第一个关闭操作执行后，第二个关闭操作就会失败。对于顺序执行的程序这不是问题，但是在多线程的程序中关闭一个已经关闭了的描述符会导致灾难。 因此，在网络套接字上不要使用标准的I/O函数来进行输入和输出，而应该使用健壮的比如RIO函数。

第11章 网络编程

网络基础

所有的网络应用都是基于相同的基本编程模型，有着相似的整体逻辑结构，并且依赖相同的编程接口。 每个网络应用都是基于客户端-服务器模型。这里的客户端和服务器是指进程，而不是机器或者主机。 每台因特网主机都运行实现了TCP/IP协议的软件，因特网的客户端和服务器混合使用套接字接口函数和Unix I/O函数来进行通信，套接字函数通常会作为陷入内核的系统调用来实现，并调用各种内核模式的TCP/IP函数。

TCP/IP为数据项定义了统一的网络字节顺序，即大端字节顺序。

一个套接字是连接的一个端点，每个套接字都有相应的套接字地址，是由一个因特网地址和一个16位的整数端口组成的。 从Unix程序的角度来看，套接字就是一个有相应描述符的打开文件。

套接字接口

套接字接口是一组函数，大多数现代操作系统上都实现了套接字接口，概述如下图：

（函数略）

第12章 并发编程

现代操作系统提供了3种基本的构造并发程序的方法：多进程、I/O多路复用、多线程。

基于进程的并发编程

每个逻辑控制流都是一个进程，由内核来调度和维护。因为进程有独立的虚拟地址空间，所以要想和其他进程通信，控制流必须使用某种显式的进程间通信机制（比较慢）。 如服务器端监听特定的端口，当有新的客户端连接时，创建新的端口号，并派生一个子进程，子进程使用这个新的端口号与客户端进行通信。这样，当有多个客户端连接时，它们将以多进程的方式并发地执行。 子进程与父进程共享文件表，但是不共享用户地址空间。

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

应用程序在一个进程的上下文中显式地调度它们自己的逻辑流，逻辑流被模型化为状态机，数据达到文件描述符后，主程序显式地从一个状态机换到另一个状态机。因为程序是一个单独的进程，所以所有的流都共享同一个地址空间。 基本的思路是使用select函数，要求内核在发生读写操作时挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序。

// 返回已准备好的描述符的个数

int select(int n, fd_set *fdset, NULL, NULL, NULL);

I/O多路复用可以作为并发事件驱动程序的基础。在事件驱动程序中，将逻辑流模型化为状态机，一个状态机就是一组状态、输入事件和转移。其中转移就是将状态和输入事件映射到新的状态。对于每个新的客户端，基于I/O多路复用的并发服务器会创建一个新的状态机，并将它和已连接的描述符联系起来。每个状态机都有一个状态：等待相应的描述符准备好可读；一个输入事件：描述符可读了；一个转移：从描述符读一个文本行。 服务器使用I/O多路复用，借助select函数检测输入事件的发生，当每个已连接描述符准备好可读时，服务器就为相应的状态机执行转移。

基于I/O多路复用的事件驱动服务器是运行在单一进程上下文中的，因此每个逻辑流都能访问该进程的全部地址空间，这使得在流之间共享数据非常容易。

基于线程的并发编程

线程是运行在进程上下文中的逻辑流，由内核自动调度，每个线程都有自己的线程上下文，包括唯一的线程ID、栈、程序计数器、通用目的寄存器和条件码等。所有运行在一个进程里的线程共享该进程的整个虚拟地址空间。

基于线程的逻辑流结合了基于进程和基于I/O多路复用的流的特性，同进程一样，线程由内核自动调度，并且内核会通过一个整数ID来识别线程。同基于I/O多路复用的流一样，多个线程运行在单一进程的上下文中，因此共享这个进程虚拟地址空间的整个内容：代码、数据、堆、共享库、打开的文件。

每个进程开始时都是单一线程，这个线程称为主线程，之后在某一时刻主线程创建一个对等线程（peer thread），然后两个线程就并发地运行。当主线程执行一个慢速系统调用时，因为它被系统的间隔计时器中断，控制就会通过切换上下文传递到对等线程，对等线程执行一段时间后再将控制传递回主线程。

线程不同于进程的方面在于线程的上下文要比进程小很多，线程的上下文切换也比进程的上下文切换开销小。此外不像进程那样严格地按照父子层次来组织，一个进程的所有线程组成一个对等线程池，独立于其他进程创建的线程。因为有对等线程池，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。每个对等线程都能读写相同的共享数据。

Posix线程

Posix线程是在C程序中处理线程的一个标准接口，在大多数Unix系统上都可用，定义了大约60个函数（以Pthread_开头），可以执行创建、杀死、回收线程，与对等线程安全地共享数据，通知对等线程系统状态的变化等等。

多线程程序中的共享变量

信号量，P、V操作，同步、互斥等，略。

AT LAST ! Tiny Web Server

twc(tiny web server)