正在努力攻克《硬件/软件接口》一书。
读到第五章 Large and Fast: Exploiting Memory Hierarchy 5.7节Virtual Memory时遭遇了较大难度。另外花费了不少功夫来看。
这一节已经开始从CPU层涉及到操作系统的内容了，现在从总帖中另外再开出来一个单独记笔记。
《计算机操作系统》中对虚拟内存的介绍
基础的存储器管理方式有一个特点，即要求将一个程序的所有内容都装入内存之后才能够运行，但是还有以下两种情况：
- 有的程序很大，其要求的内存空间已经超过了物理内存的容量，以至于程序没有办法完全装入内存，以至于无法运行；
- 有大量程序要求运行，但由于内存容量不足以容纳所有这些内容，因此只能运行一部分，而剩下的只能留在外存上等待。
出现以上两种情况的基本原因都是因为内存容量不够大。一个显而易见的解决方法是从物理内存本身上进行提升，但是这个往往会受到机器本身的限制。另一种方式就是从逻辑上扩充内存容量，这也就是虚拟存储技术要解决的问题。
1.常规存储器管理方式的特征
- 一次性，作业必须一次性地全部装入内存之后才能够开始运行。事实上，许多程序在运行时，并没有用到全部的数据，其实很多空间被浪费了；
- 驻留性，当程序被装入内存之后，就会一直留在内存中，其中任何时候都不会被换出，直至完全运行结束。
2.局部性原理
程序运行时存在的局部性现象很早就已经被人发现了：
- 程序执行时，除了少部分的转移和过程调用指令以外，大多数情况下都是顺序执行的；
- 过程调用会把程序的执行轨迹从一部分区域转到另外一部分区域，但事实上每次调用的深度都是有限的。也就是说，程序将在一段时间之内，都局限在某个范围内运行；
- 程序中存在许多循环结构，这些结构只有少数指令，但是会被反复多次执行；
- 程序中还包括对很多数据结构的处理，比如说对数组的操作，这些处理也都是局限在很小的某个范围内。
另外，局限性还表现在下面两个方面：
- 时间局限性：如果程序中的某条指令被执行，则不久之后改指令可能被再次执行；如果某条数据被访问过，则不久之后该条数据可能被再次访问；
- 空间局限性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间之内所访问的地址都集中在某一范围之内。
3.虚拟存储器的基本工作原理
根据局部性原理可知，应用程序在运行之前没有必要全部装入内存，而只需要将当前就要用到的少数内容装入就可以，其余部分可以留在外存上。
程序在运行的过程中如果还需要调用更多的内容，则再从外存上调入内存，继续执行下去。
感觉国内的教材就是这个不好，老是总结这个性质、那个性质，除了考试的时候能够拿来背一下，没有特别实际的内容…0.0
回到 5.7. Virtual Memory
构造虚拟存储器有两个主要动机：
- 允许多道程序之间有效而安全地共享存储器，尤其这里需要强调云服务器中多虚拟机之间的虚拟存储；
- 消除主存容量过小而对程序设计造成的影响。
这里的目标与《操作系统》一书中讲的相似
- 动机一：多程序运行
为了允许多程序共享同一个主存储器，主存里面只需要存放众多程序中活跃的那部分，就像cache中只存放一个程序的活跃部分一样。这就是局部性原理。
编译时，程序员事先是不知道哪些程序将和其他程序共享存储器。事实上，当程序在运行时，共享主存的情况是动态变化的，因此我们希望将每个程序都编译到它自己的地址空间——就是一连串只能由该程序访问的地址上。
由虚拟存储器来完成程序地址空间到真实的物理地址之间的转换。这也是完成了数据保护。
比如说：写两个程序时，两个程序都访问到了0x0001这个地址，然后同时运行；但两个又其实是独立的程序，不应该相互影响，程序的实际地址就是通过虚拟存储器来转换到主存上。
- 动机二：程序要求的内容超过了主存的容量
以前，为了解决内存超出限制的问题，程序员需要把整个程序分成很多个片段。每个片段由数据和代码共同构造成模块，运行的过程中由编程控制代码的装载和覆盖。
虚拟存储器的发明可以帮助程序员摆脱这种困境，它的功能就是管理主存储器和辅助存储器之间的关系，就像Cache和主存之间的关系一样。
| 机制 | Cache-主存储器系统 | 虚拟存储器系统 |
|---|---|---|
| 数据的最终目标 | CPU | 主存储器（虚拟存储器） |
| 第一级存储器 | Cache | 主存储器（物理存储器） |
| 第二级存储器 | 主存储器 | 辅助存储器（Flash/硬盘） |
| 数据单元 | 块（Blocks） | 页（Page） |
| 数据缺失 | 缺失（Miss） | 缺页（Page Fault） |
虚拟地址可以被映射到主存储器上或者辅助存储器上，多个不同的虚拟地址也可以被映射到相同的物理地址上。
虚拟存储器通过重定位技术来简化程序加载，在用地址进行访问主存储器之前，重定位将程序用到的主存虚拟地址映射到不同的主存物理地址上。虚拟存储器可以把程序加载到主存中的任何位置，这样就不一定需要用连续的块来存放程序了，只要整个主存中能够找到足够数量的页，分开映射即可。
另外考虑辅助存储器的访问速度（可见5.2节Memory Technologies中的详表），无论是Flash还是更慢的硬盘，相对内存来说都会有非常长的延时，设计时需要考虑一些关键因素：
- 访问时间太长，因此页应该足够大，一次获取就能得到足够多的数据，典型的页大小是4KB~16KB
- 选用减低缺页率的组织结构，比如让页以全相联的方式放置
- 从软件的角度，用一些更先进的算法来选择替换页
- 采用写回机制
5.7.1. 页的存放和查找
前文提到过，由于缺页的代价实在太高，所以采用全相联的方式来降低缺页率会比较好，但是全文进行顺序检索也是不现实的。因此有了下面这种存储方式：
- 每一个程序都有自己独立的页表（Page Table）；
- 页表放置在主存中，用虚拟地址中的页码来进行索引，找到相对应的物理地址页；
- 为了指出页表在主存中的位置，硬件中有一个页表寄存器，寄存器指向的是每一条页表在主存中的起始位置。
页表、PC和寄存器，这三种东西放在一起就确定了一个程序的状态（State），通常把这种状态叫做一个进程（Process）。当一个进程占用CPU时，它就是活跃的（Active）；当另一个进程需要占用CPU时，就会保存下该进程的当前状态，把它变成非活跃的（Inactive）；等下次再切回来执行的时候，操作系统再重新加载程序的状态，把它激活，进程就会在之前保存的地方继续向下执行。
每个不同的进程可能有相同的虚拟地址（因为编程的时候无需考虑这一点），但是每个进程都有自己的页表，由操作系统负责分配和更新页表（地址的映射状况），每个虚拟地址都会指向不同的物理地址，因此不会产生冲突。
上图中，首先通过页表寄存器查到一个程序页表的起始位置；
然后用程序中的虚拟地址页号（虚拟地址高位）来作为索引，定位到虚拟存储器的条目；
与Cache非常类似，一条虚拟存储器记录里面有两项：有效位、内容（物理页号）；因为页表里面包含的是所有可能的虚拟页的映射情况，因此不需要Tag位；
如果某一条是有效的，则命中，根据记录里面的内容就能找到对应的在主存上的物理页地址；否则就发生缺页，要去硬盘中提取内容到主存中来
注意上图中的设备：一个页的大小是2^12=4KB，而虚拟地址空间一共是2^32=4GB，物理地址只有2^30=1GB（可见虚拟地址系统能够让1GB的实际物理空间处理4GB内存大小的程序，还是相当强大的），然后图里面显示的一个条目宽度只有19位，事实上为了寻址方便，会加入其它保护信息把它扩到32位。
5.7.2. 缺页
如果页表中的某条有效位是0，那么就发生了缺页，转由操作系统处理，操作系统需要在下一级存储层中（一般是硬盘）找到这一页，然后把它放到主存中去。
因此除了用页表跟踪虚拟页在主存中的对应位置，如果缺页发生，还需要用一个另外的数据结构来快速找到虚拟页在硬盘中的位置。这个结构可以是页表的一部分（比如说用页表的1表示命中，然后条目内容是虚拟页在主存上的物理地址；用0表示缺页，但是这个时候条目内容是虚拟页在硬盘上的物理地址），或者另外维护一个，然后寻址方式跟页表一样。
操作系统在创建进程的时候也会在硬盘上建好一个专门的区域叫做交换区（Swap Space），把进程中所有页的内容都放进去，然后建好索引。
然后，关于主存上的哪些页可以被替换掉，操作系统中也会有另外一个结构用来维护，当需要替换主存上的内容时，把长时间不用/近期不用的页写入交换区，要用的调出来。这个策略叫做LRU（Least Recently Used）。
要完全准确地执行LRU的代价太高，所以一种简化的方式是在页表中加入一个引用位（Reference Bit）/使用位（Use Bit）。当某一页被访问过时，把它置为1，然后每过一段时间把所有引用位清零。这样就可以判定在某一段特定的时间内哪些页被访问过。
5.7.3. 关于写
在虚拟存储器系统中，对于硬盘的操作耗时过大，因此不可能使用写直达方式，必须使用写回机制，对存储器中的页进行单独读写，只有在该页要被替换出存储器时再复制到硬盘中。
并且在磁盘中，复制整页回去比写单个字要高效的多，尽管开销依然大。所以为了追踪读入主存中的页是否被重写过，可以在页表中添加一个重写位（Dirty Bit）。当该页中的任何一个字被修改之后就将其置位。
当操作系统需要替换掉一整页的时候，如果该页需要被重写才将其整页写回硬盘；否则不需要写回。
5.7.4. 加快地址转换：TLB
页表存放在主存中，因此程序每次访存实际上需要两次对主存的访问：第一次访问主存上的页表，用虚拟地址得到转换之后的物理地址；然后检查Cache上物理地址的命中情况，如果缺失，那么要用这个物理地址再次访问主存获取数据。
现代的处理器都包含一个特殊的Cache来追踪最近使用过的地址变换。这个特殊的地址变换Cache就是TLB（Translation-lookaside Buffer）。
虚拟存储器这部分多次反复使用到了Cache的思想。TLB与页表的思想区别是，页表有很多个，TLB只有一个。页表是在思想上参照了Cache，TLB则完全就是Cache的翻版。
上图中的页表加上了前几小节中提到的引用位（Reference Bit）和重写位（Dirty Bit）。虚拟地址过来首先跟Cache一样把虚拟地址页号分成两部分，用索引地址找到对应的条目，然后对比Tag，如果命中则直接使用物理地址；否则TLB缺失，则继续看能否在主存中找到，并装载到TLB中；再否则就是发生了主存缺页，进一步跳到硬盘上调取数据。
三个标志位同步更新处理即可。
5.7.5. 集成虚拟存储器、TLB和Cache
虚拟存储系统和Cache可以看成是同一级的，下面来看一下TLB、页表、Cache三个缺失和命中的所有情况：
| TLB | 页表 | Cache | 可能性 | 发生的情况 |
|---|---|---|---|---|
| Hit | Hit | Hit | 可能 | |
| Hit | Hit | Miss | 可能 | |
| Miss | Hit | Hit | 可能 | TLB缺失，但找到页表，再找Cache |
| Miss | Hit | Miss | 可能 | TLB缺失，Cache缺失，找主存 |
| Miss | Miss | Miss | 可能 | TLB缺失且缺页，需要找硬盘 |
| Hit | Miss | Miss | 不可能 | 主存中没有，TLB中就不可能有 |
| Hit | Miss | Hit | 不可能 | 主存中没有，TLB中就不可能有 |
| Miss | Miss | Hit | 不可能 | 主存中没有，Cache中也不会有数据 |
上文的所有情况都是假定Cache是完全物理寻址的，即Cache必须要由虚拟存储器对虚拟地址转换为物理地址之后才能寻址，缺点就是，CPU直接生成的地址都是虚拟地址，所以这是个串行的过程，则访问主存的时间要包括对TLB访问和对Cache访问的时间。
另外有一种方式是Cache的虚拟寻址，可以是完全的或者是部分的，通过查找和对比虚拟标签来找到目标，这样就不需要访问TLB了。当然问题就是，多个程序如果虚拟地址是相同的，那么会产生冲突，需要另外加以限制。
折中解决方案是采用虚拟寻址物理标记，使用页内偏移进行寻址（页内偏移就是地址的低位，是不被转换的，因此实际上这部分虚拟地址就是物理地址），然后高位虚拟地址经过转换之后用来作为Tag。这种方式可以拥有两种方式的优点，并且是并行的（虽然转换的时候可能有更多的延迟）。上面举例的FastMATH采用的就是这种。
5.7.6. 虚拟存储器中的保护
为了使得操作系统能够对虚拟存储器系统进行保护，硬件至少要提供3种基本功能：
1.至少支持两种模式：用户进程和操作系统进程；
2.提供一部分处理器的状态为用户只读。包括读取处理器状态、页表指针以及TLB等。只有操作系统可以通过特殊指令来对它们进行写操作；
3.提供用户态和操作系统态的相互切换机制。
页表只能被操作系统修改，用户不能对其进行操作。
一旦开始共享主存，每个用户态的进程只能够在自己的地址空间内进行操作，另外操作系统也通过设置页表上的选项来指定进程的读写能力。
5.7.7. 处理TLB缺失和缺页
TLB缺失和缺页都要通过调用系统异常（中断）来解决，主要是通过把异常发生时的状态保存在一些特定的寄存器中，如EPC等，然后调用系统异常处理程序。
TLB操作与页表操作都要通过特殊的指令来完成。
本节到此结束，真是有点累。增加了存储器部分的详细信息，尤其是支持虚拟存储器系统之后，第4章的数据通路与流水线怕是要发生很大的改动了。存储器的访问部分需要耗费的时钟周期远比原来想象的要多。
资料：