PS ：

这是很久之前写的笔记了（有道课上学的。。。），可能是照着打下来的，但是不甘就放到草稿里，还是发出来吧。。。

知识点6： Cache与虚拟存储器

引入Cache的原因：
外部设备的优先级最高，这样就会导致CPU等外部设备访存的现象，致使CPU空等一段时间，为了避免CPU与I/O设备争抢访存，可在CPU与主存之间加一个Cache。
如果外部设备正在和主存交换信息，CPU就可以不用等待，直接从Cache中取所需信息。

主存速度的提高始终跟不上CPU的发展
高速缓存Cache来解决主存与CPU速度不匹配的问题。

（Cache里的信息 可以看成 是CPU的一个副本， 如果Cache里要更新，那么还要传回CPU中在变）

1): 时间局部性原理 ： 如果某个数据或指令被使用，那么不久将可能再被使用 （例：for循环）
2): 空间局部性原理 ： 如果某个数据或指令被使用，那么附近数据也可能被使用

Cache和主存的映射关系：
Cache和主存都被分为若干大小相等的块（Cache块又称为Cache行），
每块由若干字节组成，块的长度称为块的步长（Cache行长）。
Cache的容量远小于主存的容量，Cache中的块数 要远小于 主存中的块数，它仅保存主存中最活跃的若干块的副本。
Cache和CPU之间的数据交换以字节为单位
Cache与主存 数据交换 则是以 Cache块为单位

命中率：CPU要访问的信息已在Cache中的比例。
平均访问时间： …
Cache-主存系统效率：…

地址映射机构 将 CPU送来的主存地址 转换为 Cache地址
主存和Cache的块大小相同，地址映射是 主存块号 与 Cache块号 之间的转换。
即直接映射，全相联映射，组相联映射。

在Cache中要为每一块加一个标记，指明它是主存中那一块的副本。该标记的内容相当于主存中块的编号。
为了说明该标记是否有效，每个标记至少还应设置一个有效位，该位为1时，表示Cache映射的主存块数据有效；否则无效。

直接映射： 主存数据块只能装入Cache中的唯一位置。若这个位置已有内容，则产生块冲突，原来的块将无条件地被替换出去。
直接映射简单，但不够灵活，即使Cache其他许多地址空着也不能占用，这使得直接映射的块冲突概率最高，空间利用率最低。
直接映射关系可以定义为 j = i mod 2c次方
直接映射的地址结构为：…

全相联映射： 可以把主存数据块装入Cache中的任何位置。
全相联映射的优点是比较灵活，Cache块的冲突概率低，空间利用率高，命中率也高；
缺点是地址变换速度慢，实现成本高，通常需采用昂贵的 按内容寻址的 相联存储器 进行地址映射。
全相联映射的地址结构为：…

组相联映射：将Cache空间分成大小相同的组，主存的一个数据块可以装入到一组内的任何一个位置，
即组间采取直接映射，而组内采取全相联映射，它是对直接映射和全相联映射的一种折中。
组相联映射的关系可以定义为： j = i mod Q 式中，j是缓存的组号，i是主存的块号，Q是Cache的组数
组相联映射的地址结构为：…

Cache中主存块的替换方法：
常用的替换算法有 随机（RAND）算法、 先进先出（FIFO）算法、 近期最少使用（LRU）算法、 和 最不经常使用（LFU）算法
随机算法： 随机地确定替换的Cache块。
它的实现比较简单，但没有依据程序访问的局部性原理，故可能命中率较低。
先进先出算法: 选择最早调入的行进行替换。
它也比较容易实现，但也没有依据程序访问的局部性原理，可能会把一些需要经常使用的程序块（如循环程序）也最为最早进入Cache的块替换掉。
近期最少使用算法： 依据程序访问的局部性原理 选择 近期内长久未访问过的存储行作为替换的行，平均命中率要比FIFO要高，是堆栈类算法。
最不经常使用算法： 将一段时间内被访问次数最少的存储行换出。

Cache写策略;
因为Cache中的内容是主存块副本，当对Cache中的内容进行更新时， 就需要选用写操作策略 使 Cache内容和 主存内容保持一致。
主要有2中写操作策略： 全写法和写回法
全写法（写直通法）： 当CPU对Cache写命中时，必须把数据同时写入Cache和主存。当某一行需要替换时，不必把这一块写回主存，将新调入的块直接覆盖即可。
这种方法实现简单，能随时保持主存数据的正确性。 缺点是增加了访存次数，降低了Cache的效率。
写缓冲： 为减少全写法直接写入主存的时间损耗，在Cache和主存间加一个 写缓冲（Write Buffer）。CPU同时写数据到Cache和 写缓冲中，写缓冲再控制将内容写入主存。
写缓冲是一个FIFO队列，写缓冲可以解决速度不匹配的问题。但如果出现频繁写时，会使写缓冲 饱和溢出。
写回法： 当CPU对Cache写命中时，只修改Cache的内容，而不立即写入主存，只有当此块被换出时才写回主存。
这种方法减少了访存次数，但存在不一致的隐患，每个Cache行必须设置一个标志位（脏位），以反映此块是否被CPU修改过。

虚拟存储器将主存或辅存的地址空间统一编址
用户编程允许涉及到的地址 称为 虚地址或者逻辑地址，
虚地址 对应 的存储空间 称为 虚拟空间 或 程序空间。
实际的主存单元地址称为 实地址或者 物理地址
实地址对应的是主存地址空间， 也称 实地址空间。
虚地址比实地址要大很多。

CPU使用虚地址时，由 辅助硬件 找出 虚地址和实地址之间的对应关系，并判断这个虚地址对应的存储单元内容是否已装入 主存。
如果在主存中，则通过地址变换，CPU可直接访问主存 指示 的实际单元；
如果不在主存中， 则把包含这个字的一页或一段调入主存后再由CPU访问。
（即：一个程序想要运行，必须进入主存并占有CPU）

页式虚拟存储器
以页为单位的虚拟存储器。
虚拟空间与主存空间都被划分为同样大小的页，主存的页称为实页，虚存的页称为虚页。
把虚拟地址分为2个字段：虚页号 和 页内地址。
虚地址到实地址之间的变换是由 页表 来实现的。
页表 是 一张存放在主存中的虚页号和实页号的对照表，记录着程序的虚页调入主存时被安排在主存中的位置。
页表一般长久地保存在内存中。

段式虚拟存储器
段是按程序的逻辑结构划分的，各个段的长度因程序而异。
把虚拟地址分为2部分： 段号 和 段内地址。
虚拟地址到实地址之间的变换是由 段表 来实现的。
段表 是 程序的逻辑段和在主存中存放位置的对照表。
段表的每一行记录了与某个段对应的段号、装入位、段起点、段长等信息。（段的基址和段长（起始点和步长））

段页式虚拟存储器
把程序按逻辑结构分段，每段在划分为固定大小的页，主存空间页划分为大小相等的页，程序对主存的调入、调出仍以页为基本单位 的 虚拟存储器.
每个程序对应一个段表，每个段对应一个页表，段的长度必须是页长的整数倍，段的起点必须是某一页的起点。
虚地址分为段号、段内页号（页号）、页内地址（页内偏移） 三部分。
CPU根据虚地址访存时，首先根据段号得到段表地址：然后从段表中取出该段的页表起始地址，与虚地址段内页号合成，得到页表地址；最后从页表中取出实页号，与页内地址拼接形成主存实地址。

在虚拟存储器中，必须先访问一次主存去查页表，再访问主存才能取得数据，把这些页对应的页表项 存放在高速缓冲器组成 的 快表（TLB）中，把放在主存中页表称为慢表（Page）。
快表只是慢表的一个副本，而且存放了慢表中很少的一部分。
在同时具有虚拟页式存储器（有TLB）和Cache的系统中，访问顺序为TLB-> 页表 -> Cache -> 主存。
CPU发出访存命令（逻辑地址），先查找TLB和Page，将逻辑地址转换为物理地址，再查找对应的Cache块（与驻村查找并行）。
若Cache命中，则说明所需页面已调入主存，Page必然命中，但TLB不一定命中 （因为 Cache 相当于 是主存的一个副本…）（只要你在主存中，页表里就一定有你…）
若Cache不命中，并不能说明所需页面未调入主存，和TLB和Page命中与否没有联系
若Page不命中，说明所需页面未调入主存，当然Cache和主存也不会命中