内存管理基础
内存管理基本概念
内存管理的功能
- 地址转换：内存管理提供从逻辑地址到物理地址的变换机制
- 逻辑地址空间
- 编译后的目标模块从0单元开始编址
- 各个模块按顺序链接后构成统一的从0单元开始的逻辑地址空间
- 用户可见
- 物理地址空间
- 主存中实际的物理地址
- 可执行代码装入内存时，要进行地址重定位，即把逻辑地址转换为物理地址
- 逻辑地址空间
- 内存共享：允许多个进程访问内存同一个部分，比如同一个数据块
- 内存保护
- 含义：内存分配前，保护操作系统不受用户影响、保护用户之间不相互影响
- 方法有两种
- 在CPU中设置用户作业上下限寄存器，存放用户作业在主存中的上限、下限地址
- 把逻辑地址和界地址寄存器（限长寄存器）比较，判断是否越界；不越界的情况，把逻辑地址和重定位寄存器（基址寄存器）相加，得到物理地址
- 内存分配和回收
- 由操作系统管理主存空间的分配和回收，程序员不需要考虑
- 内存扩充：利用外存扩充内存的容量，有两种方法
- 覆盖
- 思想：把用户空间分成固定区、覆盖区，活跃内容放固定区，其他即将访问的内容放覆盖区，其他暂时不用的内容放外存（需要时从外存替换入覆盖区）
- 特点：内存容量可以小于单进程总信息量；内存容量需要大于单进程任何运行时刻需要的信息量；主要应用于单进程；属于被淘汰的历史技术
- 交换
- 思想：把等待态的进程换出到外存，把调度使用CPU的进程换入到内存（进程中级调度就是交换技术）
- 特点：交换时间希望短于进程执行时间；适合多进程或多作业情况；目前主流的技术
- 覆盖
连续分配管理方式
- 连续分配管理方式指在内存中为进程分配连续的空间
- 外部碎片：没有分配给进程，且无法利用的空间
- 内部碎片：分配给进程，但无法利用的空间
单一连续分配
- 思想：内存直接分为系统区、用户区。无内存保护，因为内存中只有一道程序，空间不足采用覆盖技术，提高作业数采用交换技术
- 内存保护：界地址寄存器检查越界即可
- 优点：实现简单、无外部碎片
- 缺点：要求单用户任务、有内部碎片
固定分区分配
- 思想：把内存分为固定大小的多个分区，分区可以大小相等，也可以大小不等（多个小分区，少量大分区）
- 需要分区表，表项包括：分区号、起址、大小、分配状态
- 内存保护（两个方法）
- 上下界寄存器检查越界
- 基地址寄存器和界地址寄存器进行地址转换
- 优点：实现简单、无外部碎片；支持多道程序设计，但数量受限于分区个数
- 缺点：程序大于最大分区时需要使用覆盖技术；有内部碎片；无法内存共享
动态分区分配
- 思想：进程装入内存时动态建立分区，又叫可变分区分配
- 内存保护（两个方法）
- 上下界寄存器检查越界
- 基地址寄存器和界地址寄存器进行地址转换
- 优点：按需分配，因此无内部碎片；内存共享；程序数无限制
- 缺点：有外部碎片，但可以通过紧凑技术解决
- 常见的动态分区分配算法
- 首次适应算法First Fit：从地址递增顺序查找第一个大小满足要求的空闲分区
- 最佳适应算法Best Fit：按容量递增顺序查找查找第一个大小满足要求的空闲分区
- 最坏适应算法Worst Fit（最大适应算法Largest Fit）：按容量递减顺序查找查找第一个大小满足要求的空闲分区
- 邻近适应算法Next Fit（循环首次适应算法）：从上次查找结束的位置开始（按地址递增顺序）查找第一个大小满足要求的空闲分区
非连续分配管理方式
- 本节主要从逻辑地址结构（维度）、表项结构、寻址过程三个方面思考
- 非连续和连续分配管理方式都是传统存储管理方式，目标是建立多个进程在内存中的位置映射，而并不引入虚拟存储管理，这种传统的存储管理的特点是
- 一次性：作业一次性全部装入内存才开始运行
- 作业过大则无法运行
- 不能支持很多作业同时运行
- 驻留性：作业结束前不考虑替换出分配给作业的内存
- 因为IO等待的进程占用了内存空间
- 一次性：作业一次性全部装入内存才开始运行
基本页式管理
- 主要内容详见计算机组成原理第三章的页式虚拟存储器
- 补充内容1：页式管理的碎片情况
- 页式管理按相等大小给存储划分，无外部碎片
- 页比连续分配方式的分区小得多，因此进程只有最后一个不完整的页申请内存才会有页内碎片（平均情况即半个页大小的内部碎片）
- 补充内容2：页表项的大小
- 以32位系统为例，页大小4KB，12位
- 因此页数量有20位，即页表项至少需要3个字节
- linux中设置页表项4B，每一页可以装1K个页表项
基本段式管理
- 主要内容详见计算机组成原理第三章的段式虚拟存储器
- 补充内容1：段式管理碎片情况：有外部碎片，无内部碎片
- 补充内容2：段式管理的共享和保护
- 共享
- 两个作业的段表的表项指向同一个共享段
- 只有不能修改的代码（即纯代码、可重入代码）和不能修改的数据才可以共享
- 保护
- 段表寄存器的段表长用于越界保护（这种保护方式页式管理也有）
- 段表项的段长用于越界保护（这种保护方式页式管理不需要，因为页内大小固定，即页长固定）
- 共享
基本段页式管理
- 页式满足系统需要，段式满足用户需要（逻辑清晰、容易实现共享和动态链接），因此可以结合两者
- 需要三次访存，可以引入快表作为页表的Cache
- 主要内容详见计算机组成原理第三章的段页式虚拟存储器
虚拟内存管理
虚拟内存基本概念
局部性原理
详见计算机组成原理第三章高速缓存Cache部分的程序访问局部性原理
虚拟存储器
- 定义：由操作系统提供给用户的比实际内存大得多的存储器，大小不大于
- 计算机地址位数对应的容量
- 内存和外存的容量和
- 特征
- 多次性：允许作业分多次调入内存
- 对换性：允许作业运行结束前替换出内存
- 虚拟性：内存容量逻辑上得到扩充
- 实现方式
- 请求页式存储管理
- 请求段式存储管理
- 请求段页式存储管理
- 所需的硬件支持
- 一定容量的外存：用于内存的扩充
- 页表或段表：主要的数据结构
- 中断机构：缺页缺段时产生中断
- 地址变换机构：把逻辑地址变成物理地址
请求页管理
页表项
- 基本页式管理的页表项包括：页号、物理页号
- 请求页管理的页表项额外增加了：状态位、访问字段、修改位、外存地址（可参考计算机组成原理第三章的页式虚拟存储器）
缺页中断机构
- 内部中断，在一条指令执行期间可能多次发生
- 过程：保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境
- 处理过程
- 保存CPU现场
- 在外存中找到缺页
- 内存如果有空闲块，则分配，把调入页装入此块，修改相应页表项
- 内存如果没有空闲块，则替换某页，被淘汰的页如果修改位为1则结合回写策略写回外存
- 缺页进程唤醒、就绪
地址变换机构
- 通常引入快表（Cache一般用相联存储器实现，按内容寻址）
- 快表命中判定：要求标记位匹配且对应的页表项有效位为1，因此快表命中不用考虑缺页
- 在缺页处理完成时，不做说明，则认为快表项也得到更新
- 详见计组第三章笔记
页框分配
驻留集
- 驻留集定义：给进程分配的物理块的集合
- 页面分配和置换策略
- 固定分配、局部置换
- 分配给进程的物理块固定不变
- 进程缺页时，对该进程的驻留集调用页置换算法
- 可变分配、全局置换
- 分配给进程的物理块可变
- 操作系统维护一个全局的空闲物理块队列，进程缺页时，则从队列中取空闲物理块分配给进程
- 进程缺页且无空闲物理块时，对整个内存的所有物理块调用页置换算法
- 可变分配、局部置换
- 进程缺页时，对该进程的驻留集调用页置换算法
- 如果频繁缺页，则增加物理块分配；如果缺页率低，则减少物理块分配
- 固定分配、局部置换
页面调入时机
- 预调页策略：根据局部性原理，预测之后访问的页，在进程首次调入时，由系统程序员指定一次调入多个页（运行前调入）
- 请求调页策略：在运行时缺页则调入对应的一个页（运行时调入）
从何处调入页面
- 外存文件区：存放文件，离散分配，IO速度相对慢
- 外存对换区：存放对换页面，连续分配，IO速度相对快
- 三种情况
- 对换区充足
- 进程运行前把相关文件从文件区复制到对换区
- 之后全部从对换区调页（调入和换出）
- 对换区紧缺
- 不会被修改的文件从文件区调入，不需要换出
- 会被修改的文件从对换区调页（换出和调入）
- UNIX方式
- 未运行的页面从文件区调入
- 运行过的页面从对换区调页（换出和调入）
- 共享文件若已在内存，无需重复调入
- 对换区充足
页置换算法
当内存无空闲空间时，页面置换算法有
- 最佳置换算法OPT
- 思想：选择最长时间不被访问的页面替换
- 特点：无法准确的预测最长时间，难以实现该算法，但可以作为其他算法的评价标准
- 先进先出置换算法FIFO
- 思想：选择最早调入的页面替换
- 特点：存在Belady异常，即增加进程分配的物理块数，缺页次数反而可能增加
- 最近最久未使用置换算法LRU
- 思想：选择最久没有使用的页面替换，需要用到页表项的访问字段，即距离上一次访问的时间
- 特点：性能接近OPT的堆栈类算法（OPT是向未来看，LRU是向过去看），但需要寄存器和栈的硬件支持
- 时钟置换算法CLOCK（最近未用算法NRU）
- 所有内存页面保存在环形链表中，由指针遍历
- 需要设置使用位，当页面被访问后，使用位设置为1
- 当指针指向空闲块，将其分配给进程，使用位设置为1，指针指向下一个位置
- 当指针指向非空闲块（说明无空闲的块）
- 转第一圈，寻找第一个使用位为0的页，遇到的使用位是1的页面将其使用位设置为0
- 如果没找到，则第二圈的第一个页使用位肯定是0，用该内存块替换（要考虑写回），使用位设置为1，指针指向下一个位置
- 改进的时钟置换算法
- 针对写回开销大的问题改进，增设一个修改位，使用位和修改位用二元组(x,y)表示
- 当指针指向非空闲块（说明无空闲的块）
- 转第一圈，寻找第一个(0,0)页替换
- 如果第一圈没找到，则转第二圈，寻找第一个(0,1)的页替换，遇到的(1,x)设置为(0,x)
- 如果第二圈没找到，此时只有(0,x)，返回上面两步，一定能找到页面替换
内存映射文件
- 含义：把磁盘文件映射到虚拟地址空间中的内存映射文件（实际上虚拟存储器可以继续将其映射到内存的某位置）
- 原理
- 磁盘文件最初访问按缺页处理调入内存
- 此后访问磁盘文件不需要读写磁盘，只需要访问内存中的内存映射文件即可
- 当进程退出或解除文件映射时，所有改动需要写回磁盘
- 共享内存实现方式：如果多个进程映射了同一个文件，内存映射文件就是共享内存
工作集
- 工作集定义
- 进程一段时间内访问的页面集合
- 工作集确定
- 由时刻和工作窗口确定
- 定义中的一段时间指，从给定时刻到过去的一段时间间隔（间隔大小由工作窗口确定）
- 工作集原理
- 工作集可以理解是最近频繁使用的页面的集合
- 局部性越好的程序，工作集大小越小于工作窗口大小
- 驻留集大小要大于工作集，否则容易抖动（见后面一节）
抖动
- 又叫颠簸，指的是进程换页的时间多于执行的时间，是频繁的换页行为
- 原因：进程频繁访问的页面数目高于分配给进程的物理页框数
- 解决方法
- 驻留集应大于工作集
- 工作集的页面需要调入驻留集
- 工作集外的页面可以调出驻留集
- 进程的调入调出
- 若内存还有空闲，则可以再调一个进程进内存
- 若内存小于进程工作集之和，则需要调出一个进程出内存
- 驻留集应大于工作集
虚拟存储器的性能影响因素和改进方式
虚拟存储器的性能影响因素主要是缺页率，缺页率的影响因素如下
- 页面大小：越大缺页率低，但页表短、页内碎片大
- 驻留集大小：越大缺页率越低，但分配的内存块过多会浪费空间，缺页率降低不明显
- 页面置换算法：LRU、CLOCK算法缺页率低，这些把未来可能访问的页面尽量保留在内存
- 程序编址方法：局部化程度越高，缺页率越低（比如按行存储时应按行访问）
