PC_非连续内存分配方式@分页存储管理@地址变换机构@快表

PC_非连续内存分配方式@分页存储管理@地址变换机构@慢表@快表TLB@相联存储器CAM@有效访存时间

• 在连续分配方式中，我们发现，即使内存有超过R大小的空闲空间，但若没有连续的R的空间，对于需要总大小为R的内存空间的作业仍然是无法运行的;
• 但若采用非连续分配方式(离散式分配)，则作业所要求R大小的内存空间可以分散地分配在内存的各个区域
  • 这也需要额外的空间去存储(标记)它们(分散区域)的索引
    • 这使得非连续分配方式的存储密度低于连续分配方式。
• 非连续分配方式根据分区的大小是否固定，分为
  • 分页存储管理
  • 分段存储管理

🎈分页存储管理

• 在分页存储管理中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为
  • 基本分页存储管理
  • 请求分页存储管理(可以用来实现虚拟内存的管理方式)

基本分页存储管理

• 固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低
• 我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想:

页面和页面大小

• 不同上下文中的块的别称,包括以下两方面
• 进程中的块称为页或页面(Page)
  • 属于某个进程所持有(process-page)
• 内存中的块称为页框或页帧( Page Frame)(形容尚未被使用的内存块)
  • 可能属于为分配的空闲内存块(memory-page)
• 外存也以同样的单位块进行划分，直接称为块或盘块（Block)
• 进程在执行时需要申请主存空间
  • 🎈要为每个页面分配主存中的可用页框，页和页框的一一对应。

分块和碎片

• 把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。

• 每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

• 分页的方法从形式上看，像分区相等的固定分区技术，分页管理不会产生外部碎片。

  • 但它又有本质的不同点:
    • 块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。
    • 这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，
    • 所以尽管会产生内部碎片，但这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片(也称页内碎片)

• 为方便地址转换，页面大小应是2的整数幂。

• 同时页面大小应该适中

  • 页面太小会使进程的页面数过多，这样页表就会过长，占用大量内存，
  • 而且也会增加硬件地址转换的开销，降低页面换入/换出的效率;

• 页面过大又会使页内碎片增多，降低内存的利用率。

逻辑地址结构

• 简称为地址结构

• 页号P

  • 假设地址的高p位用来表示页号,P$\in [0,2^p-1]$

• 页内偏移W

  • 假设地址的低w位用来表示页内的字,$W\in [0,2^w-1]$

• 地址结构决定了虚拟内存的寻址空间有多大

页表

• 为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表

  • 它记录页面在内存中对应的物理块号，页表一般存放在内存中。

• 在配置页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。

• 可见，页表的作用是实现页号到物理块号的映射

• 页表是由页表项组成的

页表项结构

• 有两部分组成
• 页号
• 块号

页表项和地址比较🎈

• 页表项与(存储单元(字))逻辑地址都可以看做是由两部分构成，
  • 第一部分都是页号，
  • 第二部分
    • 页表项的是物理内存中的块号N;(PBN:physical (memory) Block Number)
    • 地址的是页内偏移W;(PIO:page inner offset )
  • PBN+PIO共同组成物理地址

页表项地址

• 一般指的是页表中的(某个)页表项相对于页表起始地址的偏移量

地址变换机构

• 地址变换机构,记为AT:(Address Translation)
• 主要分为两类:基本地址变换机构和具有快表的地址变换机构

基本地址变换机构

结构图

映射过程

• 地址变换机构的任务是将逻辑地址转换为物理地址

• 地址变换借助于页表(page table,简单记为PT或T)实现

  • 将T视为可调用对象,约定页表项表达式:$T.P或T(P)$🎈
  • $T.P$访问的是:页表T中的页号为P的页表项PTI🎈(Page Table Item)

• 在系统中通常设置一个页表寄存器(PTR(page table register)),存放以下内容(2个字段):

  • 页表在内存的起始地址$F$🎈
  • 页表长度$M$🎈

• 进程未执行时，页表的始址和页表长度存放在本进程的PCB中

• 进程被调度执行时，才将页表始址和页表长度装入页表寄存器PTR中

  • 设页面大小为$L$🎈

  • 需要被计算物理地址的*某个字的*逻辑地址为$A$🎈

  • A对应的到物理地址E🎈

  • $A\to E$的变换过程如下(记为函数(映射)E:$E=E(A)$)

    • 假设逻辑地址、页号、每页的长度都是十进制数:

  • 由给定的逻辑地址A计算对应的页号和页内偏移量

    • 页号P🎈
      • $P=A/L$
      • (向下取整整除运算$P=floor(A/L)$)
    • 页内偏移量W🎈
      • $W=A\%L$
      • 描述的是某个页内的哪一个存储字
    • 也就得到了二元组逻辑地址A的$(P,W)$

  • 比较页号P和页表(每个进程都有自己的页表)长度M

    • 若$P⩾M$,则产生越界中断，
    • 否则继续执行
      • 即,$P<M(P\in [0,M-1]$表示访问的内容(所在的页面是从内存分配给了当前进程的,是可以合法访问的)

  • 页表中:

    • 记:页号P对应的页表项地址为$T.P$

    • $$T.P=F+P\times L$$

      • 类似于访问二维数组的第P行(页号充当一个行索引的角色)
      • 取出该页表项T.P块号字段内容:$b=T.P.b$,就是所求的物理块号
        • 通常,页表是给出的,计算出T.P后,就可以直接从页表中读取出来T.P页表项的内容(即,(物理)块号)

  • 最后计算$E=bL+W$,用得到的物理地址E去访问内存(具体的存储单元)

  • 以上整个地址变换过程均是由硬件自动完成的。

页表长度@页表项长度@页表大小

• 页表长度是指一共有多少页,
• 页表项长度(大小)是指页地址占多大的存储空间
• 页表大小:
  • 指页表占用的存储空间
  • 假设页表长度为N,页表项长度为L
  • 页表大小$L(PT)=N\times L$

例

• 例如，某计算机的页面大小L为1KB，页表中的页号2对应的物理块为b=8,
  • 问,该逻辑地址A = 2500的物理地址E?:
    • 取$1K=2^{10}=1024$
    • P= 2500/1K=2
    • W= 2500%1K =452
    • 又由已知的页表(页表项(逻辑块号,物理块号)二元组(2,8))
      • 即,查找得到页号P=2对应的物理块的块号b=8，
      • $E=8\times 1024+452=8644。$
    • Note:对于计算条件用十进制数和用二进制数给出，过程会稍有不同。

小结

• 页式管理只需给出一个整数就能确定对应的物理地址，因为页面大小L是固定的。
• 因此，页式管理中地址空间是一维的。
• 页表项的大小L,不是随意规定的，而是有所约束的。如何确定页表项的大小(主要讨论下限的计算)?
  • 页表项的作用是找到该页在内存中的位置。
  • 以32位逻辑地址空间、字节编址单位、一页4KB为例，
    • 地址空间内共有$2^{32}B/4KB=1M$页
    • 因此需要${\log }_{2}1M=20$位才能保证表示范围能容纳所有页面
    • 又因为以字节作为编址单位
      • 以字节作为编址单位,主要是指,把二进制串的位数不符合8的倍数的时候加上一个对齐因子$f\in [0,7],其中7=8-1$
      • 可以处理为向上取整
    • 所以,页表项的大小$L⩾\lceil 20/8\rceil =3B$.
    • 所以在这个条件下，为了保证页表项能够指向所有页面，页表项的大小应该大于等于3B,
    • 当然，也可选择更大的页表项
      • 让一个页面能够正好容下整数个页表项，进而方便存储(如取成4B,这样一页正好可以装下1K个页表项)，或增加一些其他信息。
• 下面讨论分页管理方式存在的两个主要问题:
  • ①每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低;
  • ②每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低.

ref

• 逻辑地址：CPU所生成的地址。
  • CPU产生的逻辑地址被分为 :
    • p （页号） 它包含每个页在物理内存中的基址，用来作为页表的索引；
    • d （页偏移），同基址相结合，用来确定送入内存设备的物理内存地址。
• 物理地址：内存单元所看到的地址。
  • 逻辑地址空间为$2^m$，且页大小为$2^n$，那么逻辑地址的高$p=m－n$位表示页号，低n位表示页偏移。
• 逻辑地址空间:由程序所生成的所有逻辑地址的集合。
• 物理地址空间:与逻辑地址相对应的内存中所有物理地址的集合,用户程序看不见真正的物理地址。
  • 注：用户只生成逻辑地址，且认为进程的地址空间为0到max。
  • 物理地址范围从R+0到R+max，R为基地址
  • 地址映射－将程序地址空间中使用的逻辑地址变换成内存中的物理地址的过程。
    • 由内存管理单元（MMU）来完成。
  • 分页逻辑地址 =P(页号).d(页内位移)
  • 分页物理地址=f(页帧号).d(页内位移)
  • $P=线性逻辑地址/页面大小$
  • $d=线性逻辑地址-P\times 页面大小$

具有快表的地址变换机构

结构图

• 

• 观察改过程,可以发现比其仅包含慢表的地址变换机构,包含快表的地址变换机构多了快表这条高速路径,快速计算出物理块号b,从而通过E=bL+W得到物理地址

  • 如果访问快表命中成功,则只需要访问一次主存(直接根据E从主存取数据)
  • 否则访问2次主存(一次慢表,一次物理地址从主存取数据)

过程

• 若页表全部放在内存中，则存取一个数据或一 条指令至少要访问两次内存:

  • 第一次是访问页表， 确定所存取的数据或指令的物理地址;
  • 第二次是根据该地址存取数据或指令。
  • 显然，这种方法比通常执行指令的速度慢了一半。
  • 为此，在地址变换机构中增设具有并行查找能力的高速缓冲存储器-快表TLB
    • 可以用相联存储器(简记为AM或CAM)来实现快表(TLB),
      • 相联存储器（associative memory)
      • 也称为按内容访问存储器（content addressed memory)
    • 用来存放当前访问的若干页表项，以加速地址变换的过程。
    • 与此对应，主存中的页表常称为慢表。

• 在具有快表的分页机制中，地址的变换过程如下:

  • CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
    • 若找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样，存取数据仅1次访存便可实现。
    • 若未找到匹配的页号，则需要访问主存中的页表(慢表)，读出页表项后，应同时将其存入快表，
      以便后面可能的再次访问。
      • 若快表己满，则须按特定的算法淘汰一 个旧页表项

相联存储器CAM🎈

• 相联存储器_百度百科 (baidu.com)

快表TLB🎈

• Translation lookaside buffer - Wikipedia

• 由地址转换过程可知，访存时先访问一次主存去查页表，再访问主存才能取得数据。

  • 如果缺页，那么还要进行页面替换、页面修改等，因此采用虚拟存储机制后，访问主存的次数更多了。

• 依据程序执行的局部性原理，在一段时间内总是经常访问某些页时，若把这些页对应的页表项存放在高速缓冲器组成的快表（TLB）中，则可以明显提高效率。

ref

• TLB:Translation Lookaside Buffer

  • 被翻译为

    • 页表缓存

    • 转址旁路缓存

    • 转译后备缓冲器

• 是CPU的一种缓存，由内存管理单元用于**改进虚拟地址到物理地址的转译速度**。

• 目前所有的桌面型及服务器型处理器（如 x86）皆使用TLB。

• TLB具有固定数目的空间槽，用于存放将虚拟地址映射至物理地址的标签页表条目。

• 为典型的结合存储（content-addressable memory，首字母缩略字：CAM）。

• 其搜索关键字(输入为虚拟内存地址，其搜索结果(输出)为物理地址。

• 如果请求的虚拟地址在TLB中存在，CAM 将给出一个非常快速的匹配结果，之后就可以使用得到的物理地址访问存储器。

• 如果请求的虚拟地址不在 TLB 中(未命中)，就会使用标签页表(分页表/慢表(普通页表))进行虚实地址转换

  • 而标签页表的访问速度比TLB慢很多。
  • 有些系统允许标签页表被交换到次级存储器，那么虚实地址转换可能要花非常长的时间。

• A translation lookaside buffer (TLB) is a memory cache that stores the recent translations of virtual memory to physical memory.

• It is used to reduce the time taken to access a user memory location.[1]

• It can be called an address-translation cache.

• It is a part of the chip’s memory-management unit (MMU).

• A TLB may reside between the CPU and the CPU cache, between CPU cache and the main memory or between the different levels of the multi-level cache.

• The majority of desktop, laptop, and server processors include one or more TLBs in the memory-management hardware, and it is nearly always present in any processor that utilizes paged or segmented virtual memory.

• The TLB is sometimes implemented as content-addressable memory (CAM).

  • The CAM search key is the virtual address, and the search result is a physical address.
  • If the requested address is present in the TLB, the CAM search yields a match quickly and the retrieved physical address can be used to access memory.
  • This is called a TLB hit.
  • If the requested address is not in the TLB, it is a miss, and the translation proceeds by looking up the page table in a process called a page walk.
    • The page walk is time-consuming when compared to the processor speed, as it involves reading the contents of multiple memory locations and using them to compute the physical address.
    • After the physical address is determined by the page walk, the virtual address to physical address mapping is entered into the TLB.
    • The PowerPC 604, for example, has a two-way set-associative TLB for data loads and stores.[2]
    • some processors have different instruction and data address TLBs.

• TLB 用于缓存一部分标签页表条目。

• TLB可介于CPU和 CPU缓存之间，或在CPU、缓存和主存之间，这取决于缓存使用的是物理寻址或是虚拟寻址。

  • 如果缓存是虚拟寻址，寻址请求将会直接从 CPU 发送给缓存，然后从缓存访问所需的 TLB 条目。
  • 如果缓存使用物理寻址，CPU 会先对每一个存储器操作进行TLB查寻，并且将获取的物理地址发送给缓存。两种方法各有优缺点。
    • 采用物理寻址的缓存的一种常见优化，是并行的进行 TLB 查寻和缓存的访问。
    • 所有虚拟地址的较低比特（例如，在虚拟内存系统中具有 4KB 标签页时，虚拟地址中较低的那 12 比特）代表的是所请求的地址在分页内部的地址偏移量（页内地址），
    • 且这些比特不会在虚拟地址转换到物理地址的过程中发生改变。
    • 访问CPU缓存的过程包含两步：
      • 使用一条索引去寻找CPU缓存的资料存储区中的相应条目，然后比较找到的CPU缓存条目的相应标记。
      • 如果缓存是用虚实地址转译过程中不变的页内地址来索引组织起来的，则可并行地执行TLB上虚实地址的较高比特(即分页的页间地址／页号）的转换与CPU缓存的“索引”操作。
      • 然后，从 TLB 获得的的物理地址的页号会发送给CPU缓存。
      • CPU缓存会对页号标记进行比较，以决定此次访问是寻中或是缺失。
      • 它也有可能并行的进行 TLB 查寻和CPU缓存访问，即使CPU缓存必须使用某些可能会在地址转译后发生改变的比特；
  • 参阅缓存条目的地址翻译一节，以获取关于虚拟寻址下缓存和 TLB 的进一步细节。

慢表

• 相应地把放在主存中的页表称为慢表(普通页表)(Page Table)。

• 在地址转换时，首先查找快表，若命中，则无须访问主存中的页表。

• 快表通常采用全相联或组相联方式。

• 每个TLB项由页表项内容加上一个TLB标记字段组成，

  • TLB标记用来表示该表项取自页表中哪个虚页号对应的页表项，
  • TLB标记的内容在
    • 全相联方式下就是该页表项对应的虚页号;
    • 组相联方式下则是对应虚页号的高位部分，
    • 而虚页号的用于选择TLB组的组索引

页表分级🎈

• 考虑到页表大小在某些情况下会占用较多的内存空间,采用页表分级的机制,解决这种可能出现的不利情况
• 现代的大多数计算机系统都支持非常大的逻辑地址空间(232 B~264 B)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。
  • 例如，对于一个 具有32位逻辑地址空间的分页系统，规定页面大小为4KB即$2^{12}$B,则在每个进程页表中的页表项数可达1 MB之多。
    • 假设每个进程多要能够访问所有内存单元(映射整个用户空间)
  • 又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用1 MB的内存空间，而且还要求是连续的。
  • 可以采用这样两个方法来解决问题:
    • ①对于页表所需的内存空间，可采用离散分配方式，以解决难以找到一块连续的大内存空间的问题;
    • ②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

页表分级特点🎈

• 所用的逻辑地址从整体看)并无不同,只是划分字段的时候有所不同
• 页表项占用的总空间也不会减小(反而会由索引层次的加深而引入更多空间开销)
• 但是不再要求连续,且为’多次性’提供基础
• 页表分级改善了页表存储方式和机构,对同一个逻辑地址做不同的划分,来适应多级页表下的地址变换过程

猜测

• 目前的水平有限,参考资料的详细程度有限,留下几个猜测性的观点(ToDo)
  • 页表分级的增长需要地址位数的支持,如果机器位数(寻址空间太短,则不足以支撑级数过多的多级页表结果)

两级页表(多级页表)

• 两级页表(Two-Level Page Table)

• 针对难于找到大的连续的内存空间来存放页表的问题，可利用将页表进行分页的方法

• 使每个页面的大小与内存物理块的大小相同,并为它们**进行编号,**即依次为0#页、1#页,…n#页，

• 然后离散地将各个页面分别存放在不同的物理块中。

• 同样，也要为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)

  • 在每个页表项中记录了页表页面的物理块号。

• 页表分页:保存页表(页表项形式)的页面

• 下面我们仍以前面的32位逻辑地址空间为例来说明。

  • 当页面大小为4KB时(12位)，若采用一级页表结构，应具有30-12=20位的页号，即页表项应有1M个;

    • 每个页面的容量为$4KB$,每个页表项大小为4B,则每个页面可以容纳$\frac{4KB}{4B}=1K=1024$个页表项

    • 保存页表项的页面需要$1K=\frac{1M}{1K}$个

  • 在采用两级页表结构时，再对页表进行分页，使每页中包含$2^{10}$（即1024）个页表项

    • (外层页)最多允许有$2^{10}$个页表分页(对应于$2^{10}$个页表项)

      • 外层页面数控制在一个

      • 否则使得顶级页表页数超过一个页面,不符合使用习惯(查询不便),超出这个数值需要再建立高级页表

    • 或者说，外层页表中的外层页内地址字段$P_2$为10位，外层页号$P_1$也为10位。

      • 此时的逻辑地址结构

      • 外层页号($P_1$)	外层页内地址$P_2$	页内地址d
        10bit	10bit	12bit

    • 页表中的页表项总是由:逻辑页号,物理块号 构成

      • 二元组形式(Index,blockAddress)🎈
        • 例如:对于多级页表中,外层页表的页表项结构:
          • (页表分页的页号(索引);页表分页的首地址)

​

• 由图可以看出，

  • (内层)页表的每个表项中，存放的是进程的某页在内存中的物理块号，

    • 0#页存放在1#物理块中，
    • 1#页存放在4#物理块中。

  • 外层页表的每个页表项中所存放的是某页表分页的首址，

    • 如0#页表存放在1011#物理块中。

• 我们可以利用外层页表和页表这两级页表来实现进程从逻辑地址到内存中物理地址的变换。

  • 为了方便实现地址变换，在地址变换机构中，同样需要增设一个外层页表寄存器，用于存放外层页表的始址，
    • 利用逻辑地址中的外层页号$P_1$作为外层页表的索引(字段值)，找到指定页表分页的始址(首址)
    • 再利用$P_2$作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号P
    • 用该块号P和页内地址d即可构成访问的内存物理地址。
    • 

• 上述对页表施行离散分配的方法，虽然解决了对于大页表无需大片连续存储空间的问题

  • 但并未解决用较少的内存空间去存放大页表的问题

  • 换言之，只用离散分配空间的办法并未减少页表所占用的内存空间。

• 能够用较少的内存空间存放页表的唯一方法是

  • 仅把当前需要的一批页表项调入内存，以后再根据需要陆续调入。

  • 在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对于页表则只需调入一页或几页。

  • 为了表征某页的页表是否已经调入内存，还应在外层页表项中增设一个状态位S,其值若为0，表示该页表分页不在内存中，否则说明其分页已调入内存。

  • 进程运行时，地址变换机构根据逻辑地址中的P,去查找外层页表：

    • 若所找到的页表项中的状态位为0，则产生一个中断信号，请求OS将该页表分页调入内存。

• 以某个需要40MB内存的进程(系统分配给该进程共40MB)的内存(页框)为例,体会进程的页表可能占用掉相当客观的内存

  • 页面大小L§=4KB
  • 设(基础级/底级)页表项长度L(PTI)=4B
    • 基础级页表指定是页表内的表项中的物理块号所指的块保存的内容是物理进程数据本身而不是其他级别的页表
      • 换句话说,内容就跟单级页表结构的页表项物理块所保存的数据是一致的
  • 那么页表长度(项数)$N(I)=\frac{40MB}{4KB}=10K$
  • 🎈保存页表的空间开销:页表大小$L(PT)=N(I)\times L(PTI)=40KB$
    • 也就是说40MB的进程页表开销要再占用40KB
    • 换算为页面大小,页表需要额外占用40KB/4KB=10个页面,比例为千分之一,但是积少成多
  • 而根据局部性原理,大多情况下,映射所需要的页表项都在页表的同一个页面中
    • 不需要(同时)将进程的所有的页表项全部载入到内存中

• 为了减少载入内存中的页表占用空间，我们进一步延伸页表映射的思想，就可得到二级分页,即使用层次结构的页表:

  • 承接上述的例子,将页表的10页空间也进行地址映射，建立上一级页表(高一级页表(类比容量大小权重))，用于存储页表的映射关系。
  • 这个方案就和当初引进页表机制的方式一样，实际上就是构造一个页表的页表，也就是二级页表。
  • 容易知道,这里对页表的10个页面进行映射只需要10个页表项，所以上一级页表只需要1页就已足够
    • 每一页可以存储$\frac{4KB}{4B}=1K$= 1024个页表项,1024>>10,绰绰有余
    • 一个一级页表项可以代表一个二级页表
    • 一个二级页表又可以代表(映射)1024个页面(0级页表)
    • 🎈页表的级别(数值)越低,页表的每一项代表的容量就越大
      • 比如,一个K级页表的每一项代表的容量相当于一张K+1级的页表(整张表)的容量
    • 可见,类似于计数进位制(比如十进制,百位权重为$10^2$,十位权重$10^1$,个位权重为$10^0=1$)

多级页表

• 对于32位的机器，采用两级页表结构是合适的，但对于64位的机器，采用两级页表是否仍然合适，须做以下简单分析。
  • 如果页面大小仍采用4KB即$2^{12}$B,页内地址占用12位,那么还剩下64-12=52位
  • 假定仍按物理块的大小($2^{12}$位)来划分页表(每个页面容纳1K个页表项),1M页表项需要1K=$2^{10}$个页面,需要占用10个二进制位区分它们(页表分页)，则将余下的52-10=42位用于外层页号。
  • 此时在外层页(需要载入内存)表中可能有4096G个页表项，要占用4096*4=16384GB的连续内存空间。
    • 这样的结果显然是不能令人接受的。
    • 因此，必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。
    • 对于64位的计算机，理论上支持$2^{64}B=2^{24}TB$规模的物理存储空间，
      • 如此巨大的空间,即使是采用三级页表结构也是难以办到的，
      • 而在当前的实际应用中也无此必要。
      • 故在近两年推出的64位OS中，把可直接寻址的存储器空间减少为45位长度(即$2^{45}=32TB$)左右，这样便可利用三级页表结构来实现分页存储管理。

多级页表下的内存地址结构

• 1级(顶级)页号字段(页目录号)	2级页号字段	…	k级字段	页内偏移

• 在进程执行时，只需要将这一页的上一级页表调入内存即可

  • 进程的页表和进程本身的页面可在后面的执行中再调入内存。

  • 根据上面提到的条件(32位逻辑地址空间、页面大小4KB、页表项大小4B，以字节为编址单位)，我们来构造一个适合的页表结构。

  • 页面大小为4KB

    • 则页内偏移地址为${\log }_{2}4K=12$位，
    • 页号部分(字段)占用剩下的bit,即32-12=20位

  • 若不采用分级页表,且映射全部的地址空间,共有$2^{20}$个页面,相应地需要$2^{20}$个页表项记录,每个页表项又是占用4B,页面大小为4KB，则仅这些页表项页表就要占用$2^{20}\times 4B/4KB=1024$ 页，这大大超过了许多进程自身需要的页面，对于内存来说是非常浪费资源的

  • 若不把这些页表放在连续的空间里，则需要一张索引表来告诉我们第几张页表该上哪里去找，这能解决页表的查询问题，且不用把所有的页表都调入内存，只在需要它时才调入(下节介绍的虚拟存储器思想)，因此能解决占用内存空间过大的问题。

  • 🎈为查询方便，顶级页表(代表力权重最高的页面)最多只能有1个页面(一定要记住这个规定),

    • 对于本例而言,无论划分为多少级页表,顶级页表(1级页表)总共可以容纳4KB/4B = IK个页表项，它占用的地址位数为${\log }_{2}1K=10$ 位

    • 而之前已经计算出页内偏移地址占用了12 位，因此一个32位的逻辑地址空间就剩下了10 (32-10-12=10)位，正好使得二级页表的大小在一页之内， 这样就得到了逻辑地址空间的格式

    • 1级页号	2级页号	页内偏移
      10	10	12

tips

• 求解这类问题,通常先计算出(IPP,Blocks,N)
  • 每页面可以保存多少个页表项IPP(Items per page)
    • 每页容量L§
    • 每个表项大小L(I)
    • $IPP=\frac{L(P)}{L(I)}$
  • 逻辑地址空间对应多少个页表项(页面数或块数)Blocks
  • 所有(一级)页表共占用的页面数$N=\frac{Blocks}{IPP}$

例

• 某计算机采用二级也报的分页存储管理方式

  • 按照字节编址

  • 页面大小为L§=$2^{10}$B

  • 页表项大小L(I)=2B

  • 逻辑地址空间大小为$2^{16}$

  • 逻辑地址结构为:

    • 页目录号	页号	页内偏移

  • 表示整个逻辑地址空间的页目录表中包含的表项个数N至少是?

• 分析:

  • 每个页面可以容纳的表项数IPP=$\frac{2^{10}}{2}=2^9$
  • 逻辑地址空间需要$Blocks=2^{16}$页面
  • $N=\frac{2^{16}}{2^9}=2^7=128$

例

• 在采用二级页表的分页系统中,cpu页表机制寄存器中的内容是:
• 当前进程的一级页表(顶级页表)的起始物理地址

有效访存时间

• 有效访问时间(Effective Access Time,EAT):访问内存的有效时间

• 可以用来分析引入快表后访存性能相对于仅有慢表的情况下的提升情况.

• 从进程发出指定逻辑地址的访问请求，以下过程所需要花费的总时间，称为内存的有效访问时间(Effective Access Time,EAT)。

  • 经过地址变换得到物理地址，
  • 根据物理地址到在内存中找到对应的实际物理地址单元
  • 取出数据

• 假设访问一次内存的时间为t,在基本分页存储管理方式中，有效访问时间分为

  • 第一次访问内存时间（即查找页表对应的页表项所耗费的时间）
  • 第二次访问内存时间(即将页表项中的物理块号与页内地址拼接成实际物理地址所耗费的时间)之和：

  $$EAT=t+t=2t$$

  • 在引入快表的分页存储管理方式中，通过快表查询，可以直接得到逻辑页所对应的物理块号，由此拼接形成实际物理地址，减少了一次内存访问，缩短了进程访问内存的有效时间。

    • 但是，由于快表的容量限制，不可能将一个进程的整个页表全部装入快表，所以在快表中查找到所需表项存在着命中率的问题。
    • 所谓命中率，是指使用快表并在其中成功查找到所需页面的表项的比率。

  • 设:

    • $\delta$表示查找快表所需要的时间，

    • $a$表示命中率，

    • $t$表示访问一次内存所需要的时间

    • 每次放存都先访问一次快表

      • 如果没有命中,则需要访问两次内存
        • 这种情况下,不命中快表的访存需要$\delta +2t$
      • 如果相联存储器中的快表和内存中的慢表同时访问,那么在不命中快表的情况下,需要的时间只有$2t$

    • 这样，在引入快表的分页存储管理方式中，有效访问时间的计算公式即为：

      • 引入快表后的内存有效访问时间分为查找到逻辑页对应的页表项的平均时间
        • $t_a=a\delta +(1-a)(\delta +t)$
      • 以及对应实际物理地址的内存访问时间$t$
      • $ETA=t_a+t$

    • $$\begin{gathered} EAT=a(t+\delta )+(1-a)(2t+\delta ) \\ 或 \\ EAT=t_a+t=[a\delta +(1-a)(\delta +t)]+t \\ 化简后都等于2t-at+\delta \\ 即ETA=2t-at+\delta =t(2-a)+\delta \end{gathered}$$

    • 在命中率极高的情况下,$ETA\approx t+\delta$,相比于基础地址转换机构的时间$t_b=2t$,由于访问快表非常快,所以$\delta$很小那么最好的情况下可以少掉一次访存时间$|\Delta |=|(ETA-t_b)|\to t$