操作系统知识点——内存管理（三）

一、虚拟内存管理

（一）虚拟内存概念

1、局部性原理

通常情况下，在一个较短时间内仅使用一部分程序代码（即子集），其使用的内存空间被限制在一个特定区域内（即局部存储），这反映了程序执行中的局部性特征）。

时间集中性：一个指令的运行与其再次运行以及一个信息的获取与其再次获取之间的时间间隔都比较短

空间局部性质。相邻的一组指令及其所访问的数据与其附近的同类数据主要集中在同一个较小的空间范围内

2、虚拟内存定义

当程序开始加载时，在内存中逐步调入一部分程序代码。其余部分暂时保留在外存，在启动后会随着程序运行而被加载出来（请求调入）。在程序运行期间，当系统试图访问内存中的信息但发现该信息不在当前内存块中时（请求调出），这时操作系统会根据需求自动将所需的代码或数据从外存调入到内存中进行处理（置换功能）。另一方面的操作系统会负责将当前不活跃的任务或数据从内存中移出并发送到外存。（逻辑扩展）通过这种方式实现了对外部存储资源的高效利用，并形成了逻辑上扩展了的虚拟存储空间体系。（简称虚存）

3、虚拟内存特征

它将程序运行时所需的地址空间与系统的可用存储区区分开来，并非简单地将所有资源混为一谈。这种机制使得开发人员无需关注系统实际占用的物理内存大小，在指定的应用程序运行区域内自由编排代码位置。此外，在现代计算架构中，默认情况下虚拟存储器的最大容量也受到系统设计所限，并非理论上可无限扩展。

分散状态。程序以分散的方式存在于内存中。（这种特性并非仅限于虚拟内存系统；而基本的分页与分段同样具备这一特性）

多次性。一个作业可以多次调入内存。

对换性（交换性）作业在运行过程中可以换入、换出。

虚拟性：通过理论上的内存扩展使用户能够使用的空间远超实际内存容量。

4、虚拟内存的软硬件支持

1、要有相当数量的外存，足以存放多个用户程序。

为了存储足够的信息量，在处理器运行的过程中，程序必须将一部分数据存储在内存中。

3、中断机构，当用户访问的部分不在内存中时中断程序运行。

4、地址变换机构，以动态实现虚地址到实地址的地址变换。

5、相关数据结构，段表或页表。

（二）请求分页存储管理方式

1、请求分页原理

基于分页存储管理系统之上，在引入请求调页功能与页面置换功能后所构建的一种虚拟存储机制。在作业运行前将所需的页面组合加载至内存中，在作业运行过程中若所需页面不在内存区域，则通过调页功能将其加载至内存区域，并可利用置换功能将暂时不再需要的页面转移至外存空间以腾出内存供后续操作使用

可以说，请求分页 = 基本分页 + 请求调页功能 + 页面置换功能。

2、页表结构

1、页码和物理块编号。这两个字段在分页存储管理系统中已被预先设定作为必要参数使用。

2、状态位（存在位）。该状态标志用于判断当前页面是否存在于内存中；每次进行一次页面访问时,系统会根据该状态标志来确定目标页面是否存在于内存;如果目标页面不存在于内存,则会触发缺页中断.

3、字段信息。网站页面数据记录显示，在一定的时间段内被访问的次数以及最近一次未被访问的时间跨度（即相隔多久），以便置换算法在决定更换页面时参考这些指标。

4、修改位。用户询问在加载内存后页面是否发生过更改。当处理器采用写方式访问特定网页时（即当前处理的是一个需要更新的内容），系统会标记该网页为已更改以便后续处理。为了确保数据一致性，在内存中存在多个副本（以防主存储器故障或其他意外情况导致数据丢失）。如果未发生更改，则无需将当前网页发送至外存（减少不必要的磁盘操作）。而如果有发生更改，则必须将其发送回外存进行更新（以保证最新的数据版本）。

5、外存地址。用户指出页面在外存上的存放地址，供调入页面时使用。

3、缺页中断与地址变换

在请求分页存储管理系统中，若访问的页面已存在内存中，则其地址变换过程与分页存储管理系统一致；若访问的页面不在内存中，则应首先将该页面加载至内存中，并按照基本分页存储管理系统相同的方式进行地址变换。

当系统检测到目标页面未存在于内存中时（即外存访问超限），会触发缺页中断信号进而导致用户程序被中断并转交至操作系统进行处理）。在这种处理流程中（具体而言），当存在足够的存储容量（即存在空闲存储区）时（操作系统会）将目标页面直接加载至任一空闲存储区并同步更新相关数据项；而当所有存储区域均已被占用而无空闲空间可选时（则需）首先释放出部分已存在的页面块以便为新 arrived 的目标数据腾出位置

4、请求分页管理方式的优缺点

优点。①采用分立式存储机制，并减少了内存碎片的产生；②通过虚拟内存管理实现了高效的内存使用效率，并支持多项程并行运行以简化操作流程。

主要缺点是：①需要依赖硬件支持；②在某些情况下会出现抖动行为；③程序最后一页仍存在未被充分利用的空间

（三）请求分段存储管理方式

1、请求分段原理

在请求分段时间存储管理系统中，在作业运行阶段之前阶段，在当前系统环境中，在执行任务之前阶段：当所需的若干个数据块尚未被加载至内存量时：系统会自动触发必要的加载操作；此时可利用调片机制将其加载至内存；同时可以通过置换策略将暂时不需要的数据块移动至外部存储区域以释放内部可用空间；从而确保系统能够正常运作而不至于出现缺少数据的情况。

2、段表结构

段号、段长与内存起始地址这三个参数是进行地址变换所必不可少的；其余字段的意义与请求分页存储管理具有相同的含义。

3、缺段中断与地址变换

当当前分块位于内存内时其地址转换操作与分段存储管理机制一致；若当前分块未被加载到内存中应在执行地址转换之前完成相应加载动作并立即执行其后的地址转换操作以确保数据完整性的一致性。若所访问的当前分块未在主存内则会导致系统产生缺断状态并触发相应的中断处理流程系统将在主存中搜索是否存在足以容纳当前分块的区域若找不到此类区域则需计算所有空闲分区容量之和并根据结果决定是否需要对现有分区进行优化处理或者临时取出若干已分配区域以便腾出空间供所需区使用

（四）页面置换算法

1、最佳置换（ OPT）算法

在预知一个进程的页面引用串的情况下，在每次迭代时都会去除不再使用以及最迟未被使用的页面。

OPT代表最优方案，在呈现最低缺页率水平的同时也展现出极佳的竞争优势。然而，在实际情况中很难预见到所有将被引用的页面信息，在这种情况下最佳置换策略难以实现。因而我们需要将其作为一个评价其他置换策略性能的标准进行考量。

2、先进先出（ FIFO）算法

每次总是优先将最早进入内存的页面保留在内存中，并选择在内存中最久未被使用的页面进行淘汰。该算法虽然逻辑相对简单易懂，并且能够在一定程度上满足日常应用需求（当分配给进程的物理块号数量增加时），但仍然存在Belady异常（缺页此时随着分配的物理块号的增加而更加明显）。然而，在某些特定情况下（例如程序运行过程中频繁调用同一页面），这一算法可能会出现与实际运行规律不符的问题（如错误地淘汰掉本应优先保留的高频率使用页面）。

3、最近最少使用（ LRU）算法

选择未被使用过最长一段时间的页面予以淘汰，在常见的页面置换算法中，LRU（Least Recently Used）方法最为接近最佳置换策略。

4、时钟置换（ CLOCK）算法

时钟置换算法亦称最近未使用（NRU）算法，在先进先使用（FIFO）与最优 replacements（OPTimal）之间找到了折中方案。CLOCK算法通过在内存中的每个页框分配一个标记位来判断其是否已最近被引用过一次。为了管理这些标记位的状态,CLOCK算法构建了一个包含内存中所有页框地址的循环单链表。每当系统需要调用内存中的某个地址时,相应的标记位会被设置为1以表示已被引用过一次。如果请求到的是当前不存在于缓存中的内容,就必须释放出一个空闲的位置,随后会有一个指针从上一次被释放后的下一个空闲位置开始依次扫描整个循环单链表,直至找到第一个尚未被引用过的标记位并将其设为0之后,才会释放出相应的空间供新内容占用

还有一种改进型CLOCK算法，在处理页面加载后是否被修改的问题时采取了创新措施。该算法通过引入额外的标记位来记录页面是否发生过更新。在处理同一时间窗内访问频率为零的进程时，在未更新过的页面之间倾向于先进行淘汰，在此过程中未被更新过的页面可以直接被淘汰掉而无需进行外存重写操作。相比于基础型CLOCK机制，在减少磁盘I/O操作的同时需要进行更多的扫描操作以确保同步一致性

5、最不常用置换（ LFU）算法

采用基于访问频率的策略选择当前时间范围内访问次数最少的页面进行淘汰；该算法规定为每一页配置一个访问计数器用于记录其被访问的情况；每当页面被访问时，会将该页的访问计数器累加1次；在发生缺页中断的情况下，首先识别出当前所有页面中拥有最低访问计数值的那个或多个页面，并对该或多个最低值页面执行清零操作。

6、页面缓冲（ PBA）算法

PBA算法采用FIFO策略来选择被置换的页面。系统不会立即将选择出来的页面换出至物理内存外；而是先将其存放在两个专用链表中：如果是未经过任何修改操作的空白页，则将其添加至空闲列表末尾；反之，则加入已使用列表中进行管理。这样处理后，在程序执行过程中这两类列表中的数据项会在内存中保持一段时间：当这些空白或已被使用的数据项再次被程序调用时（即再次被访问），系统只需从相应的列表中移除它们即可释放回进程空间区域；从而避免了频繁地进行磁盘I/O操作的需求。当系统需要加载新的物理页码时，在空闲列表的第一个位置插入新的物理页码节点；随后立即删除该节点以释放其占用的空间资源。当已经存在的使用过的数据项数量达到预设阈值时，则一次性取出所有待加载的数据项并完成写入磁盘的操作；接着将它们重新编排回空闲列表中以便于后续的操作处理工作。通过这种方式就能有效减少I/O操作次数从而提高系统的运行效率

（五）抖动现象与缺页率

1、Belady 异常

FIFO算法在物理块号数量增加时会导致缺页率上升的现象被称为Belady异常。其发生的根本原因是由于FIFO算法在页面置换过程中所遵循的特点与进程对内存空间进行动态访问的需求之间存在不一致：被替换出去的页面并非进程永远不会再访问到该页面。

FIFO页面置换策略可能会遭遇Belady反例；然而LRU策略以及最佳替换策略则永远无法避免地会遇到这样的问题；同样地, 被归类于栈结构类型的页框替换策略也不会遭遇这个问题。

2、抖动现象

所谓的抖动现象是：在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问，在刚被淘汰页面之后不久又会再次访问。这种反复出现的现象会导致系统将大部分时间用于页面的加载和卸载过程，并且几乎没有任何有效业务处理的时间。其根本原因在于请求分页存储管理系统中每个进程仅能获得所需内存空间的一部分。

3、缺页率

假设一个作业共有n页，在系统中为其预留了m个字节的空间（m不超过n）。当该作业在运行期间总共访问了A次页面时（此时引用串的长度为A），其中那些不在内存中的页面需要将它们调入内存F次。而缺页率f定义为F除以A，在此情况下则被定义为了f = F/A；相应的命中率为1 - f。

缺页率是评估页面置换算法性能的关键指标，在实际应用中通常会受到多种因素的影响。在基于请求分页存储系统的环境中，默认情况下合理的缺页策略能够有效提升系统的运行效率。在实际应用中发现当缺页率过高时可能会导致读取页面的时间长度增加进而影响系统的吞吐量；而当系统运行效率明显下降时相应的优化措施就显得尤为重要。

二、内存管理方式之间的比较

表 3种离散分配方式的比较

对比及联系内存管理方式	分页存储管理	分段存储管理	段页式存储管理
有无外部碎片	无	有	无
有无内部碎片	有	无	有
优点	内存利用率高，基本解决了内存零头问题	段拥有逻辑意义，便于共享、保护和动态链接	兼有两者优点
缺点	页缺乏逻辑意义，不能很好地满足用户	内存利用率不高，难以找到连续的空闲区放入整个段	多访问一次内存

表 几种内存管理方式之间的比较

比较的方面	单一连续分配	分区	分页	基本分段	基本段页式
固定分区	可变分区	基本分页	请求分页
内存块的分配	连续	连续	离散	离散	离散
适用环境	单道	多道	多道	多道	多道
地址维数	一维	一维	一维	二维	二维
是否需要全部程序在内存	是	是	是	否	是	是
扩展内存	交换	交换	交换	虚拟存储器	交换	交换
内存分配单位	整个内存的用户可用区	分区	页	段	页
地址重定位	静态	静态	动态	静态	动态	静态	静态
重定位机构	装入程序	装入程序	重定位寄存器	页表页表控制寄存器加法器	段表段表控制寄存器加法器	段表页表段表控制寄存器加法器
信息共享	不能	不能	可以，但限制多	可以	可以