组成原理02

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和主存也不会命中