系统级程序设计笔记（unit6——存储设备层次结构、高速缓存、虚拟内存）
这个专题的所有学习笔记来自于对武汉大学计算机学院软件工程专业大三上学期的专业必修课《系统级程序设计》的学习（教材为深入理解计算机系统CSAPP），涉及的编程语言全部为C语言和C++语言。
该博客为第6单元的学习笔记，这一单元的主要内容是存储设备层次结构、缓存、高速缓存的通用组织、虚拟内存等。内容来自《深入理解计算机系统》的第六章的部分内容。对应ssd6课程的lecture7。
存储器系统Memory Systems
（1）Why Memory Hierarchy ?
到目前为止，在对系统的研究中，我们依赖于一个简单的计算机系统模型，CPU执行指令，而存储器系统为CPU存放指令和数据。
实际上，存储器系统（memory system）是一个具有不同容量、成本和访问时间的存储设备的层次结构。
CPU寄存器保存着最常用的数据。靠近CPU的小的、快速的高速缓存存储器作为一部分存储在相对慢速的主存储器中数据和指令的缓冲区域。主存缓存存储在容量较大的、慢速磁盘上的数据，而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域。
存储器层次结构是可行的，这是因为与下一个更低层次的存储设备相比来说，一个编程良好的程序倾向于更频繁地访问上一个层次上的存储设备。所以，下一层的存储设备可以更慢速一点，也因此可以更大，每个比特位更便宜。
计算机程序有一个被称为是局部性的基本属性。具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合，或是倾向于访问临近的数据项集合。具有良好局部性的程序比局部性差的程序更多地倾向于从存储器层次结构中的较高层次处访问数据项，因此运行得更快。
（2）有很多方法用来存储信息
半导体、磁盘、光盘
Read-Only Memory(ROM)只读存储器，代码和数据永久保存且不能修改，读取速度比RAM慢很多
Magnetic disks 磁盘
Magnetic tapes 磁带
Optical disks 光盘
Static Random Access Memory (SRAM) 静态随机访问存储器：是一种具有静止存取功能的内存，不需要刷新电路即能保存它内部存储的数据。SRAM的优点是较高的性能、功耗低，缺点是集成度低，掉电不能保存数据。
Dynamic Random Access Memory (DRAM) 动态随机访问存储器：DRAM 只能将数据保持很短的时间。为了保持数据，DRAM使用电容存储，所以必须隔一段时间刷新（refresh）一次，如果存储单元没有被刷新，存储的信息就会丢失。 （关机就会丢失数据）
（3）磁盘存储
磁盘存储的特性：磁盘是广为应用的保存大量数据的存储设备，存储数据的数量级可以达到几百到几千千兆字节，而基于RAM的存储器只能有几百或几千兆字节。不过，从磁盘上读信息的时间为毫秒级，比从DRAM读慢了10万倍，比从SRAM读慢了100万倍。
利用多种内存技术来同时获得速度和大小的这种方案称为内存层次结构。
（4）引用局部性
理想的情况下：
在执行过程中CPU将要访问的内存地址将提前被知道。
预取数据（prefetch data）：缓存数据预取技术应用于计算机操作系统缓存存储优化技术。数据预取指在处理器访问该数据进行计算之前，提前将数据从主存储器加载到缓存存储器上，以降低处理器访问数据的停顿时间，以提高处理器的性能。数据预取分为软件预取和硬件预取。
软件预取：编程人员和编译器通过插入软件预取指令来实现数据预取。
硬件预取：现代处理器大多数实现了硬件预取。处理器检测运行的程序的存储访问模式，并进行预测那些数据会被下次访问，并将预取这些数据。
实际情况：
无法准确地知道CPU将访问哪些地址；编译器不能自行决定将哪些数据从慢速内存移动到快速内存。
局部性：程序倾向于引用临近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。这种倾向性被称为局部性原理，对硬件和软件系统的设计和性能都有着极大的影响。
时间局部性：良好时间局部性的程序中被引用过一次的内存位置很可能在不远的将来再被多次引用。
空间局部性：良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。
★注意局部性是程序的属性，而不是计算机的属性。
在硬件层，局部性原理允许计算机设计者通过引入高速缓存存储器这一小而快速的存储器来保存最近被引用的指令和数据项，从而提高对主存的访问速度。
在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间最近被引用块的高速缓存。
操作系统使用主存来缓存磁盘文件系统中最近被使用的磁盘块。
时间局部性和空间局部性的例子，课本418-421，练习题7和8
（5）代码区别于程序数据的一个重要属性是在运行时它是不能被修改的。当程序正在执行时，CPU只从内存中读出它的指令，CPU很少会重写或修改这些指令。
（6）存储器层次结构
计算机使用不同大小和速度的存储技术，以可接受的成本实现可接受的速度和尺寸。
PPT：典型的计算机设计在层次结构中至少有四个层次。
寄存器与CPU最接近，大小最小，也是系统中最快的内存。
离CPU最远的是磁盘，程序中大的无效部分会休眠很长一段时间。
在中间：高速缓存和主存储器
这些级别的策略决策是在程序执行时做出的。
计算机有特殊的高速缓存硬件，可以实现数据在内存和缓存之间的移动。
课本：在最高层是少量快速的CPU寄存器，CPU可以在一个时钟周期内访问它们。接下来是一个或多个小型到中型的基于SRAM的高速缓存存储器，可以在几个CPU时钟周期内访问它们。然后是一个大的基于DRAM的主存，可以在几十到几百个时钟周期内访问它们。下来是慢速但是容量很大的本地磁盘。最后，有些系统甚至包括了一层附加的远程服务器上的磁盘，要通过网络来访问它们。例如，分布式文件系统、Web服务器上的远程文件。
（7）设计存储器层次结构需要考虑的一些策略：
取数据：数据应该何时向上一级层次结构移动？每个事务中应该移动多少数据？
放置：在较小的内存中，获取的数据应该存储在哪里？当CPU请求时，如何找到它？
替换：当新取的数据发现其位置已满时，哪些先前驻留的数据应该被逐出？
更新：当“缓存”数据被更改时，应该在较低级别的内存中立即或以后更新相应的数据吗？
Caches
（1）一些概念的介绍
高速缓存（cache）是一个小而快速的存储设备，它作为存储在更大更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存（caching）
存储器层次结构的中心思想是：对于每个k，位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存->层次结构中的每一层都缓存来自较低一层的数据对象。
缓存命中（cache hit）：当程序需要第k+1层的某个数据对象时，它首先在当前存储在第k层的一个块中查找，如果这个对象刚好缓存在第k层中，那么就是缓存命中。根据存储器层次结构的性质，这要比从k+1层读取更快。
缓存不命中（cache miss）：如果第k层中没有该数据对象，那么就是缓存不命中。当发生缓存不命中时，第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块。
覆盖一个现存的块的过程称为替换（replacing）或驱逐（evicting）这个块，被驱逐的这个块被成为牺牲块（victim block），决定替换哪个块是由缓存的替换策略（replacement policy）来控制的。
（2）缓存不命中的种类
①如果第k层的缓存是空的，那么对任何数据对象的访问都会不命中，一个空的缓存被称为是冷缓存（cold cache），此类不命中称为强制性不命中（compulsory miss）或冷不命中（cold miss）
②限制性的放置策略，例如确定第k+1层的块i必须放置在第k层的块（i mod 4）中，会引起冲突不命中（conflict miss），因为这些对象有时会映射到同一个缓存块，缓存会一直不命中。比如程序连续请求0、4、0、4、0、4，就会产生连续的置换，导致每次请求都会不命中。
③一个嵌套的循环可能会反复访问同一个数组中的元素，这个块的集合称为这个阶段的工作集。当工作集的大小超过缓存的大小时，缓存会经历容量不命中（capacity miss），也就是说缓存太小了，不能处理这个工作集。
（3）基于缓存的存储器层次结构行之有效的原因是程序倾向于展示局部性：
①利用时间局部性：由于时间局部性，同一数据对象可能会被多次使用。一旦一个数据对象在第一次不命中时被复制到缓存中，该目标很可能在之后有一系列的缓存命中。因为缓存比低一层的存储设备更快，对后面的命中会比开始的不命中快很多。
②利用空间局部性：块通常含有多个数据对象。由于空间局部性，我们会希望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。
（4）高速缓存的通用组织
S=：组数
E：每个组的行数
B=：块大小（字节）
m：主存的物理地址位数
M=：不同的地址数
t=m-(b+s)：标记位数量
C=B*E*S：不包括有效位和标记位这样开销的高速缓存大小（字节）
（5）直接映射高速缓存
每个组只有一行(E=1)的高速缓存称为直接映射高速缓存（direct-mapped cache）
直接映射高速缓存确定一个请求是否命中然后抽取出被请求的字的过程分为三步：（1）组选择（2）行匹配（3）字抽取
组选择由组索引位完成，例如组索引位00001被解释为一个选择组1的整数索引。
行匹配： 1.有效位必须设置 2.高速缓存行的标记位必须与地址的标记位相匹配 3.如果前两条满足，那么高速缓存命中，块偏移选择起始字节。
字抽取：一旦命中，说明w就在这个块中的某个地方。块偏移位提供了所需要的字的第一个字节的偏移，上图块偏移为100，表明w的副本是从字节4开始的。
为什么用中间的位来做索引？
高位做索引：一些连续的内存块会映射到相同的高速缓存块，空间局部性差
中间位做索引：相邻的块映射到不同的高速缓存行，从而使高速缓存能够存放整个大小为C的数组片（这里C是高速缓存的大小）。
（6）存储器山
一个程序从存储系统中读数据的速率称为读吞吐量（read throughput），或者有时称为读带宽（read bandwidth），如果一个程序在s秒的时间段内读n个字节，那么这段时间内的读吞吐量就等于n/s，通常以兆字节每秒(MB/s)为单位
存储器山（memory mountain）是一个读带宽的时间和空间局部性的二维函数，可以用来表征内存系统性能。
（7）编写高速缓存友好的代码
1.让最常见的情况运行得快2.尽量减小每个循环内部的缓存不命中数量
对局部变量的反复引用是好的，因为编译器能够将他们缓存在寄存器文件中（时间局部性）
步长为1的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块（空间局部性）
练习题7-8通过改变步长，利用空间局部性提升了程序的性能。
练习题9有利于对高速缓存的通用组织的基本构造有更好的理解。
P430的例子对理解高速缓存是如何工作的相当有帮助，多看几遍。
练习题13-16对理解在请求命中与否的过程中抽取出被请求的字的过程的三部曲：组选择、行匹配和字抽取非常有帮助。其中的16题是一种逆过程。
练习题17-20要仔细看，非常重要。
2017年-2018年的期末考试的第一问考了练习题17题的A题。
Virtual Memory (VM)
注：这部分中的许多知识在大二下学期的操作系统课程中已经详细学过。相关课程笔记也在我的博客中。
（1）
使用物理DRAM作为磁盘的高速缓存
一个进程的地址空间可以超过物理内存大小
多个进程的地址空间大小之和可以超过物理内存
简化存储管理->（5）
多进程常驻内存。每个进程都有自己的地址空间。
事实上只有只有“积极”的代码和数据在内存中，根据需要分配更多的内存给这些进程。
提供保护->（6）
一个过程不能妨碍别的进程，因为它们在不同地址空间操作。
用户进程不能访问需要特权的信息，不同的地址空间部分具有不同的权限。
（2）DRAM vs. SRAM as a “Cache”
访问延迟：在存储层次结构中，DRAM的缓存的位置对它的组织结构有很大影响。DRAM比SRAM慢大约10倍，磁盘比DRAM慢大约100000多倍。因此DRAM缓存中的不命中比起SRAM缓存中的不命中要昂贵得多，这是因为DRAM缓存不命中要由磁盘来服务，而SRAM缓存不命中通常是由基于DRAM的主存来服务的。而且从磁盘的一个扇区读取第一个字节的时间开销比读这个扇区中连续的字节要慢大约100000倍。归根结底，DRAM缓存的组织结构完全是由巨大的不命中开销驱动的。
（3）物理寻址：由CPU生成的地址直接对应于物理内存中的字节。
虚拟寻址：CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到主存之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译。
虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组，每个字节都有一个唯一的虚拟地址作为到数组的索引。虚拟内存系统将虚拟内存分割为大小固定的块，称为虚拟页（Virtual page,VP），每个虚拟页的大小为字节。类似地，物理内存被分割为物理页(Physical Page,PP)，大小也为P字节（物理页也被称为页帧page frame）
任意时刻虚拟页的集合分为三个不相交的子集：
未分配的、缓存的、未缓存的
页表（page table）用来判定一个虚拟页是否缓存在DRAM中的某个地方，如果是，存放在哪个物理页中；如果不命中，这个虚拟页存放在磁盘的哪个位置，并从物理内存找一个牺牲页进行替换。
（4）再次探讨局部性
通常，程序在整个运行期间引用的总页数可能超过物理内存的总大小。
局部性原则保证，在任何时候，它们都倾向于在一组较小的活动页面集合上工作，称为“工作集”或“常驻集”。
在将工作集页面调度到内存中之后，产生了初始开销，接下来对这个工作集的引用将会命中，而不会产生额外的磁盘流量。
工作集的大小超过物理内存的大小->导致抖动，页面不断地换进换出。
（5）大大简化内存管理：
按需页面调度和独立的虚拟地址空间的结合，对系统中内存的使用和管理造成了深远的影响。VM简化了链接和加载、代码和数据共享，以及应用程序中的内存分配。
下图展示了一个数据共享的例子，操作系统通过将不同的进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本。
（6）内存保护
不应该允许一个用户进程修改它的只读代码段，而且也不应该允许它读或修改任何内核中的代码和数据结构，不应该允许它读或者写其他进程的私有内存，并且不允许它修改任何与其他进程共享的虚拟页面（除非所有的共享者都通过调用明确的进程间通信系统调用而显式地允许它这么做）