地址变换机构用于实现逻辑地址到物理地址转换的一组硬件机构

1. 基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下:

  1. 根据逻辑地址计算出页号、页内偏移量
  2. 判断页号是否越界：页表长度就是页表中页表项的个数，有多少个页表项就有多少个页面。如果页号P >= 页表长度 M，则抛出越界中断。否则，进入 (3)
  3. 查询页表，找到页号对应的页表项，确定页面存放的内存块号: 根据页号 P 和页表起始地址F得到该页号对应的页表项在内存块中的地址=页号P * 页表项大小 + 页表起始地址 F。通过页表项在内存块中的地址，找到这个页表项之后，便可以得到页表项中的内存块号，然后进入(4)
  4. 用内存块号和页内偏移量得到物理地址: b号内存块号（即 P 号页面）在内存中的起始地址=b*每个内存块的大小。然后得到物理地址 = 内存块号 * 每个内存块的大小 + 页面偏移量

2. 具有快表的地址变换机构

2.1. 局部性原理

2.1.1. 时间局部性

  • 如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行
  • 如果某个数据被访问过,不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

2.1.2. 空间局部性

一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是
同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢？

2.2. 快表

快表,又称**联想寄存器(TLB)**，是一种访问速度比内存快很多的高速缓冲存储器,用来存放当前访问的若干页表项,以加速地址变换的过程。与此对应,内存中的页表常称为慢表。

地址的变换过程:

  1. CPU 给出逻辑地址，由硬件计算得页号、页内偏移量，将页号与快表中的所有页号进行比较

  2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。

    因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

  3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。

    因此，若快表未命中，则访问某个逻辑地址需要两次访存在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换。由于查询快表的速度比询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到 90%以上。

例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时 $1\mu s$,访问一次内存耗时 $100\mu s$.若快表的命中率为 $90%$

那么访问一个逻辑地址的平均耗时是 = $(1+100)\times 0.9+(1+100+100) \times 0.1=111 \mu s$
有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是 $(1+100) \times 0.9+(100+100) \times 0.1=110.9 \mu s$
若未采用快表机制，则访问一个逻辑地址需要 $100+100 = 200 \mu s$
显然，引入快表机制后，访问一个逻辑地址的速度快多了。