深入理解计算机系统

[TOC]

计算机系统漫游

信息就是位+上下文。
源程序实际上就是一个由值0和1组成的位(bit)序列，8个位被组织成一组，称为字节。
只由ASCII字符构成的文件称为文本文件，所有其他文件都称为二进制文件。
C语言程序的执行过程包含四个阶段，
预处理——将修改原始C程序，比如把#include的文件插入到程序文本中，由.c变成.i
编译——将C语言翻译成汇编语言，输出.s
汇编——将.s文件翻译成机器指令文件(二进制)，也叫可重定位目标程序(relocatable object program)，输出.o
链接——比如一个程序里调用了printf函数，而每个C编译器都会提供标准C库中的一个函数，存在于printf.o中，链接器将负责处理这个文件的合并，最终得到的文件是一个可执行目标文件，可以被加载到内存中，由系统执行。
系统的硬件组成
总线携带信息字节并负责在各个部件间传递。通常总线被设计成传送定长的字节块，也就是字(word)。字中的字节数(字长)是一个基本的系统参数。现在大多数机器字长有的是4个字节(32位)，有的是8个字节(64位)。
主存是一个临时存储设备，在处理器执行程序时，用来存放程序和程序处理的数据。从物理上来说，主存是由一组动态随机存取存储器(DRAM)芯片组成。从逻辑上来说，存储器是一个线性的字节数组，每个字节都有其唯一的地址(即数组索引)，这些地址是从0开始的。

处理器是解释或执行存储在主存中指令的引擎。处理器的核心是一个字长的存储设备(寄存器)，称为程序计数器(PC)。在任何时刻，PC都指向主存中的某条机器语言指令(即含有该条指令的地址)。

处理器和主存的数据交互要通过主线速度慢，而通过处理器的高速缓存存储器则快的多，其中L1高速缓存和寄存器一样快，L2通过特殊的总线连接到处理器，比L1的时间长5倍，但是仍比访问主存快5~10倍。甚至还有三级高速缓存L3.
操作系统实现两个功能，1，防止硬件被失控的程序滥用。2，向应用程序提供一种简单一致的机制来控制复杂的低级硬件设备。操作系统通过几个基本抽象概念(进程、虚拟存储器和文件)来实现这两个功能。
文件是对I/O设备的抽象，
虚拟存储器是对主存和I/O设备的抽象
进程则是对处理器、主存、I/O设备的抽象
进程是操作系统对一个正在运行的程序的一种抽象。

一个CPU看上去像是在并发得执行多个进程，这是通过处理器在进程间切换实现的，这种机制叫做上下文切换。

操作系统保持跟踪进程运行所需的所有状态信息。这种状态也就是上下文。
虽然我们认为一个进程只有单一的控制流，但是进程实际上可以由多个成为线程的执行单元组成。每个线程都运行在进程的上下文中。
虚拟存储器是一个抽象概念，它让每个进程都以为自己在独占地使用主存。每个进程看到的是一致的存储器，称为虚拟地址空间。地址是下往上增大的。
文件就是字节序列。

信息的表示和处理

大多数的计算机使用八位的块，或者字节，作为最小的可寻址的存储器单元。
机器级别程序将存储器视为一个非常大的字节数组，称为虚拟存储器。存储器的每个字节都由唯一的数字来标示，称为他的地址，所有可能地址的集合称为虚拟地址空间。
十六进制(hex)使用0-9A-F来表示，C语言中，用0x或0X开头的数字常量来表示，比如0XFA1D37B。一个字节的值域从00~FF

0 1 2 …… F

0000 0001 0010 1111
16进制转2进制，每个数字转成2进制，比如0X173A4C

000101110011101001001100
2进制转16进制，每四位一组，如果不是4的倍数，最左边一组可以前面用0补位。
2^n的二进制表示就是1的后面n个0.
每个计算机都由一个字长(word size)，指明整数和指针数据的标称大小。因为虚拟地址就是以字来编码的，所以字长决定了虚拟地址空间的最大大小。
C的数据类型char表示一个单独的字节。大多多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。
C中的字符串被编码为一个以null字符结尾的字符数组。每个字符都由某个标准编码来表示，最常见的为ASCII字符码。

程序的机器级表示

GCC C语言编译器以汇编代码的形式产生输出，汇编代码是机器代码的文本表示。GCC调用汇编器和链接器，从而根据汇编代码生成可执行的机器代码。
本章基于两种相关的机器语言：Intel IA32（Intel Architecture 32bit Intel 32位体系结构）和x86-64，后者是前者在64位机器上运行的扩展。
Intel处理器系列俗称x86.
计算机系统使用了多种不同形式的抽象，有两种尤为重要：

1，机器级程序的格式和行为，定义为指令集体系结构（ISA），它定义了处理器状态、指令的格式，以及每条指令对状态的影响。大多数ISA，包括IA32和x86-64，将程序的行为描述成好像每条指令都是按顺序执行的，一条接一条。而其实它们是并发地执行，但是可以采取措施保证整体行为和ISA指定的顺序执行完全一致。

2，机器级程序使用的存储器地址是虚拟地址，提供的存储器模型看上去是一个非常大的字节数组。

IA32机器代码和C代码差别很大，比如一些处理器状态是可见的：

程序计数器，通常称为PC，用%eip表示，指示将要执行的下一条指令在存储器中的地址。

整数寄存器文件包含8个命名的位置，分别存储32位的值。主要用来存地址、整数、某些程序状态、临时数据如过程的局部变量和函数的返回值。

条件码寄存器，保存着最近执行的算术或逻辑指令的状态信息。

一组浮点寄存器存放浮点数据。
程序存储器program memory包含：程序的可执行机器代码，操作系统需要的信息用来管理过程调用和返回的运行时栈以及用户分配的存储器块。

程序存储器用虚拟地址来寻址。在任意给定的时刻，只认为有限的一部分虚拟地址是合法的（即使32位系统可以寻址4G地址范围，但通常一个程序只会访问几兆字节）。操作系统负责管理虚拟地址空间，将虚拟地址翻译成实际处理器存储器processor memory中的物理地址。
可以使用gcc -O1 -S code.c来得到汇编代码。

用gcc -O1 -c code.c来编译并汇编该代码，得到目标文件code.o。

用objdump -d code.o反汇编得到汇编代码。
C语言基本数据类型对应的IA32的表如下：

由于是从16位体系结构扩展成32位的。Intel用术语字word表示16位数据类型。32位称为双字double words，64位为四字quad words。

大多数数据类型都是双字存储的。比如int和long int。此外所有的指针都存储位四字节的双字。

大多数GCC生成的汇编代码指令都有一个字符后缀，表明操作数大小，例如movb传送字节，movw传送字，movl传送双字。
一个IA32中央处理单元CPU包含一组8个存储32位值得寄存器。

这些寄存器用来存储整数数据和指针。

他们的名字都以%e开头。前六个可以看成通用寄存器，大多数情况对它们的使用没有限制。

最后两个寄存器保存着指向程序栈中重要位置的指针。只有根据栈管理的标准惯例才能修改这两个寄存器中的值。

字节操作指令可以独立地读或者写前4个寄存器的两个低位字节。当一条字节指令更新这些单字节寄存器元素中的一个时，该寄存器余下的3个字节不会改变。
操作数指示符。

大多数指令有一个或多个操作数operand。IA32支持多种操作数格式：

源数据可以以常数形式给出，或者从寄存器或存储器中给出。结果可以放在寄存器或存储器中。

不同操作数分为三种：

一，立即数immediate，也就是常数值。

书写方法时$根一个用标准C表示法表示的整数，比如$-577,$0x1F.

任何能放进一个32位的字里的数值都可以用作立即数。

二，寄存器register，他表示某个寄存器的内容。

对于双字操作来说，它可以是8个32位寄存器中的一个，如%eax。

对字操作来说，可以是8个16位寄存器中的一个，例如%ax.

对字节操作来说，可以是8个单字节寄存器元素中的一个，如%al。

在上图中，我们用Ea来表示任意寄存器a，用引用R[Ea]来表示它的值，这是将寄存器集合看成一个数组R，用寄存器表示作为索引。

三，存储器memory引用，它会根据计算出来的地址（通常称为有效地址）访问某个寄存器位置。因为将存储器看成一个很大的字节数组，我们用符号Mb[Addr]表示对存储在存储器中从Addr开始的b个字节值的引用。为了方便我们通常省略Mb中的b。

从上图可以看出，有多种不同的寻址模式。格式为代码中操作数表现出来的格式，操作数值表示要将左边的表现形式转换成实际的值要经过的运算。 看下面例题做一下能体会上面说的是什么意思。
数据传送指令。

这儿分为了3类，区别是操作数大小不同。

MOV类中的指令将源操作数的值复制到目的操作数中。

可以把立即数、寄存器、存储器中的值复制到寄存器或者存储器。

IA32中有一条限制：传送指令的两个操作数不能都指向存储器位置。

上面的b、w、l分别对应传送8位单字节、16位字、32位双字。

MOVS和MOVZ都是将一个较小的源数据复制到一个较大的数据位置，高位用符号的位扩展MOVS或者零扩展MOVZ进行填充。
栈是一个数据结构，遵循后进先出原则。弹出的值永远是最近被压入而仍然在栈中的值。在IA32中，程序栈存放在存储器中某个区域。栈向下增长，栈顶元素位置最低。栈指针%esp保存着栈顶元素的地址。

pushl %eax压栈操作：

将一个双字值压入栈中，首先要将栈指针减4，然后将值复制到新的栈顶地址。

pushl %ebp等效于：
```
subl $4,%esp  
movl %ebp,(%esp)  
```
如上面的图，pushl操作的时候，先把%esp减4（为什么是4？因为每个地址比如0x00000108对应1byte空间，所以4个地址对应的就是4byte空间，即双字），得到0x104，然后会将0x123保存到0x104处。

popl %edx出栈操作：

从栈顶位置复制数据，然后将栈指针加4.等效于：
```
movl (%esp),%edx  
addl $4,%esp  
```
如上面的图，先从存储器中读出值0x123，写到寄存器%edx中，然后给%esp加4变成0x108.

也可以用标准的存储器寻址方法访问栈内任意数据，比如movl 4(%esp),%edx会将栈顶第二个双字复制到寄存器%edx。

C语言中的指针，其实就是地址。间接引用指针就是将该指针放在一个寄存器中，然后在存储器引用中使用这个寄存器。

C语言中的局部变量通常保存在寄存器中，而不是存储器中。因为寄存器中速度快得多。
****算术和逻辑操作。

在上表中，除了leal，其余都带有操作数大小的变种，如ADD有addb、addw、addl。上面分成了四组：加载有效地址、一元操作、二元操作和位移。
加载有效地址：

leal实际上是movl的变形，它看上去是从存储器读数据到寄存器，而其实它是把有效地址写入到目的操作数。相当于&S取地址操作，这样D就是一个指针，它可以为后面的存储器产生指针。
一元操作和二元操作：

如上图。二元操作和mov一样，两个操作数不能同时是存储器位置。
位移操作：

允许进行0-31位的移位。

左移将右边填上0.

右移中，SAR执行算术移位，填上符号位。SHR执行逻辑移位，填上0.
控制。

机器代码提供两种基本的低级机制来实现有条件的行为：测试数据值，然后根据测试的结果来改变控制流或者数据流。

jump指令可以改变一组机器代码指令的执行顺序。
条件码：

CPU维护着一组单个位的条件码condition code寄存器，它们描述了最近的算术或逻辑操作的属性。可以检测这些寄存器来执行条件分支程序。条件码寄存器的条件码有如：

CF：进位标志。最近的操作使最高位产生了进位。

ZF：零标志。最近的操作得出的结果为0.

SF：符号标志。最近的操作得到的结果为负数。

OF：溢出标志。最近的操作导致一个补码溢出。

比如我们用ADD完成一个t=a+b的功能，然后等效于条件码各种情况如下：

CF: (unsigned) t < (unsigned) a 无符号溢出

ZF: (t == 0) 零

SF: (t < 0) 负数

OF:(a < 0 == b < 0) && (t < 0 != a < 0) 有符号溢出

在上面逻辑和算术运算的列表中，除了leal指令，其余的都会设置条件码。

除了上面，还有两类指令会设置条件码，而且只设置条件码寄存器而不改变其他其他寄存器。

CMP指令根据两个操作数之差来设置条件码。除了结果设置，其余和SUB一样。

TEST指令的行为和AND一样，除了值设置条件码。
访问条件码。

条件码通常有三种使用方法：

1，根据条件码某个组合，如SF^OF根据条件码某个标志，将一个字节设置为0.

2，可以条件跳转到程序的某个其他的部分。

3，可以有条件地传送数据。

对于第一种，有一类SET指令，见表。他们的区别是条件码的组合。比如setl和setb中的l、b代表的不是long word和byte。

一条SET指令的目的操作数是8个单字节寄存器元素之一，或者是存储一个字节的存储器位置，将这个字节设置为0或1.
跳转指令及编码。

跳转指令会导致执行切换到程序中一个全新的位置。跳转目的通常用一个标号label指明。

如上图，跳转可以是直接跳转，也可以是间接跳转，跳转目标是从寄存器或存储器位置中读的。如jmp *%eax，或者以寄存器中的值为跳转目标：jmp *(%eax).

循环。

do-while循环。如果使用goto语句表示：

loop:
    body-statement
    t = test-expr;
    if(t)
        goto loop;

061041426026694
while循环。转换成goto语句如下：

t = test-expr;
if(!t)
    goto done;
loop:
    body-statement
    t = test-expr;
    if(t)
        goto loop;
done:

这段代码，会一开始就测试。用上面的阶乘来看： 061101533057637
for循环。
for循环如果我们分析，也能将它改成do-while结构的goto语句：

init-expr:
t = test-expr;
if(!t)
    goto done;
loop:
    body-statement;
    update-expr;
    t = test-expr;
    if(t)
        goto loop;
done:

由此可见，所有循环都可以用一种简单的策略来翻译。控制的条件转移为循环翻译成机器语言提供了基本机制。 062309118203749

条件传送指令。如上面实现条件操作的传统方法是利用控制的条件转移。当条件满足时，程序沿着一条执行路径进行，当条件不满足时，就走另外一条路径。这种机制在现代处理器上，可能非常的低效。

数据的条件转移是一种替代策略。这种方法先计算一个条件的两种结果，再根据条件是否满足而选取一个。如果可行，就可以利用一条简单的条件传送指令来实现它。

来看一个数据的条件转移例子：

可以从右边b图看到，它没有使用goto语句，而是使用了条件数据传送。这种代码比基于条件控制转移的代码性能好。

因为处理器通过使用流水线pipelining来获得高性能。处理器采用非常精密的分支预测逻辑试图猜测每条跳转指令是否会执行。错误预测会带来大约20~40个时钟周期的浪费。

下图的条件传送指令，随着PentiumPro微处理器的出现增加到IA32指令集中。他们一般都有两个操作数。这些指令的结果取决于条件码的值。

使用条件传送也不是总会改进代码效率，比如求值需要大量的计算，当相应条件不满足时会造成浪费。

总之，条件数据转移提供了一种用条件控制转移来实现条件操作的替代策略。
switch语句。

它通过跳转表jump table这种数据结构使得实现得高效。当开关情况数量较多，且值的范围跨度较小时，就会使用跳转表。跳转表是一个数组，表项i是一个代码段的地址。程序代码用开关索引值来执行一个跳转表内的数组引用，确定跳转指令的目标。在上面的例子中，右边为c的扩展形式。这儿的jt包含7个表项，每个都是一个代码块的地址。这儿的符号&&，代表一个指向代码位置的指针。

下图是汇编代码。从上面右边图中可以看到，其将跳转表申明为有7个元素的数组（因为值范围为7，每个下标对应的是要跳转的地址，这些地址有重复的来应对缺失和重复）

如上面的图所示的汇编代码。而跳转表则用如下的代码来表示：
```
   .section       .rodata
    .align 4
.L7:
    .long   .L3   #100的情况，跳转到loc_A
    .long   .L2   #101 跳转到loc_def
    .long   .L4   #102 loc_B
    .long   .L5   #103 loc_C
    .long   .L6   #104 loc_D
    .long   .L2   #105 loc_def
    .long   .L6   #106 loc_D
```
上图列出了7中不同情况跳转表的情况。L7表明这段分配地址的起始。
从汇编代码还能看出102和103的情况，因为102没有break，会落到103的情况中。
过程。

一个过程调用包括将数据（以过程参数和返回值的形式）和控制从代码的一部分传递到另一部分。另外还必须在进入时为过程的局部变量分配空间，并在退出时释放这些空间。数据传递、局部变量的分配和释放通过操纵程序栈来实现。

IA32程序通过程序栈来支持过程调用。机器用栈来传递过程参数、存储返回信息、保存寄存器用于以后恢复，以及本地存储。为单个过程分配的那部分栈称为栈帧stack frame。栈帧的最顶端以两个指针界定。

如果过程P调用过程Q，则Q的参数放在P的栈帧中，如上图。

如上，参数都相对于帧指针，因为栈指针在栈顶，可以移动，而帧指针界定当前过程的底部，在过程执行时不变。返回地址为+4，即4字节偏移量，再上面的参数1为+8，为8字节偏移量。

支持过程调用的指令：

call指令有一个目标，同跳转一样。效果是将返回地址入栈，并跳转到被调用过程的起始处。返回地址就是上面当程序从Q返回时应该继续执行的地方，是在程序中紧跟在call后面的那条指令的地址。

ret指令从栈中弹出地址，并跳转到这个位置。
```
08048392  <sum>:#函数开始
 8048394:  55                 push %ebp
...
 80483a4:  c3   #函数返回     ret
...
 80483dc:  e8 b3 ff ff ff     call 8048394 <sum>#main中调用sum
 80483e1:  83 c4 13           add  $0x14,%esp
```
结合上面的图和代码来理解过程调用：
在main函数中，地址为0x080483dc的call指令调用函数sum。%eip为程序计数器的值。
call指令将返回地址0x80483e1压入栈中，这就是call的下一条指令的地址，并跳到函数sum的第一条指令，地址为0x08048394。
函数sum继续执行，直到遇到地址为0x080483a4的ret指令。
这条指令从栈中弹出值0x080483e1，然后跳到这个地址。然后继续main函数的执行。
用leave指令可以使栈做好返回准备。
程序寄存器组是唯一能被所有过程共享的资源，虽然给定的时刻只能由一个过程是活动的，但是我们必须保证当一个过程调用另一个过程时，被调用者不会覆盖某个调用者稍后会使用的寄存器的值。
当P调用Q时，可以由P先将P中的局部变量保存在自己的栈帧中，当Q返回时，P可以从栈中取出值。也可以由Q保存值到自己的寄存器中。当Q返回时，P的局部变量被恢复。
过程示例。

如图，caller调用swap_add。

上面代码说明caller是如何调用swap_add。

首先是caller执行时，运行pushl操作（栈指针帧指针的值都是地址），将栈顶%esp-4，把原来%ebp的值（也就是上一个调用栈的帧指针指向的地址）给当前%esp（已减4）的值（其结果只是把上一个帧指针指向的地址保存到栈里的某个位置）。就是左图中0的位置。第三行，%esp（已减4）的值（就是%esp-4）再给%ebp，这时将%ebp寄存器的值设置为栈帧的开始位置了（也就是%esp-4）。这样相当于先把原来的帧指针指向的地址保存在%esp-4的位置，然后把%ebp寄存器的值设置为当前的%esp-4.见下图：此时%esp和%ebp保存的地址相同，都是之前的%esp-4.而-4(%esp)的值为0x151.

然后，%esp的值-24，在栈上分配24字节的空间，然后在刚才分配的空间里给arg1和arg2赋值。（分配了浪费的空间，为的是保证访问数据的严格对齐）

然后计算&arg1和&arg2的值，并存到栈上。

然后运行swap_add，和上面一样：

首先保存原来的帧指针地址到栈内，然后把这个保存的值的地址当做帧指针的值。

当swap_add执行完时，在ret前，首先popl %ebp，这样会把当前的%esp+4，并把%esp地址对应的值，(%esp)赋值给%ebp，这个值应该就是上一个调用栈保存的%ebp的地址。然后再ret。
递归过程。

每次调用自身都会建立新的栈帧来保存临时变量等，有可能导致栈空间耗尽。
数组分配和访问。

对于数据类型T和整形常数N，声明如下：

T A[N];

首先它在存储器中分配一个LN字节的连续区域；这儿L是T类型的大小。

A可以作为指向数组开头的指针，这个指针就是xa；

可以从0到N-1之间的整数索引来访问数组元素。数组元素i会被存放在地址为xa+L·i的地方。

假设E是一个int型的数组，想计算E[i]，E的地址存放在%edx中，而i存放在%ecx中。
```
movl (%edx, %ecx, 4), $eax
```
会执行地址计算xE+4i，读取这个存储器位置的值，并将结果存放到%eax中。

单操作数&和*可以产生指针和间接引用指针。对于对象E，有&E为E的一个指针，对于一个地址表达式A，A是给出该地址的值。可以对数组和指针应用下标操作，A[i]等同于(A+i)。

上图中，整形数组E起始地址和数组索引i分别存放在寄存器%edx和%ecx中，结果存放到%eax中。其中leal指令用来产生地址。

嵌套数组

对于int A[5][3];
等价于下面的声明
```
typedef int row3_t[3];
row3_t A[5];
```
要访问多维数组的元素，编译器会以数组起始为基地址，偏移量为索引，然后使用某种MOV指令，对于一个数组声明：
T D[R][C];
他的数组元素D[i][j]的存储器地址为：
&D[i][j] = xD + L(C·i + j)

变长数组指数组申明时n为变量而不是常数，而n也必须要在数组前确定。变长数组不是说申明后还能改变大小。
变长数组的优化和问题//TODO
结构。

将多个对象集合到一个单位中。
```
struct rec{
    int i;
    int j;
    int a[3];
    int *p;
};
```
这个结构包括四个字段，两个4字节int，1个由3个4字节组成的数组和1个4字节的整型指针，总共24个字节。
(*rec).i等同于rec->i。
它们的组成和数组类似，都存放在存储器中一段连续的区域内，指向结构指针的就是结构第一个字节的地址。编译器维护这关于每个结构类型的信息，指示每个字段的字节偏移。
如果要把rec->i复制到rec->j，rec放在寄存器%edx中。
movl (%edx), %eax #把i的值取出来放到%eax中
movl %eax, 4(%edx) #把%edx偏移4的位置的值设置为%eax的值
同理，要产生一个指向结构内部对象的指针，只需将结构的地址加上该地址的偏移量。
联合。

联合的写法和结构完全一样。
```
union u3 {
    char c;
    int i[2];
    double v;
}
```
当计算union中元素的偏移时，它的p,p->c,p->i[0],p->v都是相同的。即引用的都是数据结构的其实位置。
而且一个联合的总得大小等于它最大字段的大小。
当我们知道对其中不同字段的使用时互斥的，那么可以将其申明为联合的一部分。比如一个二叉树的数据结构，每个节点要么是叶子，要么是内部节点，如果用struct就会浪费一般空间。如果申明为联合就不会。
联合还可以用来访问不同数据类型的位模式。//TODO
数据对齐。

许多计算机系统对基本数据类型合法地址做了一些限制，要求某种类型对象的地址必须是某个值K（2，4，8等）的倍数。这种对齐限制简化了形成处理器和存储器系统之间接口的硬件设计。

假设一个处理器总是从存储器中取出8个字节，则地址必须为8的倍数。这样可能会浪费一些空间，但是优化存取效率。

编译器通常用下列指令知名全局数据所需的对齐：

.align 4

这样保证了它后面的数据起始地址是4的倍数。

比如：
```
struct S1 {
    int i;
    char c;
    int j;
};
```
这个struct中间c按理分配1个字节，这样j相对第一个i的偏移就是5，不满足对齐要求。
所以c会被分配4个字节，有3个字节是浪费的。
而对于上述struct的c在末尾的情况，虽然每个field都满足对齐要求，但是对于struct S2 d[4]来说，又变成不对齐了。所以对这种还是得对char进行对齐。
理解指针。

指针以一种统一方式，对不同数据结构中的元素产生引用。

每个指针都对应一个类型。这个类型表明指针指向哪一类对象。指针类型不是机器代码中的一部分，他是C语言提供的一种抽象。
GDB调试器。
存储器的越界引用和缓冲区溢出。//TODO
将IA32扩展到64位。//TODO

系统级I/O

输入/输出I/O是在主存和外部设备（磁盘、网络等）之间拷贝数据的过程。
一般语言提供I/O的较高级别的工具，如printf这样执行带缓冲区的标准I/O函数。也可以使用较底层的Unix I/O。
一个Unix文件就是一个m个字节的序列：B0,B1,Bk,…,Bm-1。所有的I/O设备，如网络、磁盘和终端，都被模型化为文件，而所有的输入输出都被当做对应文件的读和写来执行。这种讲设备优雅地映射为文件的方式，允许Unix内核引用一个简单、低级的应用接口，称为Unix I/O。
打开文件。一个应用程序通过要求内核打开相应的文件，来宣告它想要访问一个I/O设备。内核返回一个小的非负整数，叫描述符，它在后续对该文件的所有操作中标识这个文件。内核记录有关这个打开文件的所有信息。应用程序只记住这个描述符。
Unix外壳创建的每个进程开始的时候都有三个打开的文件：标准输入（描述符为0），标准输出1和标准错误2.
改变当前的文件位置。对于每个打开的文件，内核保持着一个文件位置k，初始为0.这个位置是从文件开始的字节偏移量。应用程序能通过执行seek操作，显式地设置文件的当前位置为k。
读写文件。一个读操作就是从文件拷贝n>0个字节到存储器，从当前文件位置k开始，然后将k增加到k+n。给定一个大小为m字节的文件，当k>=m时执行读操作会触发一个叫做end-of-fileEOF的条件，应用程序能检测到这个条件。

类似的，写操作就是从存储器拷贝n>0个字节到一个文件，从当前文件位置k开始，然后更新k。
关闭文件。当应用程序完成了对文件的访问后，他就通知内核关闭这个文件。作为响应，内核释放文件打开时创建的数据结构，并将这个描述符恢复到可用的描述符池中。
打开和关闭文件。
读和写文件。

ssize_t read(int fd, void *buf, size_t n);read函数从描述符为fd的当前文件位置拷贝最多n个字节到存储器位置buf。返回值-1表示一个错误，0表示EOF。
用RIO包健壮地读写。
读取文件元数据。stat和fstat函数。
共享文件。可以用很多方式来共享Unix文件。内核用三个相关的数据结构来表示打开的文件。

描述符表。每个进程都有独立的描述符表，它的表项是由进程打开的文件描述符来索引的。每个打开的描述符表项指向文件表中的一个表项。
文件表。打开文件的集合是由一张文件表来表示的，所有的进程共享这张表。每个文件表的表项组成包括当前的文件位置、引用计数（即当前指向该表项的描述符表项数），以及一个指向v-node表中对应表项的指针。关闭一个描述符会减少相应的文件表表项中的引用计数。内核不会删除这个文件表表项，直到它的引用计数为零。
v-node表。同文件表一样，所有进程共享这张v-node表。每个表项包含stat结构中的大多数信息，如文件访问、文件大小、文件类型等。

描述符1，4通过不同的打开文件表表项来引用两个不同的文件。没有共享文件。

多个描述符也可以通过不同的文件表表项来引用同一个文件。比如以同一个filename调用open函数两次。关键思想是每个描述符都有他自己的文件位置，所以对不同描述符的读操作可以从文件的不同位置获取数据。

在调用fork之前，父进程有10-11所示的打开文件，然后调用fork后，子进程有一个父进程描述符表的副本。父子进程共享相同的打开文件表集合，因此共享了相同的文件位置。
I/O重定向。Unix外壳提供了I/O重定向操作符，允许用户将磁盘文件和标准输入输出联系起来。如unix> ls> foo.txt.

使得外壳加载和执行ls程序，将标准输出重定向到磁盘文件foo.txt。

我们可以使用dup2来实现重定向。它的作用是拷贝就得描述表表项到新的描述符表项。
标准I/O。ANSI C定义了一组高级输入输出函数，成为标准I/O库，提供了Unix I/O较高级别的替代。

这个库包含了fopen、fclose、fread、fwrite、fgets、fputs、scanf、printf等函数。

标准I/O库讲一个打开的文件模型化为一个流。对程序员而言，一个流就是一个指向FILE类型的结构的指针。

类型为FILE的流是对文件描述符和流缓冲区的抽象。流缓冲区的目的和RIO读缓冲区的一样：就是使开销较高的Unix I/O系统调用的数量尽可能的小。比如我们有一个程序，反复调用getc函数，每次调用返回文件的下一个字符。当第一次调用getc时，库通过调用一个read函数来填充流缓冲区（read函数一次读取n个字符），然后将缓冲区的第一个字节返回给应用程序。只要缓冲区还有未读的字节，接下来对getc的调用就能直接从流缓冲区得到服务。
较高级别的RIO和标准I/O都是基于Unix I/O来实现的。
标准I/O流，从某种意义上是全双工的，因为程序能够在同一个流上执行输入和输出。但是会有一些对流的限制和对套接字的限制。所以建议在网络套接字上使用健壮的RIO函数。

网络编程

每个网络应用都是基于客户端-服务器模型的。
Unix对网络的抽象是一种叫做套接字的文件类型。
因特网连接。一个套接字是连接的一个端点。每个套接字都有相应的套接字地址，是由一个因特网地址和一个16位的整数端口组成的，用地址:端口来表示。

一个连接是由它两端的套接字地址唯一确定的。这对套接字地址叫做套接字对socket pair。
套接字接口socket interface是一组函数，他们和Unix I/O函数结合起来，用以创建网络的。
从Unix内核的角度来看，一个套接字就是通信的一个端点。从Unix程序的角度来看，套接字就是一个有相应描述符的打开文件。
socket函数创建一个套接字描述符。

connect函数，客户端通过connect来建立和服务器的连接。

open_clientfd函数，将socket和connect函数包装成一个函数。

bind函数、linsten函数。内核会认为socket函数创建的描述符对应于主动套接字，存在于一个连接的客户端。服务器调用listen函数则告诉内核，描述符是位于服务器的。

open_listenfd函数，将socket、bind、listen函数结合成一个，可以创建一个监听描述符。

服务器通过调用accept函数来等待来自客户端的连接请求。连接后返回一个已连接描述符。

并发编程

逻辑控制流在时间上重叠，称之为并发的。
在下列情况下一般考虑应用级并发：

访问慢速IO设备。通过交替执行IO请求和其他有用的工作来使用并发。

人机交互。

通过推迟工作以降低延迟。

服务多个网络客户端。允许服务器同时为多个客户端服务，避免慢速客户端独占服务器。

在多核机器上进行并行计算。
使用应用级并发的应用程序称为并发程序。现代操作系统提供了三种基本的构造并发程序的方法：

进程。进程拥有独立的虚拟地址空间。

IO多路复用。所有流都共享同一个地址空间。

线程。线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。可以把线程看做是上面两种方式的混合体，像进程流一样由内核进行调度，而像IO多路复用流一样共享一个虚拟地址空间。
多进程编程。在父进程中接受客户端连接请求，然后创建一个新的子进程来为每个客户端提供服务。子进程获得了服务器描述符表的完整拷贝。

一般需要一个SIGCHLD处理程序来回收僵死子进程的资源。

多进程共享文件表，但是不共享用户地址空间。进程有独立的地址空间更稳定，但是共享信息更困难，因为他们必须使用显式的IPC（进程间通信）机制。而且开销更大。

基于I/O多路复用的并发编程。如果服务器必须响应两个相互独立的IO时间，网络客户端发起请求，用户在键盘上输入命令行。我们如果在accept中等待一个连接（阻塞中）就不能相应输入命令，反之亦然。

针对这种情况可使用IO多路复用。基本思路是使用select函数，要求内核挂起进程，只有在一个或多个IO事件发生后，才将控制返回给应用程序。

#include "csapp.h"

void echo(int connfd)
{
	int n;
	char buf[MAXLINE];
	rio_t rio;

    rio_readinitb(&rio,connfd);
    while((n=rio_readlineb(&rio,buf,MAXLINE))>0) {
        printf("server received %d bytes \n",n);
        rio_writen(connfd,buf,n);
    }

}

void command(void) {
	char buf[MAXLINE];
	printf("you input just now!\n");
	if(!fgets(buf,MAXLINE,stdin))
		exit(0);
	printf("%s",buf);
}

int main(int argc,char **argv)
{	
	int listenfd,connfd,port;
	//套接字地址結構的大小
	socklen_t clientlen=sizeof(struct sockaddr_in);
	struct sockaddr_in clientaddr;
	//fd_set为描述符集合，此處定義了兩個read_set,ready_set描述符集合,分別是讀集合/准備好集合
	fd_set read_set,ready_set;

    if(argc!=2) {
        fprintf(stderr,"usage :%s <port>\n",argv[0]);
        exit(0);
    }

    port=atoi(argv[1]);

    listenfd=open_listenfd(port);#打开一个监听描述符

    FD_ZERO(&read_set);#创建空的读集合

    FD_SET(STDIN_FILENO,&read_set);#添加标准输入

    FD_SET(listenfd,&read_set);#添加监听描述符

    while(1) {

        ready_set=read_set;	
        select(listenfd+1,&ready_set,NULL,NULL,NULL);
                #服务器循环，调用select来阻塞，直到监听描述符或者标准输入准备好可读，这时select会返回ready_set的值，这儿stdin的位会变成1，然后通过FD_ISSET宏指令来判断哪个描述符准备好可以读了。

    	if(FD_ISSET(STDIN_FILENO,&ready_set))
            command();
        if(FD_ISSET(listenfd,&ready_set)) {
            connfd=accept(listenfd,(SA *)&clientaddr,&clientlen);
            printf("client connected!");
            echo(connfd);
            close(connfd);
        }
    }

}

I/O多路复用可以用作并发事件驱动程序的基础。在事件驱动程序中，流是因为某种事件而前进的。

一般概念是将逻辑流模型化为状态机。一个状态机state machine就是一组状态state、输入事件input event和转移transition，其中转移就是将状态和输入时间映射到状态。每个状态都是将一个（输入状态、输入事件）对映射到一个输出状态。

自循环self-loop是同一输入和输出状态之间的转移。（TODO）
基于线程的并发编程。

线程就是运行在进程上下文中的逻辑流。线程由内核自动调度。每个线程都有它自己的线程上下文thread context，包括一个唯一的整数线程IDthread ID，TID、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。
每个进程开始生命周期时都是单一进程，这个线程称为主线程main thread。

某一时刻主线程创建一个对等线程peer thread，从这时候开始两个线程就并发执行。

主线程因为执行一个慢速系统调用，如read等，控制就会通过上下文切换传递到对等线程。对等线程执行一段时间，控制传递回主线程。

线程的上下文切换比进程上下文切换快得多。

线程不像进程按照严格的父子层次来组织。一个进程的相关线程组成一个对等线程池，独立于其他进程的线程。主线程和其他线程的区别是它是第一个运行的线程。

一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。

每个对等线程都能读写相同的共享数据。
Posix线程Pthreads是在C程序中处理线程的一个标准接口。
pthread_create函数创建一个新的线程。

pthread_exit函数显性地终止线程。如果主线程调用这个，会等待所有其他对等线程终止再终止主线程和整个进程。对等线程调用Unix的exit函数，该函数终止进程及所有与该进程相关的线程。对等线程通过当前线程ID作为参数调用pthread_cancel函数来终止当前线程。

线程通过调用pthread_join函数等待其他线程终止。这个函数会阻塞，直到其他线程tid终止。和Unix的wait函数不同，pthread_join函数只能等待一个指定的线程终止，而没办法等待任意一个线程终止。
分离线程。在任何一个时间点上，线程是可结合的joinable或分离的detached。

一个可结合的线程能够被其他线程收回其资源和杀死。在回收前他的资源是没被释放的。

一个分离的线程是不能被其他线程回收或杀死的。它的存储器资源在它终止时由系统自动释放。

默认情况下线程被创建出可结合的。

pthread_detach函数分离可结合线程tid。也能通过pthread_self()为参数调用其分离自己。

比如web服务器每个线程处理一个连接，所以服务器没必要显式地等待每个对等线程终止。所以每个对等线程都应该在它开始处理请求前分离它自身。
pthread_once函数允许你初始化和线程例程相关的状态。
多线程中的共享变量。

将变量映射到存储器。全局变量是定义在函数之外的变量，任何线程都可以引用。

本地自动变量，定义在函数内部没有static属性的变量。每个线程的栈都包含他自己的所有本地自动变量的实例。不共享。

本地静态变量，和全局变量一样，每个对等线程都读和写这个实例。
用信号量同步线程。

共享变量很方便，但是引入了同步错误synchronization error。举个例子，有个共享变量cnt，两个线程都在操作cnt，分别要对cnt累加1执行niters次，正确结果应该是2niters，但是得到的结果却会偏少。关键代码：
```
for (i=0;i<niters;i++)
    cnt++;
```
两个线程都同时执行上面的操作更新共享变量cnt。错误的原因我们用汇编代码来解释：
H:在循环头部的指令。
L:加载共享变量cnt到寄存器%eax的指令，这个寄存器是执行线程寄存器的值。
U:更新%eax的指令。
S:将%eax的更新值存回到cnt的指令。
T:循环底部的指令。
因为两个线程在执行上面指令时有可能是交叉的，而LUS三个指令应该是原子的，在交叉的时候就会出错。
如上图，只要LUS不是原子的就会出错，出现已经更新的值被错误覆盖的情况。
为了避免这种情况，我们使用进度图progress graph来阐明这个概念。
进度图将n个并发线程的执行模型化为一条n维笛卡尔空间中的轨迹线，每条轴k代表线程k的进度，每个点代表线程k已经完成了指令I这个状态。图的原点对应没有任何线程完成一条指令的初始状态。
进度图将指令执行模型化为从一种状态到另一种状态的转换。转换被表示为一条从一点到相邻点的有向边。只能向右或者向上。
而上面的例子中，LªUªSª构成了一个临界区critical section（关于cnt的），这个临界区不应该存在交替执行。我们要确保每个线程在执行它的临界区中的指令时，拥有对共享变量的互斥的访问，通常这种现象称为互斥mutual exclusion。
在进度图中，两个临界区的交集形成的状态空间区域称为不安全区unsafe region。绕开不安全区的轨迹线叫做安全轨迹线。
任何安全轨迹线都将正确地更新共享计数器。
为了正确执行，我们可以通过基于信号量的思想来完成。
信号量。

信号量semaphore是特殊类型变量。信号量s是具有非负整数值的全局变量，只能由两种特殊的操作来处理。

P(s):如果s是非零的，P将s-1，并立即返回。如果s为0，则挂起这个线程，直到s变非零，而一个V操作会重启这个线程，在重启后，P操作将s-1，并将控制返回给调用者。

V(s):V操作将s+1，如果有任何线程阻塞在P操作等待s变非零，则重启这些线程中的某一个，然后将该线程s-1，完成它的P操作。

P的测试和-1是不可分割的。V的+1操作也是不可分割的。

信号量的基本思想是将每个共享变量与一个信号量（初始为1）联系起来，然后用PV操作将相应的临界区包围起来。
PV的操作保证了信号量不会出现负值。这个属性叫做信号量不变性。

以这种方式来保护共享变量的信号量叫做二元信号量，因为他的值总是0或1.以提供互斥为目的的二元信号量也称为互斥锁mutex。在一个互斥锁上执行P操作称为对互斥锁加锁。V操作称为对互斥锁解锁。

看上面这个图来理解一遍。首先出现问题的操作是上面说的cnt++，就是对应LUS操作，要怎么保证三个操作是不可分割的问题。现在信号量的做法是在LUS操作前后分别加上P和V操作，如上图。

初始状态s=1，假设第一步线程执行完线程1的H1，到了(Ps,0)，接下来再将执行线程1的Ps操作。根据上面P操作的规则，这个时候s是非零的，P会将s-1，并返回。这个时候他位于(Ps,0),s的值为0，根据P规则，s为零了，这时候线程1如果要切换到线程2了，执行了H2操作，向上走一步，到达(Ps,H2)，此时s=0。如果此时接着执行线程2，往上走，根据P操作的规则，s为0，执行P操作，会挂起线程2，即它不能再往上走，只能执行线程1往右走。然后他就只能走完L1U1S1三步。

此时到达了(S1,H2)，这时因为线程2还是挂起的，还是只能往右走一步，执行V操作，到达(Vs,H2)，因为刚才执行了V操作，根据规则，将s+1，并且将等待的线程2重启（因为例子中只有线程1和2），然后往上走执行线程2，执行P操作，将s-1，到达(Vs,Ps)。

这时候线程1和2均未挂起，s=0，已经绕过了不安全区，又可以随意走动了。

刚才的线路如图，

在代码中定义一个mutex的信号量的全局变量，置为1.
```
for(i=0;i<niters;i++){
    P(&mutex);
    cnt++;
    V(&mutex);
}
```
这个时候是保证了LUS操作的原子性，保证了结果正确。
进度图在执行多处理器的时候是不能解释的。
利用信号量来调度共享资源。

信号量除了提供互斥外，另一个作用是调度对共享资源的访问。这种情况下，一个线程用信号量操作来通知另一个线程。
生产者-消费者问题。

生产者线程——>有限的缓冲区-——>消费者线程

生产者和消费者线程共享一个有n个槽的有限缓冲区。生产者线程反复地生成新的项目item，并把他们插入到缓冲区中。消费者线程不断地从缓冲区取出这些项目，然后消费他们。

这个共享的缓冲区对于生产者和消费者的访问应该是互斥的。而且如果缓冲区是满的，则生产者必须等待直到有一个槽位可用。如果缓冲区是空的，那么消费者必须等待直到有一个项目变为可用。

现实中，播放视频的时候的缓冲区就是例子，是为了减少视屏流的抖动jitter。

下面我们建立SBUF的生产者-消费者程序。

如上，buf是缓冲区空数组，n为buf的大小，front为当前队列的队首，rear为队列的队尾。

mutex为buf是否互斥，初始值为1。

slots为可用槽位的数量，一般给生产者使用。初始值为n个。

items为buf中已有的项目数量，一般给消费者使用。初始值为0个。

这里的insert用来插入项目item，remove为返回一个项目。他们互为逆操作。
在这儿回顾一下PV操作，P操作每次-1，直到为零挂起线程；V操作每次+1，遇到0时会先重启该线程并+1.

在insert中，24行，先给可用槽位-1，它一直到减为0才挂起线程。

25行，给槽位信号量1-1，这时其为0了，标志着如果这时上下文切换给另一个线程，它也不能再执行到这个P操作，如果执行了则会减到-1了，不可能。只能由这个线程安全得执行buf的赋值操作。

24，25行都能用来保证buf的正确写入，24行中，空槽位数一直减少，当减到0时，再次执行到这儿，任何执行到这的线程都会被挂起。也能保证槽位的正确使用。

26行中有一个%操作，这是因为槽位一共就n，而队列是一直增加一直减少，永远排下去的，所以槽位的下标不一定一直1，2，3…n，而可能是n-1,n,…,1,2,3这种。看例子：

假设有6个槽位，最开始是这样，假设都填满了：

1 2 3 4 5 6

当使用了一个时，移除了下标为1的，这时下标应该是这样的：

空 1 2 3 4 5

再次移除一个：

空空 1 2 3 4

再插入一个，下标应该是这样：

5 空 1 2 3 4

上面这个就是%的意义。

27行中，当buf原子地赋值完成后，对槽位的信号量mutex从0+1，这也标志着这时开始能自由安全地切换到其他线程了。

28行，对可用项目的数量+1，可用于给消费者提供remove操作了。

remove操作和上面的操作互逆。
**在生产者消费者模式中，对slots和items加锁的目的也是为了让其数量不能减少到小于0，一旦可能小于零就让线程马上被挂起。这也是利用了P操作如果遇到可能小于0的时候就挂起线程的性质。这个性质可以应用很广。

从多线程编程的意义上来看，生产者线程可能多个、消费者线程可能多个同时运行，要保证多个生产者不会让槽位溢出，多个消费者同时操作也不会让槽位出现错误的负数操作。**
读者-写者问题。

一组并发线程要访问一个共享对象，有些线程只读，有些线程只写。

写者必须独占对象的访问，读者可以无限多个共享对象。

现实中，比如订座系统就是这类问题。

第一类，读者优先，读者不能等待，除非使用对象的权限已经给了写者。第二类，写者优先，一旦一个写者在等待，后面的读者必须等待。

现在考虑第一类情况，写线程占用共享区域时，所有读线程不能使用，其他写线程也不能使用。假设一个信号量w初始值为1，当写线程占用时调用P，其值变为0，这时其他线程不能再占用共享区域。

当读线程占用共享区域的时候，所有写线程不能再使用，而其他读线程均能继续占用，直到读线程数量减少为0，写线程才能再次占用共享区域。

这段代码太巧妙了，我没想出来。

这样来思考，首先假设读和写都是对其他任何线程互斥的，那么应该是如下红框内的代码：

对于写操作，可以理解为对其他任何线程都互斥，所以不用改。

对于读线程有点特殊，首先占用共享区域之前要独占，这样对其他线程读写都互斥了。

这时考虑对其他读线程的一个例外：只要有读线程时就有P，用来对写进程排斥；但是又要对其他读线程不排斥。意思就是有读线程时就要加P，但是其他读线程执行这段时又没有加P。这时考虑cnt==1时才加P就解决了问题。

对于读线程的V操作，如果不加控制，一个读线程释放完共享区域就加V，则这时不再占用，写线程能占用了，而其实这时还有其他读线程占用着，会出错。

所以应该是只有当所有读线程都使用完了共享区域才加V。

方法如例子里，当一个读线程进来后cnt+1，当一个读线程使用完共享区域后，cnt-1，当cnt减到为0时，加V。这样就解决问题了。

这儿cnt的累加累减需要互斥避免出错。
基于预线程化的并发服务器。

预线程化prethreading，上面的生产者-消费者模式已经用到了预线程化技术。

在实际中，我们不会为每一个新的客户端生成一个新的线程，那样耗资源，我们通过预线程化先生成指定数量的对等线程，主线程负责接收客户端的连接请求，并将得到的描述符放在一个有限缓冲区。每个工作线程反复从有限缓冲区取出描述符，服务，然后等待下一个描述符。

I/O多路复用不是编写事件驱动程序的唯一方法，基于预线程化的并发服务器其实就是一个事件驱动服务器。
使用线程提高并行性。

到目前为止对并发的研究中，我们都假设是在单处理器上执行的。

并行程序是指一个运行在多个处理器上的并发程序。并行程序是并发程序的真子集。

一般来说我们期望CPU增加会让运行时间减少，所以当我们增加线程数和CPU数时，运行时间是减少的，但是当线程数大于CPU数时，运行时间实际上会增加一点，所以并行程序通常线程数等于CPU数量。

可以通过加速比和效率来作为衡量标准。
线程安全。

如果一个函数被称为线程安全的，当且仅当被多个并发线程反复调用时，它会一直产生正确的结果。不是线程安全得，称为线程不安全的。

第一类：不保护共享变量的函数。解决方法使用信号量PV加锁。

第二类：保持跨越多个调用状态的函数。比如一个伪随机数生成器。

第三类：返回指向静态变量的指针的函数。结果放在static变量中，并返回一个指向这个变量的指针。也可能导致结果被其他线程修改。方法也是加锁-拷贝。

第四类：调用线程不安全函数的函数。f调用线程不安全的函数g，如果g是一三类，只需加锁就能解决变成线程安全得。如果g是第二类，依靠多线程多次调用，则没办法除非重写g。
可重入性。

线程安全函数包含一种特殊的叫做可重入函数reentrant function，它们的特点是没有任何共享数据，即1，所有的数据都是本地栈变量，所有参数都是值传递（没有指针）（显式可重入的），2，或者有些参数是引用传递的（可以传递指针，但是不允许调用者传入共享变量的指针）（隐式可重入的，是否为隐式可重入由调用者决定）。

比如上面第二类那个rand函数，如果改成隐式可重入的，如下：
```
 int rand_r(unsigned int * nextp)
 {
     *nextp = *nextp * 1003515245 + 12345;
     return (unsigned int)(*nextp / 65536) % 32168;
 }
```
在线程化的程序中使用已存在的库函数。

大部分Unix函数是线程安全得，只有少部分是线程不安全的：
竞争。

当一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达它在控制流中x点时，就会发生竞争。

因为线程化的程序之间的执行顺序取决于内核的调度，两个线程无法判断执行的先后次序。

比如

打印的结果

不是预想的0123，因为程序员会设想一个线程中的22行完了才执行11行的i++。

而事实上可能先执行11行的i++，在执行21行的赋值，这样就得到了错误的结果。

解决办法，用一个临时变量来存当时正确的i。
死锁deadlock。

死锁指一组线程被阻塞了，等待一个永远也不会为真的条件。

使用PV操作顺序不当，以至于两个信号量的禁止区域重叠。

重叠的禁止区引起了一组称为死锁区域的状态。

死锁不总是可以预测的。

死锁的原因很多，当使用二元信号量来实现互斥时，有一个简单有效的方法来避免死锁：
加锁顺序规则：加入对于程序中每对互斥锁s、t，每个同时占用s和t的线程都按照相同的顺序对它们加锁，那么这个程序是无死锁的。

如上第一个图，有个死锁状态d，这个区域不是禁止区，但是进入后按照正常的步骤却不可走出。

从图片可以看出，原因是线程1和线程2的PV顺序不同，线程1是Ps,Pt,Vs,Vt，线程2是Pt,Ps,Vt,Vs，这样当线程1操作s信号量时，它是可以切到线程2的，因为此时线程2还没有要操作s信号量。

但是一旦它这个时候切到线程2，线程2就开始操作t信号量了。

在线程1PsVs之间有Pt，同理线程2PtVt之间有Ps，他们之间形成了一个交叉区域，所以此时它无论切到线程1或者线程2都不可避免得要执行Pt或者Ps，而s和t信号量现在都已经被锁了，这样就变成了死锁。

线程1：Ps Pt Vs Vt

线程2： Pt Ps Vt Vs

↓

此时信号量s和t均被占用且没被释放，而下一个操作无论怎样切都是P操作，无论如何会进入死锁

¹如果线程1和2是如下次序

Ps Vs Pt Vt

Pt Vt Ps Vs

或

Ps Pt Vs Vt

Pt Vt Ps Vs

这样也不会死锁，

²或者如2图的次序

Ps Pt Vs Vt

Ps Pt Vt Vs

这样也不会死锁。

现在来理解加锁顺序规则，每个同时占用s和t的线程。¹的情况其实永远不会同时占用s和t。可以通过画进度图看出来。

而对于可能同时占用s和t的情况，则肯定是两图有交集的情况。

即肯定是两个都是PPVV这种情况。

规则可以简述如下：一定都得是PP开头的次序，且st顺序一致才能避免死锁。