Storage Management PartⅢ
Virtual Memory
Virtual Memory 的引入
问题的提出
一个程序要求的存储容量超过整个内存空间
有大量的作业需要装入内存运行而内存空间不足
解决方案
从物理上增加内存容量。但这会增加系统成本，并且增加是有限的
从逻辑上增加内存容量。这正是虚拟存储技术所要解决的主要问题。
常规存储器管理方式的特征
“一次性”: 要求将一个作业全部装入内存才能运行，
1）大作业无法运行。
2）限制作业并发执行的程度。
“驻留性”: 作业装入后一直驻留内存直到作业完成。
内存中存在一些已无用的、或暂时不用的程序或数据，浪费内存空间。
一次性和驻留性严重降低内存利用率，减少系统吞吐量。
内存的扩充方法
- 物理扩充：
增加硬件投入，受机器自身和成本的限制。 - 逻辑扩充：
- 覆盖（overlay）应用程序手动把需要的指令和数据保存在内存中；解决了“一次性”问题。
- 对换（swapping）操作系统自动把暂时不能执行的程序保存到外存中;解决了“驻留性”问题。
- 虚拟存储 在有限容量的内存中，自动装入更多更大的程序
局部性原理 Principle of Locality
程序执行的局部性原理：程序的执行总是呈现局部性。即在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。
因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。
局限性又表现在下述两个方面：
- 时间局限性
如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。
产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。 - 空间局限性
一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。
程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。
不同程序编写方法的局部性特征
页面大小为 4K，分配给每个进程的物理页框数为 1。在一个进程中，定义了如下的二维数组int A[1024][1024]，该数组按行存放在内存，每一行放在一个页面中。// 程序编写方法1：for (j = 0; j < 1024; j++)for (i = 0; i < 1024; i++) A[i][j] = 0;// 程序编写方法2：for (i=0; i<1024; i++)for (j=0; j<1024; j++) A[i][j] = 0;页号 页内数据0000 a0,0 a0,1 a0,2 …………………… a0,10230001 a1,0 a1,1 a1,2 …………………… a1,1023 …………………………… ……………………………1023 a1023,0 a1023,1 ……………………....…......... a1023,1023
编写方式 1 发生了大量的缺页中断，因为程序按行存放，每次访问都会跨页，共计
编写方式 2 发生了较少的缺页中断，共计
缺页中断（Page Fault）是计算机操作系统中的一种中断或异常，当程序访问一个页面时，如果这个页面已经在物理内存中，那么就可以直接读取或者写入。但是，如果这个页面在虚拟内存中，而并没有加载到物理内存中，那么就会发生缺页中断。
Virtual Memory 概述
定义
Virtual Memory是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定
其运行速度接近于内存速度，而成本却又接近于外存。
虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。
- 当进程运行时，先将当前要运行的部分程序装入内存，其他部分暂留外存；
- 当要执行的指令不在内存时，处理器发生中断，通知操作系统将所缺部分从外存调入内存，保证程序继续执行；
- 当内存不足时，允许程序部分换入、换出。
基本工作情况
- 基于局部性原理。一个作业运行前，仅将那些当前要运行的页面（段）装入内存启动运行，其余暂在外存。
- 若运行所需页面（段）不在内存，则利用请求调页（段）功能将其调入内存。
- 若此时内存满，则利用置换功能，将内存中暂时不用的部分页面（段）调至外存，再将所需页面（段）调入。
- 这样，可实现大程序在小内存中运行，也可实现内存中同时装入更多的进程并发执行。
虚存容量
Virtual Memory 虽然给用户提供了特大地址空间，但其容量不是无限大，主要受两个方面的限制：
- 指令中表示地址的字长：这是由 CPU 的架构决定的。例如，如果 CPU 的有效地址长度为 32 位，那么它能够表示的地址空间最大为
- 外存的容量（对换区）：虚拟内存的另一个部分存储在硬盘的交换区中。如果硬盘的空间有限，那么虚拟内存的容量也会受到限制。即使 CPU 可以支持更大的虚拟内存，如果硬盘空间不足，那么虚拟内存的实际可用空间也会受到限制。
Virtual Memory 的特征
Virtual Memory 具有以下主要特征：
- 多次性 多次性是指一个作业被分成多次调入内存运行。
- 对换性 对换性是指作业的运行过程中进行换进、换出。换进和换出能有效地提高内存利用率。
- 虚拟性 虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
虚拟性是以多次性和对换性为基础的；而多次性和对换性又必须建立在离散分配的基础上。
虚拟存储管理与对换技术的区别
| 技术 | 处理单位 | 主存容量大于系统空闲量时的处理方式 |
|---|---|---|
| 虚拟存储管理 | 页或段 | 进程仍能运行 |
| 对换技术（中级调度，挂起和激活） | 进程 | 无法解除挂起 |
Virtual Memory 的实现方法
请求分页系统
它是在纯分页系统的基础上增加了请求调页、页面置换两大功能所形成的页式虚拟存储系统。为了实现请求调页、页面置换两大功能，系统必须提供如下的硬件支持：
- 请求分页的页表机制。
- 缺页中断机构。
- 地址变换机构。
此外，实现请求调页、页面置换两大功能还需得到 OS 的支持。
请求分段系统
它是在纯分段系统的基础上增加了请求调段、分段置换两大功能所形成的段式虚拟存储系统。为了实现请求调段、分段置换两大功能，系统必须提供如下的硬件支持：
- 请求分段的段表机制。
- 缺段中断机构。
- 地址变换机构。
此外，实现请求调段、分段置换两大功能还需得到 OS 的支持。
段页式虚拟系统
目前，许多虚拟存储管理系统是建立在段页式系统的基础上的，通过增加了请求调页、页面置换两大功能所形成的段页式虚拟存储系统。
如：Intel 80386 处理机便支持段页式虚拟存储系统。
抖动 Thrashing
当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。
如果系统花费大量的时间把程序和数据频繁地换入和换出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。
根本原因：选择的页面或段不恰当。
请求分页存储管理方式 Demand Paging
原理及实现
工作原理
作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由 OS 将其从辅存调入主存，如果内存无空块，则根据某种算法选择一个页淘汰以便装入新的页面。
利用这种方法，可使更多的作业处于就绪状态，且能支持比主存容量大的作业在系统中运行。从而提高存储空间利用率。
为了实现请求调页、页面置换两大功能，系统必须提供如下的硬件支持：
- 请求分页的页表机制。
- 缺页中断机构。
- 地址变换机构。
页表机制 Page Table
在虚拟存储系统中的所有的页表，其页描述子有了新的扩充，这是进行地址变换机构所必须的，增加四个信息标识位。
| 页号 | 页框号 Q | 状态位 D | 访问位 A | 修改位 M | 外存地址 |
|---|
- 状态位/存在位D：用于说明该页是否已调入内存，供程序访问时参考；
D=0，该页不在内存;D=1，该页在内存 - 访问位A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。
A=0，该页未被访问;A=1，该页被访问 - 修改位M：用于表示该页在调入内存后是否被修改过，也是提供给置换算法在换出页面时是否将该页面写回外存作参考。
M=0，该页在内存中未被修改;M=1，该页在内存中已经被修改 - 外存地址：用于指出该页在外存上的地址，供调入该页时使用。
缺页中断机构 Page Fault Interrupt
由上述页表机制知道，状态位记录了访问页面是否在内存。在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断，也称为缺页故障。OS 接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。
缺页中断是一种特殊的中断，与一般中断相比，主要表现为：
- 在指令执行期间产生和处理中断信号。通常，CPU 只能在指令之间接受中断；然而，一个缺页中断要求在指令执行中间得到服务，即发现所要访问的指令或数据不在内存时产生缺页中断并处理。
- 再则，一条指令可能引起多次不同的页面故障。
例如COPY A,B,指令本身跨了两个页面,数据 A 和 B 各自跨了两个页面,这条指令的执行需要访问六个不同的页面，对它们的访问都可能引起缺页中断,最多可能引起 6 次缺页中断(每个页面都不在内存中)
由于缺页中断的独特性，系统中需要提供硬件寄存器或其它机构，在出现页面故障时，保存部分完成的指令的状态。此外，还需要使用一条特殊的返回指令，确保在出现缺页中断处恢复该指令的处理。
- 操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；
- 操作系统通知处理机从外存读取指定的页面；
- 处理机激活 I/O 设备；
- 检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；
- 利用页面置换算法，选择内存中的某个页面，换出内存；
- 将指定页面从外存装入内存；
- 更新该进程的页表；
- 更新快表；
- 计算物理地址。
srcset="https://assets.vluv.space/UESTC/OS/Ch4-3StorageManagement/Ch4-3StorageManagement-2024-05-12-21-24-35.webp?w=500 500w, https://assets.vluv.space/UESTC/OS/Ch4-3StorageManagement/Ch4-3StorageManagement-2024-05-12-21-24-35.webp?w=1200 1200w, https://assets.vluv.space/UESTC/OS/Ch4-3StorageManagement/Ch4-3StorageManagement-2024-05-12-21-24-35.webp?w=2000 2000w, https://assets.vluv.space/UESTC/OS/Ch4-3StorageManagement/Ch4-3StorageManagement-2024-05-12-21-24-35.webp?w=3000 3000w"
loading="lazy" decoding="async"
style="width:100%; object-fit:cover; transition: opacity 0.3s; opacity:0;"
onload="this.style.opacity=1; this.parentElement.style.backgroundImage='none';"
alt="缺页中断处理过程"></div>
地址变换机构 Address Translation
内存分配策略和分配算法
在为进程分配物理块时，又将涉及到这样三个问题：
- 确定进程能正常运行所需的最少物理块数；
- 为每个进程分配的物理块，其数目是固定的还是可变的；
- 对各进程所分配的物理块数，是采取平均分配算法还是根据进程的大小按比例予以分配等。
最小物理块数的确定
显然，给每个进程所分配物理块数目越少，则进程执行中的缺页率越高，进程的执行速度也减慢。为使进程能有效地工作，应为它分配一定数目的物理块。
最小物理块数：是指能保证进程正常运行所需的最少物理块数。若系统为某进程所分配的物理块数少于此值时，进程将无法运行。
进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。
例：对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为 2。如果该机器允许间接寻址时，则至少要求有物理块数为 3。对于前面所介绍的在缺页中断机构中要发生 6 次中断的情况，至少要为每个进程分配 6 个物理块，以装入 6 个页面。
物理块的分配策略
- 固定分配局部置换 Fixed Allocation，Local Replacement
- 可变分配全局置换 Variable Allocation，Global Replacement
- 可变分配局部置换 Variable Allocation， Local Replacement
- 固定分配局部置换
为每个进程分配一定数目的物理块，在整个运行期间都不再改变。
实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。
若太少，会频繁地出现缺页中断，降低了系统的吞吐量；
若太多，又必然使内存中驻留的进程数目减少，进而可能造成 CPU 空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。 - 可变分配全局置换 （常用方式）
在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而 OS 自身也保持一个空闲物理块队列。
当某进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。
这样，凡产生缺页（中断）的进程，都将获得新的物理块；
仅当空闲物理块队列中的物理块用完时，OS 才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。 - 可变分配局部置换
为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。
在进程运行过程中统计进程的缺页率，如果缺页率高，则为其增加一定的内存页，否则适当减少其内存的页面数。
当需要置换时只从本进程的内存页中选择，但此方式实现复杂，对进程的缺页情况的统计需要额外的开销。
物理块的分配算法
在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采取下述几种方法。
- 平均分配算法
将系统中所有可供分配的物理块，平均分配给各个进程。
例：当系统中有 100 个物理块，有 5 个进程在运行时，每个进程可分得 20 个物理块。如有一个进程其大小为 200 页，只分配给它 20 个块，这样，它必然会有很高的缺页率；而另一个进程只有 10 页，却有 10 个物理块闲置未用。
这种方式貌似公平，但实际上是不公平的。因为，它并未考虑到各进程本身的大小。 - 按比例分配算法
根据进程的大小按比例分配物理块的算法。
例：系统中共有 n 个进程，每个进程的页面数为
又假定系统中可用的物理块总数为 m，则每个进程所能分到的物理块数为
b 应该向上取整，它必须大于最小物理块数。 - 考虑优先权的分配算法
通常采取的方法是把内存中可供分配的所有物理块分成两部分：
一部分按比例地分配给各进程；
另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。
在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配物理块。
调页策略
解决的问题：
- 系统应当在何时把一个页面装入内存？
- 从何处调入页面？
- 页面调入过程？
- 页面置换算法？
装入时机
系统应当在何时把一个页面装入内存?
- 预调页 (Prepaging)
- 请求调页 (Demand Paging)
可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。
处理过程：
- 当进程创建时，预先为进程装入多个页面。
- 缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。
- 若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率。预调页的成功率仅约 50％。
请求调页：仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。
当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。
采用请求调页方式，磁盘 I/O 的启动频率较高，系统的开销较大。
从何处调入页面
在请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。
通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式，故对换区的磁盘 I/O 速度比文件区的高。
这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况。
- 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页的速度。
- 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；
- 而当换出这些页面时，由于它们未被修改而不必再将它们换出到对换区，以后再调入时，仍从文件区直接调入。
- 但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。
- UNIX 方式。由于与进程有关的文件都放在文件区，应从文件区调入。故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。
页面调入过程
- 每当程序所要访问的页面未在内存时，便向 CPU 发出一缺页中断。
- 中断处理程序首先保留 CPU 环境，分析中断原因后，转入缺页中断处理程序。
- 如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果此页已被修改，则必须将它写回磁盘。
- 然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。
- 形成所要访问数据的物理地址，再去访问内存数据。
整个页面的调入过程对用户是透明的。
页面置换算法
页面置换算法的选择，是 Virtual Memory 管理系统的核心问题。
它的实质是，为系统提供一种方法，当从主存中需要换出页面时，应避免选择那些不久将再次要求访问的页面。
置换算法的选择在一定程度上取决于可用的硬件设施。
最优置换算法 Optimal Replacement Algorithm
最理想的页面置换策略是：从主存中移出永远不再需要的页面；如无这样的页面存在，则应选择最长时间不需要访问的页面。
最佳置换策略首先是由 Belady 于 1966 年提出的。
最佳置换策略本身不是一种实际的方法，因为页面访问的未来顺序是不知道的，但是，可将其它的实用方法与之比较来评价这些方法的优劣。所以，这种最佳策略具有理论上的意义。
例 设页面请求次序 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
存储块为 3(驻留集为 3)，假定最初存储块为空，采用 OPT。
