5.3.Cache替换算法

1.全相联映射中，只有完全满了才需要替换Cache内的某一块，需要替换算法

2.直接映射中，每个主存块是唯一确定Cache内的位置，非空直接替换，无需替换算法

3.组相联映射中，只有分组满了才需要替换分组内的某一块，需要替换算法

5.3.1.随机算法（RAND）

Cache已满，随机选择一块进行替换

5.3.2.先进先出算法（FIFO）

Cache已满，替换最先被调入Cache的块

可能发生抖动

5.3.3.近期最少使用算法（LRU）

为每个Cache设置计数器，用于记录该块多久没被访问，需要替换时，替换计数器中的最大的块

1.若一个计数器的值为3（2 ^ n - 1）时，则不需要进行 + 1操作，仅对其他计数器进行 + 1

2.LRU考虑到了局部性原理

3.若频繁访问的主存块数量 > Cache的块数，仍然可能发生抖动

4.计数器仅需n位

5.3.4.最不经常使用算法（LFU）

为每个Cache设置计数器，用于记录该块被访问过几次，需要替换时，替换计数器中的最小的块

1.新调入Cache的块，计数器被置为0

2.若当前有多个计数器是相同的最小值，则对这几个块采用FIFO或替换行数最小的策略

3.计数器可能需要很多位，且并没有很好的遵循局部性原理

5.4.Cache写策略

1.写命中

①写回法（write-back）：只会对Cache内容进行修改，当该块被替换回主存时候，才回将其写回主存，这样就会导致同一个块的Cache和主存内的内容不一样，因此，需要添加一个脏位用来表示该块在Cache中是否进行修改

这种方法可以减少访存次数（不需要每次都对主存的内容进行修改）

②全写法（write-through）：对Cache内容进行修改的同时，对主存的内容也进行修改，这样就能保证Cache和主存内容一致（无需脏位）

这种方法保持内容的一致性，但是会增加访存次数

采用写缓冲（SRAM实现），写缓冲的作用是能够缓解主存和CPU的速度差异

2.写不命中

①写分配法（write-allocate）：当写不命中时，先将该块从主存调入Cache中，然后搭配写回法（在Cache中进行修改）

②非写分配法（not-write-allocate）：当写不命中时，CPU直接对主存的块进行修改，而不调入Cache中（此时，只有读操作才将主存块调入Cache中），搭配全写法

6.虚拟存储器

6.1.页式存储器

1.Cache和主存的数据交换是以块为单位，在访问某个主存块后，根据局部性原理，可以把该主存块调入Cache的某个位置中（根据Cache和主存不同的映射方式）使得下次能够更快的访问该块

2.进程会被分成若干个大小相等的页，每个页的大小和块相同，并且对每个页编号，实现离散存储

3.Cache和主存的分块是物理上的；进程的分页是逻辑上的，对程序员透明，是操作系统的行为

4.逻辑地址（虚地址）：程序员视角的地址（CPU执行的机器指令中的地址是逻辑地址）；物理地址（实地址）：实际在主存的地址

5.操作系统负责将用户编程时使用的逻辑地址转换为物理地址：

①该程序共4KB = 2 ^ 12 B，即逻辑地址（程序员使用的地址）是12位：操作系统把该程序分成4个大小为1KB的页，即需要首2位表示逻辑页号（4个页），末10位表示页内地址（1KB）

②主存被分为4096个块，即需要12位表示主存块；每个块为1KB，需要10位表示页内地址

③操作系统进行地址转换时，通过逻辑页号找到其对应的主存块（通过查询页表：一种数据结构，记录每个逻辑页号对应的主存块号），然后用该主存块的主存块号替换其逻辑页号，即用主存块号+页内地址，就能得到目的地址

6.页表存在主存中，因此，每次CPU进行地址转换查询页表就需要进行一次访存；页表中的一行被称为页表项，每个页表项中记录着某个逻辑页号和主存块号的映射关系

7.地址变换过程：

①CPU将指令中的逻辑地址拆分为逻辑页号和页内地址两个部分

②通过页表基地址寄存器找到页表，并且查询页表找到①中逻辑页号对应的物理地址：页表基地址寄存器指明页表在主存中的存放地址（通过页表基地址表示），每个页表项的大小相同，得到页表基地址后，就可以找到任一特定的逻辑页表对应的页表项

③用主存块号拼接①中页内地址得到最终地址

④访问物理地址：先访问CACHE，CACHE如果未命中访存

8.引入快表的原因：每次查询页表都需要访问主存，可以用Cache的思想进行改进，即基于局部性原理，将页表中的某些页表项放进更高速的存储器中，以此提升地址转换速度

9.加入快表后的转换过程：先在快表中查找该逻辑页号对应的页表项的副本，快表未命中后再查询主存中的慢表，再将该页表项加入快表中

10.快表和CACHE的区别：快表存储的是页表项的副本，目的是加快逻辑地址到物理地址的转换速度；CACHE存储器的是主存块的副本，目的是加快对物理地址的访问速度

11.快表查询速度大于慢表的原因：快表使用SRAM，慢表使用DRAM；快表是相联存储器，即可以根据内容寻访，而普通存储器是根据地址寻访

6.2.虚拟存储器

1.程序用到的部分调入内存，暂时用不到的部分不需要调入内存，仅存在于外存（类似CACHE之于内存，都是基于局部性原理选择部分数据调入）

2.需要对页表进行改造：增加有效位，作用是表示该页是否已经被调入内存；增加外存块号，将外存分成若干个和页大小相等的块，记录该页在外存中的实际地址，即块号；访问位，用于页面替换算法，作为主存满时选择哪个页面换出外存的根据；脏位，用于记录该块在调入主存期间是否被修改过

3.物理存储器即主存，磁盘存储即外存

4.段式虚拟存储器：将程序根据功能模块（逻辑关系）的不同划分

①段长：每个段大小不一

②段首地址：不再对主存分块（每个主存地址以B为单位），每个段可以储存在主存的任何地方

5.段页式