【操作系统】第三章：内存管理

3.1.1 内存的基础知识

什么是内存？有何作用

内存可存放数据，程序执行前需要先放到内存中才能被CPU处理，为了缓和CPU与硬盘之间的速度矛盾。（CPU处理数据很快，但硬盘的读写速度很慢）

思考：再多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放到内存中。那么，如何区分各个程序是放在什么地方？

给内存的存储单源编址。就像每家每户都有一个地址一样。

一台手机有4GB内存，表示该内存可以存放4*2^30个字节，如果按字节编址的话，有4*2^30=2^32个地址，则至少需要用32个比特位来表示地址。

指令的工作原理

我们写的代码经过编译之后翻译成了CPU能识别的指令，这些指令会告诉CPU应该去内存的哪个地址读/写数据，这个数据应该做什么样的处理。

x = x + 1这段代码就包含了三条指令：

1. 将内存中x变量地址中的值取出来放到寄存器中
2. 将寄存器中的值加1
3. 将寄存的值放回内存中x变量的地址中

在这个例子中，我们默认让这个进程的相关内容从地址#0开始连续存放，指令中的地址参数直接给出了变量x的实际存放地址（物理地址）

思考：如果进程不是从#0开始的会影响指令的正常运行吗？

逻辑地址：程序经过编译、链接后生产的指令中指明的是逻辑地址（相对地址），即：相对于进程的起始地址而言的地址）

下图中，指令中指明的地址是相对于进程的起始地址来算的。

进程装入内存的三种方式

绝对装入

在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码，装入程序按照装入模块中的地址，将程序和数据装入内存。

绝对装入只适用于单道程序环境，灵活性很差，假设程序放到了其他电脑上，起始地址就变了，就没办法运行了。

重定位装入

静态重定位：编译、链接后的装入模块的地址都是从0开始的，指令中适用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置，装入时对地址进行重定位，将逻辑地址变换为物理地址（地址是在装入时一次完成的）。

动态重定位：编译、链接后的装入模块的地址都是从0开始的，装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式还需要一个重定位寄存器的支持。

从写程序到程序运行

编译：由编译程序将用户源代码编译成若干个目标模块（把高级语言翻译成机器语言）

链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块装入，由装入程序将装入模块装入内存运行。

链接的三种方式

3.1.2 内存管理的概念

内存空间的分配与回收

内存空间的扩展

地址转换

内存保护

一个进程只能访问自己的那部分内存，不能随意访问其他内存。

内存保护方法一：在CPU设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。

内存保护方法二：采用重定位寄存器和界地址寄存器进行越界检查。重定位寄存器存放的是进程的起始物理地址，接地址寄存器存放的是进程的最大逻辑地址。

3.1.3 覆盖与交换

覆盖技术

覆盖技术的思想：将程序分为多个段，常用的常驻内存，不常用的段在需要时调出内存。

内存中分为一个固定区和若干个覆盖区

需要常驻内存的段放在固定区中，调入后就不在调出（除非运行结束）

不常用的段放在覆盖区，需要用到时调入内存，用不到时调出内存。

覆盖技术的优点：提高了主存的利用率，实现了主存的逻辑扩充。

覆盖技术的缺点：需要用户建立覆盖结构；各作业占用的分区仍存在碎片；没有有效的利用辅助资源。

交换技术

内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存。

暂时换出外存等待的进程状态为挂起状态，挂起状态又可分为就绪挂起、阻塞挂起。

总结

3.1.4 连续分配管理方式

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区，系统区通常位于内存的低地址部分，用于存放操作系统相关数据，用户区用于存放用户进程相关数据。

内存中只有一道用户程序，用户程序独占整个用户区空间。

这样内存利用率就很低，造成了极大的浪费。只适用于早期的单用户、但任务的操作系统中。

固定分区分配

如果程序太大的话需要使用覆盖技术，降低性能。

如果来了一堆小程序的话又浪费了很多资源。

动态分区分配

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上

外部碎片：是指内存中的某些空闲分区由于太小而难以利用

总结

3.1.5 动态分区分配算法

首次适应算法

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

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

最佳适应算法

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

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

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

最坏适应算法

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

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

缺点：每次都选最大的分区进行分配，这样大分区越来越少，如果又大进程来了的话就无法分配了。

邻近使用算法

算法思想：首次适应算法的优化版，为了提高查找速度，每次都从上一次查找结束的位置开始查找。

总结

3.1.6 基本分页存储管理的概念

什么是分页存储

将内存空间分为大小相等的分区，每个分区就是一个页框。每个页框有一个编号，从0开始。

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页面。每个页面也有编号，从0开始。

操作系统以页框为各个进程分配内存空间。进程的每个页面分别放入一个页框中。

各个页面不必连续存放，可以放到不相邻的各个页框中。

每个页表项占多少个字节

如何实现地址的转换

逻辑地址A对于的物理地址=P号页面在内存中的起始地址（查页表）+ 页内偏移量W

如何确定一个逻辑地址对应的页号、业内偏移量

3.1.7 基本地址变换机构

逻辑地址如何转换为物理地址

1. 根据逻辑地址计算出页号、页内偏移量
2. 判断页号是否越界
3. 查询页表，找到页号对应的页表项，确定页面存的内存块号
4. 用内存块号和页内偏移量得到物理地址

对页表项大小的进一步探讨

3.1.8 具有块表的地址变换结构

什么是快表

快表：又称联想寄存器，是一种访问速度比内存快很多的告诉缓冲，用来存放最近访问的页表项的副本。可以加速地址变化的速度。

能否把整个页表都放在TLB中

由于成本的关系，快表不可能做的很大，但也满足了中小型作业的需求。即使大作业，也能做到命中率达90%以上。

具有快表的地址变换机构

局部性原理

时间局部性：如果指向了程序的某条指令，那么不久后这条指令很可能在次执行，如果某个数据被访问过，那么不久后可能会被再次访问（因为程序中存在大量的循环）

空间局部性：一旦程序访问了某个存储单元，在不久之后，附近的存储单元也很有可能被访问，（因为很多数据在内存中都是连续存放的）

3.1.9 两级页表

单级页面存在的问题

进程太大了，所需要的页面数太大了，很难找到连续的那么大一块空间存放页面，而且页面中的很多页面短时间内是用不到的，这极大地浪费了内存。

如何解决单极页面的问题

页面离散分配的方式

虚拟内存的方式

两级页表的原理、地址结构

如何实现地址转换

如何划分几级页表

访存次数分析

3.1.10 基本分段存储管理

分段

进程的地址空间，按照程序自身的逻辑关系划分为若干个分段，每个段都有一个段名，每段从0开始编址。

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

段表

段表映射了每个分段的信息。

地址变换

分段、分页管理的对比

信息共享和保护

分段实现共享

3.1.11 段页式管理方式

分页、分段的优缺点分析

段页式管理

一个进程分的各个模块先分段，在将各个段分页

段页式管理的逻辑地址结构

段表、页表

一个进程对应一个段表，一个进程可以对应多个页表（多个段可以访问同一个页面）

地址变换过程

总结

3.2.1 虚拟内存的基本概念

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

一致性：作业必须一次性装入内存才能开始运行。这回造成两个问题：①作业很大时，不能全部装入内存，导致大作业无法与性能。②当大作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。

驻留性：一旦作业被装入内存，就会一直驻留在内存，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存会驻留大量的、暂时用不到的数据，浪费了内存资源。

虚拟内存的定义和特征

定义：基于局部性原理，在程序装入时，可以将程序中很快用到的部分装入内存，暂时用不到的部分留再外存，就可以让程序开始执行。

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中在那时用不到的信息换出到外存。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

特征

• 多次性：无需再作业运行时一次全部装入内存，而是运行被分成多次调入内存。
• 对换性：在作业运行时无需一直常驻内存，而是运行在运行过程中，将作业换出外存
• 虚拟性：从逻辑上扩充了内存的容量，是用户看到的内存容量，远大于实际的容量。

如何实现虚拟内存技术

如何使用连续分配方式的话，会不方便实现，因为换入的时候需要找到之前的那部分内存相邻的区域填入，这样就很麻烦。因此，虚拟内存的实现需要简历在离散分配的内存管理方式基础上。

总结

3.2.2 请求分页管理方式

页表机制

状态位：标志是否已调入内存

访问字段：可以记录一些信息，比如记录上次访问的时间

修改位：记录有没有被修改过，如果修改过的话需要将外存的数据进行重写

外存地址：记录此页面在外存中什么位置

缺页中断机构

地址变换机构

1. 请求调页
2. 页面置换（没有空闲内存块时）
3. 修改页表项

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gsbf82XJ-1661613742189)(https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/8467/image-20220827224141745.png)]

总结

3.2.3 页面置换算法

最佳置换算法

最佳页面置换算法基本思路是，置换在「未来」最长时间不访问的页面。

这很理想，但是实际系统中无法实现，因为程序访问页面时是动态的，我们是无法预知每个页面在「下一次」访问前的等待时间。

所以，最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的

先进先出算法

既然我们无法预知页面在下一次访问前所需的等待时间，那我们可以选择在内存驻留时间很长的页面进行中置换，这个就是「先进先出置换」算法的思想。

在这个请求的页面序列中，缺页共发生了 10 次，页面置换共发生了 7 次，跟最佳页面置换算法比较起来，性能明显差了很多

最近最久未使用的置换算法

最近最久未使用（LRU）的置换算法的基本思路是，发生缺页时，选择最长时间没有被访问的页面进行置换，也就是说，该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。

这种算法近似最优置换算法，最优置换算法是通过「未来」的使用情况来推测要淘汰的页面，而 LRU 则是通过「历史」的使用情况来推测要淘汰的页面。

在这个请求的页面序列中，缺页共发生了 9 次，页面置换共发生了 6 次，跟先进先出置换算法比较起来，性能提高了一些。

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

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

所以，LRU 虽然看上去不错，但是由于开销比较大，实际应用中比较少使用

时钟置换算法

那有没有一种即能优化置换的次数，也能方便实现的算法呢？

时钟页面置换算法就可以两者兼得，它跟 LRU 近似，又是对 FIFO 的一种改进。

该算法的思路是，把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。指针指向的访问位为0的是最长时间没有使用过的页面。

最不常用算法

最不常用（LFU）算法，这名字听起来很调皮，但是它的意思不是指这个算法不常用，而是当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。

它的实现方式是，对每个页面设置一个「访问计数器」，每当一个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。

看起来很简单，每个页面加一个计数器就可以实现了，但是在操作系统中实现的时候，我们需要考虑效率和硬件成本的。

要增加一个计数器来实现，这个硬件成本是比较高的，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高。

但还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。

那这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大了被置换的概率。

3.2.4 页面分配策略、抖动、工作集

页面分配、置换策略

何时调入页面

何处调入页面

抖动现象

刚刚换出的页面马上又要调入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，主要原因是因为频繁访问的页面数目高于可用的物理块数（分配给进程的物理块数不够）

工作集：在某段时间间隔里，进程实际访问页面的集合。

总结