① linux kernel 内存管理-页表、TLB
页表用来把虚拟页映射到物理页，并且存放页的保护位(即访问权限)。
在Linux4.11版本以前，Linux内核把页表分为4级：
页全局目录表(PGD)、页上层目录(PUD)、页中间目录(PMD)、直接页表(PT) 。
4.11版本把页表扩展到5级，在页全局目录和页上层目录之间增加了 页四级目录(P4D) 。
各处处理器架构可以选择使用5级，4级，3级或者2级页表，同一种处理器在页长度不同的情况可能选择不同的页表级数。可以使用配置宏CONFIG_PGTABLE_LEVELS配置页表的级数，一般使用默认值。
如果选择4级页表，那么使用PGD，PUD，PMD，PT；如果使用3级页表，那么使用PGD，PMD，PT；如果选择2级页表，那么使用PGD和PT。 如果不使用页中间目录 ，那么内核模拟页中间目录，调用函数pmd_offset 根据页上层目录表项和虚拟地址获取页中间目录表项时 ， 直接把页上层目录表项指针强制转换成页中间目录表项 。
每个进程有独立的页表，进程的mm_struct实例的成员pgd指向页全局目录,前面四级页表的表项存放下一级页表的起始地址，直接页表的页表项存放页帧号(PFN) 。
内核也有一个页表， 0号内核线程的进程描述符init_task的成员active_mm指向内存描述符init_mm，内存描述符init_mm的成员pgd指向内核的页全局目录swapper_pg_dir 。
ARM64处理器把页表称为转换表，最多4级。ARM64处理器支持三种页长度：4KB，16KB，64KB。页长度和虚拟地址的宽度决定了转换表的级数，在虚拟地址的宽度为48位的条件下，页长度和转换表级数的关系如下所示：
ARM64处理器把表项称为描述符，使用64位的长描述符格式。描述符的0bit指示描述符是不是有效的：0表示无效，1表示有效。第1位指定描述符类型。
在块描述符和页描述符中，内存属性被拆分为一个高属性和一个低属性块。
处理器的MMU负责把虚拟地址转换成物理地址，为了改进虚拟地址到物理地址的转换速度，避免每次转换都需要查询内存中的页表，处理器厂商在管理单元里加了称为TLB的高速缓存，TLB直译为转换后备缓冲区，意译为页表缓存。
页表缓存用来缓存最近使用过的页表项， 有些处理器使用两级页表缓存 ： 第一级TLB分为指令TLB和数据TLB，好处是取指令和取数据可以并行；第二级TLB是统一TLB，即指令和数据共用的TLB 。
不同处理器架构的TLB表项的格式不同。ARM64处理器的每条TLB表项不仅包含虚拟地址和物理地址，也包含属性：内存类型、缓存策略、访问权限、地址空间标识符(ASID)和虚拟机标识符(VMID)。 地址空间标识符区分不同进程的页表项 ， 虚拟机标识符区分不同虚拟机的页表项 。
如果内核修改了可能缓存在TLB里面的页表项，那么内核必须负责使旧的TLB表项失效，内核定义了每种处理器架构必须实现的函数。
当TLB没有命中的时候，ARM64处理器的MMU自动遍历内存中的页表，把页表项复制到TLB，不需要软件把页表项写到TLB，所以ARM64架构没有提供写TLB的指令。
为了减少在进程切换时清空页表缓存的需要，ARM64处理器的页表缓存使用非全局位区分内核和进程的页表项(nG位为0表示内核的页表项)， 使用地址空间标识符(ASID)区分不同进程的页表项 。
ARM64处理器的ASID长度是由具体实现定义的，可以选择8位或者16位。寄存器TTBR0_EL1或者TTBR1_EL1都可以用来存放当前进程的ASID，通常使用寄存器TCR_EL1的A1位决定使用哪个寄存器存放当前进程的ASID，通常使用寄存器 TTBR0_EL1 。寄存器TTBR0_EL1的位[63:48]或者[63:56]存放当前进程的ASID，位[47:1]存放当前进程的页全局目录的物理地址。
在SMP系统中，ARM64架构要求ASID在处理器的所有核是唯一的。假设ASID为8位，ASID只有256个值，其中0是保留值，可分配的ASID范围1~255，进程的数量可能超过255，两个进程的ASID可能相同，内核引入ASID版本号解决这个问题。
(1)每个进程有一个64位的软件ASID， 低8位存放硬件ASID，高56位存放ASID版本号 。
(2) 64位全局变量asid_generation的高56位保存全局ASID版本号 。
(3) 当进程被调度时，比较进程的ASID版本号和全局版本号 。如果版本号相同，那么直接使用上次分配的ASID，否则需要给进程重新分配硬件ASID。
存在空闲ASID，那么选择一个分配给进程。不存在空闲ASID时，把全局ASID版本号加1，重新从1开始分配硬件ASID，即硬件ASID从255回绕到1。因为刚分配的硬件ASID可能和某个进程的ASID相同，只是ASID版本号不同，页表缓存可能包含了这个进程的页表项，所以必须把所有处理器的页表缓存清空。
引入ASID版本号的好处是：避免每次进程切换都需要清空页表缓存，只需要在硬件ASID回环时把处理器的页表缓存清空 。
虚拟机里面运行的客户操作系统的虚拟地址转物理地址分两个阶段：
(1) 把虚拟地址转换成中间物理地址，由客户操作系统的内核控制 ，和非虚拟化的转换过程相同。
(2) 把中间物理地址转换成物理地址，由虚拟机监控器控制 ，虚拟机监控器为每个虚拟机维护一个转换表，分配一个虚拟机标识符，寄存器 VTTBR_EL2 存放当前虚拟机的阶段2转换表的物理地址。
每个虚拟机有独立的ASID空间 ，页表缓存使用 虚拟机标识符 区分不同虚拟机的转换表项，避免每次虚拟机切换都要清空页表缓存，在虚拟机标识符回绕时把处理器的页表缓存清空。
② 在请求分页式存储管理中,为什么既有页表,又有快表
实际系统中的做法是采用内存页表和快表相结合的解决方案。系统总是先通过页号与快表中的所有表项进行比较。如果发现匹配的页，则将块号直接从快表中取出，而不必通过页表。
也是该块号与页内位移拼接，形成所需要的绝对地址。如果快表中没有匹配的页号时，系统访问页表进行掉进块号。提高读取数据的速度。
(2)页表高速缓存扩展阅读：
快表就是存放在高速缓冲存储器的部分页表。作为页表的Cache，它的作用与页表相似，但是提高了访问速率。由于采用页表做地址转换，读写内存数据时CPU要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。
③ Linux存储管理方式
这种方式中，将用户程序的地址空间，注意，是 用户程序的地址空间 分为若干个固定大小的区域，成为“页”或“页面”。我们可以知道，这也页其实是不存在的，只是一种划分内存空间的方法。也就是说，这种方式将用户的程序 “肢解” 了，分成很多个小的部分，每个部分称为一个“页”。
将逻辑地址的前n位作为页号，后面32-n位作为页内偏移量。
由于进程的最后一页经常装不满一个块，从而形成了不可利用的碎片，称之为 “页内碎片” 。
作用：实现页号到物理号的地址映射。
页表是记录逻辑空间（虚拟内存）中每一页在内存中对应的物理块号。但并非每一页逻辑空间都会实际对应着一个物理块，只有实际驻留在物理内存空间中的页才会对应着物理块。
系统会为每一个进程建立一张页表，页表是需要一直驻留在物理内存中的（多级页表除外），另外页表的起址和长度存放在 PCB（Process Control Block）进程控制结构体中。
可以在页表的表项中设置相关的权限控制字段，例如设置存取控制字段，用于保护该存储块的读写；若存取控制字段为2位，则可以设置读/写、只读和只执行等存取方式。
物理块是实实在在存在于内存中的：
由于执行频率高，要求效率比较高，需要使用硬件实现。
在系统中设置一个 页表寄存器(PTR) ,其中存放页表在内存的起始地址和页表的长度。平时进程未执行的时候，页表的起始地址和页表长度放在本进程的PCB中。当调度程序调度到某个进程的时候，才将这两个数据装入 页表寄存器 。
变换过程：
快表的变换机构
为了提高地址变换速度，可在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器，又称为"联想寄存器"或者“快表”。俗称TLB。
快表与页表的功能类似，其实就是将一部分页表存到 CPU 内部的高速缓冲存储器 Cache。CPU 寻址时先到快表查询相应的页表项形成物理地址，如果查询不到，则到内存中查询，并将对应页表项调入到快表中。但，如果快表的存储空间已满，则需要通过算法找到一个暂时不再需要的页表项，将它换出内存。
由于成本的关系，快表不可能做得很大，通常只存放 16~512 个页表项，这对中、小型作业来说，已有可能把全部页表项放在快表中；但对于大型作业而言，则只能将其一部分页表项放入其中。由于对程序和数据的访问往往带有局限性，因此，据统计，从快表中能找到所需页表项的概率可达 90% 以上。这样，由于增加了地址变换机构而造成的速度损失可减少到 10% 以下，达到了可接受的程度。
我们可以采用这样两个方法来解决这一问题：
① 对于页表所需的内存空间，可采用离散分配方式，以解决难以找到一块连续的大内存空间的问题；
② 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
二级页表的页表项：
过程：
在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对于内页表则只需调入一页或几页。为了表征某页的页表是否已经调入内存，还应在外层页表项中增设一个状态位 S，其值若为 0，表示该页表分页不在内存中，否则说明其分页已调入内存。进程运行时，地址变换机构根据逻辑地址中的 P1去查找外层页表；若所找到的页表项中的状态位为 0，则产生一个中断信号，请求 OS 将该页表分页调入内存。
多级页表和二级页表类似。多级页表和二级页表是为了节省物理内存空间。使得页表可以在内存中离散存储。（单级页表为了随机访问必须连续存储，如果虚拟内存空间很大，就需要很多页表项，就需要很大的连续内存空间，但是多级页表不需要。）
为什么引入分段存储管理？
引入效果：
它将用户程序的地址空间分为若干个大小不同的的段，每个段可以定义一组完整的信息。
段号表示段名，每个段都从0开始编址，并且采用一段连续的地址空间。
在该地址结构中，允许一个作业最长有64K个段，每个段的最大长度为64KB。
在分段式存储管理系统中，为每一个分段分配一个连续的分区。进程的各个段，可以离散地装入内存中不同的分区中。
作用：实现从逻辑地址到物理内存区的映射。
为了保证程序能够正常运行，就必须能够从物理内存中找出每个逻辑段所对应的位置。为此在系统中会为每一个进程建立一张 段表 。每个段在表中有一个表项，其中记录了该段在内存中的起始地址和段的长度。一般将段表保存在内存中。
在配置了段表之后，执行的过程可以通过查找段表，找到每一个段所对应的内存区。
为了实现进程从逻辑地址到物理地址的变换功能，在系统设置了段表寄存器，用于存放段表的起始地址和段表长度TL。
在进行地址变换时，系统将逻辑地址中的段号与段表长度TL 进行比较。若 S > TL，表示段号太大，是访问越界，于是产生越界中断信号。若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。然后，再检查段内地址 d 是否超过该段的段长 SL。若超过，即 d>SL，同样发出越界中断信号。若未越界，则将该段的基址 d 与段内地址相加，即可得到要访问的内存。
分页和分段系统相似之处：两者都采用离散分配方式，且都是通过地址映射机构实现地址变换。
但在概念上两者完全不同，主要表现在下述三个方面：
分页系统以页面作为内存分配的基本单位，能有效地提高内存利用率，而分段系统以段作为内存分配的基本单位，它能够更好地满足用户多方面的需要。
段页式地址结构由段号、段内页号及页内地址三部分所组成
段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。如下图展示了一个作业地址空间的结构。该作业有三个段：主程序段、子程序段和数据段；页面大小为 4 KB：
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。下图展示出了利用段表和页表进行从用户地址空间到物理(内存)空间的映射。
在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长 TL。进行地址变换时，首先利用段号 S，将它与段长 TL 进行比较。若 S < TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号 P 来获得对应页的页表项位置，从中读出该贝所在的物理块号 b，再利用块号 b 和页内地址来构成物理地址。
在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问是访问内存中的段表，从中取得页表始址；第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中取出指令或数据。
显然，这使访问内存的次数增加了近两倍。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得到相应页的物理块号，用来与页内地址一起形成物理地址：若未找到匹配表项，则仍需第三次访问内存。
参考链接：
④ CPU Cache
title: CPU Cache
date: 2019-11-17 20:20:30
keywords: cache "CPU cache" "三级缓存" 缓存映射 cache原理 多级cache TLB
引入 Cache 的理论基础是程序局部性原理，包括时间局部性和空间局部性。时间局部性原理即最近被CPU访问的数据，短期内CPU 还要访问（时间）；空间局部性即被CPU访问的数据附近的数据，CPU短期内还要访问（空间）。因此如果将刚刚访问过的数据缓存在一个速度比主存快得多的存储中，那下次访问时，可以直接从这个存储中取，其速度可以得到数量级的提高。
CPU缓存是（Cache Memory）位于CPU与内存之间的临时存储器，它的容量比内存小但交换速度快。在缓存中的数据是内存中的一小部分，但这一小部分是短时间内CPU即将访问的，当CPU调用大量数据时，就可避开内存直接从缓存中调用，从而加快读取速度。
在CPU中加入缓存是一种高效的解决方案，是对于存储器件成本更低，速度更快这两个互相矛盾的目标的一个最优解决方案，这样整个内存储器（缓存+内存）就变成了既有缓存的高速度，又有内存的大容量的存储系统了。缓存对CPU的性能影响很大，主要是因为CPU的数据交换顺序和CPU与缓存间的带宽引起的。
下图是一个典型的存储器层次结构，我们可以看到一共使用了三级缓存
各级存储访问延迟的对比
介于CPU和主存储器间的高速小容量存储器，由静态存储芯片SRAM组成，容量较小但比主存DRAM技术更加昂贵而快速， 接近于CPU的速度。CPU往往需要重复读取同样的数据块， Cache的引入与缓存容量的增大，可以大幅提升CPU内部读取数据的命中率，从而提高系统性能。通常由高速存储器、联想存储器、地址转换部件、替换部件等组成。如图所示。
早期采用外部（Off-chip）Cache，不做在CPU内而是独立设置一个Cache。现在采用片内（On-chip）Cache，将Cache和CPU作在一个芯片上，且采用多级Cache，同时使用L1 Cache和L2 Cache，甚至有L3 Cache。
上图显示了最简单的缓存配置。它对应着最早期使用CPU cache的系统的架构。CPU内核不再直接连接到主内存。所有的数据加载和存储都必须经过缓存。CPU核心与缓存之间的连接是一种特殊的快速连接。在一个简化的表示中，主存和高速缓存连接到系统总线，该系统总线也可用于与系统的其他组件进行通信。我们引入了系统总线（现代叫做“FSB”）。
引入缓存后不久，系统变得更加复杂。高速缓存和主存之间的速度差异再次增大，使得另一个级别的高速缓存不得不被添加进来，它比第一级高速缓存更大且更慢。出于经济原因，仅增加第一级缓存的大小不是一种选择。今天，甚至有机器在生产环境中使用了三级缓存。带有这种处理器的系统如图下所示。随着单个CPU的内核数量的增加，未来的缓存级别数量可能会增加。现在已经出现了拥有四级cache的处理器了。
上图展示了三级缓存的结构。L1d是一级数据cache，L1i是一级指令cache。请注意，这只是一个示意图; 现实中的数据流从core到主存的过程中不需要经过任何更高级别的cache。CPU设计人员有很大的自由来设计cache的接口。对于程序员来说，这些设计选择是不可见的。
另外，我们有拥有多个core的处理器，每个core可以有多个“线程”。核心和线程之间的区别在于，独立的核心具有所有硬件资源的独立的副本，早期的多核处理器，甚至具有单独的第二级缓存而没有第三级缓存。核心可以完全独立运行，除非它们在同一时间使用相同的资源，例如与外部的连接。另一方面，线程们共享几乎所有的处理器资源。英特尔的线程实现只为线程提供单独的寄存器，甚至是有限的，还有一些寄存器是共享的。
一个现代CPU的完整概貌如图所示。
由于cache中对应的都是主存地址，即物理地址，在cqu查看具体数据是否在cache中时，如果CPU传送过来的地址时一个虚拟地址，需要将其转换成实际物理地址再到cache中去寻找。Cache的实现需要TLB的帮助。可以说TLB命中是Cache命中的基本条件。TLB不命中，会更新TLB项，这个代价非常大，Cache命中的好处基本都没有了。在TLB命中的情况下，物理地址才能够被选出，Cache的命中与否才能够达成。
TLB是一个内存管理单元用于改进虚拟地址到物理地址转换速度的缓存。TLB是位于内存中的页表的cache，如果没有TLB，则每次取数据都需要两次访问内存,即查页表获得物理地址和取数据。
当cpu对数据进行读请求时,CPU根据虚拟地址(前20位)到TLB中查找.TLB中保存着虚拟地址(前20位)和页框号的对映关系,如果匹配到虚拟地址就可以迅速找到页框号(页框号可以理解为页表项),通过页框号与虚拟地址后12位的偏移组合得到最终的物理地址.
如果没在TLB中匹配到虚拟地址,就出现TLB丢失,需要到页表中查询页表项,如果不在页表中,说明要读取的内容不在内存,需要到磁盘读取.
TLB是MMU中的一块高速缓存,也是一种Cache.在分页机制中,TLB中的数据和页表的数据关联,不是由处理器维护,而是由OS来维护,TLB的刷新是通过装入处理器中的CR3寄存器来完成.如果MMU发现在TLB中没有命中,它在常规的页表查找后,用找到的页表项替换TLB中的一个条目.
当进程进行上下文切换时重新设置cr3寄存器,并且刷新tlb.
有两种情况可以避免刷tlb.
第一种情况是使用相同页表的进程切换.
第二种情况是普通进程切换到内核线程.
lazy-tlb(懒惰模式)的技术是为了避免进程切换导致tlb被刷新.
当普通进程切换到内核线程时,系统进入lazy-tlb模式,切到普通进程时退出该模式.
cache是为了解决处理器与慢速DRAM(慢速DRAM即内存)设备之间巨大的速度差异而出现的。cache属于硬件系统,linux不能管理cache.但会提供flush整个cache的接口.
cache分为一级cache,二级cache,三级cache等等.一级cache与cpu处于同一个指令周期.
CPU从来不从DRAM直接读/写字节或字,从CPU到DRAM的每次读或写的第一步都要经过L1 cache,每次以整数行读或写到DRAM中.Cache Line是cache与DRAM同步的最小单位.典型的虚拟内存页面大小为4KB,而典型的Cache line通常的大小为32或64字节.
CPU 读/写内存都要通过Cache,如果数据不在Cache中,需要把数据以Cache Line为单位去填充到Cache,即使是读/写一个字节.CPU 不存在直接读/写内存的情况,每次读/写内存都要经过Cache.
缓存里有的数据，主存中一定存在。
一级缓存中还分数据缓存（data cache，d-cache）和指令缓存（instruction cache，i-cache）。二者分别用来存放数据和执行这些数据的指令，而且两者可以同时被cpu访问，所以一级cache间数据时独立的。
一级没有的数据二级可能有也可能没有。因为一级缓存miss会接着访问二级缓存。
一级有二级一定有，三级也一定有。因为一级的数据从二级中读上来的。在一级缺失二级命中时发生。
二级没有的数据三级可能有也可能没有。因为二级确实会接着访问三级缓存。找不到会继续访问主存。
二级有的数据三级一定有。在二级缺失三级命中时，数据会从三级缓存提到二级缓存。
三级没有的数据，主存可能有也可能没有。三级缓存缺失，会访问主存，主存也缺失就要从外存访问数据了。
三级缓存有的数据主存一定有。因为在三级缺失主存命中时，数据会从主存提到三级缓存中来。
一级缓存就是指CPU第一层级的高速缓存，主要是为了缓存指令和缓存数据，一级缓存的容量对CPU性能影响非常大，但是因为成本太高，所以一般容量特别小，也就256KB左右。
二级缓存是CPU第二层级的高速缓存，对于CPU来说，二级缓存容量越大越好，它是直接影响CPU性能的，CPU每个核心都会有自己的缓存，一个CPU的二级缓存容量是所有核心二级缓存容量的总和。
三级缓存就是CPU第三层级的高速缓存，主要是为了降低与内存进行数据传输时的延迟问题，三级缓存与一二级不同，三级缓存只有一个，它是所有核心共享，所以在CPU参数中可以看到，三级缓存相对于其他两级缓存来说都很大。
由于缓存的设置与OS无关且透明，所以对于不同的体系架构下不同的处理器对待缓存区域的处理和方式都不同，不同的处理器也有不同的缓存设置值。从主流的处理器cache大小来看，一般一个cache line的大小都是固定的64B左右，这是经过经验得到的比较合理的大小，一般一级cache大小在数十KB左右，二级cache大小在数十到数百KB左右，而L3 cache大小在数MB左右。
由于三级cache一般来说是运用于拥有多核的处理器，对于单核处理器来说二级cache就能够足够保持够高的cache命中率。所以一般的三级cache一般只针对于多核处理器。L1和L2级cache是处理器核所单独的内容。L1又可以看成是L2的cache。L2可以看成是L3级cache的cache。所以我们分两个部分讨论数据放置与数据淘汰策略。
各级cache间的数据放置策略主要有三种。直接相连映射，全相联映射和组相联映射。将一个主存块存储到唯一的一个Cache行。对应的大小都是一个cache line的大小，一般来说是64B。
多对一的映射关系，但一个主存块只能拷贝到cache的一个特定行位置上去。cache的行号i和主存的块号j有如下函数关系：i=j mod m（m为cache中的总行数）。
可以将一个主存块存储到任意一个Cache行。
主存的一个块直接拷贝到cache中的任意一行上
可以将一个主存块存储到唯一的一个Cache组中任意一个行。
将cache分成u组，每组v行，主存块存放到哪个组是固定的，至于存到该组哪一行是灵活的，即有如下函数关系：cache总行数m＝u×v 组号q＝j mod u
组间采用直接映射，组内为全相联。硬件较简单，速度较快，命中率较高。是现代处理器中一般所常用的映射方式。
Cache工作原理要求它尽量保存最新数据，当从主存向Cache传送一个新块，而Cache中可用位置已被占满时，就会产生Cache替换的问题。
常用的替换算法有下面三种。
LFU（Least Frequently Used，最不经常使用）算法将一段时间内被访问次数最少的那个块替换出去。每块设置一个计数器，从0开始计数，每访问一次，被访块的计数器就增1。当需要替换时，将计数值最小的块换出，同时将所有块的计数器都清零。
这种算法将计数周期限定在对这些特定块两次替换之间的间隔时间内，不能严格反映近期访问情况，新调入的块很容易被替换出去。
LRU（Least Recently Used，近期最少使用）算法是把CPU近期最少使用的块替换出去。这种替换方法需要随时记录Cache中各块的使用情况，以便确定哪个块是近期最少使用的块。每块也设置一个计数器，Cache每命中一次，命中块计数器清零，其他各块计数器增1。当需要替换时，将计数值最大的块换出。
LRU算法相对合理，但实现起来比较复杂，系统开销较大。这种算法保护了刚调入Cache的新数据块，具有较高的命中率。LRU算法不能肯定调出去的块近期不会再被使用，所以这种替换算法不能算作最合理、最优秀的算法。但是研究表明，采用这种算法可使Cache的命中率达到90%左右。
最简单的替换算法是随机替换。随机替换算法完全不管Cache的情况，简单地根据一个随机数选择一块替换出去。随机替换算法在硬件上容易实现，且速度也比前两种算法快。缺点则是降低了命中率和Cache工作效率。
处理器微架构访问Cache的方法与访问主存储器有类似之处。主存储器使用地址编码方式，微架构可以地址寻址方式访问这些存储器。Cache也使用了类似的地址编码方式，微架构也是使用这些地址操纵着各级Cache，可以将数据写入Cache，也可以从Cache中读出内容。只是这一切微架构针对Cache的操作并不是简单的地址访问操作。为简化起见，我们忽略各类Virtual Cache，讨论最基础的Cache访问操作，并借此讨论CPU如何使用TLB完成虚实地址转换，最终完成对Cache的读写操作。
Cache的存在使得CPU Core的存储器读写操作略微显得复杂。CPU Core在进行存储器方式时，首先使用EPN(Effective Page Number)进行虚实地址转换，并同时使用CLN(Cache Line Number)查找合适的Cache Block。这两个步骤可以同时进行。在使用Virtual Cache时，还可以使用虚拟地址对Cache进行寻址。为简化起见，我们并不考虑Virtual Cache的实现细节。
EPN经过转换后得到VPN，之后在TLB中查找并得到最终的RPN(Real Page Number)。如果期间发生了TLB Miss，将带来一系列的严重的系统惩罚，我们只讨论TLB Hit的情况，此时将很快获得合适的RPN，并依此得到PA(Physical Address)。
在多数处理器微架构中，Cache由多行多列组成，使用CLN进行索引最终可以得到一个完整的Cache Block。但是在这个Cache Block中的数据并不一定是CPU Core所需要的。因此有必要进行一些检查，将Cache Block中存放的Address与通过虚实地址转换得到的PA进行地址比较(Compare Address)。如果结果相同而且状态位匹配，则表明Cache Hit。此时微架构再经过Byte Select and Align部件最终获得所需要的数据。如果发生Cache Miss，CPU需要使用PA进一步索引主存储器获得最终的数据。
由上文的分析，我们可以发现，一个Cache Block由预先存放的地址信息，状态位和数据单元组成。一个Cache由多个这样的Cache Block组成，在不同的微架构中，可以使用不同的Cache Block组成结构。我们首先分析单个Cache Block的组成结构。单个Cache Block由Tag字段，状态位和数据单元组成，如图所示。
其中Data字段存放该Cache Block中的数据，在多数处理器微架构中，其大小为32或者64字节。Status字段存放当前Cache Block的状态，在多数处理器系统中，这个状态字段包含MESI，MOESI或者MESIF这些状态信息，在有些微架构的Cache Block中，还存在一个L位，表示当前Cache Block是否可以锁定。许多将Cache模拟成SRAM的微架构就是利用了这个L位。有关MOESIFL这些状态位的说明将在下文中详细描述。在多核处理器和复杂的Cache Hierarchy环境下，状态信息远不止MOESIF。
RAT(Real Address Tag)记录在该Cache Block中存放的Data字段与那个地址相关，在RAT中存放的是部分物理地址信息，虽然在一个CPU中物理地址可能有40，46或者48位，但是在Cache中并不需要存放全部地址信息。因为从Cache的角度上看，CPU使用的地址被分解成为了若干段，如图所示。
这个地址也可以理解为CPU访问Cache使用的地址，由多个数据段组成。首先需要说明的是Cache Line Index字段。这一字段与Cache Line Number类似，CPU使用该字段从Cache中选择一个或者一组Entry。
Bank和Byte字段之和确定了单个Cache的Data字段长度，通常也将这个长度称为Cache 行长度，上图所示的微架构中的Cache Block长度为64字节。目前多数支持DDR3 SDRAM的微架构使用的Cache Block长度都是64字节。部分原因是由于DDR3 SDRAM的一次Burst Line为8，一次基本Burst操作访问的数据大小为64字节。
在处理器微架构中，将地址为Bank和Byte两个字段出于提高Cache Block访问效率的考虑。Multi-Bank Mechanism是一种常用的提高访问效率的方法，采用这种机制后，CPU访问Cache时，只要不是对同一个Bank进行访问，即可并发执行。Byte字段决定了Cache的端口位宽，在现代微架构中，访问Cache的总线位宽为64位或者为128位。
剩余的字段即为Real Address Tag，这个字段与单个Cache中的Real Address Tag的字段长度相同。CPU使用地址中的Real Address Tag字段与Cache Block的对应字段和一些状态位进行联合比较，判断其访问数据是否在Cache中命中
如果cache miss,就去下一级cache或者主存中去查找数据，并将查找到的数据采用上面的数据淘汰策略将数据替换到cache中。
由于在发生cache miss时会产生数据替换，在运行过程中缓存的数据也可能会被修改。所以需要一个策略来保持数据在缓存和主存间的一致性。
Cache写机制分为write through和write back两种。
⑤ 基本分页存储管理
假设是按字节编址
考虑支持多道程序的两种连续分配方式
原因：连续分配要求进程占有的必须是一块连续的内存区域
能否讲一个进程分散地装入到许多不相邻的分区，便可充分利用内存
基本分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分
页框/页帧：内存空间分成的一个个大小相等的分区（比如4KB）
页框号：页框的编号，从0开始，从低地址开始
页/页面：用户进程的地址空间分为和页框大小相等的一个个区域
页号：页/页面的编号，从0开始
进程的最后一个页面可能没有一个页框那么大，页框不能太大，否则可能产生过大的内部碎片
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中，也就是说，进程的页面与内存的页框有一一对应的关系
每个页面不必连续存放，也不必按照先后顺序，可以放到不相邻的各个页框中
进程在内存中连续存放时，通过动态重定位实现逻辑地址到物理地址的转换。在装入模块之后，内存中指令使用的依然是逻辑地址，直到指令执行的时候才会进行地址转换。系统会设置一个重定位寄存器，用来存放装入模块存放的起始位置，重定位寄存器中的值加上逻辑地址就是该逻辑地址实际对应的物理地址
如果采用分页技术
页框大小为4KB，地址空间为4GB的系统
页号为前20位，页内偏移量为后12位
页表：为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表
一个进程对应一张页表
进程的每一页对应一个页表项
每个页表项由页号和页框号组成
页表记录进程页面和实际存放的页框之间的对应关系
每个页表项的长度是相同的，页号是隐含的
各页表项会按顺序连续存放在内存中，如果该页表在内存中的起始地址是X，4GB/4KB系统的页框有
用于实现逻辑地址到物理地址转换的一组硬件机构
通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M（M个页表项）
进程未执行时，页表的起始地址和页表长度放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把他们放到页表寄存器中
基本分页存储管理中地址是一维的，即只要给出一个逻辑地址，系统就可以自动计算出页号、偏移量，不需要显式告诉系统偏移量是多少
理论上，页表项长度为3即可表示内存块号的范围，但是为了方便页表查询，会让页面恰好能装得下整数个页表项，令每个页表项占4字节
4KB页面，可以放4096/3 =1365个页表项，有4096%3 =1B的碎片，访问1365及之后的页表项时，还要考虑前面的页框中的碎片，才能得到页表项的物理地址，比较麻烦
进程页表通常存放在连续的页框中，这样就能用统一的计算方式得到想要得到的页表项存储的位置
地址变换过程中有两次访存操作：查询页表、访问目标内存单元
局部性原理
如果这个程序将程序对应的指令存放在10号内存块，将程序中定义的变量存放在23号内存块，当这个程序执行时，会很频繁地反问10、23号内存块
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能被再次执行；如果某个数据被访问过，不久之后该数据很有可能再次被访问（因为程序存在大量循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（因为很多数据在内存中连续存放）
基本地址变换机构中，每次要访问一个逻辑地址，都要查询页表，由于局部性原理，可能连续多次查询同一个页表项
快表：又称联想寄存器（TLB），是一种访问速度比内存块很多的高速缓存，用来存放当前访问的若干页表项，以加速地址变换的过程。内存中的页表常称为慢表
引入快表后地址的变换过程
一般来说，快表的命中率可以达到90%以上
单级页表存在的问题
对问题1
可将页表进行分组，使每个内存块刚好可以放入一个分组。为离散分配的页表再建立一张页表，称为页目录表，或外层页表
各级页表的大小不能超过一个页面
针对两级页表
对问题2
可以在需要访问页面时，才把页面调入内存（虚拟存储技术），可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存
若想访问的页面不在内存中，会产生缺页中断（内中断），然后将目标页面从外存调入内存
之后的文章会有展开
两级页表访存次数分析：如果没有TLB，第一次访存是访问内存中的页目录表，第二次访存是访问内存中的二级页表，第三次访存是访问目标内存单元
⑥ 为什么部分页表放入内存,另一部分放入高速缓存
页表只可能存在于TLB和memory中,不可能存在于cache中
⑦ 快表TLB和高速缓冲存储器cache有什么区别
1、快表TLB： 用于虚拟存储技术，是为了加快辅存向主存的地址映射速度（主存—辅存系统）
2、高速缓存器cache：用于解决CPU与主存速度不匹配问题。（CPU—主存系统）
2.1、cache补充：因为CPU速度远高于主存，主存跟不上，导致CPU的大量时间在等待主存，效率低下。因为cache速度介于CPU与主存之间，价格也介于两者之间，所以人们在CPU与主存之间添加“高速缓冲器cache”来缓解速度不匹配问题。
总的来说，两者属于两个不同的系统层次，功能也不同。
⑧ 什么是快表
有两种意思。一是存储器的一种，二是一个软件设计平台。
1、存储器的一种：
快表是一种特殊的高速缓冲存储器，内容是页表中的一部分或全部内容。
在操作系统中引入快表是为了加快地址映射速度。
2、软件设计平台：
快表软件是第三代Excel类软件设计平台，国内第一家纯WEB、面向各行业各层次人员的云端Excel系统设计与运行平台。
(8)页表高速缓存扩展阅读：
快表软件的优点：
1、软件集需求设计和运行于一体，非专业开发者无需掌握编程语言和数据库知识，即可根据自己的业务需求轻松搭建个性化的信息系统。
2、专业开发者也可利用快表的高级功能，降低了纯代码开发的难度并极大地提高了开发效率，实现更加专业、快速、高效的开发。
3、通过快表软件开发平台，可以快速构建报表系统、ERP、OA、CRM、EAI、BI等适合用户自身需求特色的信息化系统。
⑨ Intel 80386 Reference Programmer's Manual - 5.2 Page Translation
页转换主要实现了面向页的虚拟内存系统和页层次保护。若操作系统需要使用相关功能，则必须将CR0的PG位置位。
页是一个以4KB的连续物理地址形成的单元。
线性地址通过制定一个页表(page table)，表中的页(page)，以及页中的偏移量间接地指定一个物理地址。线性地址共分为三部分，最高位10位为页目录的索引，中间10位为页表索引，最低位12位为页偏移量。
从线性地址转换为物理地址的寻址机制为：将31-22位地址作为索引从页目录(Page Directory)中寻找到对应页表(Page Table)，将21-12位地址作为索引从页表中寻找到对应的页(Page Frame)，再使用11-0位作为页偏移量(Offset)从页中找到对应的物理地址。
页表本身是一个页，因此其拥有一个页大小的内存，即4KB。由于页表实质上是一个32位页指示符的数组，所以最多拥有1K项条目(4KB*8/32=1KB)。
页表有两层层次结构，其中位于高层次的页表仅有一个，被称为页目录(page directory)，页目录指向了共1K个第二层次的页表(page table)，而第二层次的每个页表指向1K个页，由此组织出二级页表层级结构。简单的计算可以得知，两级页表层级结构共可以指向1M(2 (20))个页，而每个页包含有4Kb(2 (12)bytes)，因此含有一个页目录的二级页表层级结构共可以组织起4GB物理地址空间(2^(20) times 2^(12) = 2^(32))。
当前的页目录的物理地址将储存在CPU的CR3寄存器中，该寄存器也可以称为页目录基地址寄存器(page directory base register)。内存管理软件可以选择为所有任务(task)使用同一个页目录，也可以选择为每个任务使用单独的页目录，或者使用这两者的混合策略。
附1：虽然在理论上，所有任务都分别使用单独的页目录使得对每个任务而言，线性地址到物理地址的映射完全不同（通过页目录指向完全不同的页表、页表指向完全不同的页等等），但在实际中，必须要有部分的线性地址映射到相同的物理地址中。例如TSS地址和GDT等等。
附：在PG位被置位前，CR3寄存器必须已经被初始化并指向一个有效的页目录的物理地址。初始化进程必须采用以下两种策略中的一种以便保证启用页前后地址的一致性：
所有层次的页表中的项(entry)都具有相同的格式。其格式如下图所示。页表项的格式可以分为两部分，分别是页地址(Page Frame Address)和标识符.
页地址位指示了页的在内存中的物理地址（其中页目录中记录的页地址为页表的物理地址，页表中记录的页地址则指向包含所需要的地址的页帧）。由于页是以4KB大小对齐的，因此页头的物理地址的低12位将始终为0.由于这种特性，页表项中以高位31-12位共20位指示页地址，而剩下的低12位用于标识符记录项的状态信息。
最低位P表示一个项是否存在(present)。当P=1时表示这个项记录的信息是可以用于进行地址转换的（或者说是有效的）。
当P=0时，无论这个项处在页表中的哪个层级，这个项都是无效的，即它不在地址转换中起到作用。而剩下的位（高位31位）可以供软件使用。当P=0时，其格式如下图所示。
如果在任何层次的页表中出现了试图对P=0的项中进行地址转换的情况，处理器则会发出一个页面异常的信号。在支持页虚拟内存的软件系统中，缺页异常(page-not-present exception)处理将请求的页加载到物理内存中，然后再次执行产生异常的指令。
注意到页目录本身没有存在位标识其是否存在。在一个任务被挂起时它的页目录有可能不被表示(not-present)，但是操作系统必须确保TSS中的CR3映像所指示的页目录在任务dispatched之前存在于物理内存中。
已访问位和脏位在两级页表中都表示页的使用情况。除了页目录项的脏位以外，这些位都由硬件设置；而处理器不会对已访问位和脏位进行清理。
在对页进行读或写操作之前，处理器会将对应的页表项的已访问位置为1.该操作对两层页表层级均是如此。在对某个页中的地址进行写操作之前，处理器会将对应的二级页表项的脏位置为1；而页目录项的脏位没有定义。
一个支持页虚拟内存的操作系统可以通过已访问位和脏位来决定当内存需求超过物理可用内存空间的时候，将哪些页从物理内存中删去。测试(test)和清除(clear)这些位是由操作系统来负责的。
这些位并不是用于进行地址转换的，而是处理器在进行地址转换的同时，用于进行基于页的保护(page-level protection)时使用的数据。
为了最大化地址转换的效率，处理器会将最近使用的页表数据存储在单片超高速缓存器(on-chip cache)中。只有当需要的分页信息没有在缓存器中的时候，两级页表才会被使用。
页转换缓存对于应用程序员(applications programmer)来说是不可见的，但是对于系统程序员(system programmer)来说是可见的；当页表改变的时候，操作系统程序员(operating-system programmer)必须刷新缓存区。页转换缓存可以使用以下两种方式进行刷新：