虚拟存储器

虚拟存储器概述

从逻辑上扩充内存容量

  1. 常规储存管理方式的特征和局部性原理

    常规存储器虽然也有许多存储方式，但是，不管是哪种存储方式，实际上都只是为了提高内存的利用率，减少内存碎片的出现，当作业的大小大于内存时，不管使用哪种方式都不能放入内存。

    其有着两个特征：一次性（作业必须全部装入内存后才能运行），驻留性（在被装入内存后，直到运行结束，都不会换出）。（整体对换不太好分类）

    但程序具有局部性原理：执行时一般顺序执行，递归调用深度不超过5，有许多循环结构并有许多对数据结构的处理，导致其有时间局限性（指令不久后可能再次执行，数据不久后会被再次访问)，空间局限性（一段时间内访问的地址可能集中在一定的范围内，程序的地址也是(顺序执行)）

    因此，在运行时，仅需将当前要运行的页面或段装入内存，当程序要访问的没有被装入内存，就发出缺页(段)中断请求，并用请求调页(段)装入内存，如果内存已满就置换暂时不用的页(段)。

  2. 虚拟存储器的定义和特征

    虚拟存储器：指具有请求调入功能和置换功能，并从逻辑上对内存容量加以扩充的一种存储器系统。（容量为内存和外存之和，速度接近与内存，成本接近于外存）

    特征：

    1. 多次性（允许被分成多次调入内存运行）
    2. 对换性（允许在作业的运行过程中进行换进换出）
    3. 虚拟性（从逻辑上提高内存容量）（可以提高多道程序度和程序执行的并发程度和吞吐量）

  3. 虚拟存储器的实现方法

    有两种实现方式：分页请求系统，请求分段系统。

    硬件上需要请求分页(段)的页(段)表机制，缺页(段)中断机构，地址变换机构。而分页在软件上实现比分段更简单，因为是固定大小。

请求分页存储管理方式

  1. 请求分页中的硬件支持

    1. 请求页表机制

      请求页表存储了逻辑地址映射到物理地址的转换。包含六项，页号，物理块号（可能为空，如果没有调入），状态位P（当前是否已调入），访问字段A（一段时间内的访问次数），修改位M（发生修改时置1在调出时也要对外存更改），外存地址。

    2. 缺页中断机构

      其中断与普通中断的处理方式差不多，要保存，转入内核态等等，但缺页中断是一种特殊中断，其在执行期间产生和处理信号（而一般中断都是执行完一条指令后），并且一条指令可能会产生多次缺页中断。

    3. 地址变换机构

  2. 请求分页中的内存分配

    1. 最小物理块数（保证进程正常运行所需的最小物理块数）的确定

      正常情况只需要2，程序1，数据1，若允许间接寻址，则3，而大部分功能较强的需要6，如下图。

    2. 内存分配策略

      1. 固定分配局部置换

        给每个进程分配的物理块数量固定，当发生缺页，就置换其中一块物理块。缺点在无法确定该分配多少内存，多了减少内存中进程数，少了会频繁中断。

      2. 可变分配全局置换

        一开始分配一定物理块，当缺页，就从当前还未分配的空闲物理块分配一块给这个进程（内存增加）。当无空闲物理块时，就对任意某个进程的物理块进行置换（内存减少）。

      3. 可变分配局部置换

        与固定分配局部置换类似，但是如果发现频繁中断，则增加其物理块，否则减少。

    3. 物理块分配算法（固定分配）

      1. 平均分配：每个进程数量一致
      2. 按比例分配：根据进程大小按比例分配（应大于最小物理块大小）
      3. 考虑优先权分配算法：为了让优先级高的尽快完成，应增加其物理块数量。因此，将内存分为两部分，一部分按比例分配，一部分按优先级进行分配

  3. 页面调入策略

    1. 何时调入页面

      1. 预调页策略：一次性调入一批页面，通过预测的方式来决定哪些会被调入。

        优点：在程序一开始，程序员可以指定一批调入页面；当程序被调度时，可以将其使用的工作集一起调入。

        缺点：预测准确率低，导致大部分调入的未被访问，效率低。

      2. 请求调页策略：当不存在时才调入

        优点：调入的页面一定会被访问，实现简单

        缺点：一次仅调入一页，增加了IO频率。

    2. 从何处调入页面

      1. 拥有足够的对换空间：进程调度时就全部放进对换区。
      2. 没有足够的对换空间：若被修改，从对换区调入（也要调出到对换区），若不变，则从文件区调入（无须调出到文件区）。
      3. UNIX方式：未运行过的从文件区调入，其他从对换区调入。

    3. 缺页率f=F访问页面失败次数A访问页面从次数缺页率f=\frac{F访问页面失败次数}{A访问页面从次数}

      受页面大小，进程所分配物理块数目，页面置换算法和程序固有特性影响。

      而实际上，换出页面时的时间是不统一的，修改花的时间更多。缺页中断处理时间t=修改概率β∗ta+(1−β)∗tb缺页中断处理时间t=修改概率\beta*t_a+(1-\beta)*t_b

页面置换算法

抖动：被换出的页面又立即被换入，进程频繁的更换页面，大部分时间都花费在页面置换上

  1. 最佳(Optimal)置换算法：最佳的方法就是换出最长时间不会再被使用的页面。

    是理想的最佳方法，但实际上这是无法预测的，因此一般用来评价其他算法。

  2. 先进先出(FIFO)页面置换算法（队列）：淘汰最先进入的页面。

    性能非常差。

  3. LRU(Least Recently Used)置换算法：换出最长时间未被访问的页面。

    以最近的过去类比最近的未来，但实际上并没有必然性。

    实现起来较为复杂，一般用寄存器或栈来实现。

    1. 寄存器

      每一个页面对应一个n为移位寄存器，当其被访问时，就将最高位置为1，每过一个时间，就将整体右移，值最小的寄存器对应的页面就是最久未被访问的页面。因为很显然越久未被访问寄存器中的第一个1越靠右。

    2. 栈

      保存各个页面的页面号。当访问时，将其移出栈，并压入栈顶，很显然，最底下的就是最久未被访问的页面。

  4. LFU(Least Frequently Used)置换算法：换出最近某一段时间内访问次数最少的页面

    实现上需要记录最近一段时间的访问次数，但这是不现实的，因为1ms内可能会对页面连续访问成千上万次。

    因此一般仍然使用移位寄存器来实现，如果被访问，就将最高位设为1，然后每隔一定时间(如100ms)就向右移一位，最后全部相加即为使用最少的页面。但实际上这也不能完全反应，因为这一段时间内访问100次和1次的效果是一样的。

  5. Clock置换算法

    LRU需要比较多的硬件支持，因此一般用Clock算法来近似LRU。

    1. 简单的Clock置换算法（NRU(Not Recently Used))

      为每一个页表增加一位bool表示是否被访问过。若被访问，则置1。并将所有内存中的页面串成一条链，每次要换出时，从前一次到达的地方往后走，如果为1，就置0，给予第二次留在内存的机会，否则如果为0，就直接换出。

    2. 改进型Clock置换算法

      在换出时，如果页面被修改了，那么其换出的代价是更大的，因此也要考虑。因此改进Clock算法对修改位M也进行考查。

      首先找未被访问且未被修改，其次是未访问但修改了的，然后是访问但没修改，最后是访问且修改了。每一次寻找都要扫描一遍所有的页面，直到找到了就停止。而在实际实现上，前两步没什么要注意的，而后两部则并非是扫描访问位A=1的，而是在第二次扫描的时候将所有1置为0，因此后两步的扫描和前两步的扫描的条件实际上是相同的（在经过第二次扫描后，所有已访问的就会变为未被访问的。

      IO减少，但算法本身开销变大。

  6. 页面缓冲算法PBA

    除了算法会影响时间，读入内存和写回磁盘的频率也会大大的影响时间。PBA就是在这方面进行优化。

    首先，他是可变分配和局部置换方式。其在内存中有两个链表，空闲页面链表和修改页面链表。当一个未被修改的页面被换出时，就放到空闲页面链表中，当再次被访问时也能很快再拿回来，但空闲链表还是起到其本身在可变分配时的作用。当一个被修改过的页面换出时，放到修改页面链表中，当再次被访问时也能很快再拿回来，并且当修改页面链表达到一定大小，再一起写入磁盘，减少IO频率。

  7. 访问内存的有效时间

    在访问时总共有三种情况。

    1. 访问页在内存中，且页表项在快表中：查找块表时间λ+访问内存时间t查找块表时间\lambda+访问内存时间t
    2. 访问页在内存中，且页表项不在快表中（在快表中的一定在内存，反之不成立）：2∗(λ+t)2*(\lambda+t)，因为还要修改快表，所以多一次更新快表时间
    3. 访问页在不内存中：2∗(λ+t)+中断时间ϵ2*(\lambda+t)+中断时间\epsilon

    再加上缺页率和命中率就能计算出平均访问内存的有效时间。

抖动和工作集

  1. 抖动：通过虚拟存储器，可以提高多道程序度，但是，随着数量的增加，到达某一个点后，处理机的利用率就会开始下降。这是因为，内存中的程序太多，每一个程序拥有的物理块太小，导致其大部分时间都在换入换出，不再能做任何有效工作，因此处理机效率就降低了。

  2. 工作集：一段时间内使用的页面的集合

    但这一般无法预测，因此也一般使用最近的过去作为最近的将来，将过去的几个页面作为工作集。在时间t大小为Δ\Delta的工作集记为w(t,Δ)w(t,\Delta)。

  3. 预防抖动的方法

    1. 采用局部置换策略：避免进程互相影响。但实际上如果某个进程发生抖动，其缺页中断也会间接的影响其他进程的缺页中断，导致影响其他进程。
    2. 把工作集算法融入到处理机调度中：当处理机利用率低时，应该先检查时候有缺页多的进程，没有才调入新的进程
    3. 利用”L=S”准则调节缺页率：L为缺页之间的平均时间，S为平均缺页服务时间。当L=S时，处理机和磁盘都达到最佳。
    4. 选择暂停的进程：当出现抖动或将要出现的时候，可以暂时将进程暂停，选择进程的方式与处理机调度类似。

请求分段存储管理方式

  1. 硬件支持

    1. 请求段表机制

      需要段名，段长，段基址，存取方式，访问字段A，修改位M，存在位P，增补位和外存始址。

      相较于页表，其多了段长，存取方式和增补位。

      存取方式：用于控制段的权限，如只读，只写。

      增补位：在内存中时时候有动态增长。

    2. 缺段中断机构

      相较于页面，段在调入的时候需要判断内存中时候有足够大小或者时候能够拼起来凑成一个足够大的空闲区，否则就要置换。

    3. 地址变换机构

      相较于页面，还需要检查其地址合法性和权限问题。

  2. 分段的共享与保护

    分段的共享和保护是通过共享段表来实现的。这张段表上存着所有被共享的共享段的基础信息，每一个共享段有着一个count计数，当为0时这段内存才能释放（共享指针）。并且还保存所有共享该段的进程信息，如状态，进程名，进程号，段号（在不同的进程中可能不一样）和存取控制（为不同的进程分配不同的权限）。

  3. 共享段的分配与回收

    分配时，第一个分配空间，并更改共享段表，后来的只需更改共享段表。

    回收时更改共享段表，最后一个释放空间。

  4. 分段保护

    1. 越界检查：检查段号的合法性和段内地址的合法性
    2. 存取控制检查：由硬件实现，无法从软件更改
    3. 环保护机构：低编号的环具有高优先权，OS核心处于0号环。

虚拟存储器
https://lhish.github.io/project/hide/虚拟存储器/
作者
lhy
发布于
2025年8月16日
许可协议