操作系统之内存管理

内存是用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理。

1.1、内存基础知识

名词解释：

• 进程运行的原理——指令：

我们写的代码要翻译成CPU能识别的指令。这些指令会告诉CPU应该去内存的哪个地址存/取数据，这个数据应该做什么样的处理。在这个例子中，指令中直接给出了变量x的实际存放地址(物理地址)。但实际在生成机器指令的时候并不知道该进程的数据会被放到什么位置。所以编译生成的指令中一般是使用逻辑地址(相对地址)。

• 进程运行的基本原理：

编译：由编译程序将用户源代码编译成若千个目标模块(编译就是把高级语言翻译为机器语言)。

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

装入：程序将装入模块装入内存运行。

1.2、内存管理的事项

1.2.1、内存空间的分配与回收

操作系统需要负责对于内存空间的分配与回收，对于一个进程来讲，有很多位置可以放置，那么应该放在哪里？所以OS需要记住那些内存区域已经被分配出去了，哪些还是空闲的，当进程运行结束之后，如何将进程占用的内存空间进行回收？这些都是操作系统对于内存空间的分配和回收功能需要考虑的问题。

1.2.2、内存空间的扩充

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

1.2.3、地址转换

操作系统需要提供地址转换功能，负责将程序的逻辑地址与物理地址的转换。为了使得编程更加的方便（这个过程叫地址重定位）应该由操作系统负责，这样就保证了程序员在写程序时不需要关注于对于物理内存的实际情况。从逻辑地址到物理地址的转换，有以下三种装入的方式：分别是绝对装入、可重定位装入和动态运行时装入。

1.2.4、存储保护

操作系统需要提供内存保护的功能，保证各个进程在各自的存储空间内运行，互相不干扰，主要有以下两种方式：

1.3、内存空间的分配与回收

（1）连续分配管理方式

连续分配：指的是用户进程分配必须是一个连续的内存空间。

a、单一连续分配

b、固定分区分配

分区说明表：实现各个分区的分配与回收。

c、动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的（比如某个计算机的内存大小为64MB，系统区是8MB，用户区共56MB……）

①系统要用怎样的数据结构记录内存的使用情况呢？

②当多个空闲分区都能满足要求时，应该选择哪个分区进行分配？

③回收内存分区时，可能遇到的四种情况：

• 情况一：回收区的后面有一个相邻的空闲分区：

  ​ 两个相邻的空闲分区合并成一个。

• 情况二：回收区的前面有一个相邻的空闲分区：

  ​ 两个相邻的空闲分区合并成一个。

• 情况三：回收区的前、后各有一个相邻的空闲分区：

  ​ 三个相邻的空闲分区合并成一个。

• 情况四：回收区的前、后都没有相邻的空闲分区：

  ​ 新增一个表项。

④动态分区分配的四种算法

• 首次适应算法

从头到尾找合适的分区。

• 最佳适应算法

优先使用更小的分区，以保留更多大分区。

• 最坏（大）适应算法

优先使用更大的分区，以防止产生太大的不可用的碎片。

• 邻近适应算法

由首次适应演变而来，每次从上次查找结束位置开始查找。

算法	算法思想	分区排列顺序	优点	缺点
首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	综合看性能最好。算法开销小，回收分区后一.般不需要对空闲分区队列重新排序
最佳适应	优先使用更小的分区，以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片;算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程;算法开销大(原因同上)
邻近适应	由首次适应演变而来，每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列(可排列成循环链表)	不用每次都从低地址的小分区开始检索。算法开销小(原因同首次适应算法)	会使高地址的大分区也被用完

（2）非连续分配管理方式

为什么非连续分配？

主要是考虑连续分配方式有如下的缺陷：

①固定分区分配：缺乏灵活性，会产生大量的内部碎片，内存的利用率很低；

②动态分区分配：会产生很多的外部碎片，虽然可以用“紧凑”技术来处理，但是“紧凑”的时间代价很高。

如果允许将一个进程分散地装入到许多不相邻的分区中，便可以充分地利用内存，而需再进行“紧凑”。基于这个思想，就出现了“非连续分配方式”，或者叫“离散分配方式”。

a、基本分页存储管理

分页存储管理：把主存分为大小相等且固定的一页一页的形式，页较小，相对相比于块式管理的划分力度更大，提高了内存利用率，减少了碎片。页式管理通过页表对应逻辑地址和物理地址。

基本分页存储管理的思想就是把内存分为一个个相等的小分区，且不要求连续，再按照分区大小把进程拆分成一个个小部分。

• 分页存储管理的重要概念？

• 基本分页存储的地址转换

物理地址=页面地址+页内偏移量。

①如何计算页号和页面的页内的偏移量？

②计算该页号对应页面在内存中的起始地址？

为了能知道进程的每个页面在内存中的存放位置，操作系统为每个进程建立一张页表。

基本地址变换机构：

• 基本地址变换机构如何借助进程的页表将逻辑地址转换成物理地址？

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表的长度放在**进程控制块（PCB）**中，当进程被调度时，操作系统内核把他们放到页表寄存器中。

设页面大小为L，从逻辑地址A到物理地址E的变换过程如下：

b、快表与两级页表

由程序的局部性原理引入快表机制：

快表：又称联想寄存器（TLB）,是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程，与此对比，内存中的页表常常叫慢表。

引进快表之后，内存变换情况：

基本地址变换和引入快表的地址变换比较图：

关于二级页表：

c、基本分段存储管理

分段的逻辑地址结构：

段表：

• 地址变换

• 分段和分页的对比

• 分段实现信息的共享

• 为什么分页不方便与信息的共享与保护？

c、段页式存储管理

• 分页和分段优缺点：

分段+分页=段页式管理

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

段页式段表和页表：

段页式地址转换：

1.4、内存空间的扩充

a、覆盖技术

覆盖技术的思想:将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。

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

需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)
不常用的段放在"覆盖区”，需要用到时调入内存,用不到时调出内存

b、交换技术

1.5、虚拟内存

为什么需要引入虚拟内存（传统存储管理方式的缺陷）？

时间和空间角度上的程序局部性原理：

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

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存，操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充。

• 通常虚拟内存有如下三个特征：

①多次性：无需在作业运行时一次性全部装入到内存，而是允许被分成多次调入内存中。

②对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。

③虚拟性：从逻辑上扩充内存的容量，使得用户看到的内存容量，远远大于时间的容量。

• 如何实现虚拟内存技术

虚拟内存技术，允许一个作业分多次调入内存，如果采用连续分配方式，会不方便实现，因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

①请求调页（或者请求调段）功能：在程序执行过程中，当所访问的信息不在内存中，由操作系统负责将所需要的信息从外存调入内存然后继续执行程序。

②提供页面置换（或者段置换）功能：若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

a、OS之请求分页管理方式：

• 页表机制—请求页表与基本页表的区别

• 地址变换机构

b、页面置换算法

页面的置换算法包括：

• 最佳置换算法—OPT

每次选择淘汰的页面将是以后永不使用的，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

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

• 先进先出置换算法—FIFO

每次选择淘汰的页面是最早进入内存的页面

实现方法：将调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可，队列的最大长度取决于系统为进程分配了多少个内存块。

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

每次淘汰的页面是最近最久未使用的页面

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间T，当需要淘汰一个页面时，选择现有页面中T值最大的，即最近最久未使用的页面。

• 4.时钟置换算法—CLOCK

• 5.改造型时钟置换算法

c、页面分配策略

• 调入页面的时机

①预调页策略：根据局部性原理(主要指空间局部性，即:如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的那些内存单元。)，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测 成功率只有50% 左右。故这种策略主要用于进程的首次调入(运行前调入)，由程序员指出应该先调入哪些部分。

②请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存(运行时调入)。由这种策略调入的页面一-定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/0操作，因此I/0开销较大。

• 从何处调入页面

• 抖动（颠簸）现象

• 工作集

驻留集:指请求分页存储管理中给进程分配的内存块的集合。
工作集:指在某段时间间隔里，进程实际访问页面的集合。

原理：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动。