操作系统原理学习笔记（二十二）-分页存储管理方式

操作系统原理学习笔记目录

分页存储管理的基本方法

• 页面：
  • 将进程的逻辑地址空间分成若干页，并进行标号：第0页、第1页...
  • 将内存的物理地址空间分成若干块，并进行标号：0#块，1#块...
  • 进程分配内存时，以块为单位，将进程若干页装入多个不相邻的物理块中。
  • 进程最后一页剩余的空间，被称为“页内碎片”
• 页面大小：
  • 页面过大，可以减少页表长度，提高页面交换速度，但会使页内碎片增大。
  • 页面过小，可以减少业内碎片大小，提高内存利用率，但会导致页表过长，占用大量内存，降低交换效率。
  • 页面大小应为2的幂次方，通常为1KB~8KB。
• 地址结构：
  • 包含页号P与偏移量W，在32位逻辑地址空间中，页号一般占20位，偏移量占12位。
  • 页号：
    • 页号若有20位，则地址空间最多分成2²⁰，即1M页。
  • 偏移量：
    • 也称位移量，是页内地址。
    • 偏移量有12位，则一页的大小为2¹²，即4KB。
  • 若知道逻辑空间地址A，与页面大小L，则：
    • 页号P为：[A/L]（整除，向下取整）。
    • 偏移位W为：[A] mod L。
    • 如，A为2170B，L为1KB，则P=2，W=122，第三页，页号为2，偏移位为122。
• 页表：
  • OS为各进程建立的页面映像表，将页号与块号对应起来。
  • 表项中的存取控制字段，如果为1位，是读写/无权限，如果是2位，是读写/读/执行等。
  • 写入只读的存储块时，将引起中端。

地址变换机构

• 借助页表，实现逻辑地址到物理地址的转换。
• 由于页内地址与物理地址对应，因此只要将逻辑地址中页号转为内存中物理块号即可。
• 基本的地址变换方式：
  • 实现方式：
    • 使用专门寄存器实现。
    • 页表存放在内存中。
      • 存放在寄存器会需要很多寄存器，成本高，因此存放于内存中。
    • 用页表寄存器(Page-Table Register, PTR)存放页表在内存中的起始地址与长度。
    • 页表始址与长度存在PCB中，仅在调度到本程序时才将其装入PTR。
    • 单处理机环境下，通过一个PTR即可运行多个进程。
  • 实现过程：
    • 进程访问某逻辑地址的数据时，分页地址变换机构将有效地址（相对地址）分为页号与页内地址，再以页号索引检索页表。
    • 查找由硬件执行，检索前：
      1. 将页号与页表长度进行比较，页号≥页表长度，则产生地址越界中断。
      2. 若未越界，则将页表始址与页号和页表项长度的乘积相加，得到该表项在页表中的位置。
      3. 从中得到该页物理块号，装入物理地址寄存器中。
      4. 同时，将有效地址寄存器直接跑每个页内地址送入物理地址寄存器的块内地址字段中。
    • 本过程于P150有图示。
• 具有块表的地址变换机构：
  • 基本地址变换机构在进程访问内存时，第一次需要将逻辑地址转为物理地址，第二次访问时才能获取数据，虽然提高了存储器空间利用率，但将计算机的处理速度降低了一半。
  • 在基本地址变换机构中，增加一个具有并行查询能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或“快表”，在IBM系统中又被称为TLB(Translation Look aside Buffer)。
  • TLB用来存放当前访问的页表项。
  • 在进行检索时，先检索TLB中是否存有该页号对应的物理块号，若无，再检索内存中的页表。
  • 当TLB满时，OS需要找到一个存在时间长且被认为不再需要的页表项，与新的页表项对换。
  • 由于成本问题，TLB一般只存放16~512个页表项，但已能满足大部分需求，将基本地址变换机构造成的速度损失降低至10%。

访问内存的有效时间

• 内存的有效访问时间(Effective Access Time, EAT)：从进程发出逻辑地址访问请求，经过地址变换，到内存物理块中取出数据的时间。
• 基本地址变换机构EAT：EAT = t+t = 2t。
  • 两个t分别为查表的时间，与获取数据的时间。
• 快表的地址变换机构EAT：EAT = a*m + (t+m)(1-a) = 2t + m - t*a
  • 其中，a为查找命中率，m为快表查询时间。
  • 查找命中率，是查找TLB表时成功的几率，当成功时，无需在内存中查询页表。

两级和多级页表

• 为了解决页表占据连续的大内存空间问题，可采用两种办法：
  • 页表离散存储。
  • 仅在内存中保留当前需要的页表。
• 两级页表(Two-Level Page Table)：
  • 实现页表离散存储。
  • 用外层页表(Outer Page Table)作为离散分配页表的页表。
  • 结构为：外层页号-外层业内地址-页内地址。
  • 将页表再进行分页，使得每个页面与物理块大小相同，并为其标号：0#页、1#页...，之后可将各页面离散的存储在不同物理块中。
  • 以32位逻辑地址空间为例，页表大小为12位时：
    • 采用一级页表结构，具有20位的页号，即1M个页表。
    • 采用两级页表，若每页包含10位页表项，则外层页号为10位。
  • P153页有图示。
  • 个人的理解：
    • 外层页内地址，存放在物理块中，并指向内存空间中的不同地址。
    • 外层页号保存的是物理块的地址。
    • 即，检索时，先在外层页表找到外层页内地址存放的物理块，再从物理块中找到内存物理地址。
• 多级页表：
  • 对于32位机器，二级页表已经够用。
  • 但对于64位机器，页面大小为12位时，还有52位的空间，若与32位机器一样，用10位划分页表，则还有42位用于外层页号，过于庞大。
  • 对外层页表再分页，形成多级页表，即可避免上述问题。
  • 现代64位机器中，一般将可直接寻址的存储器空间减少至45位，再使用三级页表结构实现分页存储管理。

反置页表

• 概念：
  • 一般的页表是按页号排序的，页表项内容是物理块号。
  • 反置页表是为每一个物理块设置一个页表项，按物理块编号排序，页表项内容是页号及其隶属进程标识符。
  • 在IBM公司推出的系统中广泛使用，如AS/400、IBM RISC System、IBM RT等。
• 地址变换：
  • 根据进程标识符与页号，检索反置页表，若找到，则其序号就是物理块号。
  • 若检索不到，则表示此页并未装入内存：
    • 不具备请求调页功能的存储器管理系统，会表示地址出错。
    • 具备请求调页功能的，则产生请求调页中断，系统把此页调入内存。
• 特点：
  • 一个64MB内存的机器，若页面大小为4KB，则反置页表占用64KB内存。
  • 但该表只包含调入内存的页面，因此还需为每个进程建立外部页表(External Page Table)，该表与传统页表一样，且仅在发现页面不在内存时会被使用。
  • 内存容量很大时，页表项数目也会很大，为此，可采用Hash算法进行检索。
    • 但Hash算法可能产生“地址冲突”，即多个逻辑地址被映射到一个Hash表项上，后续部分会对其处理方式进行讲解。