概要
CPU将主存地址 转换成 Cache地址时，需要经过 地址映射变换机构。不同层级的Cache 对 地址映射的算法方案 有不同的要求。
主存Cache地址映射变换机构
该机构主要是 将主存地址 按一定算法映射到 Cache地址
直接映射
映射算法
假设主存的块数为 m，Cache的块数为 c。那么通常会按 c个块为一组划分主存，每组的块编号依次按 0,1,2,...,c进行编号。假设m为16，c为2，其示意图如下所示
每组的编号（每组都从0开始计算），组0的块0、组1的块0（整体来看即块2）都对应着Cache的块0。也就是说，每组的第一个块 都必须存放在 Cache的第一个块里，同理 每组的第二块 都必须存放在 Cache第二个块里。示意图如下所示
用数学来表示映射算法即 z = i % c，i表示块编号，c表示cache的总块数（每组的块数）
比如：
- 3 % 2 = 1
- 2 % 2 = 0
映射流程
CPU发送来一个主存地址，该地址会分为三部分，一部分是主存组号，一部分是组内编号，一部分是块内地址，主存组号和组内编号共同组成块号。 如下图所示
- 当Cache收到CPU发送的主存地址时，提取组内编号
- 查找Cache中 组内编号指示 的块
- 将块中的标识提取出来（此处的标识保存着主存的组号）
- 比较Cache块提供的标识 和 主存提供的组号
- 如果组号一致，则进入下个判断；否则不命中
- 判断该块的有效位是否为“1”，如果为“1”，则命中；反之不命中
- 如果判断为不命中，Cache就从主存里取出新的字块，并替换旧字块，最后将该块的有效位置为“1”
总结
直接映射的缺点就是不够灵活，因为每个主存块都对应着唯一的Cache块，如果CPU频繁访问 不同组的同编号块，那么Cache就经常会发生替换，影响速度，空间利用率不高
全相联映射
映射算法
主存内每个字块都可以被存储到Cache的任意字块内。
映射流程
当CPU发出如下图所示的地址时，
- CPU通过主存块编号遍历Cache，查找Cache的标记是否和该主存编号相同
- 如果找到则命中，未找到则未命中
总结
全相联映射更加灵活，主存块可以保存到Cache的任意块中。Cache的利用率就会高，但是由于遍历，速度往往较低。
组相联映射
映射算法
主存划分为多个组，缓存也划分为多个组，每个组里的块编号都对应着缓存里的组编号。简而言之，原来的直接映射只能一个缓存块对应多个主存块，为了提高空间利用率，允许一个多个同组的缓存块对应多个主存块。示意图如下所示
每个组的第一个块都对应着缓存的第一个组。同理，每个组的第二块都对应着缓存的第二块。
映射流程
每个组的第一块 都能放到缓存的第一个组内的任意位置。一方面，主存的块可以放在对应组内的任意一个位置，体现出了全相联的思想；另一方面，主存的每个块都对应着唯一一个组，这是直接映射的思想。
该方案是直接映射和全相联映射的折中方案。
替换机构
替换就是指 Cache满了之后，如果要存放新的主存块，就需要将某个Cache块取出，并替换新的主存块进入
主存块就像是放在书架上的书，缓存块就像是放在床头的书，如果床头的书满了，就需要找个方案取出一本书，然后将想看的书加进去
替换机构就是做了 如何取书 这件事
目前有两种方案：
- 先进先出FIFO
- 近期最少使用(Least Recently Used)
LRU算法比较好的利用访存局部性原理，替换出近期用的最少的字块。通常是只记录每个快最近一次使用的时间。 - 随机法
取一个随机数，没有根据访存的局部性原理。
注意，这里讲到的访存局部性原理是指 只访问某个块的内容，而不是全部的内容，即局部性