操作系统 第五章 虚拟存储器

操作系统 评论

第五章 虚拟存储器

一、虚拟存储器概述

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

1. 常规存储管理方式的特征

  1. 一次性：作业必须一次性地全部装入内存后方可开始运行，导致大作业无法在小内存中运行，无法进一步提高系统的多道程序度，限制了处理机利用率和系统吞吐量的提高
  2. 驻留性：作业呗装入内存后，整个作业都一直驻留在内存中，其中任何部分都不会背换出，直至作业运行结束

2. 局部性原理

在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域

  1. 程序执行时大多数情况是顺序执行
  2. 过程调用将会使程序执行轨迹由一部分转移到另一部分。大多数情况过程调用的深度不超过 5
  3. 程序中存在许多循环结构，仅有少数指令构成
  4. 程序中包括许多对数据结构的处理，局限在很小的范围内

局限性又体现在

  1. 时间局限性：程序中某条指令被执行，则不久后该指令可能再次执行；某数据被访问过，不久后可能被再次访问。时间局限性的典型原因是程序中存在大量的循环操作
  2. 空间局限性：一旦程序访问了某个存储单元，不久之后其临近的存储单元也将被访问。典型情况是程序的顺序执行

3. 虚拟存储器的基本工作情况

由局部性原理知，程序运行之前不需要全部装入内存，而是讲那些当前运行的少数页面或段装入内存便可，其余暂存在盘上。

程序运行时若所要访问的页（段）已调入内存便可继续执行，否则（称为缺页或缺段）发出缺页（段）中断请求，OS 遍利用请求调页（段）功能将它们调入内存。若内存已满则利用页（段）的置换功能，将暂时不用的页（段）调至盘上，腾出足够的空间后，再调入所需的页（段），使程序继续执行

这样可使一个大的用户程序在较小的内存中间中运行，也可在内存中同时装入更多的进程使它们并发执行

1.2 虚拟存储器的定义和特征

1. 虚拟存储器的定义

虚拟存储器指具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。逻辑容量有内外存容量之和决定，运行速度接近内存速度，每位成本接近外存。

2. 虚拟存储器的特征

  1. 多次性：一个作业允许被多次调入内存运行，是虚拟存储器最重要的特征
  2. 对换性：相对于常驻性而言
  3. 虚拟性：从逻辑上扩充内存容量，是用户所看到的内存容量远大于实际内存容量。改善内存利用率，提高程序执行并发速度。是实现虚拟存储器的最重要的目标

1.3 虚拟存储器的实现方法

1. 分页请求系统

  1. 硬件支持
    1. 请求分页的页表机制
    2. 缺页中断机构
    3. 地址变换机构
  2. 实现请求分页的软件

2. 请求分段系统

  1. 硬件支持
    1. 请求分段的段表机制
    2. 缺段中断机构
    3. 地址变换机构
  2. 软件支持

二、请求分页存储管理方式

2.1 请求分页中的硬件支持

1. 请求页表机制

  1. 状态位（存在位）P
  2. 访问字段 A
  3. 修改位 M
  4. 外存地址

2. 缺页中断机构

  1. 在指令执行期间产生和处理中断信号
  2. 一条指令在执行期间可能产生多次缺页中断

3. 地址变换机构

在这里插入图片描述

2.2 请求分页中的内存分配

1. 最小物理块数的确定

最小物理块数是指保证进程正常运行所需的最小物理块数

与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式

2. 内存分配策略

  1. 固定分配局部置换

    固定分配：每个进程分配一组固定数目的物理块。进程运行期间不再改变

    局部置换：发现缺页只能从分配给该进程的 个页面中选一页换出，再调入一页，以保证分配给该进程的内存空间不变

    困难在于：确定每个进程分配多少个物理块难以确定

    太少导致频繁缺页中断降低系统吞吐量；太多导致内存中驻留进程数减少，CPU 利用率下降，而且实现进程对换更耗时

  2. 可变分配全局置换

    可变分配：先为每个进程分配一定数目的物理块，运行期间可适当增加或减少

    全局置换：进程发生缺页后，将 OS 保留的空闲物理块取一块分配给该进程

    最易于实现的一种物理块分配和置换策略

  3. 可变分配局部置换

    当缺页时，只运行从该进程在内存的页面中选择一页换出，不会影响其他进程的运行。

    若进程频繁缺页中断，则系统再为其分配若干附加的物理块；反之若缺页率特别地可适当减少分配的物理块数

3. 物理块分配算法

  1. 平均分配算法

    未考虑到进程本身的大小，实际上的不公平

  2. 按比例分配算法

    假设 个进程，每个页面数为 ，则系统中各进程页面总数为 假定物理块总数为 ，则每个进程分到的物理块数为

  3. 考虑优先权的分配算法。通常采取吧内存分为两部分，一部分按比例分配，另一部分根据优先权为晋城的优先权分配。重要的实时系统中完全按优先权分配物理块

2.3 页面调入策略

1. 何时调入页面

  1. 预调页策略
  2. 请求调页策略

2. 何处调入页面

  1. 系统拥有足够对换区空间：全部从对换区调入所需页面。为此，进程运行前将进程有关的文件从文件区拷贝到对换区
  2. 系统缺少足够对换区空间：不会被修改的文件直接从文件去调入。可能修改的文件将它们换出时需调到对换区
  3. UNIX 方式：与进程有关的文件都放在文件区，范式未运行过的页面都从文件去调入。调出的页面放在对换区

3. 页面调入过程

未修改过可以不写写会磁盘

对用户透明

4. 缺页率

访问页面成功的总数为 ，访问页面失败的次数为 ，总的页面访问次数为 ，则缺页率为 受以下因素的影响

  1. 页面大小
  2. 进程分配物理块数目
  3. 页面置换算法
  4. 程序固有特性

三、页面置换算法

3.1 最佳置换算法和先进先出置换算法

1. 最佳置换算法

被淘汰页是以后永不访问，或最长内不再被访问的页面

2. 先进先出（FIFO）页面置换算法

总是淘汰最先进入内存的页面

3.2 最近最久未使用和最少使用置换算法

1. LRU 置换算法

选择最近最久未使用的页面淘汰

2. LRU 置换算法的硬件支持

  1. 寄存器

    未记录某进程在内存中各页的使用情况，需为每个在内存中的页面配置一个移位寄存器，表示为 当进程访问某物理块时，将相应寄存器的 设为 ，定时信号每隔一段时间将寄存器右移一位。具有最小熟知的寄存器所对应的页面就是最近最久未使用的页面

  2. 栈

    每当进程访问某页面时将该页面的页面号从栈中溢出并压入栈顶，栈底就是最近最久未使用的页面号

3. 最少使用（LFU）置换算法

设置一个寄存器记录被访问的频率

同样使用移位寄存器方式

3.3 Clock 置换算法

一种成本没有 LRU 高的 LRU 近似算法

1. 简单的 Clock置换算法

为每页设置一位访问位，再将内存中所有页面通过链接指针链接成一个循环队列

某页被访问时，该位设为

检查淘汰时，若为 则换出，若为 则重新设为 暂不换出，按照 FIFO 算法检查下一个页面

又称为最近未用算法（NRU）

2. 改进型 Clock 算法

除了考虑页面的使用情况外，增加一个因素——置换代价，则访问位 A 和修改位 M 组合成一下四种页面

  • A=0，M=0：最近既未被访问，有未被修改，最佳淘汰页
  • A=0，M=1：最近未被访问，已被修改，不是很好的淘汰页
  • A=1，M=0：最近已被访问，未被修改，可能再次被访问
  • A=1，M=1：最近已被访问且已被修改，可能在北方文

执行过程可分为以下三步

  1. 寻找 A=0 且 M=0 的第一类页面，此时不改变访问位 A
  2. 如果第一步没找到，写拍照 A=0 且 M=1 的第二类页面，第二轮扫描设所有扫描过的页面的访问位为 0
  3. 第二步也是被，则所有访问位复 0，重复第一步，若仍失败则重复第二步，此时一定能找到被淘汰的页

减少了磁盘的 I/O 次数，但实现算法本身的开销有所增加

3.4 页面缓冲算法（PBA）

1. 影响页面换进换出效率的若干因素

  1. 页面置换算法
  2. 写回磁盘的频率
  3. 读入内存的频率

2. 页面缓冲算法 PBA

  1. 显著降低页面换进换出的频率，减少磁盘 I/O 次数，减少页面换入换出开销
  2. 减少了上述的开销，才能采用一种较为简单的置换策略如 FIFO 算法。不许特殊硬件支持，实现简单

3.5 访问内存的有效时间

  1. 被访问页在内存中，页表项在快表中

  2. 被访问页在内存中，页表项不在快表中

  3. 被访问页不在内存中

    设缺页中断处理时间为

令命中率为 ，缺页率为 如不考虑命中率仅考虑缺页率即 ，则

四、“抖动”与工作集

4.1 多道程序度与“抖动“

1. 多道程序度与处理机的利用率

在系统中运行更多的进程，即增加多道程序度，以提高处理机利用率

处理机利用率是一个单峰函数

2. 产生抖动的原因

同时在系统中运行的程序太多，分配给每一个进程的物理块太少，频繁缺页，对磁盘的有效访问增加，每个进程的大部分时间都用于页面的换入换出，不能做什么有效的工作，从而导致处理机的利用率急剧下降并趋于

称此时的进程处于“抖动”状态

4.2 工作集

1. 工作集的基本概念

程序在运行时间，对页面的访问是不均匀的，在一段时间内仅局限于较少的页面，另一短时间内又局限于另一些较少的页面。这些页面称为活跃页面

2. 工作集的定义

工作集，是在某段时间间隔 里，进程实际所要访问的页面集合。即进程在时间间隔 中引用页面的集合

工作集是窗口尺寸 的非降函数

4.3 “抖动”的预防方法

1. 采用局部置换策略

简单易行，效果不是很好

2. 工作集算法融入处理机调度

调度前检查是否每个进程驻留页面够多，够则调入新作业，否则给缺页率高的进程增加物理块

3. 利用“L=S”准则调节缺页率

是两次缺页之间的平均时间， 是平均缺页服务时间

说明很少缺页，磁盘能力未充分利用

缺页速度已超过磁盘处理能力

最大利用率

4. 选择暂停的进程

多道程序度偏高时，应基于某种原则暂停某些当前活动的进程，调出到磁盘上

五、请求分段存储管理方式

5.1 请求分段中的硬件支持

1. 请求段表机制

2. 缺段中断机构

3. 地址变换机构

5.2 分段的共享和保护

1. 共享段表

  1. 共享进程计数：某进程不再需要而释放时，检查 count 是否为 ，为 才回收该内存区
  2. 存取控制字段：存取权限，如文件主允许读写，其他进程允许读或只运行执行
  3. 段号：同一个共享段在不同进程可以由不同的段号，每个进程可以用自己进程的段号访问它

2. 共享段的分配与回收

  1. 共享段的分配

    第一个请求使用该共享段的进程，有系统分配物理区，调入该区，始址填入请求进程段表的相应项

    在共享段表中增加一项，count 置为

    其他的进程需要调用共享段时只需段表填写共享段的物理地址，count+=1

  2. 共享段的回收

    撤销进程段表的表项，count-=1。若 count 为零则回收，否则只是取消调用者进程在共享段表的记录

3. 分段保护

  1. 越界检查

  2. 存取控制检查

    1. 只读
    2. 只执行
    3. 读/写

  3. 环保护机构：底编号的环有高优先级。OS 核心位于 号环内；某些重要的应用程序和操作系统服务占据中间环；一般的应用程序占据外环

    程序可以访问相同/外环中的数据，调用相同/内环中的服务

不知不觉Acmer & Student

Never Settle