5 存储管理

5.4 分页存储管理

5.4.1 纯分页存储管理

a.页（页面）和物理块（帧）

分页存储管理，把进程的地址空间划分为大小相等的片段，成为页或页面。相应地，内存空间也分成与页面相同大小的若干块，成为物理快或帧。

b. 页面大小

页面大小通常在 512k~4k，大小必须适中。Why?（四个因素刘乃琦 P84）
因为：若页面太小，一方面课时内存碎片小，减少了内存碎片的总空间，有利于提高内存的利用率；但另一方面，也会使每个进程要求较多的页面，从而引起页表过长，占用大量内存；此外，还会降低页面换进换出的效率。若选择较大的页面虽然可减少页表的长度，提高页面换进换出的效率，但却又会使页面
碎片增大。因此，页面大小应选择适中。

页面碎片： 分页方式中也会出现内存碎片，它们都分布在每个作业的最后一个页面内部，故称为页面碎片。

c. 逻辑地址结构

页面大小为 2¹⁰=1K
举例：逻辑地址 5000
最多可以有 2⁶=64 页 可转换为 4*1024+904

5.5 存储扩充技术

覆盖是指一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。
覆盖技术的实现是把程序化分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一快内存区域。程序段先保存在磁盘上，当有关程序段的前一部分执行结束后把后续程序调入内存，覆盖前面的程序段。

覆盖不需要任何来自操作系统的特殊支持，可以完全由用户实现，即覆盖技术是用户程序自己附加的控制。覆盖技术要求程序员提供一个清楚的覆盖结构，即程序员要把一个程序化分成不同的程序段，并规定好他们的执行和覆盖的顺序。操作系统则根据程序员提供的覆盖结构，完成程序段之间的覆盖。

覆盖可以有编译程序提供支持：被覆盖的块是由程序员或编译程序预先（在执行前）确定的。总之，覆盖可以从用户级彻底解决内存小装不下程序的问题。

覆盖技术要求用户清楚地了解程序的结构，并制定各程序段调入内存的先后次序，以及内存中可以覆盖掉的程序段的位置等。对用户是不透明的。因此通常用于系统程序的内存管理上，因为系统软件设计者容易了解系统程序的覆盖结构。

例如：把磁盘操作系统分为两部分，一部分是操作系统中经常用到的基本部分，它们常驻内存且占用固定区域，另一部分是不太经常使用的部分，他们存放在磁盘上，当调用它们时才被调入内存覆盖区。

5.5.2 交换技术

对换——指把内存中占时不能运行的进程或暂时不用的程序和数据换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据，换入内存。

如果对换是以整个进程为单位，称之为“整体对换”或“进程对换”。这种对换被广泛地应用于分时系统；如果对换是以“页”或“段”为单位，则分别称之为“页面对换”或“分段对换”，又称为“部分对换”。这种对换方法是实现请求分页及请求分段式虚拟存储器的基础。

与覆盖技术相比，交换技术的特点是交换过程对用户是透明的，但需要更多的硬件支持。

5.5.3 虚拟存储技术

解决内存不足：

a．加内存条。
b．覆盖技术、整体对换
c．虚拟技术

虚拟存储器的基本概念

1） 常规内存管理方式的特征

a． 一次性
b． 驻留性

一次性和驻留性是许多不用或暂时不用的程序（数据）占据了大量的内存空间，将使一些需要运行的作业无法装入运行。现在的问题是：一次性、驻留性是否是存储器管理所必需的。

2） 局部性原理

局限性（时间局限性、空间局限性）局部性原理（principle of locality）：在一个作业运行的某一段时间，它所访问的地址空间往往只集中在某几页 它所访问的地址空间往往只集中在某几页，而不是整个程序的所有部分都具有平均的 而不是整个程序的所有部分都具有平均的访问概率，这种现象称为局部性原理 这种现象称为局部性原理。

3） 虚拟存储器的引入
当一个作业的地址空间很大时，不能别全部装入内存，但基于局部性原理，允许只将当前要运行的那部分程序和数据先装入内存便启动运行，其余部分仍驻留在外存上，在需要时，在通过调入功能和置换功能将其调入内存。

Def：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

在多道系统中使用虚拟存储技术，不管物理内存空间多大，系统都可以为每个用户的作业提供很大的独立的虚拟空间。例如 linux 操作系统中可以为每个用户作业提供高达 4G 的虚拟空间。

虚拟存储空间中的地址称为虚拟地址。虚拟地址空间大小由虚拟地址的长度决定。由于虚拟空间比物理内存的容量大的多，所以系统提供的虚拟地址的长度大于主存的绝对地址的长度，例如在80x86 中绝对地址是 32 位的，而虚拟地址是 46 的。

4） 虚拟存储器的特征

a． 多次性
b． 对换性
c． 离散性：多次性和对换性必须建立在离散分配的基础上，故虚拟存储管理必须建立在离散分配系统基础上。

5.5.4 请求式分页存储管理

1. 数据结构 数据结构——页表（PMT）
   在请求分页系统中的页表，时在分页系统的页表的基础上增加如下几项：
   页号：

物理块号
状态位
访问字段
修改位
外存地址

状态位：用于指出该页是否已调入内存
访问字段：用于记录本页在一段时间内别访问的次数，提供给置换机构参考
修改位：表示该页在调入内存后是否被修改过，由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需要将该页写回到外存上；否则，必须将该页重写到外存上，以保证外存中所保留的始终是最新的副本。
外存始址：指出该页在外存上的地址，供调入该页时使用。

2.页面淘汰算法
👉优化 or 最佳淘汰算法（OPT）：淘汰将永不再使用的页面，或最长时间内不再访问的页面。（无法实现，仅作为标准）
👉最近最就不用算法（LRU:Least Recently Used Replacement）：当需要置换一页面时，选择在最近一段时间内最久不用地页面予以淘汰。
👉近似 LRU 算法——NRU（not Recently Used）
👉FIFO 算法：淘汰最先进入内存的页面，即在内存中驻留时间最长的页面。
缺点：
a. 内存利用率不高——由于该算法基于 Cpu 按线性顺序访问的地址空间的，而许多时候，cpu 不是按线性顺序访问地址空间，如执行循环时，那些在内存中停留时间长最长的页往往是经常被访问的页。
b. 会出现异常现象——Belady 现象：一般来说，内存帧越多，一个作业发生缺页的次数就越少。（如果给一个进程分配了它所需要的全部页面，则不会发生缺页现象）但 Belady 举出了反例，例如使用 FIFO 算法时，在未给进程或作业分配足它所需要的页面时，有时会发生分配的页面数越多，缺页次数反而增加的奇怪现象。这种现象称为 Belady 现象。