5 Memory Hierarchy¶
5.1 Storage unit Introduction¶
5.1.1 Transistor¶
半导体：性质介于金属与绝缘体之间，通过加电场可以改变其性质
- P型半导体（电子密度比正常水平小）
- N型半导体（电子密度大）
电流只能从P型半导体流向N型半导体，所以在栅极不通电时，源极与漏极之间无电流；而当栅极通电后，P型半导体中的一部分会出现反向层，这样源极与漏极就有电流了
5.1.2 SRAM (Static Random Access Memory)¶
数据被存在一对反向门中，存储读取的速度非常快，但是相比DRAM面积要更大，所以在同样的容量下，SRAM要贵很多。
不需要刷新电路，掉电丢失数据，而且一般不是行列地址复用的。
因此目前SRAM基本上只用于CPU内部的一级缓存以及内置的二级缓存。仅有少量的网络服务器以及路由器上能够使用SRAM。
5.1.3 DRAM (Dynamic Random Access Memory)¶
掉电丢失数据。每隔一段时间就要刷新一次数据，才能保存数据。而且是行列地址复用的，许多都有页模式。DRAM利用MOS管的栅电容上的电荷来存储信息，一旦掉电信息会全部的丢失，由于栅极会漏电，所以每隔一定的时间就需要一个刷新机构给这些栅电容补充电荷，并且每读出一次数据之后也需要补充电荷，这个就叫动态刷新，所以称其为动态随机存储器。由于它只使用一个MOS管来存信息，所以集成度可以很高，容量能够做的很大，但是读写速度不如SRAM。
一个DRAM的存储单元存储的是0还是1取决于电容是否有电荷，有电荷代表1，无电荷代表0。但时间一长，代表1的电容会放电，代表0的电容会吸收电荷，这就是数据丢失的原因；刷新操作定期对电容进行检查，若电量大于满电量的1／2，则认为其代表1，并把电容充满电；若电量小于1／2，则认为其代表0，并把电容放电，藉此来保持数据的连续性。
SDRAM：数据的读写需要时钟来同步，其存储单元不是按线性排列的，是分页的
DDR SDRAM：这种改进型的RAM和SDRAM是基本一样的，不同之处在于它可以在一个时钟读写两次数据，这样就使得数据传输速度加倍了。这是目前电脑中用得最多的内存。
5.1.4 Flash Storage¶
不会断电丢失数据同时可以快速读取数据，U盘和MP3里用的就是这种存储器。虽说闪存是非易失的，但是由于闪存的存储方式是把电子打到氧化层中，电子会流失（较慢，以年为单位），所以如果长时间不通电的话，也会造成数据的流失。
目前Flash主要有NOR Flash （随机存储，速度更快）和NAND Flash（密度更高，更常用）
最近新出现的还有3D flash，使得密度更高了。之前平面的情况要提升密度只能不断缩小晶体管，这会导致相互间的影响增大，误码率提高。做成3D之后，我们不需要把晶体管做的特别小，减小了误码率，同时也保证了密度。
5.1.5 Disk Storage¶
sector（扇区）：每一个扇区包含了Sector ID，Data（512 bytes, 4096 bytes proposed)，Error correcting code (ECC)
在扇区中寻找数据的步骤
- Queuing delay if other accesses are pending
- Seek: move the heads 找到对应的sector
- Rotational latency 磁盘需要旋转
- Data transfer 数据传输
- Controller overhead 总的控制延迟
Example
一定要注意这个rpm指的是转每分钟
5.2 Memory Hierarchy Introduction¶
程序在同一个时间内只会访问一小部分地址，同时访问的数据具有以下特性
Temporal locality: Items accessed recently are likely to be accessed again soon，比如说在一个循环中，指示变量就要被多次重复访问。
Spatial locality: Items near those accessed recently are likely to be accessed soon，比如说连续的指令读取，数组数据的读取。
根据这个性质，我们可以设置Memory的层级结构，将所有数据存在磁盘中，将最近访问的（和附近的）项目从磁盘复制到较小的DRAM内存，复制最近访问过的（和附近的）从DRAM到更小的SRAM存储器
这里红线的意思是速度显著变慢。
我们设计多层cache的原因
第一层cache是为了速度更快，跟上寄存器的速度，第二层的cache容量更大，提高了hit ratio，避免数据还在DRAM层甚至更低。
下面介绍一些重要的概念
Block (aka line): Block可以理解为一种组织内存的方式，将内存一段一段地划分开来形成许多Blocks，可能包含很多字。
如果需要访问的数据在更高的层次，那么我们称这次访问是Hit，相应的Hit ratio就是 hits/accesses; 如果访问的数据没有，那么我们就称这次访问为一次miss，需要从更低的层级中调用数据上来，相应的 Miss ratio 就是 misses/accesses=1- hit ratio
Hit time: The time to access the upper level of the memory hierarchy, which includes the time needed to determine whether the access is a hit or a miss.
miss penalty: The time to replace a block in the upper level with the corresponding block from the lower level, plus the time to deliver this block to the processor.
5.3 The Basics of Cache¶
For each item of data at the lower level, there is exactly one location in the cache where it might be, but lots of items at the lower level share locations in the upper level
现在有两个问题需要解决：
- How do we know if a data item is in the cache?
- If it is, how do we find it?
5.3.1 Directed Mapped Cache¶
下一层次的内存如何映射到上一层的内存：
(Block address) modulo (Number of blocks in the cache)
我们直接对内存中地址以cache的# block取模，然后直接映射到相应编号的cache block中去。
那我们怎么知道cache中存的是内存中哪个位置的block (How do we know which particular block is stored in a cache location?)，我们可以取内存地址较高的位作为tag，这样我们就可以精确定位到cache中的数据来自于哪里了。
当然，我们也需要判断是否有数据在cache的这个block中，引入一个 Valid bit，用1代表present，用0代表 not present。
关于上图的一些解释
内存地址是以字节为单位的，然后一个字根据不同的系统包含不同的字节（16位系统是2字节，32位系统是4字节）然后上面我们内存是以block为单位编码地址的，所以可以看到上图是包含一个Byte offset,这是为了去掉一个block含有的字节数，剩下的部分一是用来代表index，另一部分用来代表tag
上图同时也展示了Hit过程，找出Tag比较，然后确定valid，得出Hit信号，如果为真，那么直接输出Data
通过下面这个例子，我们可以更加直观地理解
例1
问题的意思是cache中一共有16KB放数据的，一个Blocks一共4个字，然后地址是32位的。
第一二步16 KB的数据一共是4K word，因为一个字4个字节。这样我们就可以算出cache一共有多少个Blocks=\(2^{10}\)
第四步，一个block中的数据有128位
第五步，计算tag bits，32位去掉byte offset的4位（一个block 16个字节），再去掉10位的index位（因为cache一共\(2^{10}\)个block)
例2
参考文章：【CS202计算机组成原理】一次性搞懂cache中size, block, index, offset, tag相关计算_cachesize和blocksize-CSDN博客
Miss Rate 与 Block Size 之间的关系
左侧坐标是 Miss rate，右侧各条线的标签是缓存大小，横坐标是 Block Size。
- 越小的cache，miss rate 越高
- 同样大小的cache，miss rate 呈现一个先小后大的趋势。Block size 较小会导致一个block中存储的数据较少，由于数据有空间局部性，miss rate较稍大一点的block来说就更高。而Block size在较大的情况，在cache大小固定的条件下，数量变少了，造成冲突更多了，失效率也就变高了。（当然在cache容量较大的情况下，就显得不那么明显了）
5.3.2 Handling Cache Reads Hit and Misses¶
Read hits: 这就是我想要得到的结果，读取的数据刚好就在cache之中
Read misses: 有两种misses
- instruction cache miss
- data cache miss
我们以 instruction cache miss 为例展示一下相关步骤，先暂停CPU，然后从内存中取出block给缓存，然后再重启CPU。
-
Send the original PC value (current PC-4) to the memory.
-
Instruct main memory to perform a read and wait for the memory to complete its access. (in multiple cycles)
-
Write the cache entry, putting the data from memory in the data portion of the entry, writing the upper bits of the address (from the ALU) into the tag field, and turning the valid bit on.
-
Restart the instruction execution at the first step, which will refetch the instruction again, this time finding it in the cache
5.3.3 Handling Cache Write hit and Misses¶
Write Hits: 面对写的地方已经在内存中，我们有不同的解决方法
- write-back: 只把数据写到缓存中，写入内存的操作往后推迟。这种方法的显著特点就是快，但会造成数据的不一致。
- write-through: 数据同步更新到缓存和内存
Write Misses: 先把整个block读入到cache中，然后再写入字
为什么要先把数据从内存中先取到cache中？
因为我们写入的仅仅只是一个block中的一个字，如果我们不读入的话，这个block中的字下次写回的时候其他字的数据就被清空了
5.4 More Details about 5.3¶
5.4.1 Block placement¶
我们可以使用 Direct Mapped 来放置 Block，这样给定一个内存地址对应放置的缓存位置是固定的，这样搜索更快，但很容易造成数据的竞争。
我们也可以使用 Fully associative 的方法来放置，就是只要整个缓存中有位置可以放，那么这个 Block 就可以放在缓存当中，这种方法让竞争的可能性下降了，但是如果发生 Miss，造成的Miss Penalty就会非常大。
于是我们结合上述两种方法，提出第三种方法 Set associative，这种方法将缓存分为多个 Set，内存中的Block 会被放到 对应 Set 中的任意一个位置。If sets have n blocks, the cache is said to be n-way set associative.
Note
Note that direct mapped is the same as 1-way set associative, and fully associative is m-way set-associative (for a cache with m blocks).
Example
绿色的部分是内存中的block可能放置的位置
5.4.2 Block Identification¶
Tag
-
Every block has an address tag that stores the main memory address of the data stored in the block.
-
When checking the cache, the processor will compare the requested memory address to the cache tag -- if the two are equal, then there is a cache hit and the data is present in the cache
Valid bit
- Often, each cache block also has a valid bit that tells if the contents of the cache block are valid
对于内存地址，由三部分构成
The Index field
- In case of a set-associative cache, has as many bits as \(\log_2(\#\text{sets})\)
- In case of a direct-mapped cachr, has as many bits as \(\log_2(\#\text{blocks})\)
The Byte Offset field has as many bits as \(\log_2(\#\text{size of blocks})\)
The Tag is used to find the matching block within a set or in the cache, has many bits as \(\text{Address\_size} - \text{Index\_size} - \text{Byte\_Offset\_Size}\)
Block Identification
这个图有一点问题，我们引出比较的应该是同一个Set中的内容，并且如上图的话，我们只需要两个比较元件和and元件以及一个选择set的选择器即可
5.4.3 Block Replacement¶
当我们的block满了或是set满了的时候，我们还需要往这里面放数据，就需要把一些数据代替掉。
对于使用 directed-mapped 方法的 cache 来说，只有一个 block 可能被替换。
然而对于采用 set-associative 和 fully-associative 的cache 来说，就有很多 Block 可以被替换了。替换的方案有三种，分别是 Random replacement, Least-recently used (LRU) and First in, first out.
Random replacement¶
我们任意地选择一个可以被替换的 block ，这在硬件上很容易实现，只需要一个随机数生成器。但是这种方法的问题在于我们很有可能把一个即将要用到的 block 给替换掉了
Least-recently used (LRU)¶
我们选择最近被用的次数最少的那一个 block，这个我们其实是建立在用到次数越多的 block 更有可能被再次使用的基础上的，这种方法需要在缓存中加入额外的位来存储访问的次数
First in, first out (FIFO)¶
这个就类似于一个队列，哪个 block 先进入就先替换哪个 block
5.4.4 Write Strategy¶
当数据被写入缓存的时候，根据数据是否写入内存，分为两种写的形式
数据被写入内存，那么这种方式被称为 write-through
- 内存中存储的一直是最新的数据。
- 在处理缓存中的数据的时候，我们可以直接扔掉。
数据不被写入内存，那么这种方式被称为 wirte-back
- 我们在处理缓存中的数据的时候，我们不能直接将其丢弃，因为缓存中的数据可能还要写回到内存中。
- 我们对缓存中的数据控制就不仅仅需要 valid bit, 还需要一位的 dirty bit，来表示现在缓存中的数据是否与内存中的数据相等。
- 更加低的 bandwidth, 因为数据经常被多次覆盖，这样就不需要多次给内存数据了
Write through 的优势：Read misses don't result in writes, memory hierarchy is consistent and it is simple to implement.
Write back 的优势：Writes occur at speed of cache and main memory bandwidth is smaller when multiple writes occur to the same block.
假如我们使用的是 write-through 策略，造成的 write stall 就是每次写操作后 CPU需要等待数据被写入内存，这样的开销是巨大的。于是我们引入 write buffers，每次写操作结束后，我们只需要将数据传输到 write buffer 中而不是到内存中去，这样我们就显著减小了 write stall 的时间。
面对 Write misses 的时候（要执行写操作，发现缓存中没有目标 block）这个时候我们有两种策略
Write allcocate: 不管怎么样先把对应的block载入到缓存中
Write around (no write allocate)：我们只将数据写入 main memory中，比如说在初始化的时候，我们就可以直接将数据写入下游中，并且这样的操作对性能并不会有什么损失，即使接下来需要用到相应的数据，造成 read miss，还要将数据从内存中载入缓存中。
Note
In general, write-back caches use write-allocate , and write-through caches use write-around .
5.4.5* Large Blocks Exploit Spatial Locality¶
利用数据的空间局部性让一个 blocks 中放更多的 words 以减小 miss rate
上面这个图就是对于一个 Blocks 中放置四个 words 的情况下 cache 的简单结构，注意上图的那个MUX，选择信号是 block offset。
对于一个 blocks 中有多个 words 的情况，我们需要怎么设计内存系统？
为评估不同方法的性能，我们假设
- 1 clock cycles to send the address
- 15 memory bus clock cycles for each DRAM access initiated
- 1 bus clock cycles to send a word of data
- Block size is 4 words
- Every word is 4 bytes
a. One-word-wide memory organization¶
这种方法的 miss penalty (The time to transfer one block)
具体来说需要一个时钟传输地址，对于这个 block 中的每一个 word 都需要 15 个 cycles 去内存中访问以及一个 cycle 去传输。
这样计算得到的 bandwidth 就是 \((4\times4)/65\approx1/4\)
b. Wider memory organization¶
增加了内存的传输宽度
当我们将 main memory width 增加到四个字的时候
我们的 miss penalty 就是
Bandwidth：\(16/17\approx0.98\)
c. Interleaved memory organization¶
我们将内存分成四个 bank，交错排布。
The miss penalty
具体来说就是，访问内存的15 cycles 是并行访问的，但是我们从bus中传输到cache是一个 word 一个 word 传输上去的，所以需要 \(4\times 1\) 的cycles。
The Bandwidth: \(16/20\approx0.8\)
5.5 Measuring and improving cache performance¶
在这一节中我们主要讨论两个问题
- 如何评价缓存的性能
- 如何提高缓存的性能
5.5.1 Measure cache performance¶
我们利用 CPU time 来评估缓存的性能
其中关于内存读取的延迟可分为读延迟以及写延迟（这里采用 write-through 的方法）
如果 write buffer stalls 非常小，我们可以直接忽略掉，我们就可以将 read 和 write 直接合并，得到
如果 cache block size 只有一个 word, 那么 write miss penalty 就是 0
Calculating Cache Performance
如果我们加快clock rate，那么 Miss penalty 的时钟数就会翻倍
5.5.2 How to improve performance?¶
Reducing cache misses by more flexible placement of blocks¶
我们改进 directed-mapped cache 为 set-associate cache 来提高性能，这个在前面都说过了，基本概念不再赘述。
Miss rate versus set-associativity—4Blocks
How much of a reduction in the miss rate is achieved by associativity?
我们发现 associativity 从1增加到2的时候，miss rate 显著降低，后面associativity 增加的时候，miss rate 下降地就不明显了
对于 block 的替换，最常用的方法是 LRU。
For a two-way set associative cache（一个set中只有两个block）, the LRU can be implemented easily. We could keep a single bit in each set. We set the bit whenever a specific block in the set is referenced, and reset the bit whenever another block is referenced.
随着一个set中的block数越来越多，LRU的实现就越来越难。
lp老师还讲了一个二叉树的方法，在这里不再多说。
Decreasing miss penalty with multilevel caches¶
让L1比较小，降低了 hit time，L2就拿来兜底防止到更低的内存结构中取数据。我们用下面这个例子直观地感受一下。
Example
CPI of 1.0 on a \(5\text{GHz}\) machine with a 2% miss rate, \(\text{100ns}\) DRAM access，Adding 2nd level cache with 5ns access time decreases miss rate to 0.5%
一开始，Miss penalty 为
相应的CPI为
增加了一级缓存之后，数据在二级缓存中找到需要
那么相应的CPI为
Using multi-level caches:
-
try and optimize the hit time on the 1st level cache
-
try and optimize the miss rate on the 2nd level cache
Note
5.6 Virtual Memory¶
5.6.1 虚拟内存技术¶
Link
计组把 main memory 描述为 secondary storage (即 disk) 的 "cache"。或者，反过来说，我们把那些在 main memory 里放不下的内容存到 disk 里（这样更能符合我们熟悉的“可执行文件必须加载到内存才能运行”的一贯认知）。这种技术称为 virtual memory。
虚拟内存技术可以让多个程序之间高效、安全地共享内存，同时允许单个程序使用超过内存容量的内存（正如虽然 CPU 取数据时是从 cache 中取的，但是它能访问到的数据的数目比 cache 的容量要大）。在远古时期，很多程序因为需要使用过大的内存而无法被运行；但现在由于虚拟内存技术的广泛使用，这些程序都不成问题了。
如下图所示，实际上的 main memory（我们称之为 物理内存, physical memory）中的地址称为 物理地址, physical addresses；而我们给每一个程序内部使用到的内存另外编一套地址，称为 虚拟地址, virtual addresses；虚拟内存技术负责了这两个地址之间的转换 (address translation，我们稍后再讨论转换的方式)：
从这张图中我们也可以很容易地看出“虚拟内存技术可以允许单个程序访问超过物理内存大小限制的内存”的原因，即有一些内存可以被临时地存放在磁盘上，到被访问的时候再被放到 physical memory 中，就像 cache 做的那样。
从这张图中，我们还可以注意到 physical memory 的存放并没有分组的概念，即用 cache 的术语来说，main memory 是 fully-associative 的。
虚拟存储的技术和 cache 的原理是一样的，但是一些术语的名字并不相同。对应于 cache 中的 block / line，虚拟存储的内存单元称为 page，当我们要访问的 page 不在主存中而是在磁盘里，也就是 miss，我们称之为一次 page fault。
5.6.2 如何完成映射呢¶
首先我们要考虑的一个问题就是，一个 page 应该有多大。我们知道，访问磁盘相比于访问内存是非常慢的（相差大约十万倍），这个主要时延来自于磁盘转到正确的位置上的时间花费；所以我们希望一次读进来多一点从而来分摊这个访问时间。典型的 page 大小从 4KiB ~ 64KiB 不等。
下面我们考虑映射关系。我们不妨假设一个 page 的大小是 4KiB，那么其页内的偏移 page offset 就需要 12 位来表示；那么物理地址中除去后 12 位以外前面的部分就表征着它是属于哪一页的，我们称之为 physical page number。
Note
如我们之前所说，memory 作为 disk 的 "cache" 是 fully-associative 的，因此 physical page number 其实就是 cache 中的 "tag"，而 page offset 就是 cache 中的 "byte offset"，fully-associative 的 cache 并没有 index 这一字段。
为什么要使用 fully-associative 的存储方式呢？我们在 cache 中讨论过，这种方式的好处是失效率低，坏处是查询难度大。但是我们也讨论到了，page fault 的开销是非常大的，因此比较低的 page fault 的概率相对于额外的查询来说是非常划算的。
同样，由于读写磁盘是非常慢的，write through 的策略并不合适，因此在 virtual memory 的技术中，我们采取 write back 的方式。
而 virtual address 的形式与之类似，由若干位 page number 和若干位 page offset 组成。
我们之前提到，我们有一种方式可以找到 virtual page 对应的 physical page，因此当我们要访问一个虚拟地址时，将其 virtual page number 通过这种 translation 转换为 physical page number（这种 translation 也会负责 page fault 的处理并给出正确的转换），而 page offset 表示的是在一页内的偏移，保持不变即可。这样我们就获得了这个 virtual address 对应的 physical address，也就是它在实际的 main memory 中存储的位置。如下图所示：
同时也可以看出，virtual page number 的位数比 physical 的多；这也是显然的，因为我们引入虚拟内存的一个重要原因就是为了使用比 main memory 更大的内存。
5.6.3 页表¶
我们下面讨论这种 translation 的具体方案。之前也提到，fully-associative 的一个重要问题就是如何去定位某一项；这里我们引入 page table 这种结构，它被存放在 main memory 中，每个程序（实际上是进程，但是写课本的人好像现在并不想引入这个概念）都有一个自己的 page table；同时硬件上有一个 page table register 保存当前进程这个页表的地址。
使用页表时，我们根据 virtual page number 找到对应 page table entry, PTE 在 page table 中的偏移，然后与 page table register 相加得到对应 entry 的位置，从中读取对应的 entry。其实就是说，page table 就是一个数组， page_table[i] 表示第 i 个 virtual page 对应的 physical page number。
Note
这里其实我一开始很难读懂，解释一下。把PTE理解为跟之前指令里面那个ld指令中ld rd,rs1,offset中的offset差不多，page table register中记录的就是这个程序的基地址类似于rs1，这样我们就可以得到相应的entry，从而得到对应的物理地址了，我觉得很难读懂的一大原因是将physical address搞混了(我上面已经改为了位置)
对于一个多程序的例子，我们可以看下面这幅图
如下图所示，每个 entry 中包含了一个 valid bit 和 physical page number。如果 valid bit = 1，那么转换完成；否则触发了 page fault，handle 之后再进行转换。
Page fault 会引发一个 exception，由操作系统接管控制，处理完之后再将控制交还给进程。操作系统要做的事情是在 secondary storage 中找到这一 page，将其放到 main memory 里（可能需要与当前主存中的某个 page 交换），然后更新 page table。
操作系统在创建进程时在 disk (或者 flash memory) 上创建一个虚拟地址空间那么大的空间，以便上述的交换；这个空间称为 交换区, swap space。下面的问题是操作系统如何在 swap space 中找到需要的 page。
我们可以看到，如果 page table entry 的 valid bit 为 0，那么后面的 physical page number 是没有用到的。我们可以利用这个字段存储对应 page 被交换到了 disk 的哪个位置；或者另外开辟一个索引结构，在其中记录每个 virtual page number 对应的 disk 位置。作为前者的一个例子，请看下图：
操作系统还会跟踪哪些进程和虚拟地址正在使用哪个物理页，因为操作系统需要让交换引发后续 page fault 的次数尽可能少。操作系统会使用我们之前提到的 LRU, Least Recently Used 的策略处理交换。
LRU 的代价有点太大了，毕竟如果使用 LRU 的话需要遍历整个 main memory。因此，很多操作系统引入了 reference bit (或者称为 use bit) 来近似地实现 LRU。当一个 page 被访问时这个 bit 被置为 1；操作系统定期将 reference bit 清零。因此，在需要交换时，只需要找一个 reference bit 为 0 的就可以说明它在这段时间内没有被访问过。
5.6.4 用多级页表解决页表过大的问题¶
如我们之前所说，virtual memory 使用 write back 的策略，因此还需要一个 dirty bit。
我们不妨关注一下 page table 有多大。在我们之前的例子中，virtual address 有 48 bit，每个 page 的大小为 4KiB，所以 page table entry 的数目是 \(\frac{2^{48} B}{4 KiB}=\frac{2^{48}}{4×2^{10}}=2^{36}\)；而 RISC-V 每个表项有 8 Byte，所以 page table 的总大小来到了 \(2^{39}\) B=0.5TiB，这是极其不合理的；尤其是每个进程都有一个 page table 的前提下。
我们可以通过多级页表的方式解决这个问题。
如我们之前所述，页表是一个数组， page_table[i] 中存储的是 page number 为 i 的 page 所对应的 physcial page number。考虑我们的逻辑地址结构：
我们考虑将 \(p\) 分为 \(p_1\) 和 \(p_2\)
我们使用一个两级页表， outer_page_table[i] 中存储的是 \(p_1\) 为 i 的 inner page table，即 inner_page_table[i][] 的基地址；而 inner_page_table[i][j] 中存储的就是 \(p_1\) 为 \(i\)，\(p_2\) 为 \(j\) 的 page 对应的 physical page number，即 page number 为 \(p_1p_2\) （没有分割时的 p）对应的 physical page number。
这里，我们称 \(p_1\) 为 page directory number ，\(p_2\) 为 page table number，\(d\) 为 page offset。
考虑这样做的好处：hierarchical paging 其实就是对页表的分页（page the page table）。因此，它避免了 page table 必须处在连续内存的问题，这一问题在 p 比较大时尤其严重。
另外，这样做在一般情况下可以节省空间。我们之前提到，页表不一定会全部使用；并且由于逻辑地址是连续的，因此用到的页表项也是连续的，都排在页表的头部（很多空间都没有被利用）。因此如果我们采用了二级页表，那么许多排在后面的 inner page table 将完全为空；此时我们可以直接不给这些 inner page table 分配空间，即我们只分配最大的 \(p_1\) 那么多个 inner page table。这样我们可以节省很多空间。即使在最差的情况下，所有页表都被使用了，我们的页表所用的总条目数也只有 \(2^{m-n}+2^{m-n}⋅2^n=2^{m-n}+2^m\) 个，只比单级页表结构多了 \(2^{m-n}\)，是完全可以接受的。
类似地，我们可以设计更多级的页表。
Note
多级页表的思路就是分级查询
5.6.5 使用 TLB 加快地址转换¶
我们之前提到，使用页表时，我们根据 virtual page number 找到对应 page table entry 在 page table 中的偏移，然后与 page table register 相加得到对应 entry 的地址，从中读取对应的 entry。但是这种方法的效率存在问题。要访问 virtual address 对应的 physical address，我们首先要根据 page table register 和 page number 来找到页表在内存的位置，并在其中得到 page 对应的 physical page number，这需要一次内存访问；然后我们根据 physical page number 和 page offset 算出真实的 physical address，并访问对应的字节内容。即，访问一个字节需要两次内存访问，这会加倍原本的内存访问的时间，这是难以接受的。
这个问题的解决方法用到一个专用的高速查找硬件 cache，这里称它为 translation look-aside buffer (TLB)。它实际上就是 page table 的专用 cache（它真的是 cache；page table 并不是 cache，只是像 cache），其 associativity 的设计可以根据实际情况决定。
下图是一个 fully-associative 的 TLB 的例子；由于是 fully-associative，并不需要 index：
当 TLB miss 的时候，处理器去 page table 查找对应的项；如果发现对应项是 valid 的，那么就把他拿到 TLB 里（此时被替换掉的 TLB entry 的 dirty bit 如果是 1，也要写回 page table）；否则就会触发一个 page fault，然后在做上述的事。
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！