《操作系统》内存管理（三）

CPU速度快，存储器成本高，硬盘速度低，存储成本低，内存处于中间，缓和速度矛盾

程序的编译和运行过程

编译
链接（三种方式）
- 静态链接:
- 装入时动态链接
- 运行时动态链接
装入: 使用逻辑地址编译链接后的程序，装载到内存中后，需要映射到物理地址
- 绝对装入：编译时产生绝对地址（物理地址）
- 可重定位装入：程序使用逻辑地址，程序装入内存的时候进行地址转换，转换为绝对地址
- 动态运行时装入：程序使用逻辑地址，程序装入内存的时候使用的也是逻辑地址，通过CPU重定位寄存器修复逻辑地址到物理地址，现代操作系统采用这种方式

内存管理

操作系统对内存管理通常需要实现下面四个需求

内存空间的分配和回收

两种方式

连续分配管理方式
- 单一连续分配
- 固定分区分配
- 动态分区分配
  - 首次适应：从头查找，找出第一个满足的内存块
  - 最佳适应：空闲内存排序，取出最小适应的内存块
  - 最坏适应：空闲内存排序，取出最大适应的内存块
  - 临近适应：每次从上一次结束位置开始查找，规则和首次适应一样
非连续分配管理方式
- 基本分页存储管理: 将物理内存分页，将进程分页，各页面离散放到内存快中（如iOS A9处理器之后的内存分页大小为16K），每页有一个编号，从0开始，程序加载到内存中时，会被拆分程多个页加载，然后分别加载到内存中的不同的页
- 基本分段存储管理: 分段思想和分页类似，一个程序可以被分为多个段，每个段在内存中占据连续的空间，各个段之间可以不相邻
  内存地址空间根据模块进行划分，每个段都有段名，每个段从0开始编址
- 段页式存储管理: 先分段后分页

基本分页存储管理

页表: 记录页面和时机内存块之间的映射关系
逻辑地址：页号和页面偏移量

优点：不会产生外部碎片，只会产生少量的页内碎片
缺点：不方便按逻辑模块实现信息的共享和保护

基本分段存储管理

段表：存放段内存的映射表（段号，段长，基址），与页表类似
逻辑地址: 段号和段内地址
段表寄存器：段表始址和段表长度
分段对用户可见，分页对用户不可见
分段比分页更容易实现信息的共享和保护（如只读内存，可读写内存）

优点：很方便按逻辑模块实现信息的共享和保护
缺点：如果段长过长，分配大的连续的内存空间很不方便，段式分配会产生外部内存碎片

段页式管理

逻辑地址: 段号，页号，页面偏移量
段表寄存器：段表始址和段表长度

内存保护

不同进程的地址空间应该互相独立，各进程应该在自己的内存空间内运行，不会越界访问

设置上下限寄存器，用于检查地址是否越界
采用重定位寄存器(存放进程起始物理地址)和界地址寄存器进行越界检查（存放进程最大逻辑地址）

内存空间的扩充

内存紧张时，根据一定的策略把某些进程的内存空间换到外存，把需要的数据从外存加载到内存
通常磁盘文件为文件区和对换区，对换区采用连续存储，文件区采用随机存储，对换区的存取效率比文件区高，换初的内存放到对换区
- 覆盖技术: 内存不够时，覆盖不用的内存
- 交换技术: 内存不够的时候，内外存交换
- 虚拟存储技术: 后面说明

内存空间扩充对程序是透明

地址转换

基本地址变换机构（地址转换）

逻辑地址：包含页号和页内偏移量）
页表寄存器：存放页表起始地址和页表长度，用于做地址越界检查
通过PCB页表得到物理页号/物理页偏移量
根据逻辑偏移量和物理页偏移量算出真实物理地址
访问内存单元

现代操作系统：编写程序的时候应该只关注指令和数据的逻辑地址，而逻辑地址到物理地址的转换（也称为地址重定位）应该由操作系统完成

快表

为了提高地址变换速度，操作系统在高速缓存维护了一份页表的副本，对应内存中的页表称为慢表，快表只存放一部分慢表，快表其实是对页表做了缓存，加快了访问速度，引入快表后的地址变换过程如下

高速缓存: 速度介于寄存器和内存之间，通常位于CPU内部

多级页表

问题一：单级页表存在的问题：页表必须连续存放，页表很大的时候，占用空间大
问题二：部分页面经常使用，部分页面很少使用甚至不用，没必要加载整个页表到内存中

把分页的思想应用于页表上，建立一张页目录表用于存放页表的页号，多级页表的逻辑地址就由一级页号，二级页号，三级页号…页内偏移量组成

虚拟内存

传统的存储管理方式存在两个缺点:

一次性: 作业一次性全部调入内存
驻留性: 作业在运行期间常驻内存

局部性原理

时间局部性：现在访问的指令在不久后很可能再次访问
空间局部性：现在访问的内存单元不久后很可能再次访问

虚拟内存：程序装入内存时，将要用到的内存部分装入内存，暂时没用到部分留在外存，就可以让程序运行了，内存不够用的时候，将暂时用不到的内存信息换出到外存，用户看起来”可以”使用比实际物理内存更大的内存，该特性是是通过操作系统在逻辑上虚拟的

多次性：无需再作业运行时，一次性全部装入内存，而是允许被多次调入内存
对换性：作业运行时无需一致常驻内存，而式允许作业换入换出
虚拟性：逻辑上扩充了内存容量，宏观上，使用内存大于实际内存

请求分页管理方式

基于离散分配的内存管理方式上，操作系统需要提供下面功能

请求调页/段: 当访问的信息不在内存时候，由操作系统将所需的信息从外存加载到内存
页面/段置换: 当内存空间不够时，由操作系统将部分不用的数据放到外存中

实现

页表机制: 新增4个状态
- 状态位(是否已调入内存)
- 访问字段(访问次数,用于置换)
- 修改位(是否被修改过)
- 外存地址(页面在外存的位置)
缺页中断
- 当访问的页不在内存中，会产生一个缺页中断，操作系统会阻塞该进程，并保留CPU现场，然后将页面加载到内存中（如果内存用完了，需要考虑置换），然后恢复CPU现场，再继续该进程
- 缺页中断属于内中断
- 一条指令执行期间，可能产生多次缺页中断
地址变换: 从逻辑地址到物理地址的转换

页面置换算法

当内存不足时候，置换策略

最佳置换算法(OPT): 根据以后不使用/最长时间不实用的页面置换页面，无法实现
先进先出置换算法(FIFO)
最近最久未使用算法(LRU)：LRU算法实现起来比较麻烦，需要寄存器和栈，性能高
时钟置换算法(CLOCK): 用比较小的开销接近LRU的性能
改进型时钟置换算法：CLOCK算法添加修改位

页面分配策略

驻留集：请求分页存储管理中给进程分配的物理块的集合，或者说进程使用的物理内存的集合，通常再虚拟存储技术中，驻留集比进程总大小要小，驻留集太小，会发生缺页
工作集：在一定时间间隔内，进程实际访问的页面的集合，通常驻留集不能小于工作集
抖动（颠簸）现象: 进程频繁访问的页面数大于可用的物理内存页面数，分配给进程的物理快不够，也就是频繁缺页导致置换操作频繁

页面分配

固定分配: 系统为进程分配的物理页面固定不变，不够用/缺页的时候会发生置换
可变分配

置换策略

局部置换: 当发生缺页时，只置换当前进程的内存
全局置换: 当发生缺页时，可置换其他进程的内存