第 3 章存储管理

Pluveto

Sep 24, 2021 发布

? 次浏览

存储管理

3.1 无存储器抽象

即让程序直接访问物理内存

缺点：保护和重定位

用户程序很容易破坏 OS
难以同时运行多个程序

3.2 地址空间

1 地址空间

每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空

2 简单动态重定位

把每个进程的地址空间映射到物理内存的不同部分。

当一个进程运行时，程序的起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器

每次进程访存，会自动把地址加上基质，并检查是否越界。（这也是缺点：每次都要进行加法和比较运算）

3 交换

两种处理内存超载的通用方法：交换（swapping）和虚拟内存（virtual memory）

交换（swapping）技术：把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘

虚拟内存：让程序在只有一部分被调入内存的情况下运行。

交换会导致内存产生空闲区（空洞，hole），所以要进行空闲区合并（内存紧缩，memory compaction）内存紧缩的效率很低。

空闲内存管理

使用 Bitmap 管理

按照一定单位划分内存，每个单位对应到内存的一位，表示空闲或占用。

使用链表管理

链表的结点表示一个进程或一个空闲区。保存有如下信息：

类型（空闲或进程）
起始地址
长度
下一节点指针

为新建的进程分配内存：

首次适配（first fit）算法：存储管理器沿着段链表进行搜索，直到找到一个足够大的空闲区，将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。

下次适配（next fit）算法：每次找到合适的空闲区时都记录当时的位置。以便在下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次适配算法那样每次都从头开始。（性能略低于首次适配法）

最佳适配（best fit）算法：搜索整个链表（从开始到结束），找出能够容纳进程的最小的空闲区。更慢，而且更浪费内存，因为会产生大量无用的小空闲区。

最差适配（worst fit）算法：总是分配最大的可用空闲区

为进程和空闲区维护各自独立的链表，可以提高分配内存的效率，但是内存释放的速度会变慢。

快速适配（quick fit）算法：它为那些常用大小的空闲区维护单独的链表。例如，有一个 n 项的表，该表的第一项是指向大小为 4KB 的空闲区链表表头的指针，第二项是指向大小为 8KB 的空闲区链表表头的指针，第三项是指向大小为 12KB 的空闲区链表表头的指针，以此类推。

3.3 虚拟内存

虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作一页或页面（page）。每一页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

分页

由程序产生的地址称为虚拟地址（virtual address），它们构成了一个虚拟地址空间（virtual address space）

在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元（Memory Management Unit，MMU），MMU 把虚拟地址映射为物理内存地址

虚拟地址空间按照固定大小划分成称为页面（page）的若干单元。在物理内存中对应的单元称为页帧（page frame）。

当程序试图访问地址 0 时，例如执行下面这条指令

MOV REG,0

将虚拟地址 0 送到 MMU。MMU 看到虚拟地址落在页面 0（0～4095），根据其映射结果，这一页面对应的是页框 2（8192～12 287），因此 MMU 把地址变换为 8192，并把地址 8192 送到总线上。内存对 MMU 一无所知，它只看到一个读或写地址 8192 的请求并执行它。MMU 从而有效地把所有从 0～4095 的虚拟地址映射到了 8192～12 287 的物理地址。

缺页中断 若程序访问了未映射的页面，则 MMU 使 CPU Trap 到 Page fault。然后 CPU 把一个不常用的页帧暂时存到磁盘（换出），把需要的页面读入回收的页帧（换入）

页表

Virtual address:
| Virtual Page Num | Offset |

页表项的结构

高速缓冲禁止位：1 则禁止被 cache
访问位：在被访问时设置，用于缺页中断选择是否淘汰
修改位：是否被修改过，如果是，说明磁盘上的副本无效
保护位：0 表示 R/W，1 表示 ROnly。也可以用三位表示读、写、执行
存在位：1 表示表项有效，0 表示表项对应的虚拟页面不在内存中
页帧号

虚拟内存本质上是用来创造一个新的抽象概念 —— 地址空间，这个概念是对物理内存的抽象，类似于进程是对物理机器（CPU）的抽象。

加速分页

要解决的问题：

映射速度的问题
页表体积过大的问题

转换检测缓冲区（Translation Lookaside Buffer，TLB）：一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不必再访问页表，又称为相联存储器（associate memory），TLB 通常设计在 MMU 中。

TLB 的工作原理：

func tlb(vaddr, op):    
    items.select(
        item => 
            item.match(addr)
            and item.valid
        if item.protect_allow(op):
            return item.frame
        else 
            throw ProtectionFault
    )
    if not found:
        find_new_and_replace_old()

输入虚拟地址，硬件通过 TLB 中所有表项同时（即并行）进行匹配，判断虚拟页面是否在其中。如果发现了一个有效的匹配并且要进行的访问操作并不违反保护位，则将页框号直接从 TLB 中取出而不必再访问页表。如果虚拟页面号确实是在 TLB 中，但指令试图在一个只读页面上进行写操作，则会产生一个保护错误，就像对页表进行非法访问一样。当虚拟页号不在 TLB 中时发生的事情值得讨论。如果 MMU 检测到没有有效的匹配项时，就会进行正常的页表查询。接着从 TLB 中淘汰一个表项，然后用新找到的页表项代替它。这样，如果这一页面很快再被访问，第二次访问 TLB 时自然将会命中而不是不命中。当一个表项被清除出 TLB 时，将修改位复制到内存中的页表项，而除了访问位，其他的值不变。当页表项中从页表装入到 TLB 中时，所有的值都来自内存。

TLB 失效的情况

软失效：TLB 未命中（页面在内存而非 TLB）

硬失效：页面本身不在内存

针对大内存的页表

多级页表

例如按照下面的方法编制虚拟地址：

PT1 10BIT | PT2 10BIT | OFFSET 12 BIT

从而可以建立二级页表

倒排页表

在实际内存中每一个 frame 有一个 entry，而不是每一个 vpage 有一个 entry。

其实说白了就是建立一个页帧到进程的映射。

在正常页表中，可以通过简单的解引用查找物理页帧，但是使用倒排页表，每次都需要进行查表。

3.4 页面置换算法

缺页中断时如何决定换出哪一个页面，从而为调入的页面腾出空间？

最优页面置换算法

说白了就是预判页面的使用频率，换出最低频使用的。

每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。

如果一个页面在 800 万条指令内不会被使用，另外一个页面在 600 万条指令内不会被使用，则置换前一个页面

缺点：无法实现，操作系统无法预测未来

最近未使用（Not Recently Used，NRU）

页面关联到 访问位和 修改位(r, m)。当执行对应操作时设置 1. r 定期重置。

根据 RM 组合，页面被分为四类，优先级排序根据：访问高于未访问、修改高于未修改，访问大于修改。NRU 随机选择低优先级的换出。

先进先出（FIFO）

队列

第二次机会（Second Chance）

算法是寻找一个在最近的时钟间隔内没有被访问过的页面。如果所有的页面都被访问过了，该算法就简化为纯粹的 FIFO 算法

具体实现：检查队头（最旧），若 R=1 则放到队尾，否则直接置换

时钟页面置换（Clock）

循环队列的 FIFO，主要为了提高性能

最近最少使用（LRU）

置换未使用时间最长的页面。

缺点：代价高

最不常用（Not Frequently Used）

软件模拟 LRU，使用软件计数。

具体：每个页面关联一个计数器，每次将有 R=1 的计数增加。

缺点：没有遗忘机制

比如一个页面之前频繁被访问，导致这个它的计数器很大，但是后来它不被访问了，而它的计数器的值还是很大，所以它一直不会被置换出去。

老化算法

通过计数器二进制中 1 的数量标记使用频繁程度

具体：在 R 位被加进之前将计数器右移一位，其次，将 R 位加到计数器最左端的位而不是最右端的位

工作集页面置换算法

工作集时钟页面置换算法

分页系统的设计

局部分配和全局分配：这是相对于进程而言。比如 LRU，局部就是换出当前进程最拖后腿的，全局就是换出全局最拖后腿的

工作集 一个进程当前正在使用的页面的集合称为它的工作集。

页面抖动（颠簸） 刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。

工作集大小

如何决定一开始给进程分配多大的内存？

固定分配，局部置换：分配固定的物理块。缺页进行调入调出。缺点：难以确定初始分配物理块数目。
可变分配，全局置换：分配初始物理块，维护一个空闲物理块队列，缺页时动态分配物理块给进程并装入页
可变分配，局部置换：分配初始物理块，缺页时从该进程在内存的页面换出，频繁缺页时增加物理块（需要统计缺页率）

调入页面的时机

预先调页 一次调入一些相邻页 请求调页 页面只有在程序执行期间被请求时才被加载

调入页面的来源

根据交换区容量：
1. 交换区够用：全部从交换分区调入
2. 交换区不够：
  1. 不会被修改的文件：从文件区调入
  2. 可能被修改的文件，从交换区调入，调出到交换区
Unix 方式：与进程有关的文件都放在文件区，故未运行过的页面，都应从文件区调入。曾经运行过但又被换出的页面，由于是被放在对换区，因此下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则无需再从对换区调入。

共享页面

共享程序文本段，私有数据段

共享只读数据段，数据被改写后分叉，变为私有

共享库

这里的库是指 *.so/ *.dll 这样的动态库。

内存映射文件

一般在访问时按页读入，退出时改动写回文件。

清除策略

即写回的策略，

虚拟内存接口

3.6 实现

分页相关工作

进程创建时：创建页表，分配空间，初始化交换区，进程表添加页表和交换区相关信息
进程执行时：重置 MMU，刷新 TLB
缺页中断时：查询中断源，响应中断（如换入换出），备份 PC，重新执行引起中断的指令
进程终止时：释放页表，页面，硬盘空间。

如果某些页面是与其他进程共享的，当最后一个使用它们的进程终止的时候，才可以释放内存和磁盘上的页面。

缺页中断的处理

缺页中断发生时的事件顺序如下：

硬件陷入内核，在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的 CPU 寄存器中。
启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。
如果选择的页框 “脏” 了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
一旦页框 “干净” 后（无论是立刻还是在写回磁盘后），操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面被装入后，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。
恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。

指令备份

CPU 的设计者们提供了一种解决方法，就是通过使用一个隐藏的内部寄存器。在每条指令执行之前，把程序计数器的内容复制到该寄存器。这些机器可能会有第二个寄存器，用来提供哪些寄存器已经自动增加或者自动减少以及增减的数量等信息。通过这些信息，操作系统可以消除引起缺页中断的指令所造成的所有影响，并使指令可以重新开始执行。