318_具有快表的地址变换机构
# 3.1_8_具有快表的地址变换机构
各位同学大家好。在这个小节中我们会学习具有快表的地址变换机构，那么这种地址变换机构其实是在上个小节学习的基本地址变换机构的基础上进行改进的一个版本，在这个基础上引进了快表机制。
这个小节中我们会首先介绍什么是局部性原理，在理解了什么是局部性原理之后，大家才可以更好的理解为什么快表能够起作用。另外我们还会介绍在引入快表之后地址变换的一个过程，我们会按照从上至下的顺序依次讲解。
# 局部性原理
我们来看一个简单的小程序，在这个程序当中我们定义了一个 int 型的变量 i 还有一个 int 型的数组 a，这个数组总共有 100 个元素，之后会执行 100 次循环，每一次循环都会给 a 这个数组对应的元素进行一个赋值的操作。
那么这个程序在经过编译之后，可能会形成一系列与它对等的机器指令，然后这些指令有可能是放在某一个内存块当中的，比如说是放在 10 号内存块当中。除此之外，在这个程序当中定义的这些变量 i，还有像数组型的变量 a有可能是放在另外一个内存块当中的，比如说是 23 号内存块，
由于这个程序会一直循环的执行这一段代码，所以很显然这段程序在执行的过程当中，肯定会很频繁的访问到 10 号内存块和 23 号内存块，因为这些代码对应的指令是存放在 10 号内存块里的，而这个代码当中需要访问的这些变量又是存放在 23 号内存块当中的。由此我们引出了时间局部性和空间局部性两个概念。
所谓的时间局部性是指如果我们在程序当中执行了某一条指令，不久之后这条指令很有可能会被再次执行。如果某个数据被访问过，那不久之后这个数据很有可能会被再次访问。什么意思呢？用循环当中 i++ 这条代码来看，i++ 代码在经过编译之后，可能会形成与它对等的某一条机器指令，那么这条机器指令需要使用到 i 这个变量，并且由于我们的循环会执行 100 次，所以 i++ 对应的那条指令很有可能会很频繁的不断的执行 100 次，相应的在指令执行的过程中，也需要对 i 变量数据进行不断的访问。所以由于我们的程序当中存在着大量的循环操作，因此某一条指令被执行之后，在不久的将来很有可能会被再次执行。另外在循环当中的某一个变量，此次被访问之后，在不久的将来有可能会被再次访问，这就是时间局部性原理。
空间局部性又是指一个程序，在访问了某一个存储单元的不久之后，存储单元附近的那些存储单元也有可能被访问，还是以这个程序作为例子，我们的数组 a 总共有 100 个元素，那么这 100 个元素在内存当中其实是连续的存放在内存块当中的某一个区域当中的，在这个循环当中，我们如果访问了 a 这个数组的第一个元素，在之后不久的将来，a 这个数组的第二个元素，也就是与第一个元素相邻的存储单元，很有可能就会被再次访问，以此类推，第三个第四个第五个也是会在不久之后也会被连续的访问，所以我们定义的类似于数组这些的数据在内存当中都是连续存放的，因此我们在访问了某一个存储单元之后，很有可能会紧接着访问与它相邻的存储单元，这就是空间局部性
时间局部性和空间局部性可以统称为局部性原理。
在上个小节当中，我们介绍了基本地址变换机构，每次要访问一个逻辑地址，肯定都是需要查询内存当中的页表的。但是由于刚才我们介绍的这些局部性原理，我们会发现其实在程序运行的过程当中，很有可能会连续不断的对某一个内存块进行或者说某一个页面进行访问。既然会连续不断的访问同一个页面，那就意味着我们很有可能会连续很多次查到的都是同一个页表项。
既然如此，我们能不能利用特性来减少对列表的访问次数？基于这个原理，人们引入了快表机制
# 快表机制
快表又称为联想存储器，英文缩写是 TLB 这三个名称在题目当中都有可能会出现。
快表是一种访问速度要比内存快很多的高速缓冲存储器，快表可以用来存放当前访问的若干个页表项，用以加速地址变换的过程，那与快表相对应，内存当中的页表的查询速度，访问速度会更慢，所以内存当中的页表常称为慢表，
我们来看一个具体的例子加深理解。假设一个进程需要依次执行三条指令，这三条指令的存放位置分别是页号为 0 页内偏移量为 0 的逻辑地址，还有页号位 0，页内偏移量为 4 的逻辑地址，还有 08 这个逻辑地址，CPU 会依次执行这三条指令
在执行第一条指令的时候，程序计数器 PC 当中存放的应该是此时想要访问的那一条指令对应的逻辑地址，也就是页号为 0，页内偏移量为 0 的逻辑地址，这个逻辑地址会被拆分成页号和页内偏移量这样两个部分，之后会对页号进行合法性的检查，用页号和页表的长度进行对比，看看有没有发生越界对比的过程，咱们在上个小节介绍过，这就不展开了。
确认了页号的合法性之后，会用页号来查询快表，看一看快表当中有没有和页号对应的页表项。由于刚开始这个快表是空的，所以并没有找到与这个页号对应的页表项，也就是说查询快表是未命中的，
由于快表没有命中，所以接下来需要用页表始址和页号来计算出液号对应的页表项在内存当中存放的位置。
另外在查询到页号对应的页表项之后，系统会把页表项自动的复制到快表当中，这样的话快表当中就出现了一个与页表项相对应的一个副本，找到这个页号对应的页表项之后，我们当然就可以知道这个页面存放的内存块号到底是多少，根据内存快号和页内偏移量，我们就可以得到最终的物理地址，最后根据这个物理地址，CPU 就可以找到逻辑地址为 00 的那条指令存放的实际物理地址了。
在执行完第一条指令之后，会紧接着执行第二条指令。第二条指令在内存当中存放的位置应该是页号为 0，页内偏移量为 4的内存单元当中，那么和刚才一样，首先需要对页号进行合法性的检查，看一下它是否越界。如果这个页号没有越界的话，接下来会查询页表。但是由于我们想要查询的是 0 号页面，此时页表当中其实已经有了 0 号页面对应的页表项，所以我们在查询页表的时候就已经命中了，所以我们通过快表就可以直接知道 0 号页面对应的物理内存块号到底是多少。既然已经知道了 0 号页存放的内存块，接下来就不需要再查询内存当中的页表了，我们可以直接根据内存快号，还有页内偏移量就得到最终想要访问的物理地址。接下来 CPU 就会根据物理地址，从内存当中取出它要执行的第二条指令。所以从刚才的分析过程当中，我们也会发现，如果查询快表命中了，那么就不需要再查询内存了，因为查询快表的速度要比查询内存中页表的速度要快得多，所以如果查询快表命中的话，那么地址转换的过程就可以快很多。
继续回到刚才的过程，CPU 在执行完第二条指令之后，还会紧接着执行第三条指令的存放位置是 08 这个位置。那和刚才一样，首先需要检查页号的合法性，在确认页号合法之后再查询快表，结果发现快表当中已经有与页号对应的页表项了，于是我们可以直接得到页面存放的内存快号，然后再结合页内偏移量，最终就可以得到第三条指令存放的实际物理地址到底是多少。
从刚才的分析当中也可以看到，其实快表当中存放的是页表的一部分副本内容
# 引入块表后，地址的变换过程
接下来我们根据之前分析的这些过程来总结一下，引入了快表之后地址变换的过程是怎么样的。第一步 CPU 会给出一个逻辑地址，然后由某个硬件根据这个逻辑地址算得页号和页内偏移量这两个信息，并且会把页号和快表当中的所有页号进行比较。如果说在快表当中找到了相匹配的页号，那就说明我们要访问的页表项在快表当中是有一个副本的，我们就可以直接从快表当中取出页表项，对应的内存块号到底是多少，那之后再把内存块号和页内偏移量拼接成最终的物理地址，最后再访问物理地址对应的内存单元就可以了。所以从这个过程中我们可以看到，如果说快表命中的话，那么访问某一个逻辑地址仅需要一次访存的操作。
如果说我们在页表当中没有找到与页号相匹配的项的话，那么就需要在访问内存当中的页表。注意页表指的是慢表，找到了对应的页表项之后，就可以得到这个页面存放的实际的内存括号，之后再把内存括号和页内偏移量拼接成一个物理地址。最后根据物理地址在访问我们最终想要访问的内存单元。
所以从这个过程中我们可以看到，如果快表没有命中的话，那么我们想要访问某一个逻辑地址需要两次访存，第一次是查询内存当中的页表，第二次才是访问我们最终想要访问的内存单元，
这个地方大家需要注意的是，在找到了慢表当中的页表项之后，需要同时把页表项把它复制到快表当中，这是基于局部性原理的考虑，因为这个页表相对应的页面很有可能在后面会被再次访问到。不过如果快表当中已经存不下了，那么我们需要按照一定的算法对旧的页面项进行替换，我们到底可以用什么算法？这个问题我们会在之后学习页面置换相关的那些小节当中进行介绍，这儿就先不展开。
由于查询快表的速度要比查询慢表，也就是内存当中的页表的速度要快很多，所以只要快表命中的话，我们就可以节省很多地址转换的时间，而因为局部性原理一般来说跨表的命中率可以很高，可以达到 90% 以上。
我们来看一个例题，假设某一个系统当中使用基本分页存储管理，并且采用了具有快表的地址变换机构，访问一次快表耗时一微秒，访问一次内存耗时 100 微秒，如果快表的命中率是 90% 的话，访问一个逻辑地址的平均耗时应该是多少？通过刚才的分析可以知道，在访问一个逻辑地址的时候，首先会根据页号去优先的查询快表，查询快表的耗时是一微秒，如果说快表命中的话，就可以得到这个逻辑地址对应的最终的物理地址，接下来就再进行一次访问内存的操作，也就是访问我们最终想要访问的物理内存单元就可以了，所以如果快表命中的话，耗时应该是 1+100，也就是 101 微秒，那快表命中的概率是 90%，所以我们给它乘上一个 0.9 的权值。
另一方面如果我们查询快表没有命中的话，那么我们就需要访问内存当中的慢表，所以这会产生更多一次的访问内存的操作。最后再根据内存块号和页内片一量得到物理地址，然后对物理地址进行访问，所以这儿又是一次访问内存的操作。由于快表未命中的概率是 10%，所以这儿乘上一个 0.1 的权值，因此平均下来访问一个逻辑地址的平均耗时应该是 111 微妙。
在这个计算过程当中，我们默认是先查询快表，当快表查询失败之后才会去查询页表，但是在有的系统当中，它会支持快表和慢表同时查询，如果快表查询成功了，那么就会停止慢表的查询操作。所以在这种系统当中，慢表和快表的查询是同时开始的。因此在这种系统当中，如果说我们的快表没有命中的话，那么总共的查询耗时应该就是慢表的查询时间 100，再加上最终访问内存的时间 100 也就是 200。
所以如果题目当中告诉我们这个系统是支持快表和慢表同时查询的话，那么访问一个逻辑地址的平均耗时应该是 110.9 微秒。不过如果题目当中没有明确的告诉我们的话，我们是默认首先需要查询快表，当快表查询失败之后才会继续查询慢表，这是有可能在题目当中出现的一个小细节。
最后我们再来看一下，如果说没有采用快表机制的话，那么访问一个逻辑地址肯定是需要先查询一次慢表，然后才能找到最终要访问的内存单元。所以在这种情况下访问一个逻辑地址需要的平均耗时就应该是 200 微秒。在这个例题当中引入了快表机制之后，地址转换的耗时几乎是减了一半，所以这就可以大幅度的提高我们计算机的性能。
# 小结
这个小节中我们学习了具有快表的地址变换机构，这个小节当中大家需要着重掌握，引入了快表机制之后，地址变换的过程是什么样的，相比于上个小节学习的基本地址变换机构来说，引入了快表机制之后，地址变换的过程当中会优先的检查快表，如果快表命中了，那么就可以直接从快表当中就知道我们想要找的页面存放的内存快号到底是多少，那就可以直接通过内存块号得到物理地址。
如果说快表没有命中的话，才需要再去查询内存当中的页表或者说慢表，并且我们还需要将慢表当中的页表项复制到快表当中，这是基于局部性原理得到的一种处理的策略
另外大家也需要能够自己分析，在采用这两种地址变换机构的情况下，访问一个逻辑地址到底需要几次访存，基本地址变换机构当中肯定是需要查询内存当中的页表的，所以一定需要两次访存。而如果说引入了快表机制之后，如果快表命中就不需要在查询内存当中的页表，所以只需要一次保存，如果快表没有命中，那么还需要查询一次内存当中的页表，所以需要两次访存。
