[系统运维]CSAPP笔记（上）

1. x86-64机器码可见的寄存器

1. 程序计数器：给出将要执行的下一条指令在内存中的地址；
2. 整数寄存器文件：包含16个命名的位置，分别存储64位的值；这些寄存器可以存储地址空间，比如C语言中的指针，也可以存储整数数据；有的寄存器被用来存储比较重要的程序状态，而其他的寄存器可以用来保存临时的数据，比如说过程的参数以及局部变量和函数的返回值；
3. 条件码寄存器：保存着最近执行的算数或者是逻辑指令的状态信息，他们用来实现控制数据流中的条件变化，比如说用来实现if和while语句；
4. 向量寄存器：一组向量存储器可以存储一个或者多个整数或浮点数的值；

2. 过程及过程调用

1. 过程是软件中很重要的一种抽象，过程提供了一种封装代码的方式，用一组指定的参数和一个可选的返回值实现了某种功能。然后我们就可以在程序的不同地方对该过程进行调用。用过程进行抽象可以隐藏某个行为的具体实现，并可以提供清晰简洁的接口定义，用以说明过程计算的是哪些值，过程会对程序的状态产生什么样的影响等。在不同的编程语言中对过程有不同形式的体现：函数，方法，处理函数等，但他们都具有一致的特性；

2. 当过程P想要调用过程Q的时候，他们需要包括下面的几个机制：

   • 传递控制：在进入过程Q的时候，程序计数器必须被设置为Q的代码的起始位置；然后在返回的时候把程序计数器的值设置为P接下来要执行的指令的内存地址；
   • 传递数据：在过程调用的时候，P需要向Q传递数据，比如说参数信息，同时Q能够向P返回一个值；
   • 分配和释放内存：在开始的时候Q可能会需要为局部变量分配内存空间，而在过程Q返回之前，又必须释放掉之前分配的内存空间；

3. 运行时栈：在大多数的语言中，过程调用机制的实现的一个关键特性就是利用了栈这一数据结构后进先出的特性。比如在过程P调用过程Q的例子中，当Q在执行的时候，在Q之上的调用链中的过程都是暂时被挂起的。Q会被放到栈顶，他只需要为局部变量分配新的存储空间，或者是设置到另一个过程的调用。当Q返回的时候，任何它所分配的局部存储空间都可以被释放。需要注意的是，过程中的信息不仅仅是存放在栈上面的，它们还可会被存放于寄存器之中；x86-64的栈空间是向低地址方向增长的，栈底位于高地址，栈指针%rsp指向栈顶元素。当x86-64程序的过程需要的存储空间超过寄存器能够存放的大小的时候，过程就会在栈上分配空间，被分配的空间称为过程的栈帧。在栈这一数据结构中，当前正在执行的过程的栈帧做事位于栈顶。当过程P调用过程Q的时候，会把过程Q的栈帧压入栈顶，同时指明当Q执行完毕返回之后要从P程序的哪一个位置继续执行代码。我们通常都会把返回地址当做是P的栈帧的一部分，因为返回地址存放的是与P相关的状态信息。过程调用返回后需要继续执行的P的代码位置是用指令call Q调用过程Q开记录的，假设P在Q返回后需要继续执行的指令地址是A，那么call指令就会将A压入栈中(同时将PC设置为Q的起始地址，压入的地址A被称为返回地址，是紧跟在call指令后面的那条指令的地址)，对应的ret会从栈中弹出地址A，并把PC的值设置为A。过程Q的代码会扩展当前栈的边界用于分配Q的栈帧所需要的存储空间。在Q的栈帧之中，Q可以保存寄存器的值，也可以分配局部变量的空间，也可以为它调用的过程设置参数。大多数过程的栈帧都是定长的，在过程开始的时候就已经分配好了，但是仍存在需要变长帧的过程。当过程P要向过程Q传递参数的时候，x86-64允许P通过寄存器传递最多6个参数，如果需要传递更多的参数，P就需要在自己的栈帧中存储好那些高于6个的参数。为了提高过程执行时的空间效率以及时间效率，x86-64中的过程只会自己所需要的栈帧的部分。其实许多的过程都不会有6个参数，那么所有的参数都可以通过寄存器进行传递，因此下图中的某些栈帧部分可以省略，对于某些过程来说甚至都不需要分配栈帧。当所有的局部变量都可以保存在寄存器中并且该过程不会调用其它的任何过程的时候，x86-64就可以不为过程分配栈帧。
   
   
   
   %rsp是栈指针，%rip是程序计数器。
   
   在x86-64中，大部分的过程间数据传送是通过寄存器来实现的。当过程P调用过程Q的时候，P的代码首先吧数据复制到适当的寄存器之中，并且当Q返回到P的时候，P也可以通过访问寄存器%rax来获取其中存储的过程Q返回值。x86-64中可以通过寄存器传递最多6个参数，寄存器的名字取决于参数的大小，如下图所示：
   
   如果一个过程的参数大于6个，那么超出6个的部分就要通过栈来传递，比如P调用Q需要传递n > 6个参数，那么P的栈帧必须要能够容纳超出6的参数，参数1~6存储在寄存器之中，其余的参数存储在栈上，注意：参数7会被存储在栈顶，参数是被逆序存储的。通过栈传递参数时，所有的数据大小都向8的倍数对齐。参数到位后，程序就可以执行call指令将控制转移到Q了。
   
   
   虽说局部数据可以存放在寄存器之中，但是在以下的几种情况下局部数据必须存储在内存中，常见的情况包括：

   • 寄存器不足够存放所有的本地数据；
   • 对一个局部变量使用地址运算符&，因此必须能够为它产生一个地址；
   • 某些局部变量是数组或者是结构，因此必须能够通过数组或结构引用被访问到；

   下图所示的call_proc给出了一个必须在栈上分配局部变量存储空间的函数，同时还要向有8个参数的函数proc传递值；该函数创建一个栈帧；
   
   
   
   
   在call_proc的汇编代码之中的一大部分(2~15行)都是在为调用proc做准备。其中包含为局部变量和函数参数建立栈帧，将函数参数加载至寄存器，如上图所示，局部变量会在栈上被分配，同时值为4的参数7以及指向x4的位置的指针的参数8会被存放在栈中；当程序返回call_proc的时候代码会取出4个局部变量，并执行最终的计算。在程序结束前把栈指针增加32释放这个栈帧；
   寄存器组是唯一被所有的过程共享的资源，虽然在给定的时间内只有一个过程是在活动的，但是我们仍然必须确保当一个过程调用另一个过程的时候，被调用者不会覆盖调用者稍后会使用到的寄存器的值，为此，x86-64采用了一组统一的寄存器使用习惯，所有的过程都必须遵守。其中寄存器%rbx,%rbp和%r12~%r15被划分为被调用者保存寄存器。当过程P调用Q的时候，Q必须保存这些寄存器的值，保证它们的值在Q返回到P时与Q被调用的时候是一样的。过程Q保存一个寄存器的值不变，要么是根本不会去改变其中的值，要么是把原始的值压入到了栈中，改变寄存器的值，之后在返回之前从栈中弹出旧值。被压入寄存器中的值会在栈帧中创建标号为“保存的寄存器”的一部分。有了以上的惯例，P的代码就能够安全的把值存放到被调用者保存寄存器中(当然要先把之前的值保存在栈中)，调用Q，然后继续使用寄存器中的值，不必担心只会被破环。所有其他除栈指针%rsp之外的寄存器都被分类为调用者保存寄存器。这就意味着任何的过程都能够修改它们。过程P在某个此类寄存器中存在有局部数据，然后调用过程Q，由于Q可以随意修改这个寄存器，所以说P在调用之前应该保存好这个数据。同时，递归调用一个过程与调用其它过程是一样的，栈提供了一种机制，每次函数调用都有它自己私有的状态信息(保存的返回位置 和被调用者保存寄存器的值)存储空间，因此多个未完成调用的局部变不会相互影响。如果需要，它还可以提供局部变量的值。栈分配和释放的规则很自然地就与函数的调用与返回的顺序相匹配，这种实现函数调用与返回的方法甚至对更复杂的情况也适用，包括相互递归调用。

3. 数组相关

1. x86-64的内存引用指令可以简化数组的访问。例如，假设E是一个int型的数组，而我们想要计算E[i]，在此，E的地址存放在寄存器%rdx之中，而i索引值粗放在寄存器%rcx之中，然后会有以下的汇编指令: movl (%rdx,%rcx,4),%eax，会执行地址计算address(E) + 4i，读取这个内存位置的值，并将读取的结果存放到寄存器%eax之中，允许的伸缩因子1,2,4,8覆盖了所有基本简单数据类型的大小；
2. C语言的编译器能够优化定长多维数组上的操作代码，具体来说就是在某些情况下去掉相应的整数索引，并把所有的数组应用都替换为指针间接引用；指针间接引用更具备灵活性并且指针会更有效率；对于变长数组，GCC能够识别出程序访问多维数组的元素的步长，然后生成的代码会避免直接应用等式&D[i][j] = address(D) + L(C*i + j)会导致的乘法。不论是生成基于指针的代码还是生成基于数组的代码，这些优化都能够显著的提高程序的性能；以下分别是定长数组的优化情况以及变长数组的优化情况；
   
   

4. 数据对齐

1. 许多计算机系统对基本数据类型的合法地址做出了一些限制，要求某种类型对象的地址必须是某个值K(通常是2, 4或8)的倍数。这种对齐限制简化了形成处理器和内存系统之间接口的硬件设计。例如，假设一个处理器总是会从内存中取出8个字节的数据，则地址必须为8的倍数。如果我们能够保证所有的double类型数据的地址对齐成8的倍数，那么就可以用一个内存操作来进行读操作或者是写操作。否则我们可能需要进行两次的内存访问，因为对象可能分别放在两个8字节的内存块中。无论是否进行对齐，x86-64的硬件都能够正常的工作，但是对齐数据可以提高内存系统的性能。
2. 对齐的原则是任何K字节的基本对象的地址必须是K的倍数，所以这条对齐原则会得到如下的对齐：
   
   确保每种数据类型都是按照指定的方式来组织和分配，即每种类型的对象都满足它的对齐限制，就可以保证实施对齐。编译器会在汇编代码中放入命令来指明全局数据所需的对齐。对于包含结构的代码，编译器可能会需要在字段的分配中插入间隙，以保证每个结构的元素都满足它的对齐要求。而结构本身对它的起始地址也有一些对齐要求，比如说考虑下面的结构声明：
   
   假设编译器用最小的9字节进行分配，将会得到下图的结果
   
   这样分配是不满足字段i和字段j的4字节对齐要求的，所以说在实际上编译器会在字段c和字段j之间插入一个3字节的间隙，最终得到的结果就是j的偏移量是8，而整个结构的大小是12个字节。
   
   此外，编译器必须保证任何struct S1 * 类型的指针p都满足4字节的对齐。假设指针p的值为xp，那么xp必须是4的倍数。这样就包保证了p->i（地址xp）和p->j（地址xp+8）都满足它们的4字节对齐要求。在另个一种情况下，编译器可能会在结构的末尾进行一些填充，这样结构数组中每一个元素都会满足它的对齐要求，例如，我们有如下所示的结构体：
   
   如果编译器将这个结构体分配为9个字节的大小，只要保证结构的起始地址满足4字节对齐要求，我们就能够保证字段i和j的对齐要求，但是考虑如下所示的声明：
   
   这样的话，分配9个字节是不可能满足d的每个元素的对齐要求，因为这些元素的地址分别是xd，xd + 9，xd + 18，xd + 27，所以在实际情况中编译器会为结构S2分配12字节大小的空间，最后3和字节是用于对齐填充的：
   
   这样一来，d的地址分别为xd，xd + 12，xd + 24和xd + 36，这样一来，只要xd是4的倍数，所有的对齐限制就可以满足了。

5. 内存越界引用和缓冲区溢出

1. 在C语言之中，如果我们使用数组的话，C语言本身是不会对数组进行任何的边界检查的，而且局部变量和状态信息（例如保存的寄存器值和返回地址）都存放在栈中。这两种情况结合在一起就能导致严重的程序错误，对越界的数组元素进行的写操作会破坏存储在栈中的状态信息，当程序使用到那些被破坏的信息的状态用以重新加载寄存器或者是执行ret指令时，就会出现严重的错误；
2. 一种常见的状态破坏是缓冲区溢出，通常情况下，在栈中分配某个字符数组来保存字符串，但是当字符串的长度超过为数组分配的空间的时候，就会出现缓冲区溢出；下面的代码展示了缓冲区溢出的情况：
   
   gets会从标准输入中读入一行，在遇到一个回车符或某个错误情况时停止。它会将字符串复制到参数s指明的位置，并且在字符串的末尾加上一个null。在函数echo中我们使用到了gets，这个函数只是简单地从标准输入中读取一行，然后再把它送回到标准输出；但是gets的问题是他没有办法确定是否为需要保存的整个字符串分配了足够的空间。在echo的示例中我们故意将缓冲区设置的非常小，一共有8个字节，任何长度超过7个字符的字符串都会导致写越界；echo产生的汇编代码以及栈帧示意图如下所示：
   
   
   该程序把栈指针减去了24，在栈上分配了24个字节的空间，字符数组buf位于栈顶，栈指针%rsp被复制到%rdi作为调用gets以及puts函数的参数，这个调用的参数和返回地址的指针之间有16个字节是未被使用的。只要用户的输入不超过7个字符，gets返回的字符串（包括结尾的null）就能够放进为buf分配的空间里。不过长一些的字符串回到孩子gets覆盖栈上存储的某些信息随着字符串变长，存放的状态信息就会被破坏：
   
   字符串在到达23个字符之前都没有严重的后果，但是超过之后，返回指针的值以及更多可能的保存状态就会被破坏掉。如果存储的返回地址值被破坏了，那么在执行ret指令的时候会导致程序跳转到意想不到的地方。虽说在C语言的库函数中有更专业的fgets函数，他包括一个参数用以限制可以读入的最大字节数。但是很多常用的库函数包括strcpy，strcat以及sprintf都不需要告诉他们目标缓冲区的大小就产生一个字节序列，这样的情况就会到导致程序中存在缓冲区溢出的风险。
3. 缓冲区溢出有一个很大的风险，他会被用于进行计算机网络攻击。通常攻击者会输入给程序一个字符串，这个字符串包含一些可执行代码的字节编码，这被称为攻击代码，另外，还有一些字节会用一个指向攻击代码的指针覆盖返回地址，那么当程序执行ret指令的时候程序就会跳转到攻击者编写的攻击代码中执行攻击者所编写的攻击代码。其中一种形式是攻击代码会启动一个shell程序，用于给攻击者提供一组操作系统函数。另一种攻击形式是攻击者的恶意代码会执行一些未授权的任务，然后修复对栈的破坏，最后再（第二次）执行一次ret指令，在表面上正常返回到调用者。

6. 对抗缓冲区溢出攻击

1. 栈随机化

1. 缓冲区溢出攻击会给计算机系统造成许多的麻烦，现代的编译器和操作系统实现了很多机制用于避免缓冲区溢出攻击，其中一个方法就是栈随机化；
2. 入侵者为了在系统中插入代码并确保被插入的代码会被执行，他们除了要插入恶意代码，还需要插入指向这段代码的指针，这个指针也是攻击字符串的一部分。产生这个指针需要知道攻击字符串会放置到栈的哪个位置，也就是得到相应的栈地址。如果栈的位置过于固定，那么攻击者很容易就可以确定一个常见的Web服务器所使用的栈空间的具体信息，这使得攻击者可以对相同的很多机器发起攻击；
3. 栈随机化的思想就是使得栈的位置在程序每次运行的时候都会有所变化，因此即使在很多相同的机器上都运行相同的代码的时候，他们所得到的栈地址也是不尽相同的。实现栈随机化的方法是：每当程序开始的时候都会在栈上分配一段0~n字节之间的随机大小的空间，而程序并不使用这段空间，这样就会导致程序在每次执行时后续的栈位置发生了变化。分配的范围n需要足够大，这样才能够获得足够多的栈位置变化，但是n又不能太大，否则的话会占用过多的内存空间。
4. 在Linxu系统之中栈随机化已经成为了标准的行为。他是一个大类技术的一种，该技术被称作地址空间布局随机化（ASLR），当我们采用该技术的时候，系统在每次运行时程序的每一个部分都会被加载到内存的不同区域，它们包括程序代码，库代码，栈，全局变量和堆数据。这就意味着在一台机器上运行一个程序与哪怕同样的机器上运行同样的程序，程序的每一个部分的地址映射都是大相径庭的。这样就能够抵抗一些形式的攻击。但是某些顽固的攻击者仍能够在合理的时间内穷举破解栈随机化。

2. 栈破坏检测

1. 在之前的echo案例中我们可以发现破坏通常发生在局部缓冲区边界处，在C语言中没有可靠的方法来阻止对数组的越界写，但是我们可以在边界处做一些设置，能够在发生越界写的时候及时的检测到他么并做到合理的应对。

2. 最近的GCC版本就在代码中加入了一种栈保护机制，他的做法就是在栈帧中我们分配的局部缓冲区的边界处设置一个金丝雀值，也称为哨兵值，该值是在程序每次运行的时候随机产生的，因此攻击者并不能轻易地得到我们所设置的金丝雀值。如果我们的程序发生了越界写，那么金丝雀值就会被修改。在恢复寄存器状态并从函数返回之前，程序会检查金丝雀的值是否被修改了，如果发现该值被修改了，那么程序就会异常终止。
   

   我们可以看到如下的例子：
   
   
   在第三行，该程序从内存中读取一个值，然后将它放在栈中相对于%rsp偏移量为8的地方，其中的参数指令%fs:40指明金丝雀值是用段寻址的方式从内存中读入的，虽说在现代系统上运行的程序中已经很少能够见到了。我们所做的就是将金丝雀的值放到一个特殊的段中，并设置为只读的，这样攻击者就不能够覆盖我们存储在内存上的金丝雀值。这样在恢复寄存器状态和返回前函数会将存储在栈中的金丝雀值和存储在特殊段中的金丝雀值进行比较，如果相等的话xorq指令就会得到0，函数会按照正常的方式完成。非零的值表明栈上的金丝雀值被修改过，那么程序代码就会调用一个错误处理例程。栈保护很好的防止了缓冲区溢出攻击破坏存储在程序栈上的状态。他只会带来很小的性能损失，特别是因为GCC只有在函数中有局部char类型缓冲区的时候才会插入这样的代码。当然也有其他的方法会破坏一个正在执行的程序的状态，但是降低栈的易受攻击性能够对抗许多常见的攻击策略。

3. 限制可执行代码区域

• 还有一个方法就是消除攻击者向系统中插入可执行代码的能力，一种方法是限制那些内存区域是能够存放可执行代码的。在典型的程序中，只有保存编译器产生的代码的那部分内存才需要是可执行的，其他的区域是不可执行的，所以说攻击者就不能够向系统中插入可执行的代码。

7. 支持变长的栈帧

1. 我们目前接触到的都是固定大小的栈帧，但是有些函数需要变长的栈帧，比如说alloca函数，当我们调用该函数的时候就会需要变长的栈帧，它是一个标准库函数，可以在栈上分配任意字节数量的存储，同时，当代码声明一个局部变长数组时，也会发生以上的情况。
2. 以下的代码给出了一个变长数组的例子，该函数声明了一个容量为n的局部数组p，这里的n由第一个参数给出。这要求在栈上分配8n个字节，这里n的值在每次调用该函数的时候都有所不同，因此编译器无法确定要给该函数的栈帧分配多少的空间。此外该程序还产生了一个对局部变量i的地址引用，因此该变量必须存储在栈中。在执行过程中，程序必须能够访问局部变量i和数组p中的元素，返回时该函数必须释放掉这个栈帧，并将栈指针设置为存储返回地址的位置。
   
   
   以下为栈帧示意图
   
   为了管理变长的栈帧，x86-64代码使用寄存器%rbp作为帧指针，有时也被称作基指针（base pointer）。当使用帧指针时，栈帧的组织结构如上图所示。代码必须把旧的%rbp值保存到栈中（对应于图中的"保存的%rbp"），因为该寄存器是一个被调用者保存寄存器。然后在函数的整个执行过程中都使得%rbp指向那个时刻栈的位置。对于i来说可以使用其相对于%rbp的偏移量来引用它们。在函数刚开始的时候，会首先把%rbp的当前值压入栈中，将其设置为指向当前的栈位置。然后分配16字节的空间，其中8个字节用于存储i，另外8个字节是未使用的。接着，为数组p分配空间。程序分别在第15行以及第17行对局部变量i进行了修改和读取，两者都是通过-8(%rbp)来实现对局部变量i的访问的，该指令的意思是“相对于帧指针偏移量为-8的地方”。所以 i 的地址是引用-8(%rbp)，也就是相对于帧指针偏移量为 -8 的地方。在函数的末尾，leave指令将帧指针恢复到它之前的值，等价于如下的两条指令：
   
   也就是先把帧指针%rbp的值赋给栈指针%rsp，之后再将栈中保存的%rbp的旧值弹出到%rbp，最后栈指针%rsp指向的就是返回地址。所以说这个指令组合具有释放整个栈帧的效果。

8. 优化程序性能

1. 编译器的能力和局限性

1. 现代编译器会运用复杂精细的算法来确定一个程序中计算的是什么值以及它们是被如何使用的。然后编译器就会利用一些机会来简化表达式，做到在几个不同的地方使用同一个计算所得到的值，以及降低一个给定的计算必须执行的次数。大多数的编译器包括GCC向用户提供了一些优化控制，最简单的控制就是指定优化级别。例如使用指令-Og调用GCC是让GCC使用一组基本的优化，以选项-O1或者是更高的选项调用GCC则会让它使用更大量的优化，这样做可以进一步的提高程序的性能，但是也可能会增加程序的规模，同时使标准的调试工具更难对程序进行调试。
2. 编译器在优化的时候是以保证程序的安全以及正确为前提的，也就是说编译器优化后的程序和未优化的版本具有同样的行为，所以说有时候有一些代码是不会得到优化的，这类代码如下所示：
   
   有些人可能会觉得他们有相同的行为，他们都是将存储在由指针yp指向的位置处的值两次相加赋值给指针xp指示的位置处的值。另一方面，函数twiddle2的效率要更高一些，他只要求三次内存引用（读xp，读yp，写*xp），而twiddle1需要6次。但是编译器并不会将twiddle1优化为twiddle2，因为当xp等于yp的时候，对于twiddle1来说xp变为了原来的4倍，但是对于twiddle2来说xp变为了原来的3倍。但是编译器并不知道twiddle1会被怎么调用，所以编译器必须假定xp和yp会有相等的情况，所以它并不会将twiddle1优化为twiddle2；

2. 消除循环的低效率

1. 考虑如下所示的代码，它的功能是将大写字母转换为小写字母，但是获取s长度的地方不同，一个是在循环内部获取s的长度的，另一个是在循环外部获取s的长度的。
   
   对于一个长度为n的字符串来说，strlen所用的时间与n成正比，而对lower1的n次迭代的每一次都会调用strlen，所以说lower1的整体运行时间是字符串长度的二次项，正比于n^2.以下为对于两个函数的测量结果，从结果中我们可以看到对于lower1来说，字符串长度每增加一倍，运行时间都会变为原来的四倍：
   
   lower2仅仅是把对strlen的调用移动到了循环的外面，除此之外没有什么别的改变，但是性能却得到了显著的提升。虽说在理想的情况下编译器会对循环中的strlen进行优化，但是在实际上编译器会认为字符串的长度会有所改变，但是在实际上我们这里用到的字符串的长度并没有发生改变，尽管如此，编译器还是不会去尝试优化我们的循环，所以这就需要我们自己去解决此类的问题。
2. 减少过程调用也是一种程序优化方式，但是这需要结合实际的代码框架进行优化，有很多的过程调用是无法避免的，而且基于设计的需求有时候我们不得不进行过程调用；

3. 消除不必要的内存引用

• 在以下的代码中，我们可以看到不必要的内存引用：
  
  我们在此给出data_t为float，OP为乘法的汇编代码：
  
  可以看到在每次的迭代时，累计变量的值都要从内存中读出然后再写入内存。这样的读写是很浪费的，因为每次迭代开始时从dest中读出的值就是上次迭代最后写入的值。我们可以消除这种没有必要的内存读写，按照下图所示的方式重写代码，引入一个临时变量acc，它在循环中用来累计计算出来的值，只有在循环完成之后才将结果放入到dest中，正如其对应的汇编代码所示：
  

9. 存储器层次结构

1. 简介

1. 在简单模型之中我们将存储系统视作为一个线性的字节数组，CPU可以在常数的时间复杂度内访问每个存储的位置，但是该模型并没有体现出现代系统的工作方式；
2. 在实际上，存储器系统是一个具有不同容量以及成本和访问时间的存储设备层次结构，其中造价最高，大小最小同时访问速度最大的设备是寄存器，它用于存放CPU最经常使用的数据。靠近CPU的存储容量小的但是访问时间短的高速缓存存储器作为主存储器中数据以及指令的缓冲区域；同理，主存储器作为磁盘上的数据的缓冲区域，而磁盘又作为网路数据的缓冲区域；
3. 一个编写良好的程序更加倾向于访问更高层的存储器，所以说即使存储器的访问时间和它的造价以及存储大小是成反比的，但是编写良好的程序在实际的运行过程中得到的整体效果是我们拥有一个大的存储器池，它的成本与底层的存储设备相当，但是却拥有接近于层次顶部存储设备的访问速率；
4. 一个编写良好的程序具有良好的局部性，它会使程序倾向于反复地访问相同的数据项集合（时间局部性）或者是访问邻近的数据项集合（空间局部性）；
5. 如果我们编写的程序需要的数据是存储在CPU寄存器中的，那么在指令的执行期间CPU在0个周期内就可以访问到它们。如果将数据存储在高速缓存中呢么就需要大约4~75个周期，在主存中大约需要上百个周期，在磁盘上大约需要几千万个周期；

2. 存储技术

1. 随机访问存储器

1. 随机访问存储器（Random-Access Memory，RAM）分为静态RAM和动态RAM，其中静态的比的动态的更快，所以我们使用静态RAM也即SRAM来作为高速缓存存储器。高存储器既可以集成于CPU芯片之上，也可以集成于芯片之外。DRAM用来作为主存储器以及图形系统的帧缓冲区。SRAM将每一个位存储在一个双稳态的存储单元里，每一个单元由六个晶体管电路来实现，这种存储单元具有双稳态特性，所以只要有电，他就可以永远的保持它所存储的值，即使受到干扰它也会自动的恢复到稳定值；DRAM的存储单元是基于一个电容以及一个访问晶体管的，这种存储单元对干扰非常的敏感，当电容中的电压被干扰之后它就不能再被恢复了，而且会有漏电现象。内存系统必须周期性的通过读出然后重新写入来刷新内存中的每一位。下图总结了SRAM以及DRAM的特性：
   
2. 对于DRAM以及SRAM来说，如果断电，那么存储于其中的信息就会丢失，因此他们属于易失性存储器。非易失性存储器即使在断电之后让然能够保存着他们的信息，现如今有很多的非易失性存储器，他们被统称为只读存储器ROM，但并不是说所有的非易失性存储器都是只读的，其中很多的存储器即可以读也可以写。ROM是以他们能够被重编程的次数和对他们进行编程所使用的机制来区分的，分为PROM，EPROM，EEPROM，字母P代表Programmable，即可编程的；PROM只可以被编程一次，因为它的每个存储器单元是一种熔丝，只能被高电流熔断一次；EPROM是可擦写可编程ROM，它里面有一个透明的石英窗，可以被多次编程，它的存储单元可以被清除。该ROM能够被擦除和重编程的次数的数量级大约为1000。电子可擦除PROM类似于EPROM，但是该ROM能够被编程的次数的数量级可以达到10^5；我们平时所说的闪存就是基于EEPROM的，机械磁盘的替代者固态硬盘的实现就是基于闪存的，固态硬盘（SSD）相对于传统旋转磁盘来说更加的快速，强健，并且能耗也更低。
3. 存储在ROM中的程序通常被称为固件。当一个计算机通电启动的时候，它就会运行存储在ROM中的固件，一些系统在固件中提供了少量基本的输入和输出函数等。

2. 对主存的访问

1. 系统中的数据流通过被称为总线（bus）的共享电子电路在处理器和DRAM主存之间进行传输。每次CPU和主存之间的数据传送都是通过称为总线事务的一系列步骤来完成的。其中读事务从主存中传送数据到CPU，写事务从CPU传送数据到主存。这里的总线是一组并行的导线，它能够携带地址数据和控制信号。取决于总线的设计，数据和地址信号可以共享同一组导线，也可以各自使用各自的导线。两个以上的设备也可以共享同一个总线。控制线携带的信号会同步事务并标识出当前正在被执行的事务的类型。例如当前关注的事务是否是传输到主存的，或者是传输到磁盘控制器等IO设备的；以及该事务是读事务还是写事务；或者是总线上的信息是地址信息还是数据项信息。
2. 下图展示了计算机系统的配置，主要部件是CPU芯片，IO桥接器（其实就是一个芯片组，其中包含有内存控制器），以及由DRAM所组成的内存模块，这些模块由一对总线连接起来，其中一个总线是系统总线，它负责连接IO桥接器以及CPU，另一条总线是内存总线，它负责连接主存和IO桥接器。IO桥接器会将系统总线的电子信号转换为内存总线的电子信号。
   
3. 比如有以下的指令：movq A,%rax；在这里地址A中的内容被加载到寄存器%rax中。CPU上被称作总线接口的接电路在总线上发起对内存的读事务。读事务有以下的几个步骤组成，首先CPU将地址A发送到系统总线上，IO桥将信号发送到内存总线。主存会从内存总线上读取地址，然后在DRAM中取出存放在读取到的地址中的数据字，并将读取到的数据字写回到内存总线。IO桥将内存总线信号翻译为系统总线信号，最后CPU从系统总线中读取数据并将其存放到寄存器%rax中。过程示意图如下所示：
   
   反过来当CUP要执行以下的指令时：movq %rax,A，这里的需求是将寄存器中的值写到内存地址A处。首先CPU将地址A发送到系统总线上。DRAM从内存总线中读出地址，并等待数据的到达。之后CPU会将寄存器中的值发送到系统总线上，最后主存从内存总线上读出数据字，并将读出的数据字存放到地址A处。
   

3. 磁盘存储

1. 磁盘比DRAM读慢了10万倍，比SRAM读慢了100万倍。磁盘是由盘片构成的。每一个盘面一共有两个面或者称为表面，表面覆盖着磁性记录材料。盘片的中央有一个可以旋转的主轴，它使得盘面可以以固定的速率进行旋转，通常是5400~15000转每分钟。磁盘通常包含一个或者是多个这样的盘片并封装在一个密闭的容器之中。下图展示了一个磁盘的结构。每个表面由一组被称之为磁道的同心圆组成，每一个磁道都被划分为了一组扇区，每一个扇区包含有相等数量的数据位，通常是512个字节。这些数据被编码在扇区上的磁性材料中。扇区之间由一些间隙分隔开。在这些间隙之中不存储数据位。间隙存储用来表示扇区的格式化位。
   

2. 磁盘是由一个或者是多个叠放在一起的盘片组成的，他们通常被封装在一个密闭的包装里，如下图所示，整个装置被称之为磁盘驱动器，简称为磁盘，有时候我们将磁盘称作为旋转磁盘，目的就是将其与基于闪存的固态硬盘区别开，SSD是没有移动的部分的。有一个术语叫做柱面，柱面是所有盘片表面上到主轴中心距离相等的磁道的集合。比如图中的驱动器一共有三个盘片和留个盘面，每个表面上的磁道编号都是一样的，那么在这里柱面k就是6个磁道k的集合。
   

3. 磁盘容量：一个磁盘上可以记录的最大位数称为它的最大容量，或者直接简称为容量，磁盘的容量是由以下的技术因素决定的：

   • 记录密度：磁道一英寸的段可以放入的位数；
   • 磁道密度：从盘片中心发出半径上一英寸的段内可以有的磁道数；
   • 面密度：记录密度与磁道密度的乘积；

4. 磁盘的读写：磁盘用读写头来对存储在磁性表面上的位进行读写，读写头连接到一个传动臂的一端，如图所示。通过沿着半径前后移动这个传动臂，驱动器可以将读写头定位在盘面上的任何磁道上。这个过程被称作寻道，一旦读写头定位到了我们所期望的磁道上，那么当磁道上的每一个位通过磁头的时候，读写磁头既可以对该位进行读，也可以对该位进行写，多个盘片对每一个盘面都有一个独立的读写头，但是他们是垂直排列的，并且他们的行为是保持一致的，这也就意味着在任何时刻，读写头都是位于同一个柱面上的。
   

5. 磁盘以扇区大小的块来读写数据，对扇区的访问时间有以下的几个部分组成，分别是寻道时间，旋转时间和传送时间：

   • 寻道时间：为了读取某个目标扇区的内容，传动臂首先会将读写头定位到包含目标扇区的磁道上，移动传动臂所需要的时间被称之为寻道时间。在现代的驱动器中平均的寻道时间是3~9ms，一次寻道的最大时间可以高达20ms；
   • 旋转时间：一旦读写头定位到了我们所期望的磁道上，驱动器就开始等待目标扇区的第一个位旋转到读写头下面。驱动器所等待的时间就是旋转时间，该时间的长短取决于读写头到达目标扇区所在的磁道时目标扇区相对于读写头的位置以及磁盘的转动速度。在转动速度一定的时候，最坏的情况就是读写头定位到目标扇区所在的磁道的时候刚好错过了目标扇区，此时驱动器必须等待磁盘旋转一圈；
   • 传送时间：当目标扇区的第一个位位于读写头下方的时候，驱动器就可以对目标扇区进行读取或者是写入。一个扇区的传送时间依赖于磁盘的转动速度以及每一条磁道的扇区数目，即一个扇区的尺寸大小；
   • 在实际情况中，比如说访问一个扇区中512个字节的时间主要是寻道时间和旋转时间，访问扇区中第一个字节需要很长的时间，但是访问剩下的字节的时候几乎用不了多少时间，寻道时间和旋转时间大致是相等的，所以我们可以认为磁盘访问时间大致为两倍的寻道时间；

6. 现代磁盘的构造是非常复杂的，有多个盘面并且这些盘面上有不同的记录区，为了对操作系统隐藏这样的复杂性，通常我们会将磁盘构造为一个简单的视图。我们可以将一个B个扇区大小的磁盘构造为一个B个扇区大小的逻辑块序列，编号为0, 1, …, B-1。在这种磁盘封装中有一个小的硬件/固件设备，称为磁盘控制器，它维护着逻辑块号与实际的物理磁盘扇区之间的映射关系。如果操作系统想要读一个磁盘扇区的数据到主存，那么操作系统会发送一个命令到磁盘控制器读取某一个逻辑块号，控制器上的固件会执行一个快速表查找，将一个逻辑块号翻译成一个(盘面，磁道，扇区)的三元组，这个三元组唯一的标识了对应的物理扇区。之后控制器硬件就会解释这个三元组，将读写头移动到适当的柱面，等待扇区移动到读写头下，将读写头感应到的位数据放到控制器上的一个小缓冲区中，然后将他们复制到主存中。

7. 需要注意的是磁盘控制器必须对磁盘进行格式化之后才能够对磁盘进行存储数据的操作。磁盘格式化包括用标识扇区的信息填写扇区之间的间隙，标识出表面有故障的柱面并且不使用它们，以及在每一个扇区中预留出一组柱面作为备用，如果区中一个或者多个柱面在磁盘使用的过程中坏掉了，就可以使用那些备用的柱面，所以我们平时所使用到的磁盘存储空间是小于它的最大空间的。

8. 连接IO设备：例如监视器，鼠标，键盘和磁盘等输入输出设备都是通过IO总线连接到CPU和主存的。系统总线和内存总线总是与CPU相关的，与他们不同的是诸如PCI这样的IO总线被设计成与底层CPU无关的，下图展示了一个典型的IO总线结构，它连接了CPU，主存和IO设备；虽然IO总线的速度比系统总线以及内存总线慢，但是他们能够容纳种类繁多的第三方IO设备，图中的主机总线适配器将一个或者是多个磁盘连接到IO总线，它使用的是一个特别的主机总线接口定义的通信协议。
   
   其它的例如网络适配器等设备可以通过将适配器插入到主板上空的扩展槽中，从而连接到IO总线，这些插槽提供了到总线的直接电路连接。

9. 访问磁盘：下图总结了当CPU从磁盘读取数据时发生的步骤：
   
   CPU使用一种被称作内存映射IO的技术来向IO设备发送命令，在使用内存映射IO的系统中，地址空间中有一个地址是专门为与IO设备通信保留的。每一个这样的地址被称为一个IO端口。当一个设备连接到总线的时候，它就与一个或者是多个端口相关联，或者说该设备被映射到一个或者是多个端口。假设磁盘控制器映射到端口A，之后CPU可能会执行以下的三条对地址A的存储指令：第一条指令是发送一个命令字，告诉磁盘CPU会发起一个读操作，同时还发送了其它的参数，例如当读完成时我们是不是应该中断CPU；第二条指令指明了应该读的逻辑块号；第三条指令指明了应该存储相应磁盘扇区内容的主存的地址；当CPU发出了一个请求之后，在磁盘进行读取操作的时候CPU通常会执行其他的一些工作。因为一个1GHz的处理器的时钟周期大约为1ns，如果读磁盘的操作为10ms，那么CPU潜在的可能执行1000万条指令。在传输进行的时候如果执行简单的进行等待而什么都不去做的话，对CPU来说是一种极大地浪费。在磁盘控制器收到来自CPU的读命令之后，它将逻辑块号翻译成一个物理的扇区地址并读取该扇区中的内容，然后将内容之间传递到主存中，该过程不需要CPU的干涉（对应于图b），我们将这种设备可以自己执行读或者是写总线事务而不需要CPU干涉的过程称为直接内存访问（DMA），这种数据传送称为DMA传送。在DMA传送完成，磁盘扇区中的内容被安全的存储在主存之后，磁盘控制器通过给CPU发送一个中断信号来通知CPU，这会导致CPU暂停它当前正在做的工作并跳转到一个操作系统例程，这个程序会记录下IO操作已经完成，然后将控制返回到CPU被中断的地方。

4. 固态硬盘

1. 固态硬盘是一种基于闪存的存储技术，它在某一些方面是传统旋转磁盘的强有力的替代者，SSD封装插到IO总线上的标准硬件插槽中，它的行为对于CPU来说就和其它的硬盘一样，处理来自CPU的读写逻辑磁盘块的请求。一个SSD封装有一个或者是多个闪存芯片和闪存翻译层组成，闪存芯片替代传统旋转磁盘中的机械驱动器，闪存翻译层是一个硬件/固件设备，它负责映射逻辑块号和实际物理地址，将逻辑块的请求翻译成对底层物理设备的访问。
   
   SSD是以页为单位对数据进行读写的，只有当一个页所在的块整个被擦除的时候才能够对该页进行写操作，一旦一个块被擦除之后，块中的每一个页都可以不需要再进行擦除就写一次，正因为如此，SSD的写操作是要慢于读操作的，因为擦除快是需要额外的时间的，并且如果写操作试图修改一个包含已经有数据的页，那么该页所对应的块中的所有的页都必须被复制到一个新块中，然后才能将想要写入的数据写入到相应的页之中。同时，由于SSD是基于闪存的，而闪存是会被磨损的，所以说SSD也会被磨损。不过闪存翻译层中的平均磨损逻辑试图将擦除平均分布在所有的块上，这样就可以最大化每一个块的使用寿命。

3. 局部性

1. 一个编写良好的程序具有良好的局部性，局部性原理对硬件和软件系统的设计以及性能都有着极大的影响；

2. 局部性原理有两种不同的形式，一种被称之为时间局部性，一种被称之为空间局部性；时间局部性是指被引用过一次的内存位置可能会在不就的将来被再次引用；空间局部性是指如果一个内存位置A被引用了一次，那么程序很可能会在接下来的运行过程中引用内存位置A附近的内存位置；

3. 拥有良好局部性的程序通常不局部性较差的程序要运行的更快，这是因为在现代计算机系统的各个层次的设计之中都很好的结合了程序的局部性原理；从硬件到操作系统，再到应用程序，他们的设计都利用到了局部性。在硬件层，局部性原理允许计算机系统引入高速缓存存储器来保存最近被引用过的指令和数据项，从而提高对主存的访问速度。在操作系统层面，局部性原理允许我们使用主存来存储虚拟空间中最近被引用过的块，也就是将主存作为磁盘的高速缓存，当然我们也可以利用主存来缓存磁盘文件系统中最近被使用过的磁盘块。局部性原理同样允许我们将Web浏览器最近被引用到的数据存放在磁盘中作为缓存，这些缓存能满足对数据的请求，而不需要服务器的任何干预；

4. 对程序数据引用的局部性：下图中的简单函数对向量中的元素进行求和操作，该程序具有良好的局部性，因为sum在每次循环迭代中都会被引用一次，所以说sum具有良好的时间局部性；由于sum是标量，所以sum没有空间局部性；
   
   而对于向量v，它的元素是被顺序读取的，也就是按照他们存储在内存中的顺序，所以对于变量v具有良好的空间局部性，但是v的时间局部性是很差的，因为v中的每一个元素都只会被访问一次。因此对于整个函数来说，其中的变量要么具有好的时间局部性要么具有好的空间局部性，所以sumvec函数具有良好的局部性。

5. 对于sumvec这样顺序访问一个向量中每个元素的函数，我们称其具有步长为1的引用模式。有时也将步长为1的引用模式称作顺序引用模式。如果在一个向量中每隔k个元素进行访问，就称之为步长为k的引用模式，随着步长的增加，程序的空间局部性下降；对于一个多维数组来说，步长也是一个很重要的问题，比如说我们有一个二维数组a，如果我们以行优先的顺序读取数组中的元素的话，那么程序具有良好的空间局部性，因为数组在计算机中存储的时候就是按照行优先的顺序进行存储的，其结果就是我们会得到一个很好的步长为1的引用模式，它具有良好的空间局部性；
   
   但是如果我们将函数中i和j的顺序对调，也就是使用列优先的方式访问数组，那么程序就会是一个步长为N的引用模式，具有很差的空间局部性。
   

6. 对于程序的指令来说也是存在局部性的，因为程序指令是存放在内存中的，CPU必须取出这些指令才能够运行程序，所以我们也能够评价一个程序关于取指令的局部性，例如在sumvec的for循环体里面的指令是按照连续的内存顺序执行的，因此循环具有良好的空间局部性。因为循环体会被执行多次，所以它也有很好的时间局部性，代码区别于程序数据的一个重要属性就是在运行时diamante是不能被修改的。当程序正在执行的时候，CPU只从内存中读出它的指令，很少会重写或者是修改这些指令；

7. 所以我们可以得出以下的结论：

   • 重复引用相同变量的程序有良好的时间局部性；
   • 对于一个具有步长为k的引用模式的程序，步长越小空间局部性就越好。在内存中以大步长跳来跳去的程序空间局部性会很差；
   • 对于取指令来说，循环有好的时间局部性和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

4. 存储器层次结构

1. 在计算机系统之中不同的存储器的访问时间差异很大，访问时间快的存储器每字节的造价更贵，在计算机中所能够存储的空间也就更小，CPU和主存之间的差距也在拉大；同时，一个编写良好的程序通常会拥有良好的局部性。
2. 以上硬件以及软件的特性可以相互补充，这种相互补充的方式使我们得到了一种组织存储器系统的方法，称为存储器层次结构，所有的现代计算机都会使用这种层次结构，下图展示了一个典型的存储器层次结构，一般而言，越往高处走，存储器设备变得更快，更贵和更小，在最高层是少量快速的CPU寄存器，CPU可以在一个时钟周期内访问它们，接下来是一个或者多个小型到中型的基于SRAM的高速缓存存储器，可以在几个时钟周期内访问到它们。然后就是一个DRAM的主存，可以在几十到几百个时钟周期内访问它们，接下来是慢速但是容量很大的本地磁盘，最后有些系统会包括一层附加的远程服务器上的磁盘，通过网络访问它们。
   

存储器结构中的缓存

1. 一般而言高速缓存（cache）是一个小而且快的存储设备，它会作为更大但是速度更慢的设备的缓冲区，使用高速缓存的过程称为缓存（caching）。存储器层次结构的中心思想就是对于每一个k，位于第k层的更快更小的存储设备作为位于k + 1层的更慢更大的存储设备的缓存，也就是层次结构中的每一层都缓存来自较低一层的数据对象，例如主存作为本地磁盘上的数据的缓存，以此类推，直到最小的缓存，也就是CPU寄存器组；

2. 下图展示了存储器层次结构中缓存的一般性概念。第 k + 1 层的存储器被划分为连续的数据对象组块，称为块。每个块都有一个唯一的地址或名字使之区别与其它的块，块在通常情况下是固定大小的，但是块也可以是可变大小的，比如说存储在Web服务器上的远程HTML文件。在下图中第 k + 1 层的存储器被划分为16个块，每一个块大小固定，编号为0~15；
   
   类似地，第 k 层的存储器被划分为较少的块的集合，每一个块的大小和 k + 1 层的块的大小是一样的，第k层的缓存包含第k+1层的块集合的一个子集的副本。数据总是以块为传送单元在第k层和第k+1层之间进行来回复制，一般而言，层次结构中较低的设备的访问时间较长，因此为了弥补这种较长的访问时间，倾向于使用更大的块来与高速缓存进行数据的传输，比如说L1和L0之间的数据传输通常是一个字节大小的，而L2和L1之间，L3和L2之间以及L4和L3之间的传送通常使用的是几十个字节大小的块，而L5和L4之间的传送用的是大小为几百或几千字节的块。

3. 当程序需要第 k + 1 层的某一个数据对象d的时候，它首先会在当前存储在第 k 层中的一个块中查找d。如果d刚好缓存在第k层中，那么我们就会说我们对数据对象d的查找是缓存命中的；如果在第k层中没有缓存数据对象d，那么我们对数据对象d的查找就是缓存不命中的。当发生缓存不命中的时候，第 k 层会从第 k + 1 层中取出包含d的那一个块，如果第k层的缓存已经满了，那么从第 k + 1 层取出来的块可能就会覆盖现存的一个块。

4. 覆盖一个现存的块的过程被称之为替换或驱逐这个块，被驱逐的这个块有时也称为牺牲块。决定替换哪一个块是由缓存的替换策略来控制的，比如说采用随机替换策略或者是替换掉最近最少被使用（LRU）的那个快。在第 k 层缓存从第 k + 1 层中取出来的那个快之后，程序就能够像前面那样从第 k 层读出d了。例如在上图中在第 k 层读取块12中的一个数据对象的时候会导致缓存不命中，之后会把块12从第 k + 1 层中复制到第 k 层之中，然后块12就会保持在第k层之中等待稍后被访问。

5. 缓存不命中的种类：缓存不命中有以下的几种情况，如果第 k 层还没有存储任何的数据，那么对任何数据对象的访问都不会命中，一个空缓存有时候被称之为冷缓存，此类不命中被称作强制不命中或者是冷不命中，冷不命中只是一个短暂的状态，并不会在缓存暖身之后的稳定状态中出现。当发生不命中的时候第 k 层的缓存就会执行某一个放置策略来确定将 k + 1层中取出来的块放哪里。最灵活的方式就是允许来自 k + 1 层的块可以随机的放置于高速缓存中的任何位置。但是对于存储器层次结构中靠近CPU的缓存来说，它们是用硬件来实现的并且速度是最优的，采用随机的策略实现起来就会很昂贵，因为随机的放置块定位起来代价很高。所以硬件缓存通常使用的是更加严格的放置策略，这个策略就是将第 k + 1 层中的块限制在第 k 层中的某一个子集之中，比如我们限制第 k + 1 层中的块必须放置在第 k 层中的第 (i mod 4) 号块中，但是这种放置策略会引发一种新的缓存不命中那就是冲突不命中，在这种不命中的情况中，缓存往往是足够大的，还留有足够的空间可以放置块，但是由于我们将 k + 1 层中的每一个块限制在了第 k 层中的某一个子集之中，所以会发生很多的对象都被映射到同一个缓存块之中，缓存就会一直不命中，比如在上图中采用 (i mod 4) 的放置策略来放置块，如果程序一直反复的请求块0，块8，那么即使这个缓存可以容纳4个缓存块，缓存不命中还是会一直发生。还有一种缓存不命中称为容量不命中，也就是缓存太小了。程序在通常的情况下是按照一系列的阶段来运行的，每一个阶段都会访问缓存块中一个相对不变的集合，例如一个嵌套的循环可能会反复的访问同一个数组中的元素。缓存块中一个相对不变的集合被称作工作集，当我们的缓存太小的时候，容纳不了整个工作集，这个时候就会出现容量不命中。

6. 我们可以得到如下的结论：基于缓存的存储器层次结构是行之有效的，因为较慢的存储设备通常是更加的便宜的，同时好的程序倾向于表现出良好的局部性：

   • 利用时间局部性：由于时间局部性的存在，同一个数据对象可能会被多次的使用，如果一个数据对象在第一次被引用多个时候缓存不命中，那么我们就可以期望在后面对该目标一系列的缓存命中，由于缓存比低一层的存储设备的访问速度要更快，所有说对后面的命中的时间会比刚开始不命中的时候要快很多；
   • 利用空间局部性：一个块通常包含有多个数据对象，由于空间局部性，我们会期望后面对该块中其他对象的访问能够弥补不命中时复制该块所花费的时间；

   每一级的缓存缓存的内容以及被缓存在的地方是不一样的，同时延迟周期数以及负责管理缓存的主体也是不一样的：
   

5. 高速缓存存储器

1. 简介

在早期的计算机系统之中之后三层存储器结构，分别是CPU寄存器，DRAM主存以及磁盘存储，但是随着CPU的访问速度和主存之间的访问速度的差距逐渐增大，人们为了弥补这种较大的访问速度差距，于是就在CPU寄存器文件和主存之间插入了一个较小的SRAM高速缓存存储器，称为L1高速缓存，也被称为一级缓存，L1的访问速度几乎和寄存器是一样快的，典型的大约是4个时钟周期；

但是CPU的性能和主存的性能之间的差距还是在不断地增大，所以系统设计者又在L1高速缓存和和主存之间插入了一个容量更大的L2高速缓存，大约可以在10个时钟周期内访问到它，现代计算机中很多的还会包括L3高速缓存，可以在50个时钟周期内访问到它们，在这里我们假设只要L1高速缓存。

2. 通用的高速缓存存储器组织结构

1. 在下图中展示了一个高速缓存的通用组织：
   

2. 直接映射高速缓存：根据每个组中的行数E的不同，高速缓存被分为不同的类，每个组中只有一行的高速缓存被称为直接映射高速缓存：
   
   假设我们有这样一个系统，它拥有一个CPU，一个寄存器文件，一个L1高速缓存和一个主存。当CPU指向一条读内存字w的指令的时候，它会向L1高速缓存请求这个字，如果L1高速缓存中有w的一个缓存的副本，那么就得到L1高速缓存命中，高速缓存会抽取出w并将其返回给CPU，否则的话就是缓存不命中。此时L1会向主存请求包含字w的一个块的副本，CPU在这个过程之中必须保持等待，当请求的块最终从内存到达L1高速缓存的时候，L1会将这个块放到自己的高速缓存行之中，然后从存储的块中取出字w并返回给CPU。高速缓存确定一个请求是否命中然后抽取出所需要的字的过程包含以下的几个步骤：1. 组选择；2. 行匹配；3. 字抽取；

3. 对于直接映射高速缓存莱说，当进行组选择之后在进行行匹配是非常容易的，因为没一个组就只有一行，当且仅当设置了有效位并且高速缓存行中的标记与w的地址中的标记相匹配的时候，这一行包含w的一个副本；

4. 下入展示了直接映射高速缓存的工作流程：
   
   首先会进行组选择，在这一步中高速缓存会从w的地址空间中抽取出s个组索引位，这些会被解释为一个对应于一个组号的无符号整数，也就是图中所示的组号i；之后进行行匹配，如上图所示，选中的组中只有一个高速缓存行并且这个行的有效位被设置了，所以该行中的标记以及块中的位是有意义的。因为这个高速缓存行中的标记位与地址中的标记位相匹配，所以可以得到的结论就是我们想要的那个字的一个副本确实存储在该行里面的一个块中。最后进行字选择，w地址空间中的块偏移位提供了所需要的字的第一个字节在块中的偏移，在上图的示例中块偏移位是二进制100，也就是十进制4，说明w的副本是从块中的字节4开始的（我们假设字长为4字节）；

5. 这里有几个值得注意的点：

   • 标记位和索引位连起来唯一地标识了内存中的每一个块；
   • 因为有8个内存块，但是只有4个高速缓存组，所以说多个块会拥有相同的组索引；
   • 映射到同一个高速缓存组的块由标记位唯一地标识；

6. 直接映射高速缓存中的冲突不命中：冲突不命中在真实的程序中是非常常见的，当程序访问大小为2的幂的数组的时候，直接映射高速缓存中通常会发生冲突不命中，比如如下所示的函数：
   
   虽说对于x以及y来说该函数具有良好的空间局部性，但是它的缓存命中率并不会很高，我们采用的浮点数的大小是4个字节，x被加载到从地址0开始的32个连续的内存中，而y紧跟在x之后，从地址32开始。假设一个块的大小是16个字节，可以容纳4个浮点数，高速缓存由两个组组成，大小为32个字节，根据以上的假设每个x[i]和y[i]会映射到相同的高速缓存组：
   
   在运行的时候第一次迭代首先会使用到x[0]，缓存不命中会将x[0]~x[3]的块被加载到组0.接下来是对y[0]的引用，又会发生一次缓存不命中，之后 y[0]~y[3] 的块被复制到组0从而覆盖对x数组的缓存，从而一直循环最终会导致每一次对x和y的引用都会发生一次冲突不命中，我们将这种现象称作抖动，即高速缓存反复的加载和驱逐相同的高速缓存块的组。所以有些时候即使程序拥有良好的空间局部性，由于抖动的存在还是会使程序的运行速度下降不少。一种避免抖动的简单方法就是在每一个数组的结尾处放置B字节的填充，例如将数组x声明为float x[12]。假设在内存中y紧跟在的后面，我们就可以得到如下的已经消除抖动的从数组元素到组的映射：
   

3. 组相连高速缓存

1. 直接映射高速缓存中冲突不命中造成的问题源于每一个组只有一行，组相连高速缓存每一组中都可以存放多于一个的高速缓存行，如图展示了一个2路组相联高速缓存的结构：
   
   如下的两个图片展示了组相联高速缓存中的组选择，行匹配以及字选择：
   
   

4. 全相联高速缓存

1. 全相联高速缓存是一个包含所有高速缓存行的一个单独的组组成的，下图展示了它的结构：
   
2. 全相联高速缓存中的组只有一个，所以说地址只被划分成了一个标记和一个块偏移，下图展示了在其中寻找目标的过程：
   
   因为高速缓存电路必须并行的搜索许多相匹配的标记，所以构造一个又大又快的相联高速缓存是很困难的，而且很昂贵。因此，全相联高速缓存只适合做小的高速缓存，例如虚拟内存系统中的翻译备用缓冲器(TLB)，它缓存页表项。

5. 有关写的问题

1. 高速缓存关于读的操作是非常的简单的，但是对于写的操作就显得更加复杂了，假设我们要写一个已经缓存了的字w（写命中），在高速缓存中更新了它的w的副本之后，怎么更新w在层次结构中紧接着低一层中的副本呢？就简单的方法称作直写，就是立即将w的高速缓存块写回到紧接着的低一层中，虽然简单，但是直写的缺点就是每次写的时候都会引起总线流量，增加了总线流量，另一种方法被称作写回，思想就是尽可能的推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的低一层之中，由于局部性的存在，该方法会减少总线的容量，但是他的缺点就是增加了复杂性，高速缓存必须为每一个高速缓存行维护一个额外的修改位表明这个高速缓存块是不是被修改过。另一个问题是处理写不命中，一种方法是写分配，就是将块先加载到高速缓存之中然后再对其进行修改，该方法利用了空间局部性但是每一次都需要从低一层加载数据块。另一种方法是非写分配的，它会绕过高速缓存直接将这个字写到低一层之中。直写高速缓存通常是非写分配的，因为每一次都直接从低一层中取数据块会增加总线的负担，同样的，写回高速缓存通常是写分配的。

6. 一个真实的高速缓存层次结构示例

1. 高速缓存其实可以只保存指令或者只保存数据，前者叫做i-cache，i-cache通常是只读的，后者叫做d-cache，将指令和数据分别放在不通过高速缓存可以让处理器能够同时读取一个指令字和一个数据字，同时也确保了数据访问不会和指令访问形成冲突不命中，但是代价就是二者更可能会出现容量不命中。
2. 下图展示了Intel Core i7处理器的高速缓存层次结构，每个CPU芯片有四个核，每个核有自己私有的L1和L2高速缓存，并共享L3高速缓存。
   
   

7. 高速缓存参数的性能影响

1. 不命中率 = 不命中数量/引用数量；
2. 命中率 = 1 - 不命中率；
3. 命中时间：从高速缓存传送一个字到CPU所需的时间；
4. 不命中处罚：由于不命中所需的额外的时间；
5. 较大的高速缓存可能会提高命中率，但是却会增加命中时间，所以L0最小，之后越来越大；
6. 较大的块可以尽最大可能利用空间局部性，增加缓存命中率，但是可能会减低时间局部性比空将局部性更好的程序的命中率，同时数据块传输的时间也会更长；
7. 越往下层走，传送时间越长，所以越有可能使用写回而不是直写。直写比较容易实现并且拥有独立于高速缓存的写缓冲区，写回引起的传送比较少；
8. 不命中处罚比较高的时候使用比较小的相联度，L1高速缓存选择较低的相联度，比如Intel Core i7的L1和L2是8路组相联的，L3是16路组相联的；
9. 块是一个固定大小的信息包，在高速缓存和下一层之间来回传送；
10. 行是高速缓存中的一个容器，存储块以及有效位标和记位等其他信息；
11. 组是一个或者是多个行的集合；
12. 因为一行中总是会包含有一个块，所以经常将术语“行”和“块”互换使用；

6. 存储器山

1. 定义一个程序从存储系统中读取数据的速率称为读吞吐量，有时也称为读带宽，如果一个程序在s秒的时间段内读n个字节，那么这段时间的读吞吐量就是n/s，单位为MB/s，这里的MB/s是指10^6字节/秒，而不是 2^20 字节/秒：
   
   在以上的程序中，size越小得到的工作集也就越小，因此时间局部性越好；stride的值越小，得到的空间局部性越好，因此可以得到如下所示的存储器山：
   
   可以看到时间局部性越好，空间局部性越好，得到的吞吐量也就越高；值得注意的是即使在工作集很大即时间局部性很差的时候，随着步长的减少在存储山脊的最高点也比它的最低点高8倍。因此即使当程序的时间局部性很差的时候，空间局部性仍能够补救并且所得到的结果也是可以令人接受的。

2. 所以我们可以得到以下的几个结论：

   • 将注意力集中在内循环中，大部分的计算和内存访问都发生在这里；
   • 通过按照数据对象存储在内存中的顺序，以步长为1来读取数据，从而得到较好的空间局部性；
   • 一旦从存储器中读入了一个数据对象，就尽可能多地使用它，从而使程序中的时间局部性最大；