# Background（背景）

• 基本要求：进程必须全部放入内存后方可运行
• 如果进程大于内存的容量或者内存中同时运行多个进程
• 覆盖和动态加载
  解决办法:

1. 从物理上扩充内存容量
2. 从逻辑上扩充内存容量

# 常规存储器的特征

一次性： 作业在运行前需要一次性的全部装入内存
驻留性：作业装入内存后，便一直驻留在内存中，直到作业结束。

正是由于一次性和驻留性，使得程序中暂时不用的数据占用了大量的内存空间，从而需要运行的作业无法装入内存。

#

• 程序通常有处理异常错误的代码，很少执行
• 数组、链表和表通常分配了比实际需要更多的内存
• 程序的某些选项或特点可能很少使用
• 即使需要完整的程序，也并不是同时需要所有的程序

# 局部性原理

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

• 程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。
• 子程序调用将会使程序的执行由一部分内存区域转至另一部分区域
• 程序中存在许多循环结构，循环体中的指令被多次执行。
• 程序中还包括许多对数据结构的处理，如对连续的存储空间 —— 数组的访问，往往局限于很小的范围内

局部性表现为：

• 时间局部性：
  如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；
  如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。
  产生时间局限性的典型原因是在程序中存在着大量的循环操作。
• 空间局部性：
  一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。

# 虚拟内存技术

• 虚拟内存是一种允许进程部分装入内存就可以执行的技术
• 局部性原理 : 时间局部性，空间局部性
• 只有运行的部分程序需要在内存中
• 逻辑地址空间能够比物理地址空间大
• 必须允许页面能够被换入和换出
• 虚拟存储建立在离散分配的存储管理基础上
• Virtual memory can be implemented via（虚拟内存能够通过以下手段来执行）:
  • Demand paging （请求页式）
    在基本分页的基础上，增加了请求调页和页面置换功能后形成的页式虚拟存储系统。需要硬件和软件支持。
  • Demand segmentation（请求段式）

# 虚拟存储器的特征

• 离散性：在内存分配时采用离散的分配方式，是虚拟存储器的最基本的特征。
• 多次性：一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。是虚拟存储器最重要的特征。
• 对换性：作业运行过程中信息在内存和外存的对换区之间换进、换出。
• 虚拟性：从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

# 引入虚拟存储技术的好处

• 可在较小的可用内存中执行较大的用户程序
• 可在内存中容纳更多程序并发执行
• 简化了编程操作， 不影响编程时的程序结构（与覆盖技术比较）
• 提供给用户可用的虚拟内存空间通常大于物理内存 (real memory)

# 页面调入策略

• fetch policy 调入策略
  1. prepaging 预调页
  2. demand paging 请求调页
• assignment policy 分配策略
  为能使进程运行，事先需将一部分要执行的程序和数据调入内存
• 预调页策略：
  主动的页面调入策略，即把那些预计很快会被访问的程序或数据所在的页面，预先调入内存。
  预测的准确率不高（50%），主要用于进程的首次调入。也有的系统将预调页策略用于请求调页
• 请求调页策略：
  当进程在运行中发生缺页时，由系统将缺页调入内存。
  目前虚拟存储器系统大多采用此策略。
  在调页时须花费较大的系统开销，如需频繁启动磁盘 I/O。
• 从何处调入页面
  在虚拟存储系统中，外存（硬盘）被分成两部分：文件区和对换区。对换区（连续分配）的磁盘 I/O 速度比文件区（离散分配）要高。
  从文件系统中调入页面
  从交换区中调入页面
• UNIX 系统:
  对于从未运行过的页面，都从硬盘文件区 (可执行文件) 调入
  对于被换出的页面，从对换区调入；
  对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。
  每个作业有一个页表，还有一个与之对应的磁盘描述项:
  [块号][类型], 类型有 file (可执行文件中) 和 disk (在磁盘对换区中), 表明该块的位置

# Demand Paging（请求页式）

• 只有在一个页需要的时候才把它换入内存
  • 需要很少的 I/O
  • 需要很少的内存
  • 快速响应
  • 多用户
• Page is needed （需要页）-> reference to it（查阅此页）
  • 无效的访问 -> 中止
  • 不在内存 -> 换入内存
• 对进程页表的修改
• 缺页中断的特殊性

# 请求分页中的硬件支持

1. 请求分页的页表机制

页号	物理块号	状态位 P	访问字段 A	修改位 M	外存地址
~	~	状态位（存在位 P）：用于指示该页是否已调入内存，供程序访问时参考。	访问字段 A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。	修改位 M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。	外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。

2. 缺页中断机构
   在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求 OS 将所缺页调入内存。与一般中断的主要区别在于：

• 缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。
• 缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。
• 一条指令在执行期间，可能产生多次缺页中断。

3. 请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等

# 解决缺页中断的步骤

1. 查找页表来确定此次地址访问是否合法
2. 如果不合法，则中止该进程；否则如果有效但不在内存，即发生了缺页，则需要将其调入内存
3. 所需页在外存，找到该页
4. 找到一个空闲物理块，启动磁盘，把该页读入内存
5. 读磁盘结束后，修改页表以指出该页已在内存中
6. 重新开始执行刚才发生缺页中断的指令，这时它可以访问刚才调入的页

在每一个页表的表项有一个有效 - 无效位相关联，1 表示在内存，0 表示不内存；这个位被初始化为 0;

# Performance of Demand Paging（请求页式的性能）

• 发生缺页时会导致以下步骤的发生:
  • 陷入 OS
  • 保存该用户寄存器和进程状态
  • 确定该中断是一个缺页中断
  • 检查该页面引用是合法的并确定该页在磁盘上的位置
  • 将该页从磁盘读入一个空闲物理块:
    • 在磁盘等待队列中等待直到该请求被处理
    • 等待设备寻道延迟
    • 将该块从磁盘传送至内存

1. 为了提高 CPU 利用率，将 CPU 分派给其他进程使用
2. 磁盘 I/O 完成，产生中断
3. 保存正在执行进程的现场信息（如果第 6 步执行了）
4. 确定中断来自于磁盘
5. 修改页表以示所缺的页已进入内存
6. 等待 CPU 再次分派给这个进程
7. 恢复该进程的现场信息，包括寄存器、进程状态、页表等，恢复执行

主要过程为:

• 处理缺页中断
• 从磁盘读入所需的页
• 重新开始被中断的进程
  其中最大的一部分时间开销为从磁盘读入所需的页

# 有效存取时间

p 为缺页率
Effective Access Time (EAT) = (1 – p) x memory access + p (page fault overhead+ [swap page ]+ [restart overhead])

# Page Replacement（页置换）

• 页置换 — 找到内存中并没有真正使用的一些页，换出
  • 算法
  • 性能：找出一个导致最小缺页数的算法
• 同一个页可能会被装入内存多次

Basic Page Replacement
Find the location of the desired page on disk
Find a free frame:

• If there is a free frame, use it
• If there is no free frame, use a page replacement algorithm to select a victim frame
• write the victim page to the disk, change the page and frame tables
• Bring the desired page into the (newly) free frame; update the page and frame tables
• Restart the user process

• 如果没有空闲帧，需要两个页面传输，一个换出，一个换入。
• 可以通过修改位来降低额外开销。
• 修改（脏）位来防止页面转移过多 — 只有被修改的页面才写入磁盘
• 页置换实现了逻辑内存和物理内存的划分 — 在一个较小的物理内存基础之上可以提供一个大的虚拟内存.
  

在进程运行过程中，如果发生缺页，而内存中又无空闲块时，怎么办？
将内存中的某一页换到磁盘的对换区
将哪个页面调出？
根据页面置换算法来确定
置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生 “抖动”（Thrashing)。

# Page-Replacement Algorithms（页置换算法）

• 需要一个最小的缺页率
• 通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数

1. 最佳算法 (OPT, optimal) : 被置换的页将是之后最长时间不被使用的页
2. 先进先出算法 (FIFO)
   Belady 现象：增加可用的页框反而产生更多缺页
3. 最近最久未使用算法 (LRU,Least Recently Used):LRU 选择最长时间没有使用的页
4. LRU 近似算法 (clock)。

• 用一个计数器记录对每一个页的访问次数。
  LFU Algorithm 最少使用算法：置换计数器值最小的一个页，即访问次数最少的页
  MFU Algorithm 最常使用算法，认为：最小计数的页也许刚刚被换入和使用，所以置换计数器值最大的页

# Allocation of Frames （页帧的分配）

• 每个进程所需要的最少的页的数目
  保证进程正常运行所需的最小物理块数
  若系统为某进程所分配的物理块数少于此值时，进程将无法正常运行 (频繁发生缺页)
  这个数目取决于指令的格式、功能和寻址方式。
  主要的分配策略

# 平均分配

平均

# 按比例分配

根据每个进程的大小来分配

# 优先分配

根据优先级而不是大小来使用比率分配策略
如果进程 Pi 产生一个缺页
选择替换其中的一个页框
从一个较低优先级的进程中选择一个页面来替换

# 全局替换 vs 局部替换

• 全局替换
  进程在所有的页中选择一个替换页面；一个进程可以从另一个进程中获得页面
• 局部替换
  每个进程只从属于它自己的页中选择

局部置换时，分配给每个进程的帧的数量不变
全局置换时，进程的帧数量会增加，但是无法控制页错误率
相对而言，全局替换会带来较高的系统吞吐率

• 固定分配 & 局部置换策略：
  基于进程的类型（交互型或批处理型等），或根据程序员、系统管理员的建议，为每个进程分配固定数目的物理块，在整个运行期间都不再改变
  如果进程在运行中发生缺页，只能从该进程已在内存的页面中选一页换出，然后再调入另一页，保证分配给该进程的内存空间不变。
• 可变分配 & 全局置换策略：
  系统为每个进程分配一定数目的物理块，OS 本身也保持一个空闲物理块队列
  当某进程发生缺页时，系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。
  当空闲物理块队列中的物理块用完时，OS 才从内存中选择一页调出，该页可能是任一进程的页。
• 可变分配 & 局部置换：
  根据进程的类型或程序员的要求，为每个进程分配一定数目的内存空间，并且在进程运行期间可根据情况（缺页率）适当增加或减少所分配的物理块数
  当某进程发生缺页时，只允许从该进程已在内存的页面中选出一页换出，而不影响其它进程的运行

# Thrashing（颠簸）

如果进程没有这些必需的帧，那么很快会出现缺页，此时需置换某个页，然而，其所有页都在使用，置换出去的页立刻又需要置换进来，因此，会不断的产生缺页。
这种频繁的调页行为称作颠簸，也叫抖动。

抖动：刚被换出的页很快又被访问，需重新调入，导致系统频繁地交换页面，以致大部分 CPU 时间花费在完成页面置换的工作上。

• CPU 利用率低下
• 操作系统认为需要增加多道程序设计的道数
• 系统中将加入一个新的进程
• 当进程个数达到一定数量时，内存紧张
• 会引起更多的缺页错误，更长的等待队列，CPU 利用率进一步降低，会继续增加多道程序的程度，出现颠簸
• 采用全局置换算法，新进程会置换页，而不管这些页是属于哪个进程。
• 而其他进程也需要这些页，因此会缺页，从而再从其他进程中置换页
• 进程在磁盘等待队列等待换页，就绪队列变空，CPU 利用率下降
• 局部置换能限制系统颠簸，但也会增加进程的有效访问时间因此，为了防止颠簸，应该给进程提供足够多的帧

# Locality model（局部模型）

一个 locality 是一个进程目前的活跃页面的集合
Locality 取决于程序的结构和它的数据结构
进程从一个局部移到另一个局部
局部可能重叠
给每个进程分配的最小物理块数不能少于 locality 的大小。这样，就可以使进程在把它的 locality 页全部装入内存之后，不再发生缺页

# 工作集理论

根据程序的局部性原理，进程在一段时间内总是集中访问一些页面 (活跃页面).
如果分配给一个进程的物理块数太少了，使该进程的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生缺页
如果能为进程提供与活跃页面数相等的物理块数，则可减少缺页中断次数

• 工作集窗口（Δ）是指对于给定的访问序列选取定长的区间，落在工作集窗口中的页面集合称为工作集
• 正确选择工作集窗口（Δ）的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响。
• 具体实现：
  OS 跟踪每个进程的工作集，并为其分配大于其工作集的物理块数。
  如果还有空闲物理块，则可启动另外的进程。
  如果所有进程的工作集之和超过了可用物理块的总数，则 OS 会选择暂停一个进程，该进程被换出，所释放的物理块可分配给其他进程。
• 其困难在于如何跟踪工作集合（一般采用定时器中断和引用位实现）

# 控制缺页频率

工作集理论可用于预调页，用于防止颠簸，但不够灵活
一种更加直接的防止颠簸的方法是控制缺页频率（ Page-Fault Frequency ）：
颠簸具有较高的缺页率，所以通过控制缺页频率，可以有效地防止颠簸的发生。

• 设置可接受的缺页率，如果缺页率太低，回收一些进程的页框，如果缺页率太高，就分给进程一些页框

# Other Considerations（其他考虑）

# 预先调页

• 提前调入部分可能需要的页
• Page size selection（页面尺寸选择）
  Fragmentation（碎片）页面大，则内碎片大
  table size （表大小）页面小，则页表占用的空间大
  I/O overhead（I/O 开销）磁盘 I/O 时间中传输时间和数据量有关系，但它占的比例很小，而寻道时间和旋转延迟时间占了很大的比例。所以页面尺寸比较大会有利于减少磁盘 I/O 时间。
  减少 I/O 及内存的占用：要求页面尺寸小 ，采用小页，总的 I/O 就会降低，因为小页能够更精确的匹配局部
  减少缺页率：要求页面尺寸大
  总的趋势：页面尺寸越来越大，这是由于 CPU 速度和内存容量的增长超过了磁盘速度的加快
• TLB 命中率 TLB (Translation Lookaside Buffer)
• TLB 范围
  通过 TLB 可以访问的内存量，等于 TLB 的个数与页大小的乘积
• 增加 TLB 范围
  增加页大小
  或者提供多种页大小
• Program structure（程序结构）
• I/O interlock and addressing（I/O 互锁和寻址）
• I/O 互锁
  在请求页面调度时，允许某些页锁在内存中
• 当用户内存有 I/O 操作时
  不对用户内存进行 I/O，通过系统内存进行
  允许页锁在内存中

# Demand Segmenation（请求段式）

• 操作系统以段来分配内存，它通过段描述符来进行跟踪
• 段描述符有一个有效位来说明段是否以在内存
  • 如果段已在主存中，继续存取
  • 如果不在内存中，缺段中断

# copy on write

• 父进程与子进程在开始时共享同一页面
• 如果任何一个进程修改共享页，则拷贝该页
• 只有被修改的页才会拷贝，COW 使进程创建更高效
• 从缓冲池中分配空闲页，空闲页在分配前被清零

# 内存映射文件

每次文件访问都需要一个系统调用和磁盘访问
用虚拟内存技术将文件 I/O 作为普通内存访问，称为文件的内存映射
文件的内存映射可以将某一磁盘块映射为内存的一页（或多页）。
开始的文件访问按普通请求页面调度将其读入内存
当读入内存后，之后文件的读写就按通常的内存访问来处理，简化了文件访问和使用
但是对内存中的文件进行写操作不会立即写到磁盘上的文件，可以定期检查并更新