操作系统(二)内存管理的基础知识

本文主要涉及操作系统的简介、硬件结构、内存管理、进程管理、文件系统、设备管理等内容，可以作为学习操作系统的辅助文本记录。撰写本文的目的主要是针对操作系统整体做一个相对完整的梳理，以便后续回顾之用。 本文是第二篇，讲述操作系统的内存管理相关的基本内容。 第一篇：操作系统(一)基础知识及操作系统启动

内存是计算机中十分宝贵的资源，相较于磁盘这种大容量低速度的存储而言，内存资源容量小速度高，需要设计合理的管理方式以求最大效率地使用。

内存管理的四个目标：

地址空间定义

物理地址空间–硬件支持的地址空间（内存和磁盘内存）。

逻辑地址空间–一个运行的程序所拥有的内存范围（一维线性地址空间）

地址生成

Q: 逻辑地址空间是如何生成的？

A: 程序编译之后可以变为汇编程序。比如C程序中的变量名就是逻辑地址，汇编程序转换成.o文件其中是机器语言。linker是可以将多个.o程序转换为可执行程序，loader会将可执行程序载入到内存中。这个逻辑地址的生成基本基本不需要操作系统的参与。

CPU通过MMU查找逻辑地址的物理内存地址，找不到会产生缺页中断，去内存中查找。(具体见后面内存管理的相关内容)

地址安全检查

操作系统的地址安全检查是一项重要的机制，用于保护计算机系统免受恶意软件和非法访问的攻击。它主要涉及以下几个方面：

随着内存分配和进程使用，有一些空闲内存无法被继续利用使用，称这些空闲内存为内存碎片。

内存碎片分为 外部碎片和 内部碎片。

从地址起始处开始寻找，找到第一个能可以容纳所需内存的空闲块就分配。

优点： 高地址会有大块的空闲分区；

缺点：外部碎片，分配大块时则较慢。

分配与需求差别最小的空闲内存块

优点：避免分割大空闲块的拆分，外部碎片产生的尺寸小，当大部分分配时是小尺寸内存，十分有效；

缺点：产生的外部碎片尺寸很小，导致后续根本无法利用而使用；

分配与需求差别最大的空闲内存块

优点：避免产生琐碎的外部碎片，分配尺寸为中大型的比较合适；

缺点：拆大块导致后来分配大的分配块，分配不到；

以上为简单的内存分配算法，可以看到他们分别适合不同场景下的内存分配。

是指通过调整进程占用的分区位置来减少或避免分区碎片；

碎片紧凑（Compaction）：通过移动分配给进程的内存分区，以合并内存碎片；

分区兑换（Swapping in/out）：通过抢占并回收处于等待状态进程的分区，以增大可用内存空间；

分区兑换带来更多的问题：将哪一个等待的程序换出那？什么时候执行换入、换出这一操作那？

后续会介绍到。

连续分配分配给程序的物理内存必须连续

连续分配既有内碎片又有外碎片。

非连续分配的设计目标：提高内存利用效率和管理灵活性。

非连续内存的优点：

为什么要有虚拟内存？单片机中没有操作系统，每次都要烧录新程序，并且单片机上只能运行一个程序，这是因为单片机的CPU是直接操作内存的物理地址的。如果另一个程序也操作了某个物理地址，那另一个程序肯定直接崩溃了。

Q: （疑惑：如果限定单片机中程序的可访问物理地址，那么是否可以运行多个程序那？）

A: 应该是可以的，但也要设置轮询，并且在切换执行不同程序时，需要保存和恢复各个程序的上下文信息，包括程序计数器、堆栈指针等。这样才能确保程序在切换执行时能够正确地继续执行。

但是对于很多程序在运行的情况下，自己直接写，无疑大大提高了编程的难度。因此虚拟地址的产生就是解决这个问题的，让我们能够不关心物理地址，甚至不用操心程序的中断和恢复，从而降低编程的难度。

操作系统的虚拟内存正是解决这个问题的，操作系统为每个进程分配独立的虚拟地址，所有进程都不访问物理地址。虚拟地址是如何对应物理地址的，进程完全不需要关心，从而可以多个程序的运行。

操作系统引入了虚拟内存，进程持有的虚拟地址会通过 **CPU 芯片中的内存管理单元（MMU）**的映射关系，来转换变成物理地址，然后再通过物理地址访问内存。

Q: 虚拟内存如果没有页命中，就要产生缺页，调用缺页异常处理程序，效率会不会很低？

A: 不会的，因为局部性原理已经告诉我们尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存总的大小，也会产生一定的缺页。但局部性原则告诉我们在任何时刻，程序将趋向于在一个较小的活动页面(active page)集合上工作，这个集合叫做工作集(working set)或者常驻集合(resident set)。在初始开销，也就是工作集页面调度到内存中之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。因此虚拟内存的技术实际上是十分高效的。

主要通过 内存分段和 内存分页来管理虚拟内存地址和物理地址之间的关系

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来。

内存分段是一种管理虚拟内存地址和物理地址之间映射的方法

分段机制下的虚拟地址主要由两部分组成，分别是段选择因子和段内偏移量

段选择子中最重要的是段号，用作段表的索引。段表中所保存的是段的基地址、段的界限和特权等级等。

段内偏移量位于0~段的界限之间。如果段内偏移量是合法的，就将段基地址+段内偏移量得到物理地址。

内存分段的方法可以将虚拟地址映射到物理地址中去，然而这样的方法有以下两个问题：

由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片的问题。内存分段管理可以做到段根据实际需求分配内存，所以有多少需求就分配多大的段，所以不会出现内部内存碎片。

我们可以通过碎片紧凑（内存交换）的技术整理内存，以减少外部碎片。但如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。这也就是所谓的内存交换效率低的问题。

系统将虚拟内存分割为称为 **虚拟页（Virtual Page, VP）**的大小固定的块，每个虚拟页的大小为 P = 2 p P = 2^p P=2p字节。物理内存被分割位物理页（Physical Page, PP） 大小也为P字节（物理页也被称为 页帧（Page frame））

内存分页可以用来解决“外部内存碎片”和“内存交换效率低”的问题。

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB。虚拟地址与物理地址之间通过页表来映射。

而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。

Q: 内存分页是如何解决“外部内存碎片”的问题？ (少出现外部碎片)

A: 内存分页由于内存空间都是预先划分好的，也就不会像内存分段一样，在段与段之间会产生间隙非常小的内存，这正是分段会产生外部内存碎片的原因。而采用了分页，页与页之间是紧密排列的，所以不会有外部碎片。但是，因为内存分页机制分配内存的最小单位是一页，即使程序不足一页大小，我们最少只能分配一个页，所以页内会出现内存浪费，所以针对内存分页机制会有内部内存碎片的现象。

Q: 内存分页是如何解决“内存交换效率低”的问题的？（交换的数据量减小）

A: 如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。

Q: 内存分页机制下，虚拟地址和物理地址是如何映射的？

A: 在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址。

内存分页步骤：

页式内存的问题：

如何处理？

简单的分页有时候占用空间太大。32位操作系统中虚拟空间地址一共有4GB，假设一个页的大小定为 4KB(2^12)，那么4GB的虚拟内存一共有100万页左右（2^20）左右，假如每个页需要4字节存储，那么就需要 4MB来存储这个页表。而一个进程就有一个自己的虚拟地址空间，100个进程则需要 400MB来存储，这就很恐怖了。

因此出现了多级页表（Multi-Level Page）来解决这样的问题。将页表（一级页表）分为 1024 个页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页。每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存。如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有 20% 的一级页表项被用到了，那么页表占用的内存空间就只有 4KB（一级页表） + 20% * 4MB（二级页表）= 0.804MB，这对比单级页表的 4MB 是不是一个巨大的节约？

页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建）。

64 位的系统，两级分页肯定不够了，就变成了四级目录，分别是：

多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。

我们就可以利用这一特性，把最常访问的几个页表项存储到访问速度更快的 硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer， 翻译后备缓冲器） ，通常称为页表缓存、转址旁路缓存、快表等。

在 CPU 芯片里面，封装了内存管理单元（Memory Management Unit）芯片，它用来完成地址转换和 TLB 的访问与交互。

有了 TLB 后，那么 CPU 在寻址时，会先查 TLB，如果没找到，才会继续查常规的页表。

TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个。

不让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应

页寄存器（Page Registers）

每个帧与一个页寄存器相关联，寄存器内容包括：

Q :页式内存管理已经很方便，为什么还要用段页式内存管理？

A: 段式内存管理和页式内存管理各有其优势和适用场景，因此在某些情况下会选择使用段页式内存管理。

段式内存管理的优势在于：

而页式内存管理的优势在于：

当系统需要同时满足对逻辑地址的分段和对物理内存的分页管理时，段页式内存管理结合了两者的优点。因此，在一些对内存管理要求比较复杂的场景下，选择使用段页式内存管理可以更好地满足系统的需求。

总之，段页式内存管理相比于单纯的段式或页式管理，能够更加灵活地满足不同程序的内存管理需求，是一种更为综合的内存管理方式。

段页式内存管理实现的方式：

这样，地址结构就由段号、段内页号和页内位移三部分组成。

目标：在较小的可用内存中运行较大的程序

方法：将程序划分为若干功能相对独立的模块；将不会同时执行的模块共享同一块内存区域；

缺点：

目标：增加正在运行或需要运行的程序的内存

方法：可将暂时不能运行的程序放到外存中；

交换时机：内存空间不够或有不够的可能性时换出；

交换区大小：存放所有用户进程的所有内存映像的拷贝

程序换入时的重定位：为了程序换出再换入的继续执行，需要采用动态地址映射（动态重定位）动态地址映射的方法。

虚拟页式存储管理的性能

有效存储访问时间（effective memory access time EAT）

当出现缺页异常，需要调入新页面而内存已满时，置换算法选择被置换的物理页面；

设计目标：

页面锁定（frame locking）：

以上的实现通过页表中的锁定标志位（lock bit）来实现

置换页面的选择范围仅限于当前进程占用的物理页面内

最优页面置换算法（OPT,optimal）

缺页时，计算内存中每个逻辑页面的下一次访问时间。选择 未来最长时间不访问的页面。

这是一种理想化的算法，因为我们无法预测未来最长时间不访问的页面，但可以作为置换算法的性能评价依据，最接近这个算法的结果，说明该算法效果更好。

先进先出置换算法（FIFO）

选择在内存中驻留时间最长的页面进行置换。

该算法性能较差，缺页率不一定会减少（Belady现象），该算法很少单独使用。

最近最久未使用置换算法（LRU, Least Recently Used）

认为过去最长时间没有被访问的页面，在未来被访问的可能性也很低。

该算法是最优置换算法的一种近似，因为我们不能够对未来情况进行分析，但可以依据过去的信息进行分析。

最大的问题是开销大

实现办法：

​ 系统维护一个按照最近一次访问时间排序的页面链表，首节点位最近使用过的页面，尾节点是最久未使用的页面。

虽然 LRU 在理论上是可以实现的，但代价很高。为了完全实现 LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。

困难的是，在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作。

时钟页面置换算法(Clock)

思路：针对页面的访问情况进行大致统计

数据结构：

实现：

可以看到时钟页面置换算法既有FIFO的影子，又有LRU的特点，即考虑最近最久未使用。

改进的Clock算法

Clock算法如果遇到有修改的页，还要将修改页的数据写回到内存中，这无疑增大了页面置换的开销。

思路：减少修改页的缺页处理开销

算法：在页面中增加修改位，并在访问位时进行相应修改；

​ 缺页时，修改页面标志位，以跳过有修改过的页面。

最不常用算法（Least Frequently USed, LFU）

访问计数，每个页面设置一个访问计数，访问页面时，访问计数+1，缺页时，置换计数最小的页面。

特点：算法开销大

​ 开始时使用频繁，但以后不常使用的页面很难被置换走；

解决办法：计数定期右移，数值就会随着时间推移降低。

现象：采用FIFO算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象。

原因：

FIFO算法的置换特征与进程访问内存的动态特征矛盾

被它置换出去的页面并不一定是进程近期不会访问的

Q: LRU算法不存在Belady现象，为什么？

A:

时钟页面置换算法也是如此，不存在Belady现象。

置换页面的选择范围是所有可变数目的物理页面

进程在不同阶段的内存需求是变化的，分配给进程的内存也需要在不同阶段有所变化。全局置换算法需要确定分配给进程的物理页面数。

CPU利用率与并发进程数的关系

进程数少时，提高并发进程数，可以提高CPU利用率

并发进程导致内存访问增加；

并发进程的内存访问会降低访存的局部性特征，因为并发切换，导致之前执行的事情跟之后执行的完全没有关系，这样也就降低了访问内存的局部性特征。

局部性特征的下降会导致缺页率的上升和CPU利用率的下降；

工作集置换算法

一个进程当前正在使用的逻辑页面集合，可表示为二元函数 W ( t , Δ ) W(t, \Delta) W(t,Δ)

进程开始执行后，随着访问新界面逐步建立较为稳定的工作集；

常驻集：在当前时刻，进程实际驻留在内存当中的页面集合；

工作集和常驻集的关系

缺页率与常驻集的关系

工作集置换算法：

思路： 换出不在工作集中的页面

窗口大小 τ \tau τ: 当前时刻前 τ \tau τ个内存访问的页引用是工作集， τ \tau τ被称为窗口大小

实现方法：

缺页率置换算法（PFF, Page Fault Frequency）

缺页率（page fault rate）:缺页平均时间间隔的倒数

影响缺页率的因素：

实现：

抖动问题（thrashing）

抖动：

产生抖动的原因：

负载控制

通过调节并发进程数（MPL）来进行系统负载控制，在并发进程数和CPU利用率之间做一个平衡。

但是这个平衡我们很难考察到，因此转而利用另一个指标。

平均间隔时间（MTBF）和缺页异常处理时间（PFST）。

如果

本节主要操作系统的内存管理的一些基础知识。 本文参考：

如果您觉得我写的不错，麻烦给我一个免费的赞！如果内容中有错误，也欢迎向我反馈。