操作系统 3 内存管理

本文最后更新于：2023年12月19日晚上

王道操作系统3.1_6，3.1_7，3.1_8，3.1_9，3.1_10，3.1_11待补充

学的时候发现王道考研这样说的是内存管理，而📕上的是存储器管理

导致笨🐭有点疑惑，所以就去搜了一下，搜到了一点资料，解答了这个疑惑，或者看一下补充的3.1.0

其实就一句话：内存又叫内部存储器（不知道这样理解对不对

其实就是计组里面的知识

3.1 内存管理

3.1.0 存储器的层次结构

几乎每条指令都涉及对存储器的访问
要求对存储器的访问速度能跟得上处理机运行速度
还要求存储器具有非常大的容量，并且价格便宜

1. 多层结构的存储器系统

2. 可执行存储器

寄存器和主存储器又被称为可执行存储器
访问可执行存储器中的信息较快
- 访问寄存器or高速缓存：几十ns
- 访问主存：几百ns
访问辅存中的信息较慢，需要I/O操作
- 访问辅存：几十到几百ms
访问机制不同
- 可执行存储器：寄存器读取；内存寻址；数据总线
- 辅存：机械操作；I/O操作

3. 主存储器与寄存器

主存储器

主存储器简称内存或主存，用于保存进程运行时的程序和数据（这里™的又把主存储器给简称为内存了，测！

寄存器

寄存器具有与CPU相同的速度；故对寄存器的访问速度最快，但价格却十分昂贵，因此容量非常小

E.g.，Intel 8086 CPU有14个寄存器, AX, BX, CX, DX, SP, BP, SI, DI, IP, FLAG, CS, DS, SS, ES

4. 高速缓存和磁盘缓存

高速缓存

是介于寄存器和存储器之间的存储器，用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数；大幅提高程序执行速度

磁盘缓存

为了缓和磁盘和内存在访问速度上的不匹配而设置了磁盘缓存
用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数
注意：磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息

3.1.1 内存的基础知识

1. 一些小知识

什么是内存，有何作用：

补充知识：几个常用的数量单位

相对地址 v 绝对地址

从写程序到程序运行

不修改装入模块中的指令地址就直接装入内存的话：

如果内存地址不是从0开始，那么就会出现错误

装入模块装入内存时需要对指令中的地址进行处理，

下面介绍的装入的三种方式就是用三种不同的方法完成逻辑地址到物理地址的转换

2. 程序的装入-三种方式

绝对装入

早期计算机系统很小，仅能运行单道程序；完全有可能知道程序将驻留在内存的什么位置(地址)
此时可以采用绝对装入方式。用户程序经编译后，将产生绝对地址(即物理地址)的目标代码
缺点：程序员要非常熟悉当前内存情况；程序发生修改时，必须修改程序中所有的绝对地址

可重定位装入

只适用于单道程序环境，在多道程序环境下，编译程序不可能预知经编译后所得到的目标模块应放在内存的何处

动态运行时装入

可将程序分配到不连续的存储区中；
在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存
便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间

3. 程序的链接-三种方式

静态链接

装配成可执行程序时要解决：

对相对地址进行修改
变换外部调用符号

#### 装入时动态链接

所有的模块都装入内存

是指在将一组目标模块装入内存时，采用边装入边链接的方式，然后再按照上图所示的方式来修改目标模块中的相对地址。

在装入时，若发生一个外部模块调用事件，则找出相应的外部目标模块并将其装入内存

优点：

便于修改和更新。对于经静态链接装配在一起的装入模块，如果要修改或更新其中的某个目标模块，则要求重新打开装入模块。这不仅是低效的，而且有时是不可能的。若采用动态链接方式，由于各目标模块是分开存放的，所以要修改或更新各目标模块是件非常容易的事。
便于实现对目标模块的共享。在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享。但采用装入时动态链接方式，OS则很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。

缺点：

有的模块在运行时没有被调用；浪费了内存
装入时间开销相对较大

运行时动态链接

需要某个模块时才装入内存

在程序执行中需要该目标模块时，才对它进行链接。

克服了装入时动态链接方式的缺点
仅在程序运行时需要调用相关模块时才将那些模块进行动态链接

3.1.2 内存管理的概念

内存管理管些什么

操作系统负责内存空间的分配与回收

操作系统需要提供某种技术从逻辑上对内存空间进行扩充

操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换

操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

这节主要是对内存管理有一个大体的框架

3.1.3 覆盖技术与交换技术

理解思想即可

1. 覆盖技术

B，C不可能在同一个时间段被访问，覆盖区以B和C中较大的来计算

D，E，F也不能在同一个时间段来访问

2. 交换技术

中级调度就是为了实现交换技术

对换(Swapping)

也称为交换技术；最早用于麻省理工学院的单用户分时系统CTSS中
当时计算机内存非常小，为了使该系统能分时运行多个用户程序，把所有的用户作业存放在磁盘上，每次只能调入一个作业进入内存
当该作业的一个时间片用完时，将它调至外存的后备队列上等待，再从后备队列上将另一个作业调入内存

多道程序环境下的对换技术

对换的引入

在内存中的某些进程由于阻塞而停止运行，但却占用了大量的内存空间，甚至有时可能内存中所有进程都被阻塞，而无可运行之进程，迫使CPU停止下来空等
另一方面，可能又有许多作业因内存空间不足，一直驻留在外存上而不能进入内存运行。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降

对换的类型

在每次对换时，将一定数量的程序或数据换入或换出内存。根据每次对换时所对换的数量，可将对换分为：
- 整体对换：将整个进程换入、换出
- 页面(分段)对换：以进程的“页面”或者“段”为单位进行换入、换出

有关交换技术的一些问题

对换区空闲盘块管理中的数据结构

为了实现对对换区中的空闲盘块的管理，在系统中有对换进程，同时应配置相应的数据结构，用于记录外存对换区中的空闲盘块的使用情况
其数据结构的形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链
在空闲分区表的每个表目中，应包含两项：对换区的首址及其大小，分别用盘块号和盘块数表示

对换空间的分配与回收

由于对换分区的分配采用的是连续分配方式，因而对换空间的分配与回收与动态分区方式时的内存分配与回收方法雷同
其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法等。具体的分配操作也与图4-8中内存的分配过程相同

进程的换出

对换进程在实现进程换出时，是将内存中的某些进程调出至对换区，腾出内存空间。换出过程可分为：

选择被换出的进程

原则：选阻塞/睡眠进程、优先级低的进程

进程换出过程

原则：换出没有共享程序段/数据段的进程

进程的换入

对换进程将定时执行换入操作，首先查看PCB集合中所有进程的状态，从中找出“就绪”状态但已换出的进程
当有许多这样的进程时，它将选择其中已换出到磁盘上时间最久的进程作为换入进程
为该进程申请内存，如申请成功，可直接将进程从外存调入内存；如失败，则需先将内存中的某些进程换出，腾出足够的内存空间后，再将磁盘上的进程调入
反复换入进程，直到无进程可换入

3.1.4 连续分配存储管理方式

内存管理下面的三个作用已经讲过了，这节课我们来看连续分配管理方式

1. 单一连续分配

2. 固定分区分配

操作系统应该怎么记录内存当中各个分区空闲或者分配的情况呢？

3. 动态分区分配

1 动态分区分配中的数据结构

2 分区分配算法

3 如何分配

如果分配的进程大小和分区大小刚好相，就删除分区对应的表项，空闲分区链的话就把一个节点给删除

4 如何回收

4. 内部碎片与外部碎片

可以通过紧凑（拼凑，Compaction）技术来解决外部碎片

3.1.5 动态分区分配算法

下面应该说是考研要求掌握的四种算法

首次适应(first fit，FF)算法

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

最佳适应(best fit，BF)算法

算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区即，优先使用更小的空闲区。

如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

“最佳”含义：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免内存浪费

缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

最坏适应(worst fit，WF)算法

WF算法使得存储器中缺乏大的空闲分区，故把它称为是最坏适应算法

算法思想：为了解决最佳适应算法的问题一一即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了

邻近适应算法

算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现：空闲分区以地址递增的顺序排列 (可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链 (或空闲分区表)，找到大小能满足要求的第一个空闲分区。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来 (这隐含了最佳适应算法的优点)

邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用 (这隐含了最大适应算法的缺点)

综合来看，四种算法中，首次适应算法的效果反而更好

四种算法的比较总结

这里是算法开销指的是对分区表或分区链表的重新排序和查找消费

张老师的pipiti上面是这样分的，或者说书上是这样来分类的：

🎈基于顺序搜索的动态分区分配算法：

首次适应(first fit，FF)算法
循环首次适应(next fit，NF)算法
- 目的：避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销
- NF算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。
- 其实就是上面提到的邻近适应算法
最佳适应(best fit，BF)算法
最坏适应(worst fit，WF)算法

🎈基于索引搜索的动态分区分配算法：

快速适应(quick fit)算法

将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表

在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针

伙伴系统(buddy system)

该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，k∈[1,m])。\(2^m\)是整个可分配内存的大小

假设系统的可用空间容量为\(2^m\)个字，则系统开始运行时整个内存区是一个大小为\(2^m\)的空闲分区。在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区

将这些空闲分区按分区的大小进行分类。对于具有相司大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了多个空闲分区链表

在伙伴系统中，对于一个大小为\(2^k\) ，地址为\(x\)的内存块，其伙伴块的地址则用\(buddy_k(x)\)表示，其计算公式为： \[ buddy_k(x)=\left\{\begin{matrix}x+2^k（若x\mod2^{k+1}=0）\\x-2^k（若x\mod2^{k+1}=2^k）\end{matrix}\right. \]

哈希算法

上述算法中都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表

在为进程分配空间时，需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针

建立哈希函数，以内存分区大小为查找关键字，加快查找合适大小分区的速度

*3.1.6 基本分页存储管理

思路：连续分配方式局限性大；可以将进程分散式的装入内存；根据分散分配时不同的地址空间基本单位分为：

分页存储管理方式：将进程地址空间划分成“页”，例如，每页1KB
分段存储管理方式：将进程地址空间划分成逻辑上完整的“段”
段页式存储管理方式

3.1.6 OS之分页存储（页号、页偏移量等）_计组的页内偏移量-CSDN博客

思考：

每个页表项多大?占几个字节?
如何通过页表实现逻辑地址到物理地址的转换?

这节课有点没听懂，看了期末考试好像对这部分要求的比较少，就先不查资料进行学习了😥😥

等期末考完再来补充，~~没办法，一切以期末考试为导向进行学习~~

3.2 虚拟内存管理

3.2.1 虚拟内存的基本概念

1 传统存储管理的特征、缺点

2. 局部性原理

3. 虚拟内存的定义和特征

4. 如何实现虚拟内存技术

3.2.2 请求分页存储管理方式

1. 页表机制

2. 缺页中断机构

3. 地址变换机构

快表中有的页面一定是在内存中的。若某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面

在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是：

查快表(未命中)——查慢表(发现未调入内存)——调页(调入的页面对应的表项会直接加入快表)——查快表(命中)——访问目标内存单元

3.2.3 页面置换算法

1. 最佳置换算法—OPT

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

2. 先进先出置换算法—FIFO

3. 最近最久未使用置换算法—LRU

该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大

4. 时钟置换算法—CLOCK

访问6号页面时，需要淘汰某个页面，先从1检查，都会改成0，然后第二轮扫描时，发现1是0，所以6号页会置换1号页

7会置换2号页面（可以自己分析一下）

5. 改造型时钟置换算法

3.2.4 页面分配策略

1. 驻留集

驻留集：指请求分页存储管理中给进程分配的物理块的集合

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小

-----考虑一个极端情况，若某进程共有100个页面，则该进程的驻留集大小为100时进程可以全部放入内存，运行期间不可能再发生缺页。若驻留集大小为1，则进程运行期间必定会极频繁地缺页

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少
驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

2. 页面分配、置换策略

固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
- 这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。 (采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)
可变分配全局置换：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
- 系统会锁定一些页面，这些页面中的内容不能置换出外存(如：重要的内核数据可以设为“锁定”)
可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

可变分配全局置换：只要缺页就给分配新物理块

可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块