一、基本分页存储管理

1.1、分页思想

• 分页思想
  • 将内存空间划分为一个个大小相等的分区，每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块” 。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号” 、“物理块号” )页框号从0开始。
  • 将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。每个页面也有一个编号，即“页号”,页号也是从0开始。
    (注:进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片)
  • 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框(离散)中。也就是说，进程的页面与内存的页框有一一对应的关系。

• 无外部碎片，会产生内部碎片，如果页面大小确定，那么只需要知道逻辑地址就可以自动计算其他信息，因此页式管理的地址是一维的。

1.2、地址转换和计算

• 如何实现地址的转换：

  • 动态重定向，需要重定向寄存器存放装入模块(页)的起始位置

  • 用户进程的每个页装入前的逻辑地址经动态重定向转为各个物理地址

    

• 地址转换的计算

  

  • 结论:如果每个页面大小为\(2^KB\)，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号
  • 地址结构包含两个部分:前一部分为页号，后- 部分为页内偏移量W。在上图所示的例子中，地址长度为32位，其中0~11位为“页内偏移量”，或称“页内地址”; 12~31 位为“页号”。
  • 如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是\(2^K\)个内存单元
  • 如果有M位表示“页号”，则说明在该系统中一个进程最多允许有\(2^M\)个页面

1.3、页表数据结构

• 数据结构：页表

  • 一个进程一张页表

  • 每一页对应一个页表项(页号+块号)

  • 页表记录进程页面和实际存放内存块之间的对应关系：进程-页表-内存

    

    

二、基本地址变换机构

• 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

• 通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M

  • 进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中
  • 当进程被调度时，操作系统内核会把它们放到页表寄存器(PTR)中。

  

  • 设页面大小为L，逻辑地址A到物理地址E的变换过程如下:
    • ①计算页号P和页内偏移量W (如果用十进制数手算，则P=A/L, W=A%L)
    • ②比较页号P和页表长度M，若\(P>M\)，则产生越界中断，否则继续执行。(注意: 页号是从0开始的，而页表长度至少是1，因此P=M时也会越界)
    • ③页表中页号P对应的页表项地址=页表起始地址F+页号P页表项长度，取出该页表项内容b,即为内存块号。(页表长度：总共有几个页:页表项长度：每个页表项占多大的存储空间;页面大小：一个页面占多大的存储空间)
  • ④计算E=b*L + w,用得到的物理地址E去访存。( 如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了)

三、具有快表结构的变化机构

3.1、局部性原理

• 时间局部性
  • 如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;
  • 如果某个数据被访问过，不久之后该数据很可能再存放程序中定次被访问。(循环)
• 空间局部性
  • 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)
  • 如存放变量的存储单元和计算变量的存储单元

3.2、快表

• 快表
  • 又称联想寄存器(TLB），是一种访问速度比内存快很多的高速缓冲存储器(不在内存)，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。
  • 由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到90%以上。
• 地址查询
  • ①CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
  • ②如果找到匹配的页号(快表+对应存储单元)
    • 说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
  • ③如果没有找到匹配的页号(快表+页表+对应存储单元)
    • 则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，再访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存
    • 注意:在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换

• 访问一个逻辑地址的平均耗时T
  • 查询快表的时间\(t_1\),访问一次内存的时间\(t_2\),快表命中率m
  • 不支持快慢表同时查找的系统(默认)：\(T=(t_1+t_2)*m+(t_1+2*t_2)*(1-m)\)
  • 支持快慢表同时查找的系统：\(T=(t_1+t_2)*m+2*t_2*(1-m)\)
  • 不支持快表的系统：\(T=2*t_2\)

四、两级页表

4.1、单级页表存在的问题

• 问题一:页表必须连续存放，因此当页表很大时，需要占用内存中很多个连续的页框。
• 问题二:没有必要让整个页表常驻内存(虚拟存储技术)，因为进程在一段时间内可能只需要访问某几个特定的页面。

4.2、两级页表

• 将长长的页表进行分组，使每个内存块刚好可以放入一一个分组

  • 如图：32位逻辑存储空间，页面地址\(4kB=2^{12}\),占12位，页面为20位，共\(2^{20}\)个页面，每个页面长度是\(\frac{4KB}{4B}=2^{10}=1024\)
  • 将\(2^{20}\)的长页表分组为\(2^{10}\)个长度为\(2^{10}\)的小页表

  

• 为离散分配的页表(得到的小页表)再建立一张页表，称为页目录表，或称外层页表，或称顶层页表

  

两级页表查找物理地址

• ①按照地址结构将逻辑地址拆分成三部分
• ②从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一-级页表在内存中的存放位置
• ③根据二级页号查表，找到最终想访问的内存块号
• ④结合页内偏移量得到物理地址