替换算法、虚拟存储器、TLB、RAID

1、需要替换算法的原因

1.2、4种常见的替换算法

1.2.1、先进先出法——FIFO（First in First out）

1.2.2、最不经常使用法——LFU（Least Frequently Used ）

1.2.3、近期最少使用法——LRU（Least recently used）

1.3、FIFO替换算法的抖动问题

二、虚拟存储器

由于冯诺依曼的计算机结构中，程序只有调入到计算机的存储中，才能够被cpu访问并且执行，因此在冯诺依曼的计算机结构无法执行比主存空间更大的程序。因此有了虚拟存储器

2.1、虚拟存储器的概述

虚拟存储器是处于主存和辅存这个层次的，主要作用是解决主存容量不足的问题，为程序设计者提供比主存空间大的编程空间，主要分为以下3类：
①、页式虚拟存储器；
②、段式虚拟存储器 ；
③、段页式虚拟存储器。

2.2、虚拟存储器的地址访问

2.3、虚拟存储器的地址访问

2.4、逻辑地址与物理地址的转换

cpu在访问有虚拟存储器的存储系统的时候，用的是虚拟地址，cpu通过MMC将物理地址转换为虚拟地址。页表中的每一行叫做页表项，若干个页表项的集合构成了页表，页表的长度与序列号的位数相关联，为了实现基于页表的逻辑地址和物理地址的转换，首先需要由mmu当中的页表寄存器作为一个基地址来指示页表在主存中的起始地址，由于对虚拟存储器进行了页划分，分为页内偏移地址（VPO）和虚拟页号（VPN），当cpu访问的时候会基于虚拟页号（VPN）和页表寄存器（MMU）的值做一个偏移，就找到了与这个序号相对应的一个页表项在主存当中的一个物理地址，如果有效位为1的话，那么我们就从主存中将这个页表项取出来，也就是将这个页表项对应的物理页号取出来，并与本次访问的虚拟地址当中取出来的页内偏移地址相拼接，这样就得到物理地址，从而实现基于mmu和页表的逻辑地址向物理地址的转换过程。如下：

三、TLB（地址转换后备缓冲器）

3.1、虚地址转换过程中存在的问题

cpu在基于虚拟地址（由本次虚地址当中剥离出来的序列号与在mmu当中的一个页表寄存器的值进行偏移，去找到存放在主存的那个列表当中与虚页号对应的页表项的物理地址）访问mmu时，需要去判断与这个虚地址对应的物理页是否在主存当中，所以要把页表读回来去判断，我们假定与这个虚地址对应的这个虚页对应的物理页在主存当中，那么这一次访问就是命中的，当命中之后就得到了与这个虚地址对应的那个数据在主存的哪个物理地址上，之后再基于物理地址去访问主存，这次从主存当中得到的将是与这个虚地址相对应的那个数据。如下所示

上述过程基于虚地址访问存储数据时，访问了2次主存：第1次访问主存是要拿回页表项并判断页表项是否在主存当中，如果在的话，第2次访问主存才能得到数据。这个过程对于cpu的高速特性是一个巨大的损失。并且在虚实地址转换过程中，当发生缺页的时候，它对于存储系统的性能会带来更大的损失，如下：

基于以上2种情况，需要引入TLB。

3.2、TLB的工作原理

3.3、基于TLB的虚实地址转换

如上图所示，采用了TLB之后，我们还会对这个地址进行二次划分，主要是针对VPN划分出TLB Tag和TLB Index，页内偏移地址（VPO）不变，有了TLB Index就可以去找特定位置（该位置存放着在TLB当中经过变换以后的一个页表，该页表跟主存当中的页表有差别，相当于主存当中页表的子集，该子集中的Tag就是判断与虚页对应的物理页是否存在）。由于TLB存放的是子集的原因，因此，不可能基于这个地方剥离出来的index或者原来的vpn去找到所有的列表项，如果要找到所有的列表项，那么就需要做列表的变换（根据Tag去判断与虚页对应的物理页是否存在），如果存在且有效位唯一的话，我们就把TLB当中与这个index字段指向的特定行的物理地址读出来，该物理地址只是一个物理页号，如果要构成一个完整的物理地址，还需要将该物理页号与本次虚地址中剥离出来的页内偏移地址去做拼接，最终才得到一个物理地址。整个过程抽象成下图：