操作系统之存储管理

一、基本概念：地址重定位

1.1 需要了解的内容

• 程序装载到内存才可以运行 通常，程序可以执行文件格式保存在磁盘上
• 多道程序设计模型 允许多个程序同时进入内存
• 每个进程有自己的地址空间 一个进程执行时不能访问另一个进程的地址空间 进程不能执行不合适的操作

1.2 要解决的问题

说明： 在左边的单处理器系统中，如果一个进程想要运行，那么必须将进程地址空间装载到物理内存中才可以运行。 而右边的是多处理器系统中有多个进程需要进入物理内存执行，这里要解决的问题就是，如何将进程地址空间合理的装载到物理内存中，如何合理的分配使用内存，使得每个进程能正确执行。

1.3 复习：进程地址空间

1.4 注意

• 进程中的地址不是最终的物理地址
• 在进程运行前无法计算出物理地址

这就需要地址重定位来解决这些问题。

二、地址重定位

• 逻辑地址（相对地址、虚拟地址） 用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余地址都相对于首地址而编址。 不能用逻辑地址在内存中读取信息。
• 物理地址（绝对地址、实地址） 内存中存储单元的地址，可直接寻址

为了保证cpu执行指令时可以正确访问内存单元，需要将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址，这一过程称为地址冲地位。

2.1 静态重定位与动态重定位

• 静态重定位 当用户程序加载到内存时，一次性实现逻辑地址到物理地址的转换。 一般可由软件完成。
• 动态重定位(重点) 在进程执行过程中进行地址变换，即逐条指令执行时完成地址转换。 支持程序浮动 需要硬件部件支持，较为常用。

2.2 动态重定位实现

三、物理内存管理

3.1 空闲内存管理

**说明：**我们对物理内存有不同的划分，一种是等长的划分，一种是不等长的划分。

• 数据结构 1、位图 对于等长划分这种我们可以使用位图的方式。每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）。对于不等长的划分可以使用下面两种分配结构。 2、空闲区表、已分配区表 表中每一项记录了空闲区（或已分配区）的起始地址、长度、标志 3、空闲块链表

3.2 内存分配算法

这里我们使用空闲区表、已分配区表为例来说明内存分配算法。

• 首次适配first fit 在空闲区表中找到第一个满足进程要求的空闲区
• 下次适配next fit 从上次找到的空闲区处接着查找
• 最佳适配best fit 查找整个空闲区表，找到能够满足进程要求的最小空闲区
• 最差适配worst fit 总是分配满足进程要求的最大空闲区

当找到满足进程需求的空闲区表后，需要将空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。

3.3 回收问题

• 内存回收算法
  • 当某一块归还后，前后空闲空间合并，修改内存空闲区表。
  • 四种情况 上相邻、下相邻、上下都相邻、上下都不相邻

3.4 伙伴系统(重点)

这是Linux底层内存管理采用的一种方法

• 一种经典的内存分配方案，是一种特殊的分离适配算法
• 主要思想：将内存按2的整数次幂进行划分，组成若干空闲块表；查找该链表找到能满足进程需求的最佳匹配块。
• 算法
  • 首先将整个可用空间看作一块：2^U
    • 假设进程申请的空间大小为s， 如果满足2^(U-1)，则分配整个块 否则，将块划分为两个大小相等的伙伴，大小为2^(U-1)
  • 一直划分下去直到产生大于或等于s的最小块。

3.5 伙伴系统例子

**说明：**从上图中可以看到上面的算法是如何工作的。

四、连续内存管理方案

4.1 单一连续区

特点：一段时间内只有一个进程在内存中，简单、内存利用率低。 这种方案是在早期系统中使用的，有三种不同的布局：

4.2 固定分区

• 把内存空间分割成若干个区域，称为分区
• 每个分区的大小可以相同也可以不同
• 分区大小固定不变
• 每个分区装一个且只能一个进程

说明： 不同的进程链分排在不同分区位置。缺点是有的进程链很长，一时得不到分区，但是此时可能有些空闲分区根本没有被使用。 于是还有右边这种排队方案，就是只有一个进程链，然后哪个分区空闲了，排在首位的进程就进入执行。早期手机中就是采用这种方法。

4.3 可变分区

• 根据进程的需要，把内存空闲空间分割出一个分区，分配给该进程
• 剩余部分称为新的空闲区
• 会导致一些问题：导致一些外碎片，这样会导致内存利用率下降。

碎片问题解决

• 碎片：很小的、不易利用的空闲区，导致内存利用率下降
• 解决方案：紧缩技术(又称压缩，紧致，搬家技术) 在内存中移动程序，将所有小的空闲区合并为较大的空闲区
• 紧缩时要考虑的问题 系统开销、移动时机

五、离散内存管理方案(重点)

5.1 页式存储管理方案

• 设计思想 用户进程地址空间被划分为大小相等的部分，称为页（page），从零开始编号。 这是逻辑地址空间上的称谓。
  • 内存空间按同样大小划分为大小相等的区域，称为页帧（page frame），从零开始编号
  • 内存分配（规则） 以页为单位进行分配，并按进程需要的页数来分配 逻辑上相邻的页，物理上不一定相邻。
  • 典型的页面尺寸：4K或4M
• 逻辑地址

**说明：**逻辑地址分为页号和页内地址（页内偏移），这种划分是系统自动完成的，对用户是透明的。

• 内存分配

**说明：**可以看到连续的进程地址空间映射到页帧中的物理内存是杂乱的。

**说明：**对于逻辑地址空间和物理内存空间的杂乱的映射，如何进行映射呢？这里我们需要使用页表来记录这种映射。

相关数据结构及地址转换

• 页表 由若干页表项（记录了逻辑页号与页框号对应关系）构成
  • 每个进程一个页表，存放在内存
  • 页表起始地址保存在何处？
• 空闲内存管理 其实我们可以使用位图就可以管理物理内存了
• 地址转换（硬件支持） **cpu**取到逻辑地址，自动划分为页号和页内地址； 用页号查页表，得到页框号，再与页内偏移拼接成物理地址。 在这种方案中我们也会遇到碎片问题，这里的碎片是内碎片。比如某个进程需要5页加一条指令，于是这里我们需要分配6页给这个进程。

5.2 段式存储管理方案

• 设计思想 用户进程地址空间：按程序自身的逻辑关系划分为若干个程序段，每个段都有一个段名
  • 内存空间被动态划分为若干长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定
  • 内存分配：以段为单位进行分配，每段在内存中占据连续空间，但各段之间可以不相邻。其实就是将程序分为若干段，每段占用一块内存空间。
• 逻辑地址

**说明：**和页式类似，逻辑地址分为段号和段内地址。 不同的是段号和段内地址不是自动划分的。看个例子：

**说明：**同样的，和页式类似，每个段的位置都不一样或不连续。而我们这里使用段表来将逻辑段号和物理内存映射起来。其中段表包含长度和段起始地址。

相关数据结构及地址转换

• 段表 每项记录了段号，段首址和段长之间的关系 每个进程一个段表，存放在内存 段表起始地址保存在何处？
• 物理内存管理 我们可以使用不等长的分配方案进行管理
• 地址转换（硬件） **cpu**取到逻辑地址，用段号查段表，得到该段在内存的起始地址，与段内偏移地址计算出物理地址

5.3 段页式存储管理方案

• 背景 综合页式、段式方案的优点，克服二者的缺点
• 思想 用户进程划分：先按段划分，每一段按页面划分 逻辑地址：

内存划分：同页式存储管理方案 内存分配：以页为单位进行分配

• 数据结构及有关操作 段表：记录了每一段的页表起始地址和页表长度 页表：记录了逻辑页号与页框号对应关系，每一段有一张页表，一个进程有多个页表 空闲区管理：同页式管理 内存分配、回收：同页式管理
• 地址转换 由硬件支持

5.4 小结

六、交换技术

6.1 内存不足时如何管理

即如何在一个较小的物理内存空间中运行一个会占用较大地址空间的进程？

6.2 内存“扩充”技术

• 内存紧缩技术（例如：可变分区。即有时候可以使用内存紧缩技术来满足进程所需内存），但是这种技术一般不能解决问题
• 覆盖技术（overlaying）
• 交换技术（swapping）
• 虚拟存储技术（virtual memory）

6.3 覆盖技术

• 解决问题：程序大小超过物理内存总和
• 程序执行过程中，程序的不同部分在内存中相互替代。
  • 按照其自身的逻辑结构，将那些不会同时执行的程序段共享同一块内存区域
  • 要求程序各模块之间有明确的调用结构
• 程序员声明覆盖结构，操作系统完成自动覆盖

这种技术主要用于早期的操作系统，现在使用不多。

6.4 交换技术

• 设计思想 内存空间紧张时，系统将内存中某些进程暂时移动到外存，把外存中某些进程交换进内存，占据前者所占用的区域（进程在内存与磁盘之间的动态调用）。
• 讨论：实现时遇到的问题 进程的哪些内容要交换到磁盘？会遇到什么困难？ 在磁盘的什么位置保存被换出的进程？ 交换时机？ 如何选择被换出的进程？ 如何处理进程空间增长？
• 哪些内容要交换到磁盘？会遇到什么困难？ 1、运行时创建或修改的内容：栈和堆 2、交换区：一般系统会指定一块特殊的磁盘区域作为交换空间，包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问。 3、何时需要发生交换？只要不用就换出；内存空间不够或有不够的危险时换出，一般与调度器结合使用 4、考虑进程的各种属性；不应换出处于等待I/O状态的进程
• 进程空间增长的困难及解决

**说明：**这里给出了两种解决方案，一种是左边的为栈预留一部分空间；一种是右边的让数据区和栈去同向增长，即在一个预留区中增长。

七、虚拟存储技术

• 所谓虚拟存储技术是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作
• 虚拟地址空间即为分配给进程的虚拟内存
• 虚拟地址是在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分
• 特点(重点)
  • 离散性
  • 多次性
  • 对换性(交换性)
  • 虚拟性

7.1 存储器的层次结构

• 综合读写速度、存储容量、价格等因素：

7.2 虚拟内存与存储体系

• 把内存与磁盘有机地结合起来使用，从而得到一个容量很大的“内存”，即虚拟内存
• 虚存是对内存的抽象，构建在存储体系之上，由操作系统协调各存储器的使用
• 虚存提供了一个比物理内存空间大得多的地址空间,扩大逻辑内存容量

7.3地址保护

• 确保每个进程有独立的地址空间
• 确保进程访问合法的地址范围，即我们需要访问地址越界
• 确保进程的操作是合法的

7.4 虚拟页式(请求页式)(重点)

我们将虚拟存储技术和页式存储管理方案结合起来得到了虚拟页式存储管理系统。具体有两种方式，一是请求调页，二是预先调页。以cpu时间和磁盘换取昂贵内存空间，这是操作系统中的资源转换技术。

• 基本思想
  • 进程开始运行之前，不是装入全部页面，而是装入一个或零个页面
  • 之后，根据进程运行的需要，动态装入其他页面
  • 当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面

八、页表及页表项的设计

2.1 页表项设计

• 页表由页表项组成
• 页框号、有效位、访问位、修改位、保护位 页框号（内存块号、物理页面号、页帧号）：通过页框号给出具体对应的物理页面 有效位（驻留位、中断位）：表示该页是在内存还是在磁盘 访问位：引用位。当要使用某个页面时，需要访问位作出相应的记录，表示此页面被访问过 修改位：此页在内存中是否被修改过 保护位：读/可读写

通常，页表项是硬件设计的。

2.2 页表

• 32位虚拟地址空间的页表规模？ 页面大小为4k，页表项大小为4字节，则一个进程地址空间有2^20页。这里首先是虚拟地址空间可以达到2^32字节，这里注意：在二级页表中才可以表示2^32的地址空间，除以页面大小可以得到有多少个页面。而一个页表项可以表示1k的页面，于是页表项就要占用1024页（页表页，就是页表项占用的空间）。
• **64**位虚拟地址空间 页面大小为4k，页表项大小为8字节，则页表规模为32000TB。这里没说清楚，到底是几级页表中的结果？
• 页表页在内存中若不连续存放，则需要引用页表的地址索引表，即页目录。即一个多级页表结构。

2.3 二级页表结构及地址映射

**说明：**这里还是32位的虚拟地址空间。每个进程有一个页目录，根据页目录得到页表地址，然后从页表中的页表项的页框号找到真正的物理内存地址。32位的虚拟地址分为页目录偏移、页表偏移和页内偏移。页目录地址保存在一个寄存器中，根据此地址找到页目录起始地址，然后根据月页目录偏移找到对应的页表地址，根据页表偏移找到页表项，从页表项中取得页框号，然后结合页内偏移找到对应的物理内存。对于二级页表，在32位系统中可以表示4G的虚拟地址空间。如果需要超过4G的虚拟地址空间，则二级页表满足不了。

2.4 I386页目录和页表项

**说明：**总共有32位地址。

2.5 反转（倒排）页表

2.6 地址转换过程及TLB

**说明：**上图是虚拟地址通过页表和物理地址映射的关系。这个过程是有内存管理单元完成的。

2.6.1 快表（TLB）的引入

• 问题 页表：两次或两次以上的内存访问。如果是二级页表就要访问两次，四级页表访问四次.cpu的指令处理速度与内存指令的访问速度差异较大，cpu的速度得不到充分利用。 那如何加快地址映射速度，以改善系统性能？这里我们利用程序访问的局部性原理：引入快表（TLB）。

2.6.2 快表

• TLB（Translation Look-aside Buffers） 在cpu中引入的高速缓存，可以匹配cpu的处理速度和内存的访问速度。是一种随机存取型存储器，除连线寻址机制外，还有接线逻辑，能按特定的匹配标志在一个存储周期内对所有的字同时进行比较。
• 快表一般称为相连存储器：按内容并行查找
• 保证正在运行进程的页表的子集（部分页表项）

2.6.3 加入TLB后地址转换过程

**说明：**首先根据虚拟地址去查TLB，如果能找到页框号，则直接和偏移结合找到对应的物理内存；如果TLB中没有页框号，则需要去查页表，之后在找到对应的物理内存；在页表中如果对应的页表项无效，则会出现page fault的异常，然后由系统处理之后再进行同样的操作。

2.7 页错误（page fault）

• 又称页面错误、页故障、页面失效
• 地址转换过程中硬件产生的异常
• 具体原因 1、所访问的虚拟页面没有调入物理内存，即缺页异常 2、页面访问违反权限（读/写、用户/内核），比如用户访问内核空间。 3、错误的访问地址，比如

图中标注的位置都是有内容的，如果访问地址指向没有标注（没有内容）的位置，则就是错误的访问地址。

2.8 缺页异常处理

• 是一种页错误
• 在地址映射过程中，硬件检查页表时发现所要访问的页面不在内存，则产生异常–缺页异常
• 操作系统执行缺页异常处理程序：获得磁盘地址，启动磁盘，将该页调入内存
  • 如果内存中有空闲页框，则分配一个页框，将调入页装入，并修改页表中相应页表项的有效位及相应的页框号
  • 若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘。

三、虚拟页式存储中软件相关策略

3.1 驻留集

• 所谓驻留集，是指在某段时间间隔内，进程要访问的页面集合
• 驻留集大小：给每个进程分配多少页框？
• 固定分配策略 进程创建时确定。可以根据进程类型（交互、批处理、应用类）或者基于程序员或系统管理员的需要来确定
• 可变分配策略 根据缺页率评估局部性表现 缺页率高–>增加页框数 缺页率低–>减少页框数 系统开销

3.2 置换问题

• 置换范围

计划置换页面的集合是局限在产生缺页中断的进程，还是所有进程的页框？

• 置换策略
  • 在计划置换的页框集合中，选择换出哪一个页框？其目标是置换最近最不可能访问的页。
  • 根据局部性原理，最近的访问历史和最近将要访问的模式间存在线惯性，因此，大多数策略都基于过去的行为来预测将来的行为。**注意：**置换策略设计得越精致、越复杂，实现的软硬件开销就越大。当然有些被锁定的页框是不能被置换的。

3.3 页框锁定

为什么要锁定页面？

• 采用虚拟存储技术后，相关的开销使得进程的运行时间变得不确定
• 给每一页框增加一个锁定位
• 通过设置相应的锁定位不让操作系统将进程使用的页面换出内存，避免产生由交换过程带来的不确定的延迟
• 例如：操作系统核心代码、关键数据结构、I/O缓冲区。特别是正在I/O的内存页面。Windows中的VirtualLock和VirtualUnLock函数。

3.4 清除策略

3.5 页面置换算法(页面淘汰算法)

最佳算法–>先进先出–>第二次机会–>时钟算法–>最近未使用–>最近最少使用–>最不经常使用–>老化算法–>工作集–>工作集时钟

3.5.1 最佳置换算法（OPT）

• 设计思想 置换以后不再需要的或最远的将来才会用到的页面
• 实现 基于进程的走向来实现，更多的是作为一种标准来衡量其他算法的性能。

3.5.2 先进先出算法（FIFO）(重点)

• 选择在内存中驻留时间最长的页并置换它
• 实现：页面链表法

3.5.3 第二次机会算法（SCR）

在先进先出算法的基础上进行该机而来的，此算法按照先进先出算法选择某一页面，检查其访问位R，如果为0，则置换该页；如果为1，则给第二次机会，并将访问位置零，并将其从链头取下放到链尾。

3.5.4 时钟算法（CLOCK）

在第二次机会算法中当给某个页面第二次机会的时候，将其访问位置零，然后将其挂到链尾，这都是需要开销的，于是我们改进为时钟算法。

**说明：**其实就是将之前的链表改为了环形链表，当给某个页面第二次机会的时候不需要将其取下然后挂到链尾，只需要移动一下指针即可，这样可以降低开销。

3.5.5 最近未使用算法（NRU）

3.5.6 最近最少使用算法（LRU）(重点)

选择最后一次访问时间距离当前时间最长的一页并置换，即置换未使用时间最长的一页

• 性能接近最佳页面置换算法
• 实现：时间戳或维护一个访问页的栈，导致开销较大。下面看一种硬件实现：

**说明：**访问第0页时先将页的第0行置为1，然后将第0列置为0， 以此类推，在访问完之后将行编号最小的那一页置换出去 我们看到j中最小的是第1行，于是将第1页置换出去。当然这里只有四页。

3.5.7 最不经常使用算法（NFU）

即Not frequently Used，选择访问次数最少的页面置换

3.5.8 老化算法（AGING）

• 改进（模拟LRU）：计数器在加R前先右移一位，R位加到计数器的最左端。

这样如果R值为零，则计数器没有影响，如果值为1，则会变得很大，于是如果一个页面长久不被访问，则计数器值就会越来越小。最后选择值最小的置换出去。

3.5.9 页面置换算法的应用

例子：

• 系统给某进程分配了三个页框（采用固定分配策略），初始为空
• 进程执行时，页面访问顺序为：2 3 2 1 5 2 4 5 3 2 5 2

要求：

计算应用FIFO、LRU、OPT算法时的缺页次数

应用FIFO、LRU页面置换算法

可以看到FIFO发生六次缺页异常，而LRU发生四次缺页异常。

应用OPT页面置换算法

发生三次缺页异常。

3.5.10 BELADY现象

例子：系统给某进程分配m个页框，初始为空页面访问顺序为

1 2 3 4 1 2 5 1 2 3 4 5，采用FIFO算法，计算当m=3和m=4时的缺页中断次数。

结论：m=3时，缺页中断九次；m=4时，缺页中断十次。注意：FIFO页面置换算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加。

3.5.11 页面缓冲算法(PBA)(重点)

该算法采用了可变分配和局部置换方式，置换算法则采用FIFO。 该算法规定将一个被淘汰的页放入两个链表中的一个， 若页面未被修改，直接放入空闲链表末尾，否则放入已修改页面链表末尾。 这种方式使得已修改和未修改的页面都仍然留在内存中，当进程以后再次访问这些页面时，只需花较小的开销，使这些页面又返回到该进程的驻留集中。 当被修改页面达到一定数量时，才一次性地将他们写回到外存，这样就显著地减少了外存的I/O次数

假设采取FIFO固定分配局部置换，每次缺页都要淘汰该进程最早装入内存的页面，而这里采用可变分配局部置换，即分配进程一个空白块，将原本应该淘汰的最早装入的页面挂在两个队列之一，直到没有空白块或修改页面达到上限才启动磁盘写回外存

3.6 页面置换算法2：工作集算法

3.6.1 影响缺页次数的因素

• 页面置换算法的不同
• 页面本身的大小
• 程序的编制方法
• 分配给进程的页框数量

缺页越多，系统的性能越差，这称为颠簸（抖动）：虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动。

3.6.2 页面尺寸问题

• 确定页面大小对分页的硬件设计非常重要，而对操作系统是个可选的参数
• 要考虑的因素 内部碎片 页表长度 辅存的物理特性
• Intel 80x86/Pentium: 4096或4M
• 多种页面尺寸：为了有效使用TLB带来灵活性，但给操作系统带来复杂性。

3.6.3 程序编制方法对缺页次数的影响

例子：

分配了一个页框，页面大小为128个整数，矩阵A(128 x 128)按行存放。

可以看到左边是按列赋值，右边是按行赋值。按列编制就是首先读入第一页（一行，因为矩阵是按行存放的），然后给第0个位置赋值，每次读入一行，直到将第0列赋值完，读完之后再给第1列赋值，这样会产生128*128次缺页异常；而按行赋值，第一次读入一页，给第0行的所有元素赋值，这样会产生128次缺页异常。于是可以看到程序的编制方法对缺页次数是有很大影响的。

3.6.4 分配给进程的页框数与缺页率的关系

**说明：**可以看到页框数越多那么缺页率越低，但是我们不可能给出所有的页框，于是需要找到一个平衡点W，超过这个点之后页框数的增加对缺页率的降低有限，这也是工作集算法的出发点。

3.7 工作集模型

• 基本思想 根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使得该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。

如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数，这是由Denning提出的。

• 工作集：一个进程当前正在使用的页框集合

• 例子

3.8 工作集算法

四、其他与存储管理相关技术

4.1 内存映射文件

• 基本思想 进程通过一个系统调用（mmap）将一个文件（或部分）映射到其虚拟地址空间的一部分，访问这个文件就像访问内存中的一个大数组，而不是对文件进行读写
• 在多数实现中，在映射共享的页面时不会实际读入页面的内容，而是在访问页面时，页面才会被每次一页的读入，磁盘文件则被当作后备存储。
• 当进程退出或显式地解除文件映射时，所有被修改页面会写回文件

4.2 支持写时复制技术

**说明：**如图，两个进程共享同一块物理内存，每个页面都被标志成了写时复制。注意：共享的物理内存中每个页面都是只读的。如果每个进程想改变某个页面时，就会与只读标记冲突，而系统在检测出页面是写时复制的，则会在内存中复制一个页面，然后进行写操作。新复制的页面对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的。