一、虚拟存储技术

1. 理论依据：程序的局部性原理

在一段较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。其具体表现为：

• 时间局部性(Temporal Locality) 一条指令的执行和下次执行、一个数据的访问和下次访问，都集中在一个较短的时间内。

• 空间局部性(Spatial Locality) 当前指令和将要执行指令、当前访问的数据和将要访问的数据，都集中在一个较小的区域内。

2. 常规存储管理技术

特点

• 一次性

  • 要求将作业全部装入内存后才能运行

• 驻留性

  • 作业装入内存之后，一直驻留内存，直至作业运行结束

问题

• 难以满足大作业的运行要求

  • 若作业的逻辑空间大于实际物理内存，则作业无法运行。

• 难以满足大量作业并发运行的要求

  • 多道程序度严重受限于实际物理内存，并发程度较低。

• 某些已装入内存的代码利用率低

3. 理想存储管理技术

• 程序不受实际物理内存空间的限制

• 并发程序高，用以提高CPU的利用率

程序不必完全装入内存即可执行

4. 程序运行特点

• 程序在执行时，除了少数部分的转移和过程调用外，在大多数情况下仍然是顺序执行的。

• 过程调用将程序的执行轨迹从一个部分迁移到另一部分，但通常过程调用的深度不超过5，即在某段时间内程序的执行仍局限在某些函数内。

• 程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。

• 程序中存在相当多特定数据结构的操作，如数组操作，往往局限在较小范围内。

5. 基本思想

• 在程序装入时，只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。

• 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存(称为缺页或缺段)，则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。

• 另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。

6. 虚拟存储器

概念

具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

• 虚拟存储器的实际容量由内存容量和外存容量之和所决定

• 运行速度接近于内存速度,而每位的成本却又接近于外存

特征

• 离散性：程序在内存中离散存放

• 局部性：进程无需全部驻留内存，只需载入必要的进程空间

• 对换性：允许进程在运行过程中换入、换出

• 虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量

7. 需要的硬件支持

• 相当数量的外存

• 一定容量的内存

• 请求分页或分段的页表或段表机制

• 缺页或缺段机构

• 地址变换机构

8. 常用的虚拟存储技术

• 请求分页存储管理

• 请求分段存储管理

• 请求段页式存储管理

二、简单分页系统的问题

页面与页框的大小

• 分页系统中，页面 = 页框。页框的大小由计算机的硬件逻辑定义。通常，页框大小是2的幂次个字节，通常在512B-4KB，最新64位机可达4MB。

• 将页框大小设置为2的幂次，可以简化处理机中地址变换硬件逻辑的设计与实现。

• 影响页面与页框大小的主要因素：页内零头、地址转换速度和页面交换效率。

• 较小的页面有利于减少页内零头，从而有利于提高内存的利用率。然而，较小的页面也将导致页表过大，从而降低处理机访问快表时的命中率。

• 块越大，内/外存之间的数据交换效率越高。因此，对于支持交换技术的系统，较大的页面有利于提高页面换进/换出内存的效率。

庞大的页表组织

• 大逻辑地址空间，页表非常大，需要占用相当大的内存空间。

• 比如，32位逻辑地址空间，假设页面大小为4KB(212)，则4GB(232)的逻辑地址空间将被划分成220个页面。

• 若采用一级页表，则其内将包含1M(220)个页表项。若按字节寻址，一个页表项占4B，则一级页表需要占用4MB(222)内存空间。

• 不可能将4MB的页表保存在一个连续区中。

• 那么，如何处理大页表的存储与检索呢？

• 更进一步，64位逻辑地址空间又该如何处理？

三、二级页表

庞大页表的离散存储解决方案——多级页表

1. 二级页表

• 将一个大页表全部保存在内存中。
• 将页表进行分页，并离散地将各个页面存放在内存的多个页框中。
• 建立外层页表(Outer Page Table)，记录页表页面的页框号。
• 逻辑地址结构

2. 地址转换流程

3. 示例

某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2¹⁰字节，页表项大小为2字节，逻辑地址结构为：

逻辑地址空间大小为2¹⁶页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是多少？

答案

逻辑地址空间的大小：2¹⁶页，页的大小是2¹⁰=>逻辑地址空间是2²⁶

表中三项一共26位，页内偏移位占10位，要让页目录号最少，就要让页号最多，而页号最多只能占据一页的容量，也就是2¹⁰/2=2⁹，也就是9位，最后26-10-9=7，2⁷=128

4. 80x86硬件分页地址转换

32位逻辑地址空间、4KB页面、4B页表项

如何将逻辑地址0x20021406转换为物理地址？

• 0x20021406转化为二进制，并进行划分

  • 0010 0000 0000 0010 0001 0100 0000 0110

• 顶级页表字段

  • 0x80，用于选择顶级页表的第0x80表项，指向二级页表

• 二级页表字段

  • 0x21，用于选择二级页表的第0x21表项，指向逻辑地址所在页框

• 页内偏移地址字段

  • 0x406，逻辑地址在页框内的偏移量

5. 二级页表地址转换示例

32位逻辑地址空间、4KB页面、4B页表项、4197721的物理地址？

• 4197721转化为二进制，并进行划分

  • 0100 0000 0000 1101 0101 1001

• 顶级页表字段

  • (01)₂，用于选择顶级页表的第1表项，指向二级页表202

• 二级页表字段

  • (0)₂，用于选择二级页表的第0表项，指向逻辑地址所在页框(505)₁₀=(1 1111 1001)₂

• 页内偏移地址字段

  • (1101 0101 1001)₂逻辑地址在页框内的偏移量

• 物理地址：1 1111 1001 1101 0101 1001

6. 多级页表

• 对于某些机器，二级页表也可能非常大。可以采用多级页表，对外层页表再进行分页，将各个页面离散地存储到不相邻接的物理页框中。——三级页表

• 对大页表而言，多级页表方法消除了对较大的连续内存空间的需要，但未解决大页表占用较大的内存空间的问题，建立多级页表反而会增加额外的存储空间。

• 页表的级数越多，地址转换过程越复杂，转换的速度也越慢。

• 4级以上的页表机制很少采用。

四、快表

1. 快表的引入

• 在分页系统中，处理机每次存取指令或数据至少需要访问几次物理内存？

  • 第一次访问页表
  • 第二次存取指令或数据

• 为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表、TLB(Translation Lookaside Buffer)，或联想存储器(Associative Memory)

2. 快表的工作原理

• 快表的工作原理类似于系统中的数据高速缓存(cache)，其中专门保存当前进程最近访问过的一组页表项。

• 根据局部性原理，在一个很短的时间段内，程序的执行总是局部于某一个范围。即，进程最近访问过的页面在不久的将来还可能被访问。

3. 与快表有关的地址转换

• 通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项。

• 若快表中存在该表项，称为命中(hit)，取出其中的页框号，加上页内偏移量，计算出物理地址。

• 若快表中不存在该表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应页框号。同时，更新快表，将该表项插入快表中，并计算物理地址。

4. 具有快表的地址转换流程

1. 根据逻辑地址分离出页面号和页内偏移

2. 检查页面号是否非法，若非法则产生越界错误，否则继续

3. 根据页面号检索快表(由硬件实现)，如果找到则获得对应的页框号，转到第5步

4. 如果在快表中未找到，则在内存页表中检索，并将其结果载入快表，替换未使用或者很久不用的表项

5. 检查访问控制字段，确定访问是否合法

6. 用页框号乘以页面大小获得其对应的起始地址，并将其送入物理地址的高端

7. 将页内偏移送入物理地址的低端，即形成完整的物理地址

5. 快表提高内存访问速度示例

有一页式系统，其页表存放在主存中：

1. 对主存的一次存取需要1.5μs，试问实现一次页面访问的存取时间是多少？

2. 如果系统有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略，试问此时的存取时间是多少?

答案

若页表存放在主存中，则要实现一次页面访问需两次访问主存：第一次是访问页表，确定所存取页面的物理地址。第二次根据该地址存取页面数据。

1. 页表在主存的存取访问时间：1.5*2=3μs

2. 增加快表后的存取访问时间：0.85*1.5+(1-0.85)*2*1.5=1.725μs