【操作系统】内存管理
什么是内存
内存是存放数据的硬件，程序执行前，需要先放到内存中才能被CPU处理。
-
内存由一个个存储单元组成。
-
地址从0开始，每个地址对应一个存储单元。
-
如果按字节编址，则每个存储单元大小为1个字节。
-
如果按字编址，则每个存储单元的大小为一个字，字的大小视不同计算机的情况而言。
程序执行过程
|
|
代码会被编译汇编成机器能识别的指令，这些指令会告诉CPU去内存的哪个地址存/取数据。
但是，在生成机器指令时，通常并不知道进程数据会被放到什么位置。
所以生成的机器指令中，通常使用的是逻辑地址。
为什么需要区分内核空间和用户空间
CPU的所有指令中，有些指令很危险，如果错用会导致系统崩溃。
CPU将指令分为特权指令，和非特权指令。
CPU将特权等级分为4个等级：Ring0 ~ Ring3。
当进程运行在Ring3级别时，被称为运行在用户态。
当进程运行在Ring0级别时，被称为运行在内核态。
逻辑地址 VS 物理地址
只要知道进程在内存中的起始地址，和进程数据的相对地址，就能求出进程数据的绝对地址。
相对地址就是逻辑地址，绝对地址就是物理地址。
装入方式
- 绝对装入
- 静态重定位
- 动态重定位
1. 绝对装入
事先就知道程序会放到内存中的哪个位置，生成的目标模块中使用的是绝对地址。
装入程序按照装入模块中的地址，将程序和数据放入内存。
只适用于单道程序环境。
2. 静态重定位
又称可重定位装入。
生成的装入模块，地址从0开始，使用的是逻辑地址。装入时，再将逻辑地址变换为物理地址。
特点：
- 装入内存时，必须分配其要求的全部内存空间。
- 如果没有足够的内存空间，就不能装入该程序作业。
- 一旦进入内存后，运行期间不能再移动，也不能再申请内存空间。
- 适用于多道批处理系统。
3. 动态重定位
又称动态运行时装入。
链接生成的装入模块，地址从0开始，使用的是逻辑地址。装入内存后，并不会马上把逻辑地址转换为物理地址，而是在程序真正执行时，才进行地址转换。
这种方式依靠重定位寄存器（基址寄存器），用来存放装入模块的起始地址。
特点：
- 允许程序在内存中发生移动。
- 程序可分配到不连续的存储区。
- 程序运行前只需要装入部分代码即可，然后根据需要动态申请分配内存。
- 便于程序段的共享。
- 可以向用户提供一个比存储空间大的地址空间。
- 适用于现代操作系统。
链接方式
1. 静态链接
程序运行前，将目标模块及它们所需的库函数，链接成一个可执行文件（装入模块）。
2. 装入时动态链接
将目标模块装入内存是，边装入边链接。
3. 运行时动态链接
在程序执行过程中，需要某目标模块时，才对它进行链接。
内存管理
操作系统主要负责：
- 内存空间的分配与回收。
- 从逻辑上对内存进行扩充。
- 逻辑地址与物理地址的转换（地址重定向）。
- 提供内存保护功能。
内存保护
保证各进程在自己的内存空间内运行，不会越界访问。
1. 上下限寄存器
CPU可以设置上、下限寄存器，存放进程的上、下限地址。
进程的指令访问某个地址时，CPU检查是否越界。
2. 重定位寄存器/界地址寄存器
可以采用“重定位寄存器”和“界地址寄存器”进行越界检查。
重定位寄存器（又称基址寄存器）存放进程的起始物理地址。
界地址寄存器（又称限长寄存器）存放进程的最大逻辑地址。
覆盖
解决程序大小超过物理内存总和的问题。
思想：
内存分为“一个固定区和若干个覆盖区”。
常驻内存的段，放在“固定区”，调入后就不再调出。
不常用的段，放在“覆盖区”，用到时调入内存，用不到时调出内存。
实现
按照自身逻辑结构，让不可能同时被访问的程序段，共享同一个覆盖区。
特点
必须由程序员声明覆盖结构，操作系统自动完成覆盖。
增加了用户编程负担。
只用于早期的操作系统中
交换
思想
内存空间紧张时，系统将内存中某些进程暂时换出外存。
将外存某些已经具备运行条件的进程换入内存
总而言之，就是进程在内存和磁盘间动态调度
中级调度
又称内存调度。
决定将某个处于挂起状态的进程重新调入内存。
挂起状态
又称挂起态suspend。
暂时换出外存等待的进程状态，称为挂起状态。
挂起状态分为：就绪挂起、阻塞挂起。
被换出进程保存位置
磁盘空间一般分为“文件区”和“对换区”。
文件区：
- 主要存放文件
- 主要追求存储空间的利用率
- 采用离散分配方式进行管理
对换区：
- 只占磁盘空间的小部分
- 被换出进程数据存放在对换区
- 主要追求换入换出速度
- 采用连续分配方式管理
对换区的I/O速度快于文件区。
交换时机
进程运行数较多，且内存吃紧时进行交换，负荷降低后就暂停。
如经常发生缺页，说明内存紧张，可换出一些进程。
如果缺页率明显下降，可暂停换出。
换出哪些进程
- 阻塞进程
- 优先级低的进程
- 有时还会考虑进程在内存中的驻留时间，太短则不换出
PCB会常驻内存
内部碎片和外部碎片
内部碎片：在分配给某进程的内存区域中，如果有些部分没有用上，这部分就是内部碎片。
外部碎片：指内存中的某些空闲分区，由于太小而难以利用。
连续分配和非连续分配
连续分配：为用户进程分配的必须是一个连续的内存空间。
内存连续分配方式有：单一连续分配方式、固定分区分配方式、动态分区分配方式。
非连续分配：为用户进程分配的可以是分散的内存空间。
非连续分配方式有：基本分页存储管理、基本分段存储管理、段页式存储管理。
单一连续分配
内存分为系统区和用户区。
系统区
位于内存的低地址部分，用于存放操作系统相关数据
用户区
位于高地址部分，用于存放用户进程相关数据
内存中只能有一道用户程序，独占整个用户空间
优点
- 实现简单
- 无外部碎片
- 可以采用覆盖技术扩充内存
- 不一定需要内存保护
缺点
- 只能用于单用户、单任务操作系统
- 有内部碎片
- 存储器利用率极低
固定分区分配
将整个用户空间，分成若干个固定大小的分区，在每个分区中只装入一道作业。
分为两种方式：分区大小相等、分区大小不等。
分区说明表
为了实现各个分区的分配与回收，需要建立“分区说明表”。
每个表项的内容为：分区号、分区大小、起始地址、状态（分配/未分配）。
优点
- 实现简单
- 无外部碎片
缺点
- 程序太大时，无分区满足条件，此时得用覆盖技术来解决
- 会产生内部碎片，内存利用率低
动态分区分配
又称可变分区分配。
不会预先划分内存分区，而是当进程装入内存时，根据进程大小动态建立分区，并使分区大小正好适合进程需要。
记录内存情况
两种常用数据结构记录内存使用情况：
- 空闲分区表（类似分区说明表）
- 空闲分区链
动态分区分配算法
从空闲分区表（或空闲分区链）中，选出一个分区分配给新进程，这种算法称为动态分区分配算法。
常见的分区分配算法有：
- 首次适应算法
- 最佳适应算法
- 最坏适应算法
- 邻近适应算法
首次适应算法：
效果最佳。
思想：从低地址开始查找，找到第一个满足大小的空闲分区。
实现：空闲分区以地址递增的方式排列。每次分配时，顺序查找空闲分区链（或表），直到找到第一个满足条件的分区。
优点：开销小，分区回收后一般不需要重新排序。
最佳适应算法：
思想：优先使用更小的空闲区
实现：空闲分区按照容量递增的方式排列。每次分配时，顺序查找第一个大小满足要求的空闲分区。
优点：会留下很多大分区。
缺点：会产生很多外部碎片。
最坏适应算法：
思想：优先使用最大的连续空闲区
实现：空闲分区按容量递减次序排列。每次分配时，顺序查找第一个大小满足要求的空闲分区。
优点：能减少小碎片数量。
缺点：大进程没有分区可用。
邻近适应算法：
思想：每次查找都从上次查找结束的位置开始。
实现：空闲区按地址递增的顺序排列成一个循环链表。每次分配时，从上次查找结束的位置开始，找到第一个大小满足要求的空闲分区。
优点：检索时不需要从低地址开始，算法开销小。
缺点：高地址的大分区，被使用的可能性很大，从而导致最后无大分区可用。
紧凑技术
如果内存中空闲空间碎片的总和满足进程的要求，但是进程需要的是一整块连续的内存空间，这时可以使用紧凑技术，解决外部碎片。
缺点
- 会产生很多外部碎片
- 利用紧凑技术处理外部碎片时，时间代价很高
非连续分配管理方式
常见的非连续分配管理方式为：
- 基本分页存储管理
- 基本分段存储管理
- 段页式存储管理
基本分页存储管理
由“固定分区分配”方式改进。
思想
基本思想为：
-
把内存分为大小相等的小分区，再按照分区大小，将用户进程的地址空间，拆分成与页框大小相等的区域。
-
操作系统以页框为单位，为每个进程分配内存空间。进程的页面和内存的页框有一一对应的关系。
内存中的每个分区，称为页框、页帧、内存块、或者物理块。
每个分区有一个编号，称为页框号、页帧号、内存块号、或者物理块号，页框号从0开始。
用户进程的每个区域，称为页、或者页面。页面的编号称为页号，每个页号从0开始。
注意：
- 页框不能太大，否则会产生过大的内部碎片。
页表
用于获得进程的每个页面在内存中存放的位置。
- 一个进程对应一张页表。
- 进程每一页对应一个页表项。
- 页表项包含页号和内存块号两个信息，页号是隐含的。
- 每个页表项的长度都是相同的。
- 各页表项，会按顺序连续存放在内存中。
- 根据页表在内存的起始地址，和页表项长度，就可找到各个页号对应页表项的地址
- 为了方便查询，通常会让一个页表占更多字节，使得每个页面恰好可以装下整数个页表项。
逻辑地址到物理地址的转换
转换过程：
- 确定逻辑地址对应的页号。
- 确定页号对应页面在内存中的起始地址。
- 计算逻辑地址在页面内的偏移量。
- 物理地址 = 页面始址 + 页内偏移量
一般计算公式：
|
|
为了计算方便，页面大小一般设置为2的整数幂。
-
如果每个页面大小为
2^kB，用二进制表示逻辑地址，则末尾k位为页内偏移量，其余部分为页号。 -
如果页面大小为2的整数次幂，则只需把页表中记录的物理块号拼接上页内偏移量，就能得到物理地址。
页表寄存器
页表寄存器PTR，存放页表在内存中的起始地址F和页表长度。
进程未执行时，页表的起始地址和页表长度，放在进程控制块PCB中。
进程被调度时，内核会将上述两个值放入页表寄存器。
地址转换的具体过程
- 根据逻辑地址计算出页号、页内偏移量。
- 比较页号和页表长度，判断是否产生越界中断，页号大于等于页表长度则越界。
- 查询页表，找到页号对应页表项，确定页面存放的内存块号。
- 用内存块号和页内偏移量，得到物理地址。
- 访问物理内存单元。
缺点
每次访问逻辑地址的时候，都需要查询内存中的页表，且每次查到的结果可能都是同一个页表项。
具有快表的地址变换
时间局部性：
- 如果执行了程序中某条指令，该指令可能很快会被再次执行。
- 如果某个数据被访问过，不久之后该数据可能被再次访问。
空间局部性：
- 程序访问了某个存储单元，不久之后其附近的存储单元也可能被访问。
快表：
- 又称联想寄存器，是一种访问速度比内存快很多的高速缓冲存储器。用来存放当前访问的若干页表项。
- 访问内存中的页表项之前，会先查询块表。如果查询命中，则可以直接访问物理地址。
慢表：
- 内存中的页表项常称为慢表。
单级页表的问题
单级页表存在的问题：
- 页表必须连续存放，因此当页表很大，需要占用很多个连续的页框。可以采用多级页表解决。
- 没有必要让整个页表常驻内存，因为进程在一段时间内，可能只访问某几个特定的页面。可以采用虚拟存储技术解决。
基本分段存储管理
按照程序自身的逻辑关系，将进程地址空间分为若干个段，每个段都有一个段名，每段从0开始编址。编译程序会将段名转换为段号。
以段为单位进行分配，每个段在内存中占据连续空间，但是各段之间可以不相邻。
分段系统的逻辑地址：段号 + 段内地址（段内偏移量）
段号位数，决定了每个进程最多可以分为几个段。
段内地址位数，决定了每个段的最大长度是多少。
段表
段表：每个进程拥有的一张段映射表，用于在物理内存中查找各个逻辑段的存放位置。
每个段对应一个段表项，记录了基址（段在内存中的起始位置）和段长。
各个段表项的长度是相同的，比如，操作系统可规定为6个字节。
短号是隐含的，不占用存储空间。
段表寄存器
包含：段表始址 + 段表长度
地址转换过程
- 根据逻辑地址，得到段号、段内地址。
- 判断段号是否越界，如果段号大于等于段表长度，则产生越界中断。
- 查询段表，找到对应的段表项。
- 检查段内地址是否超过段长，超过则产生越界中断。
- 计算得到物理地址，物理地址 = 段基址 + 段内地址。
- 访问目标内存单元。
块表
分段也可以引入块表机制，和分页类似，不再赘述。
分段和分页的对比
- 页是信息的物理单位，对用户是不可见的；段是信息的逻辑单位，分段对用户是可见的，用户编程时需要显示的给出段名。
- 分页的内存空间利用率高，不会产生外部碎片，只会产生少量内部碎片；分段会产生外部碎片。
- 分段比分页更容易实现信息的共享和保护。
段页式管理
思想：先将进程按逻辑块分段，再将各段分页。
逻辑地址结构为：段号、页号、页内地址（页内偏移量）
段号的位数，决定了每个进程最多可以分成几个段
页号位数，决定了每个段最大有多少页
页内偏移量，决定了页面大小、内存块大小
段表和页表
每个段对应一个段表项
每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。
段表项长度相等，段号是隐含的
地址转换过程
- 根据逻辑地址，得到段号、页号、页内偏移量
- 判断段号是否越界，如果段号大于等于段表长度，则越界中断
- 查询段表，找到对应的段表项
- 检查页号是否越界，如果页号大于等于页表长度，则越界中断
- 根据页表存放块号、页号查询页表，找到页表项
- 根据内存块号、页内偏移量找到最终的物理地址
- 访问内存单元
虚拟内存
虚拟存储技术主要用于解决传统内存管理的局限性。
传统存储管理
包括连续分配管理和非连续分配管理。
一次性：
作业必须一次性装入内存后，才能开始执行。
一次性缺陷：
- 作业很大时，无法运行。
- 无法实现大量作业同时运行，多道程序并发度降低。
驻留性：
作业被装入内存后，会一直驻留在内存中，直到作业运行结束。
驻留性缺陷：
- 内存中会驻留大量暂时用不到的数据，浪费内存资源。
什么是虚拟内存
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存。
在程序执行时，如果所需信息不在内存中，操作系统负责将其从外存调入内存。
若内存空间不足，操作系统负责将内存中暂时用不到的信息换出外存。
在用户看来，会存在一个比实际内存大的内存，这就是虚拟内存。
虚拟内存的容量
最大容量：
由计算机的地址结构（CPU寻址范围）确定的。
实际容量：
实际容量 = min(内存和外存容量之和，CPU寻址范围)
虚拟内存的主要特征
- 多次性：作业运行时，无需一次性装入内存，允许被分成多次调入内存
- 对换性：在作业运行过程中，允许将作业换入、换出
- 虚拟性：从逻辑上扩充了内存的容量
实现
虚拟内存的实现，建立在离散分配的内存管理方式基础上：
- 基本分页存储管理
- 基本分段存储管理
- 基本段页式存储管理
虚拟内存的实现：
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
操作系统要提供请求调页（或请求调段）功能。
操作系统要提供页面置换（或段置换）功能。
请求分页存储管理
操作系统需要：
- 提供请求调页功能，将缺失页面从外存调入内存
- 提供页面置换功能，内存不够时，将暂时用不到的页面换出外存
管理方式：
- 页表机制
- 缺页中断机构
- 地址变换机构
页表
页表项的组成为：
- 内存块号。如果信息位于外存，该字段为空。
- 状态位。表示是否已经调入内存。
- 访问字段。记录最近被访问过几次，或者记录上次访问的事件。
- 修改位。页面调入内存后，是否被修改过。
- 外存地址。页面在外存中的存放位置。
缺页中断机构
如果要访问的页面不在内存中，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
缺页中断属于内中断。
此时，缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放入就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺失页面装入该块，并修改页表的页表项。
如果内存中没有空闲块，则由页面置换算法，选择一个页面淘汰。如果被淘汰页面被修改过，则还需要写回外存。
地址变换机构
- 根据页表项，检查页面是否在内存中。
- 若页面不在内存中，请求调页。
- 若内存空间不够，需要换出页面。
- 页面调入内存后，修改对应页表项和快表。
快表
快表中有的页面一定存在内存中。如果某个页面被换出外存，则快表中的表项也要删除。
页面置换算法
-
最佳置换算法
淘汰将来不再使用、或者最长时间不再访问的页面。
该算法无法实现。
-
先进先出置换算法
淘汰最早进入内存的页面。
会产生
Belady异常，当为进程分配的内存块增多时，缺页次数也会增多。 -
最近最久未使用置换算法
LRU淘汰最近最久未使用的页面。
页表项记录的是上次被访问以来经历的时间，时间最大的页面被淘汰。
-
时钟置换算法
循环扫描各个页面，并检查访问位，1表示被访问过。
如果访问位为1，则置为0，如果访问位为0，则淘汰。
若第一轮无页面淘汰，则进行第二轮扫面。
-
改进型时钟置换算法
循环扫描各个页面，并检查访问位和修改位，1表示访问过，1表示修改过。
第一轮扫描，淘汰第一个(0,0)。
第二轮扫描，淘汰第一个(0,1)，并将扫描过的访问位设为0。
第三轮扫描，淘汰第一个(0,0)。
第四轮扫描，淘汰第一个(0,1)。
只要有一个页面被淘汰，就不再继续后续扫描，所以最多扫描4轮。
页面分配
-
驻留集
请求分页存储管理中，为进程分配的内存块集合。
-
固定分配
每个进程的驻留集大小不变。
-
可变分配
每个进程的驻留集大小可变。
-
局部置换
只能使用进程自己的内存块进行置换。
-
全局置换
可以使用操作系统的空闲内存块，以及其它进程的物理块，进行置换。
对换区
对换区采用的是连续存储方式，读写速度更快。
如果对换区足够大，进程数据将直接从文件区复制到对换区，之后的页面调入调出，都是在内存和对换区之间进行。
如果对换区不够大，进程不会修改的数据会从文件区调入，调出时不会写回文件区；会修改的数据，第一次从文件区调入，之后会调出到对换区，下次再从对换区调入。
对于UNIX，第一次使用的页面从文件区调入，调出的页面写回对换区，下次从对换区调入。