内存管理

内存管理概述

操作系统主要负责：

内存空间分配与回收
内存空间扩充(虚拟化)
逻辑地址到物理地址的转换
- 绝对装入、可重定位装入、动态运行时装入
内存保护：保护各进程在自己的内存空间内运行，不会越界访问
- 设置上下限寄存器
- 利用重定位(基址)寄存器记录起始物理地址、界地址(限长)寄存器记录进程最大逻辑地址进行判断

内存空间扩充

覆盖技术

将程序分为多个模块，内存中设置一个固定区和若干个覆盖区，

常驻内存的模块放入固定区，调入后不再调出
不常用的模块放入覆盖区，不需要时即调出，覆盖区大小取决于最大的那个模块大小。

必须由程序员声明覆盖结构，对用户不透明

交换技术

内存空间紧张时，系统在内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)

中级调度（内存调度），决定将哪个处于挂起态的进程重新调入内存

操作系统通常将磁盘分为文件区与对换区，

文件区追求空间的利用率，采用离散分配方式
对换区空间只占磁盘空间的小部分，存储被挂起进程，追求换入换出速度，采用连续分配方式，其I/O速度比文件区更快。

交换通常发生于很多进程运行且内存吃紧时进行，系统负荷降低就暂停，比如许多进程运行时经常发生缺页，就说明内存紧张，进行交换，降低缺页率。

一般优先换出阻塞进程。

交换时，进程的PCB常驻内存，不会被换出外存，只有程序与数据会被换出

内存虚拟化

详见虚拟内存

内存空间连续分配管理

单一连续分配

将内存分为系统区和用户区，内存中只能有一道用户程序，用户程序独占整个用户区空间

实现简单，无外部碎片，可采用覆盖技术扩充内存，不一定需要采取内存保护
只能用于单用户、单任务的OS，有内部碎片

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

固定分区分配

基于单一连续分配，将整个用户空间划分为若干个固定大小的分区，每个分区中只装入一道作业

操作系统需要维护一个分区说明表，实现各个分区的分配与回收，包含分区号、大小、起始地址、状态(分配与否)

实现简单，无外部碎片
会产生内部碎片，可能会出现覆盖，导致性能降低。

动态分区分配

又称可变分区分配，其不会预先划分内存分区，在进程装入内存时，根据进程的大小动态地建立分区

采用空闲分区表或空闲分区链记录内存的使用情况。

使用动态分区分配算法为新作业分配内存空间。

回收内存空间：

回收区前面或者后面有一个相邻的空闲分区：两个相邻的空闲分区合并为一个，更新分区表
回收区前、后面都有一个相邻的空闲分区：三个相邻的空闲分区合并为一个，更新分区表
回收区前、后面都没有相邻的空闲分区：分区表新增一个空闲分区

动态分区分配没有内部碎片，有外部碎片

内存中某些空闲分区由于太小而难以利用的部分，叫做外部碎片

通过紧凑(拼凑)技术可以解决外部碎片

动态分区分配算法

接上文中动态分区分配方式

首次适应算法

每次都从低地址开始，找到第一个能满足大小的空闲分区

实现：空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链(或空闲分区表)，

找到大小能满足要求的第一个空闲分区

综合性能最佳，算法开销小，回收分区后一般不需要对空闲分区队列重新排序

最佳适应算法

为了保证当“大进程”到来时有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区

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

会留下越来越多、细小难以利用的外部碎片

最坏适应算法

又称最大适应算法，基于最佳适应算法，在每次分配时优先使用最大的连续空闲区

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

这将导致较大的连续空闲区被迅速消耗完，如果有其他大进程抵达，就没有分区可用了。

邻近适应算法

基于首次适应算法改进，从上一个查找结束的位置开始，而非链头，找到大小能满足要求的第一个空闲分区

实现：需要将空闲分区链(空闲分区表)改为循环链表，仍以地址递增的顺序排列

算法开销比首次适应算法更小
会使高地址的大分区快速用完

内存分页存储管理(非连续)

将内存n等分，每个分区就是一个页框（页框=页帧=内存块=物理块=物理页面）

每个页框有一个编号，叫页框号（页框号=页帧号=内存块号=物理块号=物理页号），从0开始编号

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

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

进程页面与内存页框存在一一对应关系
各个页面不必连续存放，可以放到不相邻的各个页框中
会产生内部碎片

页表

操作系统为每个进程建立一张页表，存放在PCB中

每个页表项对应一个进程页面，由页号与块号组成，表明进程页面与实际存放的内存块之间的映射关系

然而，页号并不占据存储空间，类似于数组下标，是隐含的，所以问页表项的长度就是在问块号的长度。

地址转换

进程的各个页面离散存放在内存中，然而在页面内部是连续存放的

访问一个逻辑地址A：

确定逻辑地址A对应的页号P=逻辑地址/页面长度（向下取整）。
确定逻辑地址A的页内偏移量W=逻辑地址%页面长度
找到P号页面在内存中的起始地址
起始地址+页内偏移量=实际物理地址

如果有K位表示页内偏移量，则说明系统中一个页面的大小是2^k个内存单元

如果有M位表示页号，则说明在该系统中，一个进程最多有2^m个页面

基本地址变换机构

通常会在系统中设置一个页表寄存器PTR，存放页表在内存中的起始地址F和页表长度M

进程未执行时，页表的初始地址和页表长度放在进程控制块PCB中
当进程被调度时，操作系统内核会把他们放到页表寄存器中。

变换时需要比较页号P与页表长度M，若$$P\geq M$$则发生越界中断(内部中断)，否则继续执行

页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度

具有快表的地址变换机构

快表，又称联想寄存器（TLB），一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加速地址变换的速度，

慢表，存放在内存中的页表

工作原理：

在进程切换时，清空快表内容
当通过越界检查，如果：
1. 快表中没有目标页表项，慢表命中，将目标页表项复制一份到快表中，开始访存
2. 快表命中，直接得出物理地址，开始访存

根据局部性原理，快表的命中率一般可达90%以上

快表命中，一次访存；快表未命中，两次访存

基本分段存储管理

按程序自身的逻辑关系划分为若干个段，每个段在内存中占据连续空间，但各段之间可以不相邻

其逻辑地址由段号、段内地址（段内偏移量）组成：

段号位数决定了该进程可以被分为多少段
段内地址位数决定每一段的最大长度

会产生外部碎片，可以用紧凑技术解决，需要付出较大时间代价

段表

与页表类似，记录各个逻辑段到物理段的映射关系，表项包含段号，段长，基址

同样的，段号不占存储空间

地址变换

与页表的地址变换类似，同样拥有段表寄存器，存储段表始址F和段表长度M。

判断段号S是否越界，$$S \geq M$$,产生越界中断，否则继续执行
查询段表，段表项的存放地址为F+S*段表项长度
检查段内地址W是否超过段长C，若$$W \geq C$$则产生越界中断，否则继续执行
计算物理地址，进行访存

同样可以引入快表来加速地址转换

分段、分页管理对比

页是信息的物理单位，主要实现离散分配提高内存利用率，纯系统行为，用户不可见

段是信息的逻辑单位，主要实现更好地满足用户需求，分段对用户是可见的，在编程时需要显式给出段名。

分页的用户进程地址空间是一维的，这主要是因为页的大小是固定不变的

分段的用户进程地址空间是二维的，既要给出段名，又要给出段内地址，因为段的大小不固定

分段比分页更容易实现信息的共享和保护，因为其按逻辑模块划分段，单模块不会被切割

段页式管理方式

对每个段再进行切割，也就是分页，再将每个页装入内存中

所以得到段页式管理的逻辑地址结构，即段号+页号+页内偏移量，

页号与页内偏移量拆分自原段内地址

页内偏移量位数决定了页面大小、内存块大小

在对段分页的这个过程，由系统完成，用户不可见

段页表

每个段对应一个段表项，每个表项**由段号、页表长度、页表存放块号(页表起始地址)**组成

每个段表项长度相等，段号是隐含的

每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成，每个页表项长度相等，页号是隐含的

地址转换

对段号进行越界检查，
第一次访存，查询段表，找到对应段表项
检查页号是否越界，若页号大于等于页表长度，发生越界中断，否则继续执行
第二次访存根据页表存放块号、页号查询页表，找到对应页表项
第三次访存，根据内存块号和页内偏移量计算物理地址

可引入快表机构，以段号和页号为查询关键字，若命中，仅需访存一次

虚拟内存

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

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

若内存不够，由操作系统将内存中暂时用不上的信息换出到外存

特性：

多次性：无需再作业运行时一次性全部装入内存，允许多次装入
对换性：在作业运行时无需一直常驻内存，允许换入换出
虚拟性：逻辑上扩充内存容量，用户看到的内存容量，远大于实际容量

实现:

请求分页存储管理
请求分段存储管理
请求段页式存储管理

与传统方式不同在于，当所访问的信息不在内存中时，由操作系统负责将信息从外存调入内存

请求分页管理

页表机制

将页表项进行扩展，新增：

状态位：标识是否已调入内存
访问字段：记录最近被访问过几次或上次访问时间，供置换算法参考
修改位：页面调入内存后是否被修改过
外存地址：页面在外存存放的地址

缺页中断机构

每当要访问的页面不在内存中，便产生一个缺页中断，然后由操作系统的缺页中断程序处理中断，此时缺页的进程阻塞，放入阻塞队列，调页完成后将其唤醒，放入就绪队列

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中的相应空闲项。

如果没有，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则将其写回外存，若没有发生修改，直接丢弃。

缺页中断是属于内中断的，可能可以被缺页中断程序修复

一条指令执行期间，可能产生多次缺页中断。

地址转换

新增：

在查不到页表项时请求调页
当需要调入页面，且没有空闲内存块时进行页面置换
需要修改请求页表中新增的表项

注：

换入换出页面都需要启动慢速I/O操作，大量换入换出将增大系统开销
页面调入内存后，需要修改慢表，同时需要将表项复制给快表。

页面置换算法

尽可能追求最少的缺页率，减少I/O操作

最佳置换算法OPT

每次淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面

从淘汰备选中，在访问队列往后寻找，最后一个出现的备选页面就是要被淘汰的页面（最长时间不被访问的页面）

理想算法，实际因无法预估访问队列，无法实现

先进先出置换算法FIFO

每次淘汰最早进入内存的页面，队列最大长度取决于系统为进程分配多少内存块

会出现Belady异常：为进程分配的物理块数增大时，缺页次数不增反减的异常现象

也只有FIFO算法会出现Belady异常
未遵循局部性原理，算法性能差

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

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

在访问字段记录该页面上次被访问以来所经历的时间t
当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面
从置换位置，逆向向前扫描，物理块中最后一个出现的页面就是被淘汰的页面

实现困难，开销大，性能最接近最佳置换算法

时钟置换算法CLOCK

又称最近未用算法NRU

简单的CLOCK算法实现：

将可能被置换的页面排成一个循环队列
每个页面设置一个访问位：当某页被访问时，访问位置为1
需要淘汰页面时，检查页的访问位，如果是0，就选择该页换出，如果是1，置为0，暂不换出

简单的CLOCK算法选择一个淘汰页面最多经过两轮扫描

改进型CLOCK算法实现：

基于简单的CLOCK算法，新增一个修改位：0表示未被修改，1表示修改过
用(1,1)表示该页面被访问过，被修改过

第一轮：从当前位置开始扫描到第一个(0,0)的帧用于替换，本轮不修改任何标志位
- 最近没访问，没修改过的页面
第二轮：若第一轮扫描失败，重新扫描，查找第一个(0,1)帧替换，本轮将所有扫描过的帧访问位置为0
- 最近没访问，但修改过的页面
第三轮：若第二轮扫描失败，重新扫描，查找第一个(0,0)的帧用于替换，不修改任何标志位
- 最近访问过，但没修改的页面
第四轮：若第三轮扫描失败，重新扫描，查找第一个(0,1)帧替换
- 最近访问过，且修改过的页面，最坏的选择

改进型CLOCK算法最多进行四轮扫描淘汰一个页面

页面分配策略

页面分配

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

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

固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变，即，驻留集大小不变

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，驻留集大小可变

置换策略

局部置换：发生缺页时，只能选进程自己的物理块进行置换

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

注：全局置换意味着一个进程拥有的物理块数必然会改变，不可能搭配固定分配

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

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

若已无空闲物理块，可选择一个未锁定的页面换出外存再将该物理块分配给缺页的进程
被选择调出的页所属进程的物理块减少，缺页率增加

调入页面时机

预调页策略：根据局部性原理，一次调入若干个相邻的页面更为高效，预测不久之后可能访问的页面，将他们预先调入内存，但预测成功率只有50%左右，故主要用于进程的首次调入(运行前调入)，由程序员指出先调入哪些部分

请求调页策略：进程在运行期间发生缺页时才将所缺页面调入内存，由这种策略调入的页面一定会被访问到，但由于每次只调入一页，每次调页都需要I/O操作，因此I/O开销较大

从何出调入页面

从外存的对换区调入页面，在进程运行前，将相关数据从文件区复制到对换区，

如果连对换区空间也不足的话，将不会被修改的数据直接从文件区调入，换出时由于没有数据被修改，不用写回磁盘

UNIX方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入，若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入

抖动(颠簸)现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动(颠簸)，

产生的主因是进程频繁访问的页面数目高于可用的物理块数(物理块不够)

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

操作系统将根据窗口尺寸算出工作集，工作集大小可能小于窗口尺寸，操作系统可以根据统计进程的工作集大小，给进程分配若干内存块。

一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页

内存映射文件

操作系统向上层程序员提供的功能（系统调用）

方便程序员访问文件数据
方便多个进程共享同一个数据

这实现了以访问内存的方式访问文件数据

文件数据的读入、写出由操作系统自动完成
进程关闭文件时，操作系统自动将文件被修改的数据写回磁盘